线性表的链式存储的基本操作

发表于 | 分类于 | 阅读次数
  1. 线性表的链式存储是用结点来存储数据元素，基本结点的结构为
数据域 指针域

其中，数据域用于存放存储数据元素的值，指针域存储当前元素的直接前驱或者直接后继的位置信息，指针域中的信息称为指针（或链）。

设线性表中的元素是整形，则单链表节点类型的定义为：

1
2
3
4
5
typedef struct Node
{
	int data; 	/*节点的数据域*/
	struct Node *next;	/*节点的指针域*/
}Node, *LinkList;
  1. 在链式存储结构下进行插入
    在单链表中p所指结点后插入新元素结点s(s所指结点已生成)，基本步骤如下：
1
2
s->next=p->next;
p-next=s;

即先将p所指结点的后继结点指针赋给s所指的结点的指针域，然后将p所指的结点的指针域修改为s所指的结点

  1. 在链式存储结构下进行删除
    在单链表中删除p结点所指结点的后继结点，基本步骤如下：
    1
    2
    3
    s=p->next;
    p->next=s->next;  /*或者p->next=p->next->next;*/
    free(s);

先令临时指针s指向待删除的结点，然后修改p所指结点的指针域为指向p所指结点的后继的后继结点，从而将待删除结点从链表中删除，最后释放s所指的结点的空间

  1. 单链表的创建、输出、查询、插入、删除运算的实现过程
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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
#include <stdio.h>

typedef struct Node
{
	int data;
	struct Node *next;
}Node, *LinkList;

//链表初始化
LinkList Init_LNode()          
{
	Node *L;
	L = (LinkList)malloc(sizeof(Node));
	if (L == NULL)
	{
		printf("初始化失败!\n");
		exit(-1);
	}
	L->next = NULL;
	return L;
}

//头插法
LinkList Creat_List(Node *L)          
{
	int i, num, n;
	Node *p;
	printf("请输入要输入的元素个数：n = ");
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		printf("请输入第%d个数：", i + 1);
		scanf("%d", &num);
		p = (LinkList)malloc(sizeof(Node));
		p->data = num;
		p->next = L->next;
		L->next = p;
	}
	return L;
}

//单链表的查找，某元素是由存在链表中
LinkList Find_List(Node *L, char e){
	Node *p;
	p = L;
	int i=0;
	while (p && p->next)
	{
		p = p->next;
		i++;
		if (p->data == e)
		{
			return i;			
		}
	}
		return 0;
}

//单链表查找，某位置是否存在元素
LinkList Find(Node *L, int k)
{
	Node *p;
	int i;
	i = 1;
	p = L->next;
	while (p && i < k)
	{
		p = p->next;
		i++;
	}
	if (p && i == k)
	{
		return p;
	}
	return 0;
}

//单链表的插入
int Insert_List(Node *L, int k, int e){
	Node *p, *s;
	if (k == 1)
	{
		p = L;
	}
	else
	{
		p = Find(L, k - 1);
	}
	if (!p)
	{
		return 0;
	}
	s = (LinkList)malloc(sizeof(Node));
	if (!s)
	{
		return 0;
	}
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

//单链表的删除
int Delete_List(Node *L, int k)
{
	Node *p, *s;
	int e;
	if (k == 1)
	{
		p = L;
	}
	else
	{
		p = Find(L, k - 1);
	}
	if (!p || !p->next)
	{
		return 0;
	}
	s = p->next;
	p->next = s->next;
	e = s->data;
	free(s);
	return e;
}

//输出单链表元素
PrintResult(Node *L)
{
	Node *p;
	p = L;
	while (p && p->next)
	{
		p = p->next;
		printf("%d", p->data);
	}
	printf("\n");
}

//主程序
int main(){

	Node *L;
	L = Init_LNode();
	L = Creat_List(L);

	printf("****************************************\n");
	printf("****  1.查看链表元素               *****\n");
	printf("****  2.查询某元素是否存在         *****\n");
	printf("****  3.查询某位置是否存在元素     *****\n");
	printf("****  4.插入元素                   *****\n");
	printf("****  5.删除元素                   *****\n");
	printf("****  0.退出程序                   *****\n");
	printf("****************************************\n");

	char ch;
	printf("\n是否继续？（Y/N or y/n）");
	scanf("%s", &ch);
	while (ch=='y' || ch=='Y')
	{
		int num;
		printf("请输入所需操作：（0-5）");
		scanf("%d", &num);

		int i, k, e;
		Node *p;
		switch (num)
		{
		case 1:
			PrintResult(L);
			break;
		case 2:
			printf("请输入所需查询的元素：");
			scanf("%d", &e);
			k = Find_List(L, e);
			if (k)
			{
				printf("该元素所在位置为%d！\n",k);
			}
			else
			{
				printf("所查询元素不存在！\n");
			}
			break;
		case 3:
			printf("请输入想要查看的位置：");
			scanf("%d", &k);
			p = Find(L, k);
			if (p)
			{
				printf("该位置存在元素为%d\n", p->data);
			}
			else
			{
				printf("该位置为空！\n");
			}
			break;
		case 4:
			printf("请输入插入元素的位置：");
			scanf("%d", &k);
			printf("\n请输入插入元素：");
			scanf("%d", &e);
			i = Insert_List(L, k, e);
			if (i)
			{
				printf("插入成功！\n");
			}
			else
			{
				printf("插入失败！\n");
			}
			break;
		case 5:
			printf("请输入删除的元素的位置：");
			scanf("%d", &k);
			i = Delete_List(L, k);
			if (i)
			{
				printf("删除成功,删除元素为%d\n",i);
			}
			else
			{
				printf("删除失败！\n");
			}
			break;
		case 0:
			exit();
			break;
		default:
			break;
		}

		printf("\n是否继续？（Y/N or y/n）");
		scanf("%s", &ch);
	}

	return 0;
}