数据结构---单链表的基本操作代码块

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
单链表的基本操作
//定义
typedef struct LNode
{
ElemType data;
//数据域
struct LNode *next;
//指针域
}LNode , *LinkList;
//初始化
Status InitList(LinkList &L)
{
L = new LNode;
//生成一个新结点
L->next = NULL;
//结点指针域置空
return ok;
}
//判空
Status Empty(LinkList L)
{
return (L->next == NULL);
}
//表长
int Length(LinkList L)
{
int len = 0;
LNode *p = L;
while (!p->next)
{
p = p->next;
len++;
}
return len;
}
//取值，在L表中，取第i个元素的值，并用e带回
Status GetElem(LinkList L, int i, ElemType &e)
{
LNode *p = L->next;
//定义一个结点类型的指针p，指向首元结点
int j = 1;
//p指向头结点j为1,记录p扫描的结点数
while (p && j < i - 1)
//p不为空且还没到i - 1个元素时
{
p = p->next;
//p顺着链域继续找
j++;
}
if (!p)
//p为空，返回error
return error;
e = p->data;
//找到了，就把该结点的数据域赋给e
return ok;
}
//按值查找, 在单链表中查找元素值为e的结点
LNode *LocateElem(LinkList L, ElemType e)
{
LNode *p = L->next;
//p指向首元结点
while (p && p->data != e)
//p不为空且p所指结点的数据域不等于e
p = p->next;
//p继续向下查找
return p;
}
//按位查找,返回第i个元素
LNode *GetElem(LinkList L, int i)
{
LNode *p ;
p = L;
//p指向头结点
int j = 0;
if (i == 1)
//查找第一个元素，就返回头结点
return L;
if (i < 1)
//i < 1位置不合法
return NULL;
if (p || j < i )
//p不为空且j小于i，p向下继续找
{
p = p->next;
j++;
}
return p;
//找到了，返回P
}
//插入算法，在L的第i个元素中插入e
Status ListInsert(LinkList L, int i, ElemType e)
{
LNode *p = L;
//定义一个结点类型的指针P指向头结点
int j = 0;
//记录p所扫描的结点数
while (p && j < i - 1)
{
p = p->next;
j++;
}
if (!p || j > i - 1)
return error;
LNode *s;
//将插入的元素，存放在一个s的新结点
s = new LNode;
//为新结点new一个结点空间
s->data = e;
//把e存放在新结点的数据域
s->next = p->next;
//将ai结点的地址存放在新结点的next域
p->next = s;
//再把新结点的地址存放在ai-1的next域
return ok;
}
//删除
//ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
//1、查找结点ai-1（要删除结点的前驱结点）,并由指针p指向该结点；
//2、临时保存待删除结点a1的地址在q中，以备释放；
//3、将结点*p的指针域指向ai的直接后继结点；
//4、释放结点ai的空间。
Status ListDelete(LinkList &L, int i, ElemType &e)
{
LNode *p, *q;
//p指向当前扫描的结点
int j = 0;
//记录当前结点p指向第几个结点
p = L;
//L指向头结点，第0个结点（不存数据）
while (p->next && j < i- 1)
//循环找到删除结点的前驱结点，即第i-1个结点
{
p = p->next;
j++;
}
if (!p->next || j > i - 1)
//位置不合法
return error;
q = p->next;
//q指向被删除的结点
p->next = q->next;
//将*q结点从链中断开
e = q->data;
//用e返回元素的值
delete q;
//释放结点空间
return ok;
}
//输出
Status DispLsit(LinkList L)
{
LNode *p;
p = L->next;
while (p)
{
cout << p->data << ' ';
p = p->next;
}
cout << endl;
return ok;
}
//头插法
void CreatList_H(LinkList &L, int n)
{
L = new LNode ;
L->next = NULL;
//建立一个带头结点的单链表
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
//生成新结点*p
cin >> p->data;
//输入元素值赋给新结点的数据域
//将新结点插入到头结点之后
p->next = L->next;
L->next = p;
}
}
//尾插法
void CreatList_R(LinkList &L, int n)
{
L = new LNode ;
L->next = NULL;
//创建一个到头结点的空链表
LNode *r = L;
//尾指针指向头结点
for (int i = 0; i < n; i++)
{
LNode *p = new LNode;
//生成新结点
cin >> p->data;
//输入元素值赋给新结点*p的数据域
//将新结点*p插入到尾结点*r之后
p->next = NULL;
r->next = p;
r = p;
//r指向新的尾结点*p
}
}
//销毁
Status DestoryList(LinkList &L)
{
LNode *p ;
while (L)
{
p = L;
L = L->next;
delete p;
}
return ok;
}
//清空
Status ClearList(LinkList &L)
{
LNode *p , *q;
p = L->next;
while (p)
//没到表尾
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
//头结点指针域为空
return ok;
}