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
|
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
// 单链表的结点 自定义的数据类型
struct Node
{
DataType data;
struct Node *next;
};
typedef struct Node Node;
typedef struct Node *LinkList;
// 创建带头结点的空单链表 算法2-12
LinkList createNullList()
{
LinkList head = (LinkList)malloc(sizeof(Node));
if (head != NULL)
head->next = NULL;
else
printf("内存空间不足！");
return head;
}
// 尾插法建表 算法2-15
void creatAtTail(LinkList head)
{
Node *p, *q = head;
DataType data;
printf("请录入 link1 数据，以 -1 结尾：\n");
scanf("%d", &data);
while (data != -1)
{
p = (Node *)malloc(sizeof(Node));
p->data = data;
p->next = NULL; // 尾结点赋空值
q->next = p; // q 指的是原来单链表中的末尾结点 把新结点 p 链入到单链表的尾部
q = p; // q 重新记录末尾结点
scanf("%d", &data);
}
}
// 打印链表中的元素
void printLinkList(LinkList head)
{
LinkList p = head->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
// 计算链表长度，并将结果存放在头结点的数据域中
void lenthOfList(LinkList head)
{
LinkList p = head;
int len = 0;
while (p->next != NULL)
{
len++;
p = p->next;
}
head->data = len;
}
// 使用后插法在链表中插入元素
int insertPost_link(LinkList head, LinkList p, DataType data)
{
LinkList q;
if (p == NULL)
{
printf("插入位置错误\n");
return 0;
}
q = (Node *)malloc(sizeof(Node));
if (q == NULL)
{
printf("内存分配失败\n");
return 0;
}
else
{
q->data = data;
q->next = p->next;
p->next = q;
return 1;
}
}
// 在链表尾部插入元素
void insertAtTail(LinkList head, DataType data)
{
Node *p = head, *q;
while (p->next != NULL)
{
p = p->next;
}
insertPost_link(head, p, data);
}
// 产生 10 个 1-200 的随机整数，并存入链表中
void creatRandomList(LinkList head)
{
int i;
for (i = 0; i < 10; i++)
{
insertAtTail(head, rand() % 200 + 1);
}
}
// 查找链表中指定位序的元素，成功返回该元素，失败返回空值
DataType findByOrder(LinkList head, int order)
{
if (order < 1)
return NULL;
Node *p = head;
int i;
for (i = 0; p->next != NULL && i < order; i++)
{
p = p->next;
}
if (i == order)
return p->data;
else
return NULL;
}
// 查找链表中指定元素的位序，成功返回该元素的位序，失败返回 0
int findByData(LinkList head, DataType data)
{
int i = 1;
Node *p = head->next;
while (p != NULL && p->data != data)
{
p = p->next;
i++;
}
if (p == NULL)
return 0;
else
return i;
}
// 删除链表中指定位序的元素，成功返回 1，失败返回 0
int deleteByOrder(LinkList head, int order)
{
if (order < 1)
return 0;
Node *p = head, *q;
int i;
for (i = 1; p->next != NULL && i < order; i++)
{
p = p->next;
}
if (i != order)
return 0;
else
{
q = p->next;
p->next = q->next;
free(q);
return 1;
}
}
int main()
{
// 定义单链表 link1，用尾插入法创建 link1，并输出创建后的 link1 元素序列
LinkList link1 = createNullList();
creatAtTail(link1);
printf("\nlink1 创建后的元素序列：\n");
printLinkList(link1);
// 计算 link1 的长度，并将结果存放在头结点的数据域中，然后输出单链表的所有元素（包含头结点，头结点作为第一个输出）
lenthOfList(link1);
printf("\nlink1 的长度及其元素：\n%d ", link1->data);
printLinkList(link1);
// 定义单链表 link2，产生 10 个 1-200 的随机整数，通过插入函数依次保存到带头结点的 link2 中，并输出插入后的 link2 元素序列
LinkList link2 = createNullList();
int i;
for (i = 0; i < 10; i++)
if (!insertPost_link(link2, link2, rand() % 200 + 1))
{
printf("插入失败\n");
break;
}
printf("\nlink2 创建后的元素序列：\n");
printLinkList(link2);
// 查找 link1 中第 i 个元素（i由用户输入），输出第i个元素的值
printf("\n请输入 link1 中要查找的元素的位置：");
scanf("%d", &i);
DataType result;
if ((result = findByOrder(link1, i)) != NULL)
printf("\nlink1 中第 %d 个元素为：%d", i, result);
else
printf("\nlink1 中不存在第 %d 个元素", i);
// 由用户输入一个数，然后通过查找函数查找这个数是否在 link1 中，如果在则删除这个数并输出删除后的 link1，如果不在则输出找不到
printf("\n\n请输入要查找的 link1 元素：");
DataType find;
scanf("%d", &find);
if ((i = findByData(link1, find)) != 0)
{
printf("\nlink1 中存在 %d 元素，删除后元素序列：\n", find);
deleteByOrder(link1, i);
printLinkList(link1);
}
else
printf("\nlink1 中不存在元素 %d\n", find);
// 调用删除函数删除link2中第i个元素（i由用户输入），删除成功后输出删除后的link2的元素序列，删除失败则显示不存在这个数。
printf("\n请输入要删除的 link2 元素的位置：");
scanf("%d", &i);
if (deleteByOrder(link2, i))
{
printf("\nlink2 中删除第 %d 个元素后的元素序列：\n", i);
printLinkList(link2);
}
else
printf("\nlink2 中不存在第 %d 个元素", i);
return 0;
}
|
Zuwei
支付宝
微信