单链表的基本操作及C语言代码实现-数据结构与算法教程

内容摘要
遍历单链表（打印，修改）便利的概念想必大家都不会陌生，即就是从链表的头开始，逐步向后进行每一个元素的访问，这就是遍历，对于遍历操作，我们可以衍生出很多常用的数据操
文章正文

1.   遍历单链表（打印，修改）

便利的概念想必大家都不会陌生，即就是从链表的头开始，逐步向后进行每一个元素的访问，这就是遍历，对于遍历操作，我们可以衍生出很多常用的数据操作，比如说查询元素，修改元素，获取元素个数，打印整个链表数据等等。

进行遍历的思路极其简单，只需要建立一个指向链表L的结点，然后沿着链表L逐个向后搜索即可。

对于遍历操作，以下是代码实现：

1
2
3
4
5
6
7
8
9
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
}

对于元素修改操作，以下是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}

简单的遍历设计的函数只需要void无参即可，而当我们需要进行元素修等涉及到元素操作时，我们可以设计一个LinkedList类型的函数，使其返回一个修改后的新链表。

以上的操作均用到了遍历的思维，针对于遍历还有非常多的用法供自主设计，请参考后文配套的习题进行练习。

2.   插入操作

链表的增加结点操作主要分为查找到第i个位置，将该位置的next指针修改为指向我们新插入的结点，而新插入的结点next指针指向我们i+1个位置的结点。其操作方式可以设置一个前驱结点，利用循环找到第i个位置，再进行插入。

如图，在DATA1和DATA2数据结点之中插入一个NEW_DATA数据结点：

从原来的链表状态

数据结构16

 

到新的链表状态：

数据结构17

 

以下是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//单链表的插入，在链表的第i个位置插入x的元素
  
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
  
    return L;
}

3.  删除操作

删除元素要建立一个前驱结点和一个当前结点，当找到了我们需要删除的数据时，直接使用前驱结点跳过要删除的结点指向要删除结点的后一个结点，再将原有的结点通过free函数释放掉。

参考如图

数据结构18

 

以下是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//单链表的删除，在链表中删除值为x的元素
  
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}

 

4.  附：完整实现代码

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
#include <stdio.h>
#include <stdlib.h>
 
//定义结点类型
typedef struct Node {
    int data;           //数据类型，你可以把int型的data换成任意数据类型，包括结构体struct等复合类型
    struct Node *next;          //单链表的指针域
} Node,*LinkedList;
 
//单链表的初始化
LinkedList LinkedListInit() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请结点空间
    if(L==NULL){    //判断申请空间是否失败
        exit(0);    //如果失败则退出程序
    }
    L->next = NULL;          //将next设置为NULL,初始长度为0的单链表
    return L;
}
 
 
//单链表的建立1，头插法建立单链表
LinkedList LinkedListCreatH() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                      //初始化一个空链表
 
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        p->next = L->next;                    //将结点插入到表头L-->|2|-->|1|-->NULL
        L->next = p;
    }
    return L;
}
 
 
//单链表的建立2，尾插法建立单链表
 
LinkedList LinkedListCreatT() {
    Node *L;
    L = (Node *)malloc(sizeof(Node));   //申请头结点空间
    L->next = NULL;                  //初始化一个空链表
    Node *r;
    r = L;                          //r始终指向终端结点，开始时指向头结点
    int x;                         //x为链表数据域中的数据
    while(scanf("%d",&x) != EOF) {
        Node *p;
        p = (Node *)malloc(sizeof(Node));   //申请新的结点
        p->data = x;                     //结点数据域赋值
        r->next = p;                 //将结点插入到表头L-->|1|-->|2|-->NULL
        r = p;
    }
    r->next = NULL;
 
    return L;
}
 
 
//单链表的插入，在链表的第i个位置插入x的元素
 
LinkedList LinkedListInsert(LinkedList L,int i,int x) {
    Node *pre;                      //pre为前驱结点
    pre = L;
    int tempi = 0;
    for (tempi = 1; tempi < i; tempi++) {
        pre = pre->next;                 //查找第i个位置的前驱结点
    }
    Node *p;                                //插入的结点为p
    p = (Node *)malloc(sizeof(Node));
    p->data = x;
    p->next = pre->next;
    pre->next = p;
 
    return L;
}
 
 
//单链表的删除，在链表中删除值为x的元素
 
LinkedList LinkedListDelete(LinkedList L,int x) {
    Node *p,*pre;                   //pre为前驱结点，p为查找的结点。
    p = L->next;
     
    while(p->data != x) {              //查找值为x的元素
        pre = p;
        p = p->next;
    }
    pre->next = p->next;          //删除操作，将其前驱next指向其后继。
    free(p);
     
    return L;
}
 
//链表内容的修改，再链表中修改值为x的元素变为为k。
LinkedList LinkedListReplace(LinkedList L,int x,int k) {
    Node *p=L->next;
    int i=0;
    while(p){
        if(p->data==x){
            p->data=k;
        }
        p=p->next;
    }
    return L;
}
 
 
//便利输出单链表
void printList(LinkedList L){
    Node *p=L->next;
    int i=0;
    while(p){
        printf("第%d个元素的值为:%d\n",++i,p->data);
        p=p->next;
    }
} 
 
int main() {
    //创建 
    LinkedList list;
    printf("请输入单链表的数据：以EOF结尾\n");
    list = LinkedListCreatT();
    //list=LinkedListCreatT();
    printList(list);
     
    //插入 
    int i;
    int x;
    printf("请输入插入数据的位置：");
    scanf("%d",&i);
    printf("请输入插入数据的值：");
    scanf("%d",&x);
    LinkedListInsert(list,i,x);
    printList(list);
     
    //修改
    printf("请输入修改的数据：");
    scanf("%d",&i);
    printf("请输入修改后的值：");
    scanf("%d",&x);
    LinkedListReplace(list,i,x);
    printList(list);
     
    //删除 
    printf("请输入要删除的元素的值：");
    scanf("%d",&x);
    LinkedListDelete(list,x);
    printList(list);
 
    return 0;
}

 
代码注释
[!--zhushi--]
上一篇单链表的基本设计（C语言代码实现）-数据结构与算法教程下一篇双向链表的基本设计（C语言代码实现）-数据结构与算法教程

作者：喵哥笔记

IDC笔记

学的不仅是技术，更是梦想！