我家自动化

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

热门标签

C语言基础之单向链表_c语言单向链表

作者：我家自动化 | 2024-07-21 05:55:39

踩

c语言单向链表

一、链表的概述

1、单向链表的概述

单向链表是由一个个节点组成，节点没有名字，链表中的每个节点都包含一个存储空间，用于存储数据，以及一个指针，指向下一个节点的位置达到逻辑上连续。这些节点在内存中是分散存储的，而不是连续存储的。这种分散存储的方式使得链表具有了动态内存分配的能力，可以在运行时根据需要创建和删除节点。

在这里插入图片描述

2、链表和数组优缺点

**静态数组：**int arr[5]; 必须事先确定数组元素的个数，过多浪费，过小溢出，删除插入效率低（需要移动大量数据）

动态数组：不需要事先知道元素个数，在使用中动态申请，删除插入数据效率低（需要移动大量数据）

随机访问效率非常高。我们可以直接通过索引来访问数组中的任意一个元素，而不需要遍历整个数组。

**链表：**不需要事先知道数据个数，在使用中动态申请，插入删除不需要移动数据，在运行时我们只需要改变几个指针就可以在任何位置插入或删除一个元素。（缺点：遍历效率低）

3、单向链表的设计

（1）链表节点设计

#include <stdio.h>

//节点的设置
struct stu
{
    //数据域
    int num;
    char str[128];
    //指针域 连接到的节点
    struct stu *next;
};

int main(int argc, char const *argv[])
{
    //申请空间
    struct stu* data1 = (struct stu*)malloc(sizeof(struct stu));
    struct stu* data2 = (struct stu*)malloc(sizeof(struct stu));
    struct stu* data3 = (struct stu*)malloc(sizeof(struct stu));
    struct stu* data4 = (struct stu*)malloc(sizeof(struct stu));
    struct stu* data5 = (struct stu*)malloc(sizeof(struct stu));
    //初始化数据内容
    data1->num = 10;
    data2->num = 20;
    data3->num = 30;
    data4->num = 40;
    data5->num = 50;
    strcpy(data1->str,"xixi");
    strcpy(data2->str,"haha");
    strcpy(data3->str,"lala");
    strcpy(data4->str,"hehe");
    strcpy(data5->str,"dsds");
    data1->next = NULL;
    data2->next = NULL;
    data3->next = NULL;
    data4->next = NULL;
    data5->next = NULL;

    //定义链表头
    head = data1;//将data1的地址定义为表头
    //连接链表
    data1->next = data2;
    data2->next = data3;
    data3->next = data4;
    data4->next = data5;
    data5->next = NULL; 
    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

（2）链表的遍历

    void print_array(struct stu * head)
    {
        //链表的遍历
        struct stu *pb = head;
        while (pb != NULL)
        {
            printf("%d %s\n",pb->num,pb->str);
            pb = pb->next;
        }
    }
1
2
3
4
5
6
7
8
9
10

4、单向链表的使用

（1）节点的插入

①头部插入

struct stu* head_in(struct stu* head)//头部插入
{
    //为插入的数据申请空间
    struct stu* data = (struct stu*)malloc(sizeof(struct stu));
    //赋值
    data->num = 20;
    strcpy(data->str,"didi");
    data->next = NULL;
    struct stu* pb = head;
    data->next = head;//将原本的头地址赋到新数据的指针域
    head = data;//让新数据的地址作为头地址
    return head;//返回新的头地址
}
1
2
3
4
5
6
7
8
9
10
11
12
13

②尾部插入

//尾部插入
void tail_in(struct stu* head)
{
    struct stu* data = (struct stu*)malloc(sizeof(struct stu));
    data->num = 80;
    strcpy(data->str,"wei");
    data->next = NULL;
    struct stu* pb = head;
    while (pb->next != NULL)//判断指针域是否为空，为空说明是最后一个数据
    {
        pb = pb->next;
    }
    pb->next = data;//将新数据连接到尾端
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

③有序插入

//有序插入
struct stu* order_in(struct stu* head)
{
    //为插入的数据申请空间
    struct stu* data = (struct stu*)malloc(sizeof(struct stu));
    //赋值
    data->num = 45;
    strcpy(data->str, "youxu");
    data->next = NULL;
    struct stu* pb = head;
    struct stu* fp = head;
    struct stu* ff = head;

    if(data->num < pb->num)//小的在前
    {    
        data->next = head;
        head = data;
    }
    else if(data->num > pb->num)
    {

        while (pb->next != NULL && data->num > pb->num)
        {   
            fp = pb;
            pb = pb->next;
        }
        ff = data;
        ff->next = data->next;

        data = fp;
        data->next = ff;
        ff->next = pb;
    }
    return head;

}
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

（2）链表的节点查找

struct stu* node(struct stu* head, char *str)
{
    struct stu* pb = head;
    while (strcmp(pb->str, str) != 0 && pb->next != NULL)
    {
        pb = pb->next;
    }
    if(strcmp(pb->str, str) == 0)
    {
        return pb;
    }
    printf("NO\n");
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

（3）链表节点的删除

//节点删除
struct stu* delet_node(struct stu* head, char *str)
{
    struct stu* pb = head , *pf = head;
    while (strcmp(pb->str, str) != 0 && pb->next != NULL)
    {
        pf = pb;
        pb = pb->next;
    }
    if(strcmp(pb->str, str) == 0)
    {
        if(pb == head)//头节点
        {
            head = head->next;
        }
        else  //中节点
        {
            pf->next = pb->next;
        }
        free(pb);
        return head;
    }
    printf("NO\n");
    return NULL;
}
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

（4）链表的释放

//释放链表
void free_file(struct stu* head)
{
    struct stu* pb = head;
    while (pb != NULL)
    {
        head = pb->next;
        free(pb);
        pb = head;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12

（5）链表的翻转

//链表翻转
struct stu* serversal(struct stu* head)
{
    struct stu* pf = NULL;
    struct stu* pb = head->next;
    head->next = NULL;
    while (pb != NULL)
    {
        pf = pb->next;
        pb->next = head;
        head = pb;
        pb = pf;
    }
    return head;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

（6）链表的排序

//链表排序
void sort_file(struct stu* head)
{
    struct stu* p_i = head, *p_j = head; 
    while (p_i->next != NULL) 
    {
        struct stu* p_min = p_i; 
        p_j = p_min->next; 
        while (p_j != NULL) 
        {
            if (p_min->num > p_j->num) 
                p_min = p_j; 
            p_j = p_j->next; 
        }
        if (p_i != p_min) 
        {
            //交换数据
            struct stu tmp = *p_i;
            *p_i = *p_min;
            *p_min = tmp;

            tmp.next = p_i->next;
            p_i->next = p_min->next;
            p_min->next = tmp.next;
        }
        p_i = p_i->next; //i++
    }
}
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

5、单向链表案例

单向链表存储学生信息

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//节点的设置
struct stu
{
    //数据域
    int num;
    char str[128];
    //指针域
    struct stu *next;
};
struct stu * head = NULL;

void print_array(struct stu * head);//遍历
struct stu* delet_node(struct stu* head, char *str);//节点删除
struct stu* head_in(struct stu* head, int q,char * w);//头部插入
void free_file(struct stu* head);//释放链表
struct stu* node(struct stu* head, char *str);//节点查找
void sort_file(struct stu* head);//链表排序

void help(void)
{
    printf("*******************************\n");
    printf("*            Help             *\n");
    printf("*            Output           *\n");//输出
    printf("*            Input            *\n");//输入
    printf("*            Delete           *\n");//删除
    printf("*            Query            *\n");//查询
    printf("*            Sort             *\n");//排序
    printf("*            Free             *\n");//关闭
    printf("*******************************\n");
}
int main(int argc, char const *argv[])
{
    help();
    while (1)
    {
        char cmd[128] = "";
        printf("--->Please enter the commed:\n");
        scanf("%s",cmd);
        if(strcmp(cmd, "Help") == 0)
        {
            help();
        }
        else if (strcmp(cmd, "Output") == 0)
        { 
            print_array(head);
        }
        else if (strcmp(cmd, "Input") == 0)
        {
            int q = 0;
            char w[128] = "";
            printf("--->Please input information:\n");
            scanf("%d %s",&q ,w);
            head = head_in(head,q,w);
        }
        else if (strcmp(cmd, "Delete") == 0)//删除
        {
            char data[128] = "";
            printf("--->Please input link\n");
            scanf("%s",data);
            head = delet_node(head,data);
        }
        else if (strcmp(cmd, "Query") == 0)//查询
        {
            struct stu* pf = NULL;
            char data[128] = "";
            printf("--->Please input link\n");
            scanf("%s",data);
            pf = node(head,data);
            if(pf != NULL)
            {
                printf("%d %s\n",pf->num, pf->str);
            }
            
        }
        else if (strcmp(cmd, "Sort") == 0)//排序
        {
            sort_file(head);
        }
        else if (strcmp(cmd, "Free") == 0)//关闭
        {
            free_file(head);
            return 0;
        }
        
    }
    
    return 0;
}
//遍历
void print_array(struct stu * head)
{
    //判断链表是否存在
    if (head == NULL) //不存在
    {
        printf("link not exits\n");
        return;
    }
    //链表的遍历
    struct stu *pb = head;
    while (pb != NULL)
    {
        printf("%d %s\n",pb->num,pb->str);
        pb = pb->next;
    }
}
//节点删除
struct stu* delet_node(struct stu* head, char *str)
{
        if(head == NULL)
    {
        printf("link not exist\n");
        return NULL;
    }
    struct stu* pb = head , *pf = head;
    while (strcmp(pb->str, str) != 0 && pb->next != NULL)
    {
        pf = pb;
        pb = pb->next;
    }
    if(strcmp(pb->str, str) == 0)
    {
        if(pb == head)//头节点
        {
            head = head->next;
        }
        else  //中节点
        {
            pf->next = pb->next;
        }
        free(pb);
        return head;
    }
    printf("NO\n");
    return NULL;
}
//头部插入
struct stu* head_in(struct stu* head,int q, char *w)
{
    struct stu* data = (struct stu*)malloc(sizeof(struct stu));
    data->next = NULL;
    if(head == NULL)
    {
        data->num = q;
        strcpy(data->str,w);
        head = data;
        return head;
    }
    else
    {
        data->num = q;
        strcpy(data->str,w);
        data->next = NULL;
        struct stu* pb = head;
        data->next = head;
        head = data;
        return head;
    }
    
}
//释放链表
void free_file(struct stu* head)
{
    if(head == NULL)
    {
        printf("link not exist\n");
        return;
    }
    struct stu* pb = head;
    while (pb != NULL)
    {
        head = pb->next;
        free(pb);
        pb = head;
    }
    
}
//节点查找
struct stu* node(struct stu* head, char *str)
{
    if(head == NULL)
    {
        printf("link not exist\n");
        return NULL;
    }
    struct stu* pb = head;
    while (strcmp(pb->str, str) != 0 && pb->next != NULL)
    {
        pb = pb->next;
    }
    if(strcmp(pb->str, str) == 0)
    {
        return pb;
    }
    printf("NO\n");
    return NULL;
}
//链表排序
void sort_file(struct stu* head)
{
    if(head == NULL)
    {
        printf("link not exist\n");
        return;
    }
    struct stu* p_i = head, *p_j = head; 
    while (p_i->next != NULL) 
    {
        struct stu* p_min = p_i; 
        p_j = p_min->next; 
        while (p_j != NULL) 
        {
            if (p_min->num > p_j->num) 
                p_min = p_j; 
            p_j = p_j->next; 
        }
        if (p_i != p_min) 
        {
            //交换数据
            struct stu tmp = *p_i;
            *p_i = *p_min;
            *p_min = tmp;

            tmp.next = p_i->next;
            p_i->next = p_min->next;
            p_min->next = tmp.next;
        }
        p_i = p_i->next; //i++
    }
}

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

6、如有错误欢迎指正

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】

C语言基础之单向链表_c语言 单向链表