2.1 线性表的链式存储--单链表（C语言详细实现）

2 线性表的链式存储

2.1 链式存储

如果一个结点有多个前驱和后继，采用顺序表需要足够大的连续存储分区，否则无法实现。为了解决连续分区不足的问题，我们可以采用链式存储方式。

在链式存储方式下，实现时除存放一个结点的信息外，还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或前驱，那么可以附设多个指针。

在线性结构中，每个结点有最多只有一个前驱和后继，第一个结点没有前驱；最后一个结点没有后继，C语言中指针未空用NULL表示，结点结构如下：

• info：存放该结点的数据信息
• next：存放指向下一个结点的指针

在C语言的动态分配函数malloc()和free()分别实现内存空间的动态分配和回收，所以一般用户不必知道某个结点具体的地址是多少。

注意：在这种链式存储方式下，必须有一个头指针指向第一个结点的存储位置，否则无法访问整个数据结构的各个结点。，头指针用head表示。

2.2 单链表

2.2.1 单链表的基本概念及描述

1、概念

单链表是线性表链式存储的一种形式，其中的结点一般含有两个域。信息域：info和指针域next。单链表必须有一个头指针指向单链表的第一个结点：

2、描述

数据集合 K：K={k1,k2,k3…,kn},n≥0，K中的元素是datatype类型；

数据关系R：R={r} ， r = {|i=1,2,…，n-1};

操作集合如下：

3、重要操作

1. 插入（在第i-1(1<= i <=n+1 )）个结点后插入一个值为x的新结点
   • 1 先构造一个新结点，用s指向
   • 2 在找到链表的第i-1个结点，用p指向
   • 3 然后修改指针，插入结点（p之后插入新结点是s）

2. 删除（删除链表的第i(1<=i<=n)）个位置上的结点
   • 先找到链表的第i-1个结点，用p指向
   • 再用指针s指向要删除的结点（p的下一个结点）
   • 然后修改指针，删除s所指结点
   • 最后释放s所指结点的空间，这样内存空间才不会泄漏

2.2.2 单链表编程实战

​ 创建一个单链表可以从一个空的单链表开始，通过不断插入心结点增加单链表的长度，已知一个单链表的首指针就可以找到单链表中的第一个结点，依据该结点得到指针与可以获得它的后继结点，反复这一操作，直到遇到一个阶段的指针域为空，表明已经遍历到最后一个结点了，依次可以访问单链表中的所有结点。

1、头文件：slnklist.h

#ifndef __SLNKLIST_H
#define __SLNKLIST_H
#include
#include
#define error NULL
typedef int datatype;

typedef struct link_node { //结构体标签link_node
	datatype info;
	struct link_node* next;
}node;  //结构体变量node

typedef struct link_node  *Linklist;
int create(Linklist* L); //创建链表

node* init(); //链表初始化

void display(node* head);//打印结点信息

node* findth(node* head, int i);  //按序号查找

node* find(node* head, datatype x);  //按值查找

node* insert(node* head, datatype x, int i);//插入在i位置新结点x

node* dele(node* head, datatype x);//删除结点中值为x的结点

int length(node* head); //返回链表的长度



#endif


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

2、函数定义：slnklist.c

#include"slnklist.h"

//建立一个空的单链表
// 参数：无
//返回值：指向node类型变量的指针

node* init()
{
	return NULL;
}

//int create(Linklist* L)
//{
//	L = (Linklist)malloc(sizeof(node));
//	if (!(*L))
//	{
//		return 0;
//	}
//	(*L)->next = NULL;
//	return 1;
//}

//输出单链表中各个结点的值
// 参数：指向node类型的变量的指针
//返回值：无
void display(node* head)
{
	node* p;
	p = head;
	if (!p)
	{
		printf("single linked list is NULL\n");
	}
	else
	{
		printf("The values from the list header to the list tail are :\n");
		while (p)
		{
			printf("%5d", p->info);
			p = p->next;       //point to the next node
		}
		printf("\n");
	}
}

//按序号查找，在单链表中查找第i个结点
/*
函数参数:指向node类型变量的指针head，int型变量i
函数返回值：指向node类型变量的指针
单链表不同于顺序表，它不能随机访问某个结点，必须从单链表的第一个结点开始，沿着next指针域向后查找
*/
node* findth(node* head, int i)
{
	int j=1;
	node* p = head;
	if (i<0)
	{
		return NULL;  //查找错误
	}
	while (p&&i!=j)
	{
		p = p->next;
		j++;
	}
	return p;		//找到则返回指向x结点的指针，否则返回NULL
}
//按值查找，在单链表中查找第i个结点
node* find(node* head, datatype x)
{
	node* p = head;
	while (p!=NULL && p->info!=x)
	{
		p = p->next;
	}
	return p; //找到则返回指向x结点的指针，否则返回NULL
}

//在单链表中插入一个值为x的新结点
/*
参数:指向node类型变量的指针head，datatype类型变量x，int 型变量i
*/
node* insert(node* head, datatype x, int i)
{
	node* s=NULL, * q;
	q = findth(head , i);
	if (!q && i!=0)
	{
		printf("找不到%d个结点，不能插入%d\n",i,x);
	}
	else
	{
		s = (node*)malloc(sizeof(node));  //开辟新将插入结点的空间
		s->info = x;
		if (i==0)		//如果插入的结点为单链表的第一个结点时
		{
			s->next = head;
			head = s;
		}
		else
		{
			s->next = q->next;
			q->next = s;
		}
	}
	return head;  //返回头结点
}

//在单链表中删除一个值为x的结点
node* dele(node* head, datatype x)
{
	node* pre = NULL, * s;
	if (!head)
	{
		printf("单链表是空的\n");
		return head;
	}
	s = head;
	while (s &&s->info!=x)   //寻找到指向数据位x的前驱
	{
		pre = s;
		s = s->next;
	}
	if (s)
	{
		if (!pre)
			head = head->next;
		else
		{
			pre->next = s->next;
			free(s);   //释放s结点内存空间
		}
	}
	return head;
}

int length(node *head)
{
	node* p = head;  //p指向表的第一个结点
	int j = 0;
	while (p)
	{
		p = p->next;
		j++;
	}
	return j;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

3、主函数：main.c

#include"slnklist.h"
node* p;
void main()
{
	int j = 0;
	struct link_node* head=NULL;
	int command = 0, position;
	head = init();
	//if (j)
	//{
	//	printf("链表创建成功\n");
	//}
	//else
	//{
	//	printf("链表创建失败\n");
	//}
	while (j>=0&&j<=10)
	{
		head=insert(head, j, j);
		j++;
	}

	while (command<10)
	{
		printf("请输入要执行的操作：0:free		1:display		2:findth		3:find		4:insert	5:dele		6:length\n");
		scanf_s("%d", &command);
		switch (command)
		{
		case 0:free(head); init(); break;
		case 1:display(head); break;
		case 2: {
			printf("请输入要查找的结点的序号\n");
			scanf_s("%d", &j);
			p = findth(head, j);
			printf("info: %5d  next:%5d", p->info, p->next);
			break;
		}
		case 3: {
			printf("请输入要查找的结点的值\n");
			scanf_s("%d", &j);
			p = find(head, j);
			printf("info: %5d  next:%5d", p->info, p->next);
			break;
		}
		case 4: {
			printf("please input the datatype and position that you want：\n");
			scanf_s("%d %d", &j, &position);
			head=insert(head, j, position);
			break;
		}
		case 5: {
			printf("input delete datatype ：\n");
			scanf_s("%d", &j);
			dele(head, j);
			break;
		}
		case 6:printf("The Linklist length is :%5d\n", length(head)); break;
		default:printf("input is error,input again\n"); break;
		}
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

4、运行结果