LinkList的模板案例

EaborH
  2025-07-24 2025-07-24 Created   2025-08-26 19:34:41 2025-08-26 19:34:41 Updated       
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
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
using namespace std;  
  
#define MaxSize 50  
#define InitSize 100  
  
typedef int ElemType;  
  
// 线性表静态分配  
typedef struct {  
    ElemType StaticData[MaxSize];  
    int length;  
}SqList;  
// 线性表动态分配  
typedef struct {  
    ElemType *DynamicData;  
    int DynamicMaxSize;  
    int length;  
}SeqList;  
  
// 静态线性表初始化  
void InitStaticList(SqList &L) {  
    L.length=0;  
}  
// 动态线性表初始化  
void InitDynamicList(SeqList &L) {  
    L.DynamicData=(ElemType *)malloc(InitSize*sizeof(ElemType));  
    L.length=0;  
    L.DynamicMaxSize=InitSize;  
}  
// 线性表扩容  
void IncreaseSize(SeqList &L, int len) {  
    ElemType *p=L.DynamicData;  
    L.DynamicData=(ElemType *)malloc((L.DynamicMaxSize+len)*sizeof(ElemType));  
    for (int i=0;i<L.length;i++) {  
        L.DynamicData[i]=p[i];  
    }  
    L.DynamicMaxSize=L.DynamicMaxSize+len;  
    free(p);  
}  
// 静态线性表插入  
bool StaticListInsert(SqList &L, int i, ElemType e) {  
    if (i<1 || i>L.length+1)  
        return false;  
    if (L.length>=MaxSize)  
        return false;  
    for (int j=L.length;j>=i;j--) {  
        L.StaticData[j]=L.StaticData[j-1];  
    }  
    L.StaticData[i-1]=e;  
    L.length++;  
    return true;  
}  
// 静态线性表删除  
bool StaticListDelete(SqList &L, int i, ElemType &e) {  
    if (i<1 || i>L.length)  
        return false;  
    e=L.StaticData[i-1];  
    for(int j=i;j<L.length;j++)  
        L.StaticData[j-1]=L.StaticData[j];  
    L.length--;  
    return true;  
}  
// 静态线性表按值查找  
int StaticLocateElem(SqList L, ElemType e) {  
    int i;  
    for(i=0;i<L.length;i++) {  
        if(L.StaticData[i]==e)  
            return i+1;  
    }  
    return 0;  
}  
  
// 单链表的定义  
typedef struct LNode {  
    ElemType data;          // 数据域  
    struct LNode *next;     // 指针域  
}LNode, *LinkList;  
  
// 单链表初始化(带头节点)  
bool Init_SLinkList_WithHeadNode(LinkList &L) {  
    L=(LNode *)malloc(sizeof(LNode));  
    L->next=NULL;       // 头节点指向NULL  
    return true;  
}  
// 单链表初始化(不带头节点)  
bool Init_SLinkList_WithoutHeadNode(LinkList &L) {  
    L=NULL;  
    return true;  
}  
// 单链表求表长操作  
int SLinkList_Length(LinkList L) {  
    int len=0;      // 长度计数，初始为 0    LNode *p=L;     // 创建一个LNode * 指针变量且指向传入的单链表  
    while(p->next!=NULL) {  
        p=p->next;  
        len++;  
    }  
    return len;  
}  
// 单链表按序号查找节点  
LNode *SLinkList_GetElem(LinkList L, int i) {  
    LNode *p=L;  
    int j=0;  
    while (p!=NULL && j<i) {  
        p=p->next;  
        j++;  
    }  
    return p;  
}  
// 单链表按值查找节点  
LNode *SLinkList_LocateElem(LinkList L, ElemType e) {  
    LNode *p=L->next;  
    while(p!=NULL && p->data!=e) {  
        p=p->next;  
    }  
    return p;  
}  
// 单链表按位序插入节点的操作(带头节点)  
bool SLinkList_InsertByIndex_WithHeadNode(LinkList &L, int i, ElemType e) {  
    if (i<1)  
        return false;  
    LNode *p=L;  
    int j=0;  
    while (p!=NULL && j<i-1) {      // j<i-1,找到i-2个节点后在循环内部会将指针p指向(i-2)->next即实际的i-1  
        p=p->next;  
        j++;  
    }  
    if (p==NULL)        // i值不合法  
        return false;  
    LNode *s=(LNode *)malloc(sizeof(LNode));  
    s->data=e;  
    s->next=p->next;  
    p->next=s;  
    return true;  
}  
// 单链表按位序插入节点的操作(不带头节点)  
bool SLinkList_InsertByIndex_WithoutHeadNode(LinkList &L, int i, ElemType e) {  
    if (i<1)  
        return false;  
    if (i==1) {  
        // 不带头节点插入第一个节点与其他节点不同  
        LNode *s=(LNode *)malloc(sizeof(LNode));  
        s->data=e;  
        s->next=L;  
        L=s;
        return true;  
    }  
    LNode *p;  
    int j=1;  
    p=L;  
    while (p!=NULL && j<i-1) {  
        p=p->next;  
        j++;  
    }  
    if (p==NULL)  
        return false;  
    LNode *s=(LNode *)malloc(sizeof(LNode));  
    s->data=e;  
    s->next=p->next;  
    p->next=s;  
    return true;  
}  
// 单链表指定节点的后插操作(在指定节点p之后插入元素e)  
bool SLinkList_InsertByNode_AfterPod(LNode *p, ElemType e) {  
    if(p==NULL)  
        return false;  
    LNode *s=(LNode *)malloc(sizeof(LNode));  
    if (s==NULL)  
        return false;  
    s->data=e;  
    s->next=p->next;  
    p->next=s;  
    return true;  
}  
// 单链表指定节点的前插操作(在指定节点p之前插入元素e)  
bool SLinkList_InsertByNode_BeforePod(LNode *p, ElemType e) {  
    if(p==NULL)  
        return false;  
    LNode *s=(LNode *)malloc(sizeof(LNode));  
    if (s==NULL)  
        return false;  
    s->next=p->next;  
    p->next=s;  
    s->data=p->data;  
    p->data=e;  
    return true;  
}  
// 单链表按位序删除(带头节点)  
bool SLinkList_DeleteByIndex_WithHeadNode(LinkList L, int i, ElemType &e) {       // e为返回的删除元素  
    if (i<1)  
        return false;  
    LNode *p;  
    int j=0;  
    p=L;  
    while (p!=NULL && j<i-1) {  
        p=p->next;  
        j++;  
    }  
    if (p==NULL || p->next == NULL)  
        return false;  
    LNode *q=p->next;  
    e=q->data;  
    p->next=q->next;  
    free(q);  
    return true;  
}  
// 单链表指定节点的删除  
bool SLinkList_DeleteByNode(LNode *p) {  
    if (p==NULL || p->next==NULL)  
        return false;  
    LNode *q=p->next;  
    p->data=p->next->data;      // 写法B: p->data = q->data;  
    p->next=q->next;  
    free(q);  
    return true;  
}  
// 尾插法建立单链表  
LinkList Create_SLinkList_TailInsert(LinkList &L) {  
    ElemType x;     // x 为元素, ElemType为元素的类型，此处为int  
    L=(LNode *)malloc(sizeof(LNode));       // 创建头节点  
    LNode *s, *r=L;         // r为表尾指针  
    scanf("%d", &x);  
    while (x!=9999) {  
        s=(LNode *)malloc(sizeof(LNode));  
        s->data=x;  
        r->next=s;  
        r=s;  
        scanf("%d", &x);  
    }  
    r->next=NULL;  
    return L;  
}  
// 头插法建立单链表  
LinkList Creare_SLinkList_HeadInsert(LinkList &L) {  
    LNode *s;  
    int x;  
    L=(LNode *)malloc(sizeof(LNode));  
    scanf("%d", &x);  
    while (x!=9999) {  
        s=(LNode *)malloc(sizeof(LNode));  
        s->data=x;  
        s->next=L->next;  
        L->next=s;  
        scanf("%d", &x);  
    }  
    return L;  
}  
  
// 双链表的定义  
typedef struct DNode {  
    ElemType data;  
    struct DNode *prior, *next;  
}DNode, *DLinkList;  
  
// 带头结点的双链表初始化  
bool InitDLinkList_WithHeadNode(DLinkList &L) {  
    L=(DNode *)malloc(sizeof(DNode));  
    if (L==NULL)        // 内存不足，分配失败  
        return false;  
    L->prior=NULL;      // 头节点的 peior 永远指向NULL  
    L->next=NULL;  
    return true;  
}  
// 双链表的后插  
bool InsertNextDNode(DNode *p, DNode *s) {      // 将s插入到p之后  
    if (p==NULL || s==NULL)  
        return false;       // 非法参数  
    s->next=p->next;  
    if (p->next!=NULL)  
        p->next->prior=s;  
    s->prior=p;  
    p->next=s;  
    return true;  
}  
// 删除 p 节点的后继节点  
bool DeleteNextDNode(DNode *p) {  
    if (p==NULL)    return false;  
    DNode *q=p->next;  
    if (q==NULL)    return false;  
    p->next=q->next;  
    if (q->next!=NULL)  
        q->next->prior=p;  
    free(q);  
    return true;  
}  
// 双链表的删除  
void DestoryDList(DLinkList &L) {  
    // 循环删除各个数据节点( 循环调用DeleteNextDNode() )  
    while (L->next!=NULL)  
        DeleteNextDNode(L);  
    free(L);    // 释放头节点  
    L=NULL;     // 头指针指向NULL  
}  
  
/* 循环单链表  
 * 使用的定义和单链表的定义相同  
 * 具体参考 LNode and *LinkList */  
// 初始化一个循环单链表  
bool Init_CSList(LinkList &L) {  
    L=(LNode *)malloc(sizeof(LNode));  
    if (L==NULL)  
        return false;       // 内存不足，分配失败  
    L->next=L;  
    return true;  
}  
// 判断循环单链表是否为空  
bool isCSListEmpty(LinkList L) {  
    if (L->next==L)  
        return true;  
    else  
        return false;  
}  
// 判断节点 p 是否是循环单链表的表尾节点  
bool isCSListTail(LinkList L, LNode *p) {  
    if (p->next==L)  
        return true;  
    else  
        return false;  
}  
  
/* 循环双链表  
 * 使用的定义和双链表的定义相同  
 * 具体参考 DNode and *DLinkList */  
// 初始化空的循环双链表  
bool Init_CDLinkList(DLinkList &L) {  
    L=(DNode *)malloc(sizeof(DNode));  
    if (L==NULL)  
        return false;       // 内存不足，分配失败  
    L->prior=L;             // 头节点的 prior 指向头节点  
    L->next=L;              // 头节点的 next 指向头节点  
    return true;  
}  
// 判断循环双链表是否为空  
bool isCDLinkListEmpty(DLinkList L) {  
    if (L->next==L)  
        return true;  
    else  
        return false;  
}  
// 判断节点 p 是否是循环双链表的表尾节点  
bool isCDListTail(DLinkList L, DNode *p) {  
    if (p->next==L)  
        return true;  
    else  
        return false;  
}  
// 双链表的插入(在 p 节点之后插入 s 节点)  
bool CDList_InsertNextDNode(DNode *p, DNode *s) {  
    s->next=p->next;  
    p->next->prior=s;  
    s->prior=p;  
    p->next=s;  
    return true;  
    /* 删除同理  
    * p->next=q->next;    
    * q->next->prior=p;    
    * free(q);    
    */}
  • Title: LinkList的模板案例
  • Author: EaborH
  • Created at : 2025-07-24 00:00:00
  • Updated at : 2025-08-26 19:34:41
  • Link: https://eabor.xyz/2025/07/24/LinkList/
  • License: This work is licensed under CC BY-NC-SA 4.0.
On this page
LinkList的模板案例