C语言学习之链表的实现详解

C语言链表实现 C语言链表 2022-11-13 19:11:39 338人浏览安东尼

摘要

目录一、链表的概念二、链表的结构三、顺序表和链表的区别和联系四、链表的实现一、链表的概念链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次

一、链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的

二、链表的结构

（1）单链表

（2）带头结点的单链表

（3）双向链表

（4）循环单链表

（5）双向循环链表

注释：

（1）无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

（2）带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

三、顺序表和链表的区别和联系

（1）顺序表：

优点：空间连续，支持随机访问。

缺点：中间或前面部分的插入删除时间复杂度为O（n），并且增容代价比较大。

（2）链表

优点：任意位置插入删除时间复杂度为O(1) 2.没有增容问题，插入一个开辟一个空间。

缺点：以节点为单位存储，不支持随机访问。

四、链表的实现

（1）单链表的增删查找等操作

#pragma once
#include"common.h"


typedef struct SListnode
{
	ElemType data;
	struct SListNode* next;
}SListNode;

typedef struct SList
{
	SListNode* head;
}SList;

///
///
//单链表的函数接口声明
void SListInit(SList* plist);
static SListNode* _Buynode(ElemType x);
void SListPushBack(SList* plist, ElemType item);//1
void SListPushFront(SList* plist, ElemType item);//2
void SListShow(SList* plist);//3
void SListPopBack(SList* plist);//4
void SListPopFront(SList* plist);//5
void SListInsertVal(SList* plist, ElemType val);//7
void sqlistDeleteByVal(SList* plist, ElemType val);//9
SListNode* SListFind(SList* plist, ElemType key);//10
size_t SListLength(SList* plist);//11

void SListSort(SList* plist);//13
void SListReverse(SList* plist);//14
void SListClear(SList* plist);//15
void SListDestroy(SList* plist);

///
///
//单链表的函数接口实现
void SListInit(SList* plist)
{
	plist->head = NULL;
}
static SListNode* _Buynode(ElemType x)
{
	SListNode* s = (SListNode*)malloc(sizeof(SListNode));
	assert(s != NULL);
	s->data = x;
	s->next = NULL;
	return s;
}
//1
void SListPushBack(SList* plist, ElemType item)
{
	assert(plist != NULL);
	SListNode* s = _Buynode(item);
	//插入的节点为第一个节点
	if (plist->head == NULL)
	{
		plist->head = s;
		return;
	}
	//O(n)
	SListNode* p = plist->head;
	//查找链表的尾部节点
	while (p->next != NULL)
	{
		p = p->next;
	}
	p->next = s;
}
//2
void SListPushFront(SList* plist, ElemType item)
{
	assert(plist != NULL);
	SListNode* s = _Buynode(item);
	s->next = plist->head;
	plist->head = s;
}
//3
void SListShow(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL)
	{
		printf("%d-->", p->data);
		p = p->next;
	}
	printf("Over.\n");
}
//4
void SListPopBack(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	if (plist->head == NULL)
	{
		printf("单链表为空，输出失败!\n");
		return;
	}
	if (p->next == NULL)
	{
		plist->head = NULL;
		return;
	}
	SListNode* prev = NULL;
	while (p->next != NULL)
	{
		prev = p;
		p = p->next;
	}
	prev->next = NULL;
	free(p);
}
//5
void SListPopFront(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	if (plist->head == NULL)
	{
		printf("单链表为空，输出失败!\n");
		return;
	}
	plist->head = p->next;
	free(p);
}
//6

//7
void SListInsertVal(SList* plist, ElemType val)
{
	assert(plist != NULL);
	SListNode* prev = NULL;
	SListNode* p = plist->head;
	SListNode* s = _Buynode(val);
	while (p != NULL && val > p->data)
	{
		prev = p;
		p = p->next;
	}
	if (prev == NULL)
	{
		s->next = p;
		plist->head = s;
	}
	else
	{
		s->next = prev->next;
		prev->next = s;
	}
}
//10
SListNode* SListFind(SList* plist, ElemType key)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL && p->data != key)
		p = p->next;
	return p;
}
//9
void SqListDeleteByVal(SList* plist, ElemType val)
{
	assert(plist != NULL);
	SListNode* prev = NULL;
	SListNode* p = SListFind(plist, val);
	if (p == NULL)
	{
		printf("要删除的节点不存在.\n");
		return;
	}

	if (p == plist->head)
		plist->head = p->next;
	else
	{
		prev = plist->head;
		while (prev->next != p)
			prev = prev->next;

		//删除
		prev->next = p->next;
	}
	free(p);
}

//11
size_t SListLength(SList* plist)
{
	assert(plist != NULL);
	size_t len = 0;
	SListNode* p = plist->head;
	while (p != NULL)
	{
		len++;
		p = p->next;
	}
	return len;
}

//13
void SListSort(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head->next;
	SListNode* q, * t, * prev = NULL;

	plist->head->next = NULL;  //断开链表

	t = plist->head;
	while (p != NULL)
	{
		q = p->next;
		while (t != NULL && p->data > t->data)
		{
			prev = t;
			t = t->next;
		}
		if (prev == NULL)
		{
			p->next = plist->head;
			plist->head = p;
		}
		else //if(prev->next!=NULL)
		{
			p->next = prev->next;
			prev->next = p;
		}
		p = q;
		t = plist->head;
	}
}

//14
void SListReverse(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head->next;
	SListNode* q;
	if (p->next == NULL)
		return;
	//断开第一个节点
	plist->head->next = NULL;
	while (p != NULL)
	{
		q = p->next;
		p->next = plist->head;
		plist->head = p;
		p = q;
	}
}


//15
void SListClear(SList* plist)
{
	assert(plist != NULL);
	SListNode* p = plist->head;
	while (p != NULL)
	{
		plist->head = p->next;
		free(p);
		p = plist->head;
	}
}
void SListDestroy(SList* plist)
{
	SListClear(plist);
	plist->head = NULL;
}
```c

（2）带头的双循环链表的实现

#pragma once
#include"common.h"

/
//带头的双循环链表
typedef struct DCListNode
{
	ElemType data;
	struct  DCListNode* next;
	struct DCListNode* prev;
}DCListNode;

typedef struct DCList
{
	DCListNode* head;
}DCList;

static DCListNode* _Buydnode(ElemType x);
void DCListInit(DCList* plist);
void DCListDestroy(DCList* plist);
void DCListPushBack(DCList* plist, ElemType x);//1
void DCListPushFront(DCList* plist, ElemType x);//2
void DCListShow(DCList* plist);//3
void DCListPopBack(DCList* plist);//4
void DCListPopFront(DCList* plist);//5
void DCListInsertByVal(DCList* plist, ElemType val);//7
void DCListDeleteByVal(DCList* plist, ElemType val);//9
size_t DCListLength(DCList* plist);//11
void DCListSort(DCList* plist);//13
void DCListReverse(DCList* plist);//14
void DCListClear(DCList* plist);//15



DCListNode* DCListFind(DCList* plist, ElemType key);//10

static DCListNode* _Buydnode(ElemType x)
{
	DCListNode* s = (DCListNode*)malloc(sizeof(DCListNode));
	assert(s != NULL);
	s->data = x;
	s->next = s->prev = s;
	return s;
}

void DCListInit(DCList* plist)
{
	plist->head = _Buydnode(0);
}

//1
void DCListPushBack(DCList* plist, ElemType x)
{
	assert(plist != NULL);
	DCListNode* s = _Buydnode(x);
	s->prev = plist->head->prev;
	s->prev->next = s;
	s->next = plist->head;
	plist->head->prev = s;
}

//2
void DCListPushFront(DCList* plist, ElemType x)
{
	assert(plist != NULL);
	DCListNode* s = _Buydnode(x);

	s->next = plist->head->next;
	s->next->prev = s;
	plist->head->next = s;
	s->prev = plist->head;

}


//3
void DCListShow(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		printf("%d->", p->data);
		p = p->next;
	}
	printf("Over.\n");
}

//4
void DCListPopBack(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->prev;
	if (plist->head->next == plist->head)
		//if(p == plist->head)
	{
		printf("循环双链表只有头结点,操作失败.\n");
		return;
	}

	plist->head->prev = p->prev;
	p->prev->next = plist->head;
	free(p);
}

//5
void DCListPopFront(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	if (p == plist->head)
	{
		printf("循环双链表只有头结点,操作失败.\n");
		return;
	}

	plist->head->next = p->next;
	p->next->prev = plist->head;
	free(p);
}

//7
void DCListInsertByVal(DCList* plist, ElemType val)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head && p->data < val)
	{
		p = p->next;
	}
	DCListNode* s = _Buydnode(val);
	s->next = p;
	s->prev = p->prev;
	p->prev->next = s;
	p->prev = s;
}

//9
void DCListDeleteByVal(DCList* plist, ElemType val)
{
	assert(plist != NULL);
	DCListNode* p = DCListFind(plist, val);
	if (p == NULL)
		return;
	p->next->prev = p->prev;
	p->prev->next = p->next;
	free(p);
}


//10
DCListNode* DCListFind(DCList* plist, ElemType key)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	if (p == plist->head)
	{
		printf("双循环链表只有头结点，查找失败.\n");
		return 0;
	}
	while (p != plist->head && p->data != key)
	{
		p = p->next;
	}
	if (p != plist->head)
		return p;
	return NULL;
}


//11
size_t DCListLength(DCList* plist)
{
	assert(plist != NULL);
	size_t len = 0;
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		len++;
		p = p->next;
	}
	return len;
}

//13
void DCListSort(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	DCListNode* q = p->next;

	//断开链表
	p->next = plist->head;
	plist->head->prev = p;

	while (q != plist->head)
	{
		p = q;
		q = q->next;

		//寻找p插入的位置
		DCListNode* t = plist->head->next;
		while (t != plist->head && t->data < p->data)
			t = t->next;

		p->next = t;
		p->prev = t->prev;
		p->next->prev = p;
		p->prev->next = p;

		p = q;
	}
}

//14  
void DCListReverse(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	DCListNode* q = p->next;
	//断开链表
	p->next = plist->head;
	plist->head->prev = p;
	while (q != plist->head)
	{
		p = q;
		q = q->next;

		p->next = plist->head->next;
		p->prev = plist->head;
		p->next->prev = p;
		p->prev->next = p;  //plist->head->next = p;
	}
}

//15
void DCListClear(DCList* plist)
{
	assert(plist != NULL);
	DCListNode* p = plist->head->next;
	while (p != plist->head)
	{
		p->next->prev = p->prev;
		p->prev->next = p->next;
		free(p);
		p = plist->head->next;
	}
}

void DCListDestroy(DCList* plist)
{
	DCListClear(plist);
	free(plist->head);
	plist->head = NULL;
}

以上就是C语言学习之链表的实现详解的详细内容，更多关于C语言链表的资料请关注编程网其它相关文章！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言学习之链表的实现详解

本文链接: https://www.lsjlt.com/news/170844.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档

去做题

猜你喜欢

C语言学习之链表的实现详解

目录一、链表的概念二、链表的结构三、顺序表和链表的区别和联系四、链表的实现一、链表的概念链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次...

99+

2022-11-13

C语言链表实现 C语言链表
C语言算法学习之双向链表详解

目录一、练习题目二、算法思路1、设计浏览器历史记录2、扁平化多级双向链表3、展平多级双向链表4、二叉搜索树与双向链表一、练习题目题目链接难度1472. 设计浏览器历史记录★★★☆☆...

99+

2022-11-13
Go语言学习之链表的使用详解

目录1. 什么是链表2. 单项链表的基本操作3. 使用 struct 定义单链表4. 尾部添加节点5. 头部插入节点6. 指定节点后添加新节点7. 删除节点1. 什么是链表链表是一...

99+

2022-11-13
C语言链表案例学习之通讯录的实现

目录一、通讯录需要实现的功能二、项目目的三、项目开发一、通讯录需要实现的功能 1，通讯录可以存储编号，联系人的姓名，电话号码和家庭住址。 2，通讯录最基本的功能是添加联系人，用户可以...

99+

2022-11-13

C语言链表实现通讯录 C语言实现通讯录 C语言链表通讯录 C语言通讯录
详解C语言之单链表

目录一、思路步骤1. 定义结构体2.初始化3.求当前数据元素的个数4.插入5.删除6.释放内存空间二、代码总结一、思路步骤 1. 定义结构体 a.数据域：用来存放数据 b.指针域...

99+

2022-11-12
C语言线性表之双链表详解

目录定义1.删除2.插入3.建立4.查找总结定义链表是通过一组任意的存储单元来存储线性表中的数据元素，每一个结点包含两个域：存放数据元素信息的域称为数据域，存放其后继元素地址的域称...

99+

2022-11-13
C语言链表与单链表详解

链表是什么及链表的优势链表是一种介于数组的另外一种数据结构：我们知道数组可以存放很多的元素，这些元素都是呈线性排列，也就是一个挨着一个连续存放但是当元素足够多时，还能继续正常的...

99+

2022-11-13
详解C语言学习记录之指针

目录1指针是什么2指针和指针类型3野指针（1）三种情况（2）如何规避野指针4指针运算5指针和数组6字符指针7数组指针8指针数组9其他总结1指针是什么指针是汇编语言中的一个对象，利用...

99+

2022-11-12
C语言学习之指针的使用详解

目录一、指针概念1.指针变量2.指针类型3.二级指针二、野指针1.野指针成因2.规避野指针三、指针运算1.指针±整数2.指针-指针3.指针关系运算四、指针数组1.指针和...

99+

2022-11-13

C语言指针使用 C语言指针
C语言实现无头单链表详解

目录链表的结构体描述(节点)再定义一个结构体(链表) 断言处理 & 判空处理创建链表创建节点头插法打印链表尾插法指定位置插入头删法尾删法&n...

99+

2022-11-13
C语言学习之关键字的示例详解

目录1. 前言2. 什么是关键字3. extern-声明外部符号4. auto-自动5. typedef-类型重定义（类型重命名）6. register-寄存器6.1 存储器6.2 ...

99+

2022-11-13

C语言关键字
C语言学习之标识符的使用详解

目录命名规则命名规范示例代码总结C语言标识符是用于表示变量、函数、常量、类型等程序元素的名称。在 C语言中，标识符的命名规则和命名规范非常重要，它们直接影响到代码的可读性、可维护性和...

99+

2023-05-20

C语言标识符用法 C语言标识符使用 C语言标识符
C语言线性表的链式表示及实现详解

目录前言代码实现1. 单链表的结点构造2. 构造一个空的头结点3. 对线性表进行赋值4.对线性表进行销毁5.对线性表进行重置6.判断线性表是否为空7.获取线性表的长度8.获取线性表某...

99+

2022-11-13
C语言数据结构之双链表&循环链表&静态链表详解

目录单链表 VS 双链表双链表双链表的初始化（带头结点）双链表的插入双链表的删除双链表的遍历循环单链表循环双链表循环双链表的初始化循环双链表的插入循环双链表的删除静态链表什么是静态链...

99+

2022-11-13
C语言实现单链表的基本功能详解

1.首先简单了解一下链表的概念: 要注意的是链表是一个结构体实现的一种线性表,它只能从前往后,不可以从后往前(因为next只保存下一个节点的地址).在实现单链表的操作时,需要用指针...

99+

2022-11-12
详解C语言中双向循环链表的实现

目录实现细节辅助理解图具体实现代码1、对链表进行初始化2、任意位置前的插入3、任意位置的删除4、头插和尾删完整代码头文件具体函数测试实现细节 1、带一个哨兵位（哨兵节点，初始节点，不...

99+

2022-11-13
C语言类的双向链表详解

目录前言双向链表的定义双向链表的创建节点的创建双向链表节点查找双向链表的插入双向链表的节点删除双向链表的删除总结前言链表（linked list)是一种这样的数据结构，其中的各对象...

99+

2022-11-12
C++编程语言实现单链表详情

目录一、单链表简单介绍二、下面我们先实现单链表的初始化。三、实现单链表的插入与删除数据一、单链表简单介绍首先，我们再回顾一下线性表的两种存储方式——顺序存储与链式存储上图左边...

99+

2022-11-12
C语言数据结构之单链表存储详解

目录1、定义一个链表结点2、初始化单链表3、输出链表数据4、完整代码如果说，顺序表的所占用的内存空间是连续的，那么链表则是随机分配的不连续的，那么为了使随机分散的内存空间串联在一起形...

99+

2022-11-13
C语言数据结构之单链表操作详解

目录1、插入操作2、删除操作3、查找操作4、修改操作5、完整代码1、插入操作（1）创建一个新的要插入的结点（2）将新结点的 next 指针指向插入位置后的结点（3）将插入位置前...

99+

2022-11-13