不正经

这个屌丝很懒，什么也没留下！

热门标签

C语言实现单链表的基本操作_c语言单链表的基本操作

作者：不正经 | 2024-05-28 08:26:27

踩

c语言单链表的基本操作

C语言实现单链表的基本操作

一：单链表

1：定义

链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的，每个结点只有一个链域的链表称为单链表（Single Linked List）。

2：特点

物理上不连续，逻辑上连续：可以将物理地址上不连续的内存空间连接起来，通过指针来对物理地址进行操作，实现逻辑上的连续（线性）。
头指针：单链表中每个结点的存储地址是存放在其前趋结点的next域中，而开始结点无前趋，故应设头指针head指向开始结点。链表由头指针唯一确定。
尾巴：终端结点无后继，故终端结点的指针域为空，即NULL。

二：单链表相关实现算法

L=(LinkList) malloc(sizeof (LinkList)); 在分配内存空间时，得注意malloc（）函数的使用

1：单链表结构体定义

typedef int Elemtype：指的是在当前程序中Elemtype就代表的int（整型）的数据类型，相当于给int类型起了一个别名。
其中LNode,*LinkList写在{}后面的目的是为了方便使用。

/*数据元素类型*/
typedef int ElemType;
/*单链表结构体定义*/
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
}LNode,*LinkList;
//LinkList L; 声明一个指向单链表第一个结点的指针,这种方法代码可读性更强
/*
等价于
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
};
 typedef struct Lnode Lnode;
 typedef struct Lnode * Linklist;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2：单链表的初始化

//初始化一个单链表--带头结点
LinkList InitList(LinkList L){
    //申请一块LinkList类型的空间给L
    L=(LinkList) malloc(sizeof (LinkList));   //f分配一个头结点
    if(L==NULL){
        return NULL;     //内存不足，分配失败
    }
    //将L的指针域设为空
    L->next=NULL;
    return L;
}
1
2
3
4
5
6
7
8
9
10
11

3：按照指定位序插入

按照位序插入在第i个位置插入，插入的元素的值为e
思想：

首先判断i的值是否合法
初始化好一个指向头结点的指针
定义一个整型变量用来存储当前指针所指向结点的位置
其次将定义的指针移动到i-1结点点处
然后判断移动i-1位置的结点是否为NULL
在不为NULL的情况下，开辟一个新的LinkList类型的空间，其数据域中存入e
最后，进行连接结点的操作。

//按照位序插入   在第i个位置插入，插入的元素的值为e
int ListInsert(LinkList L,int i,ElemType e){
    if(i<1){//位置不合法
        return 0;
    }
    LNode *p;        //指针p指向当前扫描到的结点
    int j=0;         //当前指针指向的第几个元素
    p=L;             //L指向头指针，这里把头结点假设为第0个结点（不存在数据）
    //移动到第i-1个结点出
    while (p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    p = NULL;
    if(p){//i值所对应的结点不合法
        return 0;
    }
    //创建一个新的结点，并对新结点进行连接操作
    LNode *s= (LNode *)malloc(sizeof (LNode));
     s->data=e;//将待插入的数据放到新创建的指针的data中
     s->next=p->next;//将s与p结点的后继结点相连接
     p->next=s;//将p与结点s相连接
    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
24

3：创建一个新结点

//创建一个新结点，并指定其数据域
LNode* CreatNode(int data){
    LNode *newNode=(LNode *) malloc(sizeof (LNode));
    if(newNode==NULL){
        printf("分配结点失败,请检查内存!");
        return NULL;
    }
    //将data传入新结点的数据域
    newNode->data=data;
    newNode->next=NULL;
    //返回新结点的指针
    return newNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4：指定结点的后插操作

后插操作：在p结点之后插入元素

思想：

首先对待插入的结点进行判断
然后利用malloc函数申请一个结点的内存空间
对该内存空间进行判断
将待插入的数据放到新建结点的数据域中
然后利用链表的连接操作即可

//指定结点的后插操作:在p结点后插入数据元素
int InsertNextNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    //然后进行取e值,连接结点的操作
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5：指定结点的前插操作

前插操作：在p结点之前插入元素

思想:
第一种：通过遍历单链表找到p的前驱结点q，然后在q结点后面插入一个新的元素。由于这种所耗费的时间复杂度为O(n)。

第二种：（偷天换日）–时间复杂度为O(1)

将新结点s连接的p之后
然后将p中的数据域中的值复制到新结点s
将p中的元素用待插入的元素进行覆盖

//指定结点的前插操作
int InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    s->next=p->next;//将新结点s连接的p之后
    p->next=s;
    s->data=p->data;//然后将p中的数据域中的值复制到新结点s
    p->data=e;      //将p中的元素用待插入的元素进行覆盖
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6：按位序删除

按位序删除 --i指的是第i个结点，e用来返回删除的结点的数据域的数值

思想:首先得遍历到第i-1个结点，对该节点进行判空以及对该节点的后继结点进行判空操作，然后修改指针的执行删除第i个结点。

//按位序删除  --i指的是第i个结点，e用来返回删除的结点的数据域的数值
int ListDelete(LinkList L,int i,ElemType e){
    if(i<1){
        return 0;
    }
    LNode *p;   //指向当前扫描到的结点
    int j=0;    //当前p指针所指的是第几个结点
    p=L;        //L指向投机诶单，头结点是第0个结点(不存在数据)
    while (p!=NULL&&j<i-1){ //循坏找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL){  //i值不合法
        return 0;
    }
    if(p->next==NULL) {//表示p结点后再无结点
        return 0;
    }
    LNode  *q=p->next;//令指针q指向待删除的结点
    e=q->data;      //用来记录删除结点的数据域中的值
    p->next=q->next; //将待删除的结点*q从当前链表中断开
    free(q);//释放结点所占用的内存空间
    return e;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

7：指定结点的删除

由于删除该结点得修改前驱结点的next指针
方法1：传入头指针，循环寻找p的前驱结点
方法2：偷天换日（类似与结点前插的实现）–利用数据域中的值进行更新。

思想:

将待删除指针后面的数据域给待删除元素
然后只需将待删除指针后面的结点删除即可

//指定结点的删除--偷天换日
int DeleteNodee(LNode *p){
    if(p==NULL){
        return 0;
    }
    //这里如果p是最后一个结点，只能从表头依次寻找p的前驱结点
    LNode *q=p->next;   //令q指向*p的后继结点
    p->data=q->data;    //和后继结点交换数据域
    p->next=q->next;    //将*q结点从链表中断开
    free(q);    //释放后继结点的存储空间
    return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12

8：按位查找

//按位查找，返回第i个元素(带头结点)
LNode  * GetElem(LinkList L,int  i){
    if(i<0){
        return NULL;
    }
    LNode *p;   //指向p指针当前扫描的结点
    int j=0;    //用来记录当前p指针指向的第几个结点
    p=L;        //L指向头结点，头结点是第0个结点
    while(p!=NULL&&j<i){//循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

9：按值查找

//按值查找
LNode * LocateElem(LinkList L,ElemType e){
    LNode  *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}
1
2
3
4
5
6
7
8

10：求单链表的长度

//求单链表的长度
int LengthList(LinkList L){
    int len=0;
    LNode  *p=L->next;
    while (p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}
1
2
3
4
5
6
7
8
9
10

11：创键单链表

a:头插法:可用于链表的逆置

思想：

数据是通过输入来获取
没插入一个结点先申请一个结点所需的内存空间
然后利用头指针和新结点连接起来

//头插法
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;
    L=(LinkList *) malloc(sizeof(LNode));   //创建头结点
    L->next=NULL;   //初始为空链表
    scanf("%d",&x); //输入结点的值
    while (x!=1000){  //当输入1000时结束
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); //输入结点的值
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

b:尾插法

思想：

用一个指针一直为表尾指针
利用表尾指针和新开辟的内存空间进行操作

//尾插法
LinkList List_TailInsert(LinkList L){
    int  x;
    L=(LinkList) malloc(sizeof (LNode));//建立头结点，初始化一空表
    LNode *s,*r=L;          //r为表尾指针
    scanf("%d",&x); //输入结点的值
    while (x!=1000){    //当输入1000代表结束
        //在r结点之后插入x元素
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;      
        r=s;            //r指向新的表的尾结点
        scanf("%d",&x); //输入结点的值
    }
    r->next=NULL;           //为几点指针置为空
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

三：完整代码

/**
 * 单链表的实现
 */
#include "stdio.h"
#include "stdlib.h"				//提供malloc()和free()
/*数据元素类型*/
typedef int ElemType;
/*单链表结构体定义*/
typedef struct LNode        //定义单链表结点类型
{
    ElemType data;          //每个结点存放一个数据元素
    struct LNode *next;     //指针指向下一节点
}LNode,*LinkList;



//初始化一个单链表--带头结点
LinkList InitList(){
    //申请一块LinkList类型的空间给L
    LinkList L=(LinkList) malloc(sizeof (LinkList));   //f分配一个头结点
    if(L==NULL){
        return NULL;     //内存不足，分配失败
    }
    //将L的指针域设为空
    L->next=NULL;
    return L;
}
//按照位序插入   在第i个位置插入，插入的元素的值为e
int ListInsert(LinkList L,int i,ElemType e){
    if(i<1){//位置不合法
        return 0;
    }
    LNode *p;        //指针p指向当前扫描到的结点
    int j=0;         //当前指针指向的第几个元素
    p=L;             //L指向头指针，这里把头结点假设为第0个结点（不存在数据）
    //移动到第i-1个结点出
    while (p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL){//i值所对应的结点不合法
        return 0;
    }
    //创建一个新的结点，并对新结点进行连接操作
    LNode *s= (LNode *)malloc(sizeof (LNode));
     s->data=e;//将待插入的数据放到新创建的指针的data中
     s->next=p->next;//将s与p结点的后继结点相连接
     p->next=s;//将p与结点s相连
    return 1;
}
//创建一个新结点，并指定其数据域
LNode* CreatNode(int data){
    LNode *newNode=(LNode *) malloc(sizeof (LNode));
    if(newNode==NULL){
        printf("分配结点失败,请检查内存!");
        return NULL;
    }
    //将data传入新结点的数据域
    newNode->data=data;
    newNode->next=NULL;
    //返回新结点的指针
    return newNode;
}
//指定结点的后插操作:在p结点后插入数据元素
int InsertNextNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    //然后进行取e值,连接结点的操作
    s->data=e;
    s->next=p->next;
    p->next=s;
    return 1;
}
//指定结点的前插操作
int InsertPriorNode(LNode *p,ElemType e){
    if(p==NULL){
        return 0;
    }
    LNode *s=(LNode *) malloc(sizeof (LNode));
    if(s==NULL){
        printf("内存分配失败！");
        return 0;
    }
    s->next=p->next;//将新结点s连接的p之后
    p->next=s;
    s->data=p->data;//然后将p中的数据域中的值复制到新结点s
    p->data=e;      //将p中的元素用待插入的元素进行覆盖
    return 1;
}
//按位序删除  --i指的是第i个结点，e用来返回删除的结点的数据域的数值
int ListDelete(LinkList L,int i,ElemType e){
    if(i<1){
        return 0;
    }
    LNode *p;   //指向当前扫描到的结点
    int j=0;    //当前p指针所指的是第几个结点
    p=L;        //L指向投机诶单，头结点是第0个结点(不存在数据)
    while (p!=NULL&&j<i-1){ //循坏找到第i-1个结点
        p=p->next;
        j++;
    }
    if(p==NULL){  //i值不合法
        return 0;
    }
    if(p->next==NULL) {//表示p结点后再无结点
        return 0;
    }
    LNode  *q=p->next;//令指针q指向待删除的结点
    e=q->data;      //用来记录删除结点的数据域中的值
    p->next=q->next; //将待删除的结点*q从当前链表中断开
    free(q);//释放结点所占用的内存空间
    return e;
}
//指定结点的删除--偷天换日
int DeleteNode(LNode *p){
    if(p==NULL){
        return 0;
    }
    //这里如果p是最后一个结点，只能从表头依次寻找p的前驱结点
    LNode *q=p->next;   //令q指向*p的后继结点
    p->data=q->data;    //和后继结点交换数据域
    p->next=q->next;    //将*q结点从链表中断开
    free(q);    //释放后继结点的存储空间
    return 1;
}
//按位查找，返回第i个元素(带头结点)
LNode  * GetElem(LinkList L,int  i){
    if(i<0){
        return NULL;
    }
    LNode *p;   //指向p指针当前扫描的结点
    int j=0;    //用来记录当前p指针指向的第几个结点
    p=L;        //L指向头结点，头结点是第0个结点
    while(p!=NULL&&j<i){//循环找到第i个结点
        p=p->next;
        j++;
    }
    return p;
}
//按值查找
LNode * LocateElem(LinkList L,ElemType e){
    LNode  *p=L->next;
    while (p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}
//求单链表的长度
int LengthList(LinkList L){
    int len=0;
    LNode  *p=L->next;
    while (p!=NULL){
        len++;
        p=p->next;
    }
    return len;
}
//头插法
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x;
    L=(LinkList *) malloc(sizeof(LNode));   //创建头结点
    L->next=NULL;   //初始为空链表
    scanf("%d",&x); //输入结点的值
    while (x!=1000){  //当输入1000时结束
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x); //输入结点的值
    }
    return L;
}
//尾插法
LinkList List_TailInsert(LinkList L){
    int  x;
    L=(LinkList) malloc(sizeof (LNode));//建立头结点，初始化一空表
    LNode *s,*r=L;          //r为表尾指针
    scanf("%d",&x); //输入结点的值
    while (x!=1000){    //当输入1000代表结束
        //在r结点之后插入x元素
        s=(LNode *) malloc(sizeof (LNode));
        s->data=x;
        r->next=s;
        r=s;            //r指向新的表的尾结点
        scanf("%d",&x); //输入结点的值
    }
    r->next=NULL;           //为几点指针置为空
    return L;
}
//判空操作
int  IsEmpty(LinkList L){
    if(L->next==NULL){
        return 1;
    }
    return 0;
}
//打印
void PrintList(LinkList L) {
    LNode *p;
    p=L->next;
    printf("单链表的数据为");
    while (p!=NULL){
        printf("%d   ",p->data);
        p=p->next;
    }
    printf("\n");

}
    int main(){
        //定义一个链表
        LinkList L = NULL;
        //[2]将链表初始化
        L = InitList();
//        L=List_TailInsert(L);      //利用尾插法创建单链表
        L=List_HeadInsert(L);        //利用头插法创建单链表--与输入的数值相逆
        PrintList(L);                //打印头插法创建的单链表
        if(IsEmpty(L)==1){           //对单链表进行判空
            printf("当前链表是空的！\n");
        } else{
            printf("当前链表不是空的！\n");
        }
        int len=LengthList(L);       //求链表的长度
        printf("当前单链表的长度为%d\n",len);

        LNode *s=LocateElem(L,2); //按照值查找
        printf("查找成功！值为%d\n",s->data);

       DeleteNode(s);           //删除s结点
        printf("删除成功!删除后的");
        PrintList(L);

        ListInsert(L,2,11);
        printf("新增成功!新增后");
        PrintList(L);
        return 0;

    }
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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/636549