C语言的链表实现_c语言实现链表

1.导言

（1）这篇博客起源

单纯的学习记录。

（2）C语言中的链表

在日常使用中，我们往往需要导入一些不知道具体数目的数据，而在C语言中我们常常用数组来储存一系列同类型数据，而标准库中的数组在分配内存后大小不可变化。而通过自己写的可变数组往往对内存的使用率较低，于是链表由此产生。

2.单向链表实现

（1）单向链表基本结构

单向链表的每个节点（链表中的每个单元称作节点）由一个储存数据的类型变量和指向下一个节点的指针变量组成，同时单向链表还有一个指向第一个节点的头指针（一般命名为head）,用以对链表进行操作。
下图为一个链表的节点结构定义：

typedef struct Node {int value; struct Node* next;} Node;
typedef struct list (Node* head;) list;
1
2

(typedef重命名结构类型以方便后续引用Node)

(2)单向链表的添加

基本思路：首先需要定义一个链表的头指针

list* head;
head=NULL;
1
2

随后定义函数，向函数体中传入该指针，并由头指针开始插入新的节点。

I.头插法添加

头插入法顾名思义，就是从头部开始插入新节点，代码如下：

void add (list*head,int num) //链表的添加
{
	Node* p = (Node*)malloc(sizeof(Node)); //生成第一个结点
	if (p) //判断内存是否够创造新节点
	{
		p->value = num; //储存数据
		p->next = NULL; //表明该结点是最后一个
		Node* last = plist->head; //用last从head开始遍历链表
		if (last)//判断last所指向的结点head是否为0，如为0则说明此时链表只有一个结点
		{
			while (last->next)//判断last所指结点的next是否为NULL
				last = last->next;//若不是，则指向下一个结点，直至指到最后一个结点
			last->next = p;//在最后一个结点尾部添加新结点
		}
		else//当链表只有一个结点时，将head指向p
			head = p;
	}
	else
		printf("Fail");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

注：定义list*而不是list是因为list是局部变量，出函数体会被清空，而指针不会。

II.尾插法添加

不难发现，头插法每插入一次新节点，都需要遍历一遍链表，这会产生大量的操作消耗，而每次遍历的目的是为了找到最后一个节点，我们不妨再添加一个指针以始终指向最后一个节点，我一般习惯将其命名为tail.
节点结构不变：

typedef struct Node { int value; struct Node* next; }Node;
1

由于list同时有着tail和，head，不妨这么定义。

typedef struct list { Node* head; Node* tail; }list;
list* a; //链表初始化
a->head=NULL;
a->tail=NULL;
1
2
3
4

添加代码如下：（有着注释）

void listadd(list* a, int num) //链表元素添加
{
	Node* new= (Node*)malloc(sizeof(Node));
	if (new)
	{
		new->value = num;
		new->next = NULL;
		if (a->head == NULL)//判断是否只有一个结点
			a->head = new;
		else
			a->tail->next = new;//将new接到尾部
		a->tail = new;//使尾部指向new
	}
	else
		printf("创建失败，可能是内存不足");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（3）单向链表输出

   链表遍历输出代码：
1

void listput(list* head) //链表遍历输出
{
	Node*b=head; 
	int cnt = 0;
	for (b = head; b; b = b->next)//直到b为NULL时结束
	{
		cnt++;
		printf("Num%d:%d\n",cnt, b->value);
	}
}
1
2
3
4
5
6
7
8
9
10

（4）单向链表搜索

遍历判断后输出：

void listser(list* head)//链表数据搜索
	int cnt = 1;
	list*p=head;
	for (p =head; p; p = p->next)
		if (p->value != num)
		{
			cnt++;
		}
		else if (p->value == num)
			break;
	if (!p)
		printf("None");
	else
		printf("Location is %d", cnt);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（5）单向链表某一节点删除

先搜索出，随后释放相应节点，再将其上一个节点指向其下一个节点。
因为是单向链表，所以这时需要两个指针进行遍历，一个在前一个在后。
代码如下：

void listdlt(list* head, int num)//链表数据删除
{
	Node* p = NULL, * q =head;
	for (p = NULL, q = head; q; p = q, q = q->next)
		if (q->value == num)//判断所删数据
		{
			if (p)//判断此时是否是第一个节点
			{
				p->next = q->next;//如果不是第一个节点，将所删除节点的上一个节点指向所删节点的下一个节点
			}
			else
				head = q->next;//如果所删节点就是第一个节点，让head指向第二个节点。
			free(q);//将目标节点删除
			break;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（6）单向链表内存释放

同删除，双指针遍历链表实现释放：

void freelist(list* head)
{
	Node* p = head,*q=NULL;
	for (p = head; p; p = q)
	{
		q = p->next;
		free(p);
	}
}
1
2
3
4
5
6
7
8
9

3.双向链表实现

（1）双向链表结构

不同于单向链表的只能向下遍历，双向链表能够向前遍历，这里先介绍双向非循环链表（即第一个节点向前指向NULL而非指向最后一个节点，最后一个节点向后指向NULL而非第一个节点）
结构代码如下：

typedef struct dnode { struct dnode* pre; int value; struct dnode* next; } dnode;//dnode指的是double node
1

定义链表结构及其初始化：

typedef struct dlist { struct dnode* head; struct dnode* tail; } dlist;
int main(void)
{
dlist a;
	a.head = NULL;
	a.tail = NULL;
return 0;
}
1
2
3
4
5
6
7
8

（2）双向链表添加

由于尾插法相对于头插法更加方便且快速，这里采用尾插法：

void addlist(dlist* a, int num)
{
	dnode* p = (dnode*)malloc(sizeof(dnode));//创建新节点
	if (p)//判断内存是否充足
	{
		p->pre = NULL;
		p->next = NULL;
		p->value = num;
		dnode* b = a->head;//创建指针指向第一个节点
		if (b)//判断第一个节点是否为NULL
		{
			a->tail->next = p;//如果不是，让末尾的节点指向新节点
			p->pre = a->tail;//让新节点的的pre指向上一个节点
		}
		else//如果是NULL，将新节点作为第一个节点
			a->head = p;
		a->tail = p;//始终让尾指针指向新节点
	}
	else
		printf("Fail");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

（3）双向链表输出

由于双向链表特性，可以正序也可以逆序输出

void toplist(dlist* a)//逆序输出
{
	dnode* p = a->tail;
	for (p = a->tail; p; p = p->pre)
		printf("%d", p->value);
}
void soplist(dlist* a)//正序输出
{
	dnode* p = a->head;
	for (p = a->head; p; p = p->next)
		printf("%d", p->value);
}
1
2
3
4
5
6
7
8
9
10
11
12

（4）双向链表搜索

与单向链表同理

oid listsearch(dlist* a,int num)
{
	Node* p;
	int cnt = 1;
	for (p = a->head; p; p = p->next)
		if (p->value != num)
			cnt++;
		else
		{
			printf("找到了：在第%d个结点\n", cnt);
			break;
		}
	if (!p)//如果最后p是NULL，则找不到
		printf("找不到");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（5）双向链表结点删除

与单向链表同理，但要注意要同时修改pre和next，同时可以少用一个指针，只用一个指针就能完成删除

void listdlt(dlist* a, int num)//链表数据删除
{
	Node * q = a->head;
	for (q = a->head; q; q = q->next)
		if (q->value == num)
		{
			if (q->pre)//判断被删除的数据是否在第一个节点
			{
				q->pre->next = q->next;//如果q不是第一个节点，则让其前后两个节点互联
				q->next->pre=q->pre;
			}
			else
				{
				a->head = q->next;
				q->next->pre=NULL;
				}
			free(q);//无论如何，删除q；
			break;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（6）双向链表内存释放

与单向链表同理

void freelist(dlist* a)
{
	Node* p = a->head,*q;
	for (p = a->head; p; p = q)
	{
		q = p->next;
		free(p);
	}
1
2
3
4
5
6
7
8

4.单向循环链表实现

（1）单向循环链表结构

单向循环链表指的是单向链表的最后一个节点的next指向了第一个节点，从而构成了循环结构。
其结构与单向链表相同：

typedef struct Node { int value; struct Node* next; }Node;
typedef struct forlist { Node* head; Node* tail; }forlist;//这里用for代表了“循环”
1
2

（2）单向循环链表添加

同样采用尾插法，让尾节点指向头节点即可。

void listadd(forlist* a, int num) 
{
	Node* new = (Node*)malloc(sizeof(Node));
	if (new)
	{
		new->value = num;
		new->next = NULL;
		if (a->head == NULL)
			a->head = new;
		else
			a->tail->next = new;
		new->next = a->head;
		a->tail = new;
	}
	else
		printf("创建失败，可能是内存不足");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（3）单向循环链表输出

由于构成了循环结构，用之前的遍历就无法停止，这里改变一下循环结束条件，用双指针遍历。

void listput(forlist* a)
{
	Node* b = a->head, * c = NULL;
	int cnt = 0;
	for (c=NULL; c!=a->head; b = c)
	{
		cnt++;
		c = b->next;
		printf("Num%d:%d\n", cnt, b->value);
	}
}
1
2
3
4
5
6
7
8
9
10
11

（4）单向循环链表搜索

同样的，改变一下循环结束条件

void listsearch(forlist* a, int num)
{
	Node* p=a->head,*c=NULL;
	int cnt = 1;
	for (c = NULL; c != a->head; p = c)
	{
		if (p->value != num)
		{
			c = p->next;
			cnt++;
		}
		else
		{
			printf("找到了：在第%d个结点\n", cnt);
			break;
		}
	}
	if (c==a->head)
		printf("找不到");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（5）单向循环链表数据删除

void listdlt(forlist* a, int num)//链表数据删除
{
	Node* p = NULL, * q = a->head;
	for (p = NULL, p!=a->tail;p=q,q=q->next; )//改变循环条件防止进入死循环
		if (q->value == num)
		{
			if (p)//判断所删数据是否在第一个节点
			{
				p->next=q->next;//如果不是，让前一个节点指向所删数据的下一个节点
			}
			else//如果是第一个节点
				{
				a->head = q->next;
				a->tail->next=q->next;
				}
			
			free(q);
			break;
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（6）单向循环链表内存释放

与单向链表相同

void freelist(forlist* a)
{
	Node* p = a->head, *q = NULL;
	for (p = a->head;p; p = q)
	{
		q = p->next;
		free(p);
	}
}
1
2
3
4
5
6
7
8
9

双向循环链表与单向循环链表思路相似，不多赘述。