服务器之家：专注于VPS、云服务器配置技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - ​​​​​​​C语言实现单链表基本操作方法

​​​​​​​C语言实现单链表基本操作方法

2022-12-02 15:26苏州程序大白 C/C++

这篇文章主要介绍了​​​​​​​C语言实现单链表基本操作方法，文章围绕主题展开详细介绍，具有一定的参考价值，需要的小伙伴可以参考一下

存储结构

?
1
2
3
4
5
typedef int dataType；//爱护据类型
typedef struct Node {
    DataType data;   // 结点数据
    struct Node *next; // 指向下一个结点的指针
} Node, *LinkList;

基本功能

  • 头插法创建单链表void CreateListHead( LinkList &head)
  • 尾插法创建单链表void CreateListTail( LinkList &head)
  • 获取指定位置的元素 int GetElement(LinkList head, int i, DataType &e)
  • 获取指定元素的位置 int LocateElement(LinkList head, int e)
  • 在指定位置插入元素 int InsertList(LinkList head, int i, DataType e)
  • 删除指定位置的元素 int DeleteList(LinkList head, int i, DataType &e)
  • 获取单链表的长度 int LengthLinkList(LinkList head)
  • 合并两个非递减的单链表 void MergeList(LinkList La, LinkList Lb, LinkList &Lc)
  • 寂链表void Destroy( LinkList &L)
  • 遍历打印单链表中的所有元素 void PrintList(LinkList head)

头插法创建单链表

每次添加链的结点都能找到头结点的第1号位置，所以创建单表中的元素的顺序是输入元素的逆序。 ​

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 头插法创建单链表，输入以-1结束
 */
void CreateListHead(LinkList &head) {
    DataType x;
    LinkList p;
 
    head = (LinkList)malloc(LEN);
    head->next = NULL;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        p->next = head->next; // 新增的结点指向头结点的下一个结点
        head->next = p;  // 头结点指向新增的结点
        scanf("%d", &x);
    }
}

尾插法创建单链表

每次新增的结点都放在单链表的后面，接下来和接下来的顺序保持一致。 ​

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 尾插法创建单链表，输入以-1结束
 */
void CreateListTail(LinkList &head) {
    LinkList p, q;
    DataType x;
 
    head = (LinkList)malloc(LEN);
    q = head;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}

获取指定位置的元素

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 获取指定位置的元素
 * @param head 指向单链表头结点的指针（头指针）
 * @param i 位置
 * @param e 用来存放对应位置的元素值
 * @return 0：获取失败；1：获取成功
 */
int GetElement(LinkList head, int i, DataType &e) {
    LinkList p = head->next;
    int j = 1;
 
    while (p && j < i) { // 依次后移，直至为空或到达位置
        p = p->next;
        j++;
    }
    if (!p || j > i) { // p为空表示位置超过最大位置，j > i表示位置不合法(i < 1)
        return 0;
    }
    e = p->data;
    return 1;
}

在指定位置插入元素

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 在单链表插入元素到位置i
 * @param head 单链表的头指针
 * @param i 插入位置
 * @param e 插入元素
 * @return 1：插入成功，0：插入失败
 */
int InsertList(LinkList head, int i, DataType e) {
    LinkList p = head; // 从头结点开始
    int j = 1;
    while (p && j < i) { // 找到插入位置的前一个结点
        p = p->next;
        j++;
    }
    if (!p || j > i) { // p为空或i < 1，插入位置不合法
        return 0;
    }
    LinkList q = (LinkList)malloc(LEN); // 创建新结点
    q->data = e;
    q->next = p->next; // 将新结点指向前一个结点的后一个结点
    p->next = q; // 前一个结点指向新结点
    // 执行上述两个操作后，达到的效果是新结点插入到了前一个结点的后面
}

删除指定位置的元素

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 删除指定位置的元素
 * @param head
 * @param i 位置
 * @param e 被删除的元素的值存放在e中
 * @return 1：删除成功，0：删除失败
 */
int DeleteList(LinkList head, int i, DataType &e) {
    LinkList p = head;
    int j = 1;
 
    while (p && j < i) {  // 找到位置的前一个结点
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList s = p->next;
    e = s->data;
    p->next = s->next; // 改变前一个结点的指向，使其指向删除结点的后一个结点
    free(s);
    return 1;
}

获取单链表的长度

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * 获取单链表的长度
 * @param head
 * @return 单链表的长度
 */
int LengthLinkList(LinkList head) {
    LinkList p = head->next;
    int count = 0;
 
    while (p) {
        count++;
        p = p->next;
    }
    return count;
}

合并两个非递减的单链表

合并两个非递减的单链，新链表仍然保持非递减。 ​

?
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
/**
 * 合并两个非递减的单链表，新的链表仍然非递减
 * @param La
 * @param Lb
 * @param Lc
 */
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
    LinkList pa, pb, pc;
    pa = La->next;
    pb = Lb->next;
    pc = Lc = (LinkList)malloc(LEN);
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}

晴链表

?
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 销毁链表
 */
void Destroy(LinkList &L) {
    LinkList p, q;
    p = L;
    while (p) { // 遍历所有结点，释放内存
        q = p;
        p = p->next;
        free(q);
    }
    L = NULL; // L置为NULL
}

遍历打印单链表

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 遍历打印单链表的所有元素
 */
void PrintList(LinkList head) {
    LinkList p = head->next;
 
    if (p == NULL) {
        cout << "List is NULL!" <<endl;
    } else {
        while (p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

附上完整代码

?
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
#include<cstdlib>
using namespace std;
#define LEN sizeof(Node)
typedef int DataType;
typedef struct Node {
    DataType data;
    struct Node *next;
} Node, *LinkList;
 
/**
 * 头插法创建单链表
 * @param head
 */
void CreateListHead(LinkList &head) {
    DataType x;
    LinkList p;
 
    head = (LinkList)malloc(LEN);
    head->next = NULL;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        p->next = head->next;
        head->next = p;
        scanf("%d", &x);
    }
}
 
/**
 * 尾插法创建单链表
 * @param head
 */
void CreateListTail(LinkList &head) {
    LinkList p, q;
    DataType x;
 
    head = (LinkList)malloc(LEN);
    q = head;
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList)malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}
 
/**
 * 获取指定位置的元素
 * @param head 单链表头指针
 * @param i 位置
 * @param e 获取的元素赋值该参数
 * @return 0：获取失败；1：获取成功
 */
int GetElement(LinkList head, int i, DataType &e) {
    LinkList p = head->next;
    int j = 1;
 
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    e = p->data;
    return 1;
}
 
/**
 * 获取某个元素的位置
 * @param head
 * @param e
 * @return 元素的位置
 */
int LocateElement(LinkList head, int e) {
    LinkList p = head->next;
    int j = 1;
 
    while (p && p->data != e) {
        p = p->next;
        j++;
    }
    if (!p) {
        return 0;
    }
    return j;
}
 
/**
 * 在单链表插入元素到位置i
 * @param head 单链表的头指针
 * @param i 插入位置
 * @param e 插入元素
 * @return 1：插入成功，0：插入失败
 */
int InsertList(LinkList head, int i, DataType e) {
    LinkList p = head;
    int j = 1;
 
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList q = (LinkList)malloc(LEN);
    q->data = e;
    q->next = p->next;
    p->next = q;
}
 
/**
 * 删除指定位置的元素
 * @param head
 * @param i 位置
 * @param e 被删除的元素的值存放在e中
 * @return 1：删除成功，0：删除失败
 */
int DeleteList(LinkList head, int i, DataType &e) {
    LinkList p = head;
    int j = 1;
 
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) {
        return 0;
    }
    LinkList s = p->next;
    e = s->data;
    p->next = s->next;
    free(s);
    return 1;
}
 
/**
 * 获取单链表的长度
 * @param head
 * @return
 */
int LengthLinkList(LinkList head) {
    LinkList p = head->next;
    int count = 0;
 
    while (p) {
        count++;
        p = p->next;
    }
    return count;
}
 
/**
 * 合并两个非递减的单链表，新的链表仍然非递减
 * @param La
 * @param Lb
 * @param Lc
 */
void MergeList(LinkList La, LinkList Lb, LinkList &Lc) {
    LinkList pa, pb, pc;
 
    pa = La->next;
    pb = Lb->next;
    pc = Lc = (LinkList)malloc(LEN);
 
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}
 
/**
 * 销毁链表
 * @param L
 */
void Destroy(LinkList &L) {
    LinkList p, q;
    p = L;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    L = NULL;
}
 
/**
 * 遍历打印单链表的所有元素
 * @param head
 */
void PrintList(LinkList head) {
    LinkList p = head->next;
 
    if (p == NULL) {
        cout << "List is NULL!" <<endl;
    } else {
        while (p != NULL) {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}
int main() {
    LinkList L;
    printf("头插法创建单链表：（输入以-1结束）\n");
    CreateListHead(L);
    PrintList(L);
    printf("尾插法创建单链表：（输入以-1结束）\n");
    CreateListTail(L);
    PrintList(L);
    InsertList(L, 1, 100);
    printf("在1号位置插入100后，单链表如下：\n");
    PrintList(L);
    DataType e;
    DeleteList(L, 1, e);
    printf("删除1号位置的元素，被删除的元素为：\n");
    printf("删除后的单链表为：\n");
    PrintList(L);
    printf("单链表的长度为：%d\n", LengthLinkList(L));
    GetElement(L, 1, e);
    printf("1号位置的元素为：%d\n");
    printf("元素4在单链表中的位置为：%d\n", LocateElement(L, 4));
    cout << endl;
    LinkList La, Lb, Lc;
    printf("尾插法创建单链表La：\n");
    CreateListTail(La);
    PrintList(La);
    printf("尾插法创建单链表Lb：\n");
    CreateListTail(Lb);
    PrintList(Lb);
    MergeList(La, Lb, Lc);
    printf("合并单链表La和Lb后的新单链表Lc如下：\n");
    PrintList(Lc);
    return 0;
}

运行结果： 

​​​​​​​C语言实现单链表基本操作方法

 注意：

写法采用了C++引用参数的写法，LinkList &head，C语言下不支持这种写法，需要在C++环境下使用，即.cpp文件。

下面附上C语言的：

?
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
/**
 * LinkList 本身已经是结构体指针，参数再使用LinkList *的形式
 * 可以理解为要想改变一个结构体指针，则需要取指针的指针。
 * 类似于改变int a，则需要使用 int *a，这里要改变LinkList head，则需要使用LinkList *head
 */
void CreatListTail(LinkList *head) {
    int x;
    LinkList *p, *q;
 
    *head = (LinkList *) malloc(LEN);
    q = *head;
 
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList *) malloc(LEN);
        p->data = x;
        q->next = p;
        q = p;
        scanf("%d", &x);
    }
    q->next = NULL;
}
// 可以不传参，函数里面定义头指针，创建链表，然后把头指针返回，主函数用结构体指针接收即可
LinkList CreateListhead() {
    int x;
    LinkList *head, *p;
 
    head = (LinkList *) malloc(LEN);
    head->next = NULL;
 
    scanf("%d", &x);
    while (x != -1) {
        p = (LinkList *) malloc(LEN);
        p->data = x;
        p->next = head->next;
        head->next = p;
    }
    return head;
}

到此这篇关于C语言实现单链表基本操作方法的文章就介绍到这了,更多相关C语言单链表内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://juejin.cn/post/7091839297757642788

  • 单链表
  • ​​​​​​​C语言

    • 延伸 · 阅读

    精彩推荐
    • C/C++C++归并排序算法实例

      C++归并排序算法实例

      这篇文章主要介绍了C++归并排序算法实例,本文先是介绍了什么是归并排序,然后给出了实现代码,需要的朋友可以参考下...

      果冻想11432021-02-05
    • C/C++OpenCV实现人脸检测

      OpenCV实现人脸检测

      这篇文章主要为大家详细介绍了OpenCV实现人脸检测的相关资料，具有一定的参考价值，感兴趣的小伙伴们可以参考一下...

      林多10512021-06-15
    • C/C++C/C++ 避免数组越界的方法

      C/C++ 避免数组越界的方法

      这篇文章主要介绍了C/C++ 避免数组越界的方法，文中讲解非常细致，代码帮助大家更好的理解和学习，感兴趣的朋友可以了解下...

      慢慢爬的绿毛龟10192021-09-10
    • C/C++C语言找出数组中的特定元素的算法解析

      C语言找出数组中的特定元素的算法解析

      这篇文章主要介绍了C语言中找出数组中特定元素的算法解析,包括找出数组中两个只出现一次的数字的方法,需要的朋友可以参考下...

      wuzhekai19855802021-03-28
    • C/C++c++ 虚函数与纯虚函数的区别(深入分析)

      c++ 虚函数与纯虚函数的区别(深入分析)

      本篇文章是对c++中虚函数与纯虚函数的区别进行了详细的分析介绍，需要的朋友参考下...

      C++教程网4822020-12-11
    • C/C++C++实例输入多行数字到数组

      C++实例输入多行数字到数组

      这篇文章主要介绍了C++实例输入多行数字到数组的相关资料,这里提供实例代码帮助大家学习理解，需要的朋友可以参考下...

      marcusxu3952021-04-21
    • C/C++C语言简明讲解操作符++和--的使用方法

      C语言简明讲解操作符++和--的使用方法

      ++和--运算符分别是+=1和-=1的简写。设计这样两个运算符的本意是⽅便程序员，但i++和++i使⽤不恰当有时候会造成混淆，反倒令刚入门的C程序员有点混乱...

      清风自在 流水潺潺10652022-11-11
    • C/C++C语言 模拟实现strcpy与strcat函数详解

      C语言 模拟实现strcpy与strcat函数详解

      这篇文章主要介绍了怎样用C语言模拟实现strcpy与strcat函数，strcpy()函数是C语言中的一个复制字符串的库函数，strcat()函数的功能是实现字符串的拼接...

      不一样的烟火a8692022-11-04
    最近更新
    编辑推荐
    阅读排行
    热门标签
    1015 　 小提琴图 　 地址参数 　 多继承法 　 ZOJ 　 Fishing 　 同名 　 libfreetype 　 Simulink 　 数据滚动 　 右值引用 　 NSString 　 消息传递 　 平滑处理 　 Visual C++ 　 栈区 　 堆区 　 C语言程序设计 　 内存错误 　 对象模型 　 颜色加亮 　 程序内部 　 strcat 　 WinExec 　 打开程序 　 错误调试 　 C++教程 　 tinyxml 　 XML解析器 　 静态存储区 　
    © 2019-2022 服务器之家(www.tuohang.net) 版权所有关于我们联系我们版权申明网站地图