线性表复习

Author: 张浩森 Date: Jul 8, 2018 Updated On: Jul 8, 2018
Categories:
Tags:

数据结构线性表章节复习,基本操作伪代码手打:

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
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
/***
线性表章节代码盲打
***/

/**
顺序表定义以及基本操作
**/
#define maxsize 100
typedef struct
{
int data[maxsize];
int length;
}Sqlist;

/**
已知一个顺序表L,其中的元素递增有序排列,设计一个算法,插入一个元素x(x为int型)后保持
该顺序表仍然递增有序排列
**/

/**
寻找第一个比x大的元素的下标
**/
int findElem(Sqlist L, int x){
for(int i = 0; i < L.length; i++){
if(x <= L.data[i]){
return i;
}
}
return i; //如果顺序表中没有元素比x大,则最后i是原来顺序表中最大元素后面的那个索引
}
//插入x
void insertElem(Sqlist &L, int x){
int p = findElem(x);
for(int i = L.length - 1; i >= p; i--){ //如果顺序表中没有元素比x大,则p是原来顺序表中最大元素后面的那个索引,i<p,直接不进循环
L.data[i + 1] = L.data[i];
}
L.data[p] = x;
L.length++;
}

/**
按元素值的查找算法
**/
int findElem(Sqlist L, int x){
for(int i = 0; i < L.length; i++){
if(L.data[i] == x){
return i;
}
}
return -1;
}

/**
插入数据元素的算法,在顺序表上的第p个位置插入新的元素e
**/
int insertElem(Sqlist &L, int p, int e){
if(p < 0 || p >= L.length || L.length == maxsize) return 0;
else{
for(int i = L.length - 1; i >= p; i++){
L.data[i + 1] = L.data[i];
}
L.data[p] = e;
L.length++;
return 1;
}
}

/**
删除顺序表L中下标为p(0<=p<=length-1)的元素,成功返回1,不成功返回0,将删除的元素赋值给e
**/
int deleteElem(Sqlist &L, int p, int &e){
if(p < 0 || p >= L.length) return 0;
e = L.data[p];
for(int i = p; i < L.length - 1; i++){
L.data[i] = L.data[i + 1];
}
L.length--;
return 1;
}

/**
初始化顺序表
**/
void initList(Sqlist &L){
L.length = 0;
}

/**
求指定位置元素的算法
**/
int getElem(Sqlist L, int p){
if(p < 0 || p >= L.length) return -1;
else return data[p];
}

/**
链表定义以及基本操作
**/

/*
单链表
*/
typedef struct LNode{
int data;
struct LNode *next;
}LNode;

/*
双链表
*/
typedef struct DLNode{
int data;
struct DLNode *next;
struct DLNode *prior;
}DLNode;

/**
定义一个指向LNode的指针并且指向赋值号后面构造的那个结点,用这个指针的名称来作为结点的名称。
**/
LNode *A = (LNode*)malloc(sizeof(LNode));

/**
两个链表A、B都是递增的有序单链表,带头结点,现在将两个链表合成一个有序不递减的链表C。
思想:尾插法,因此必须有一个指向构造的链表末端的指针,能够一次找到,不能从头找。而且也必须有指向头结点的指针,这里C就是,而且也是要构造的链表
**/
void mergeR(LNode *A, LNode *B, LNode *&C){
LNode *p = A->next;
LNode *q = B->next;
C = A;
C->next = NULL;
LNode *r;
r = C;
free(B);
while(p != NULL && q != NULL){
if(p->data <= q->data){
r->next = p;
p = p->next;
r = r->next;
}
else{
r->next = q;
q = q->next;
r = r->next;
}
}
if(p != NULL){
r->next = p;
}
if(q != NULL){
r->next = q;
}
}

/**
有n个元素已经存在数组中,利用尾插法建立链表C
**/
void creatlistR(LNode *&C, int a[], int n){
LNode *s, *r;
C = (LNode*)malloc(sizeof(LNode));
C->next = NULL;
r = C;
for(int i = 0; i < n; i++){
s = (LNode*)malloc(sizeof(LNode));
s->data = a[i];
s->next = NULL;
r->next = s;
r = r->next;
}
r->next = NULL;
}
/*
头插法
*/
void creatlistF(LNode *&C, int a[], int n){
LNode *s;
C = (LNode*)malloc(sizeof(LNode));
C->next = NULL;
for(int i = 0; i < n; i++){
s = (LNode*)malloc(sizeof(LNode));
s->data = a[i];
s->next = C->next;
C->next = s;
}
}

/**
利用头插法将两个递增的单链表归并成一个递减的单链表
**/
void mergeF(LNode *A, LNode *B, LNode *&C){
LNode *p = A->next;
LNode *q = B->next;
LNode *s;
C = A;
C->next = NULL;
free(B);
while(p != NULL && q != NULL){
if(p->data <= q->data){
s = p;
p = p->next;
s->next = C->next;
C->next = s;
}
else{
s = q;
q = q->next;
s->next = C->next;
C->next = s;
}
}
while(p != NULL){
s = p;
p = p->next;
s->next = C->next;
C->next = s;
}
while(q != NULL){
s = q;
q = q->next;
s->next = C->next;
C->next = s;
}
}

/**
查找链表C(带头结点)中是否存在一个值为x的结点,若存在,则删除该结点并返回1,否则返回0
**/
int findAndDelete(LNode *C, int x){
LNode *p;
LNode *q;
p = C;
while(p->next != NULL){
if(p->next->data == x){
break;
}
p = p->next;
}
if(p->next == NULL){
return 0;
}
else{
q = p->next;
p->next = p->next->next;
free(q);
return 1;
}

}

总结,链表定义的结点都是有指针指向的,定义的LNode *A都是指针,要理解这些都是指针,而不是结点,结点是由指针找到的,因此变量访问符都是->而不是.,由这个指针可以找到这个链表中的每一个结点。

/**
双链表的操作
**/

/**
采用尾插法建立双链表
**/
void createDlistR(DLNode *&L, int a[], int n){
DLNode *s, *r;
L = (DLNode*)malloc(sizeof(DLNode));
L->next == NULL;
L->prior == NULL;
r = L;
for(int i = 0; i < n; i++){
s = (DLNode*)malloc(sizeof(DLNode));
s->data = a[i];
r->next = s;
s->prior = r;
r = r->next;
}
r->next = NULL;
}

/**
查找结点的算法
**/
DLNode* findNode(DLNode *C, int x){
DLNode *p = C->next;
while(p != NULL){
if(p->data == x){
break;
}
p = p->next;
}
return p;
}

/**
插入结点的算法
**/
假设要插入一个结点DLNode *s指向的结点,插入在DLNode *p指向的结点和p->next指向的节点中间,过程如下:
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s; //假如p指向最后一个结点,则本行可以去掉,也就是在双链表尾部插入一个结点,s->next=NULL

/**
删除结点的做法
**/
设要删除双链表中p结点的后继结点,其操作语句如下:
DLNode *q = p->next;
p->next = q->next;
q->next->prior = p; //或者p->next->prior = p;两句效果一样
free(q);


/**
**/
循环链表的操作也是从上面衍生出来的。判断p走到尾结点的条件是p->next == head;


总结,链表的各种操作是通过指针实现的,只能改指针进行各种操作。根据各种不同的情景可以定义指向不同结点的指针进行操作。
头插法只需要两个指针,一个指向头结点的指针,一个指向当前插入结点的指针。
尾插法需要三个指针,一个指向头结点的指针,一个指向尾部的指针,一个指向当前插入结点的指针。

看来自己的大二的时候链表就根本没学明白,到了快大四了才明白。实在是惭愧。