数据结构与算法（C语言）代码实现-线性表的相关操作代码实现（单链表）_数据结构与算法线性表实验代码

c语言代码实现

C语言实现 线性表（单链表）的相关操作，实现了如下方法：

• 初始化单链表
  InitLinkList(LinkList &L);
• 销毁单链表
  DestroyLinkList(LinkList &L);
• 清空单链表
  ClearLinkList(LinkList &L);
• 在单链表指定位置插入元素
  LinkListInsert(LinkList &L, int i, ElemType e);
• 单链表头插法
  LinkListInsert_h(LinkList &L, ElemType e);
• 单链表尾插法
  LinkListInsert_r(LinkList &L, ElemType e);
• 获取单链表的长度
  LinkListLength(LinkList L);
• 在单链表中查找指定元素所在的位置
  LocateElem(LinkList L, ElemType e);
• 在单链表中查找指定元素是否存在，存在就把该节点作为函数返回值返回
  LocateElem_(LinkList L, ElemType e);
• 在单链表中获取指定位置的元素
  GetElem(LinkList L, int i, ElemType &e);
• 判断单链表是否为空
  IsEmpty(LinkList L);
• 删除单链表指定位置的元素
  LinkListDelete(LinkList &L, int i, ElemType &e);

写的匆忙，如有错误，请大家指正一下。

#include <stdio.h>
#include <cstdlib>

//###一些常量
//函数结果状态码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//单链表最大容量
#define MAXSIZE 100


//函数类型
typedef int Status;
//单链表的元素类型
typedef char ElemType;


//定义单链表的结构体
typedef struct node{
    //链表的数据域
    ElemType data;
    //链表的指针域
    struct node *next;
}LinkListNode, *LinkList;

//---------------------------------------------------------------
//初始化单链表
Status InitLinkList(LinkList &L);
//销毁单链表
void DestroyLinkList(LinkList &L);
//清空单链表
void ClearLinkList(LinkList &L);
//在单链表指定位置插入元素
Status LinkListInsert(LinkList &L, int i, ElemType e);
//单链表头插法
Status LinkListInsert_h(LinkList &L, ElemType e);
//单链表尾插法
Status LinkListInsert_r(LinkList &L, ElemType e);
//获取单链表的长度
int LinkListLength(LinkList L);
//在单链表中查找指定元素所在的位置
int LocateElem(LinkList L, ElemType e);
//在单链表中查找指定元素是否存在，存在就把该节点作为函数返回值返回
LinkListNode* LocateElem_(LinkList L, ElemType e);
//在单链表中获取指定位置的元素
Status GetElem(LinkList L, int i, ElemType &e);
//判断单链表是否为空
Status IsEmpty(LinkList L);
//删除单链表指定位置的元素
Status LinkListDelete(LinkList &L, int i, ElemType &e);
//---------------------------------------------------------------
int main(){
    /**
    * 对线性表的相关操作进行测试
    */
    //定义一个链表
    LinkList list;
    //初始化顺序表
    InitLinkList(list);
    //将元素插入到线性表中
    ElemType e1 = 'a';
    ElemType e2 = 'b';
    ElemType e3 = 'c';
    ElemType e4 = 'd';
    ElemType e5 = 'e';
    LinkListInsert(list, 1, e1);
    LinkListInsert(list, 2, e2);
    LinkListInsert(list, 3, e3);
    LinkListInsert(list, 4, e4);
    LinkListInsert(list, 5, e5);
    //打印线性表的元素，打印结果：a	b	c	d	e
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    //查看线性表是否为空
    Status s = IsEmpty(list);
    printf("\n是否为空线性表：%d\n", s);//0
    //查看线性表的长度
    int length = LinkListLength(list);//返回
    printf("线性表的长度：%d\n", length);//5
    //删除一个元素
    ElemType e6;
    LinkListDelete(list, 2, e6);
    printf("被删除的元素：%c\n", e6);//b
    //打印线性表的元素，打印结果：a	c	d	e
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    printf("\n");
    //查找元素c所在的序号
    ElemType c = 'c';
    int index = LocateElem(list, c);
    printf("元素c所在的序号是：%d\n", index);//2
    //头插法和尾插法
    ElemType e7 = '7';
    ElemType e8 = '8';
    LinkListInsert_h(list, e7);
    LinkListInsert_r(list, e8);
    //打印线性表的元素，打印结果：7	a	c	d	e	8
    for(int i = 0; i < LinkListLength(list); i++){
        ElemType e;
        GetElem(list, i+1, e);
        printf("%c\t", e);
    }
    printf("\n");
    //查找元素c所在的结点
    ElemType e9 = 'c';
    LinkListNode *locateNode = LocateElem_(list, e9);
    printf("查找到的结点的数据域：%c，下一个结点的地址：%p\n", locateNode->data, locateNode->next);//c
    //清空线性表
    ClearLinkList(list);
    //查看线性表是否为空
    s = IsEmpty(list);
    printf("是否为空线性表：%d\n", s);//1
    //销毁线性表
    DestroyLinkList(list);
    return 0;
}

/**
 * 初始化单链表，将L指向头结点，并将头结点的next指针域设置为空
 * @param L 单链表
 * @return
 */
Status InitLinkList(LinkList &L){
    //C语言写法，创建一个头结点，L指向这个头结点
    //L = (LinkList)malloc(sizeof(LinkListNode));
    // c++写法
    L = new LinkListNode;
    //判断是否创建头结点成功
    if (!L){
        printf("单链表初始化失败！");
        return OVERFLOW;
    }
    //初始化头结点，指针域设置为空
    L->next = NULL;
    return OK;
}
/**
 * 判断单链表是否为空，如果单链表的头结点的next指针域为空，说明单链表为空
 * @param L 单链表
 * @return
 */
Status IsEmpty(LinkList L){
    //三目运算符
    return L->next? FALSE: TRUE;
}
/**
 * 销毁单链表，从头结点开始，依次销毁每个结点
 * @param L
 */
void DestroyLinkList(LinkList &L){
    for(LinkListNode *p = L; p; p = L->next){
        //记录当前结点指向的下一节点
        L = p->next;
        //销毁当前结点
        delete p;
        //p指向下一节点
    }
}
/**
 * 清空单链表，头结点的next指针域设为空，后面的元素都进行销毁
 * @param L
 */
void ClearLinkList(LinkList &L){
    //方法一：
    //把头结点的next指针传入DestroyLinkList函数进行销毁
    DestroyLinkList(L->next);


    //方法二：
    //从首元节点开始，每个结点都进行销毁
    LinkListNode *p1 = L->next, *p2;
    //p1为空，说明没有要删除的元素了，退出循环
    while(p1){
        //p1指向当前要删除的结点，p2指向当前节点的下一个结点
        p2 = p1->next;
        //销毁当前元素
        delete p1;
        //p1指向下一个要删除的元素，即p2
        p1 = p2;
    }
    //将头结点的next指针域设置为空
    L->next = NULL;
}
/**
 * 获取单链表的长度
 * @param L 单链表
 * @return
 */
int LinkListLength(LinkList L){
    int count = 0;
    //从首元节点开始计算
    //循环计数
    for(LinkListNode *p = L->next; p; (p = p->next), count++);
    return count;
}
/**
 * 获取单链表中指定位置的元素
 * @param L 单链表
 * @param i 第几个位置
 * @param e 用来接收找到的元素
 * @return
 */
Status GetElem(LinkList L, int i, ElemType &e){
    LinkListNode *p = L;
    for(int k = 1; k <= i && p; k++){
        //指向下一个结点
        p = p->next;
        //不是要找的位置，跳过本次循环
        if (k != i) continue;
        //已经到第i个了，将e指向这个结点
        e = p->data;
        return OK;
    }
    //没有找到
    return ERROR;
}
/**
 * 在单链表中查找指定元素所在的位置
 * @param L 单链表
 * @param e 要查找的元素
 * @return
 */
int LocateElem(LinkList L, ElemType e){
    //指向首元节点
    LinkListNode *p = L->next;
    for(int i = 1; p; i++){
        //找到相同的元素，返回位置
        if(p->data == e) return i;
        //指向下一个元素
        p = p->next;
    }
    //没有找到
    return 0;
}
/**
 * 在单链表中查找指定元素是否存在，存在就把该节点返回
 * @param L 单链表
 * @param e 要查找的元素
 * @return
 */
LinkListNode* LocateElem_(LinkList L, ElemType e){
    //指向首元节点
    LinkListNode *p = L->next;
    while(p){
        //找到相同的元素，返回该结点
        if(p->data == e) return p;
        //指向下一个元素
        p = p->next;
    }
    //没有找到，返回空
    return NULL;
}
/**
 *在单链表的指定位置插入元素
 * @param L 单链表
 * @param i 位置
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert(LinkList &L, int i, ElemType e){
    LinkListNode *p = L;
    //p为空时结束循环
    for(int k = 1; k <= i && p; k++, p = p->next){
        //没到指定位置，跳过本次循环
        if(k != i) continue;
        //进行插入相关操作
        //新建一个结点
        LinkListNode *newNode = (LinkListNode*)malloc(sizeof(LinkListNode));
        //把元素放入新建的结点的数据域中
        newNode->data = e;
        //插入，新结点的next指针域指向当前结点的next指针域
        newNode->next = p->next;
        //当前结点的next指针域指向新结点，完成插入
        p->next = newNode;
        //插入完成
        return OK;
    }
    //插入失败
    printf("插入失败！\n");
    return ERROR;
}
/**
 * 删除单链表指定位置的元素
 * @param L 单链表
 * @param i 要删除的位置
 * @param e 接收删除的节点的元素
 * @return
 */
Status LinkListDelete(LinkList &L, int i, ElemType &e){
    //指向首元节点
    LinkListNode *p = L->next;
    //计算出删除元素的前一个元素的位置
    int deletePreIndex = i - 1;
    for(int k = 1; k <= deletePreIndex; k++, p = p->next){
        //没有到指定位置，跳过本次循环
        if(k != deletePreIndex) continue;
        //删除相关操作
        //把e指向要删除的结点的元素
        e = p->next->data;
        //记录要删除的结点
        LinkListNode *delNode = p->next;
        //把当前结点指向下一节点(要删除的结点)的下一节点，完成删除
        p->next = delNode->next;
        //销毁要删除的结点
        delete delNode;
        //完成删除
        return OK;
    }
    //没有删除
    return ERROR;
}
/**
 * 在单链表的头结点后插入一个元素
 * @param L 单链表
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert_h(LinkList &L, ElemType e){
    //创建一个新结点，并将数据域指向e
    LinkListNode *newNode = new LinkListNode;
    newNode->data = e;

    //将新结点的next指针域指向头结点的next
    newNode->next = L->next;
    //将头结点的next指针域指向新结点，完成插入
    L->next = newNode;
    return OK;

}
/**
 * 在单链表的最后一个结点插入元素
 * @param L 单链表
 * @param e 要插入的元素
 * @return
 */
Status LinkListInsert_r(LinkList &L, ElemType e){
    //将p指向单链表最后一个结点
    LinkListNode *p = L;
    for(; p->next; p = p->next);
    //创建一个新结点，并将数据域指向e，指针域设置为空
    LinkListNode *newNode = new LinkListNode;
    newNode->data = e;
    newNode->next = NULL;
    //最后一个结点的指针域指向新结点，完成插入
    p->next = newNode;
    return OK;
}
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