LinkList

Posted by mapoto4 on 2017-03-16

链表

线性表的链式存储,用一组任意的存储单元存储线性表的数据元素,这些存储单元可以是连续的也可以是不连续的。

链表特性

  1. 不支持随机访问
  2. 动态分配
  3. 结点的存储空间利用率稍低

备注

头指针与头结点
头指针:链表指向的第一个结点的指针,若有头结点,则是指向头结点的指针,通常用头指针作为链表的名字,无论链表是否为空,头指针都不为空。
头结点:非必要元素,为方便操作设立,一般数据域用来存放链表长度或者无意义。

代码实现

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
240
241
242
243
244
245
246
#include <iostream>
#include <time.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

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

int InitList(LinkList *L) {
*L = (LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
if (!(*L)) /* 存储分配失败 */
return ERROR;
(*L)->next = NULL; /* 指针域为空 */
cout << "初始化成功!" << endl;
return OK;
}

void ListEmpty(LinkList L)//判断是否为空
{
if (L->next)
cout << "链表非空!" << endl;
else
cout << "链表为空!" << endl;
}

void CreateListHead(LinkList *L, int n)//头插法
{
LinkList p;
int i;
srand(time(0));
*L = (Node*)malloc(sizeof(Node));
(*L)->next = NULL;
for (i = 1; i < n; i++)
{
p = (LinkList)malloc(sizeof(Node));
p->data = rand() % 100 + 1;
p->next = (*L)->next;
(*L)->next = p;
}
}

void CreateListTail(LinkList *L, int n)//尾插法
{
LinkList p, r;
int i;
srand(time(0));
*L = (LinkList)malloc(sizeof(Node));
r = *L;
for (i = 0; i < n; i++)
{
p = (Node*)malloc(sizeof(Node));
p->data = rand() % 100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}

int GetLinkListLength(LinkList L) //返回链表长度
{
int length=0;
LinkList s;
s = L->next;
while (s)
{
length++;
s = s->next;
}
return length;
}

int ClearList(LinkList *L)//整表删除
{
LinkList p, q;
p = (*L)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*L)->next = NULL;
return OK;
}

int GetElem(LinkList L, int i, int *e)//将链表L中第i个元素返回给e
{
int j;
LinkList p;
p = L->next;
j = 1;
while (p&&j < i)
{
p = p->next;
j++;
}
if (!p || j > i)
return ERROR;
*e = p->data;
return OK;
}

int LocateElem(LinkList L, int e)//将链表L中值为e的元素位置返回
{
LinkList p;
int count=0;
p = L->next;
while (p!=NULL&&(p->data!=e))
{
p = p->next;
count++;
}
return count;
}

int ListInsert(LinkList *L, int i, int e)//在链表L中第i个结点插入新的数据元素
{
int pos = 1;
LinkList p, s;
p = *L;
while (p&&pos < i)
{
p = p->next;
pos++;
}
if (!p || pos > i)
return ERROR;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

int ListDelete(LinkList *L, int i, int *e)//删除链表L中第i个元素
{
int pos = 1;
LinkList p, s;
p = *L;
while (p->next&&pos < i)
{
p = p->next;
pos++;
}
if (!(p->next) || pos > i)
return ERROR;
s = p->next;
p->next = s->next;
*e = s->data;
free(s);
s->next = NULL;
return OK;
}

int output(LinkList L)//输出链表
{
LinkList p = L->next;
while (p)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
return OK;
}

int main()
{

LinkList L;
int e;
int i;
int Len;
int find_E, find_L;
int insert_L, insert_E;
int delete_L;

i = InitList(&L);
Len = GetLinkListLength(L);
cout<<"链表长度为"<<Len<<"\n\n";

cout << "1.头插法建立链表" << endl;
cout << "2.尾插法建立链表" << endl;
cout << "3.返回第i个元素的值" << endl;
cout << "4.返回值为i的元素位置" << endl;
cout << "5.插入元素" << endl;
cout << "6.删除元素" << endl;
cout << "7.清空" << endl;

int switch_on = 99;
while (switch_on != 0)
{
cin >> switch_on;
switch (switch_on)
{
case 1:
CreateListHead(&L, 20);
output(L);
break;
case 2:
CreateListTail(&L, 20);
output(L);
break;
case 3:
GetElem(L, 5, &e);
cout << "第五个元素的值:" << e << endl;
break;
case 4:

cout << "输入要查找的元素:";
cin >> find_E;
find_L = LocateElem(L, find_E);
cout << "元素" << find_E << "的位置是:" << find_L + 1 << endl;
break;
case 5:
cout << "输入插入位置:";
cin >> insert_L;
cout << "输入插入元素:";
cin >> insert_E;
ListInsert(&L, insert_L, insert_E);
output(L);
break;
case 6:
cout << "输入删除位置:";
cin >> delete_L;
ListDelete(&L, insert_L,&e);
output(L);
break;
case 7:
i = ClearList(&L);
printf("清空L后:ListLength(L)=%d\n", GetLinkListLength(L));
ListEmpty(L);
break;
case 0:
exit(0);
}
}
}