C语言自学系列四_链表与动态链表

字数统计: 1.7k   |   阅读时长≈ 7 分钟

#链表

什么是链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

存储结构

链表中会有个指向下一节点的指针next

链表示例图

定义使用一个链表

首先这里创建一个小姐姐的结构体，包含姓名开始营业时间和结束营业时间。

1
2
3
4
5
6
7
8

typedef struct chick{
    char *name;
    char *opens;
    char *closes;
    struct chick *next;
} chick;

那么我们来定义几个小姐姐吧

1
2
3
4
5
6
7
chick xiaohong = {"小红红","23:00","01:00",NULL};
chick xiaohuang = {"小晃晃","23:00","01:00",NULL};
chick xiaolan = {"小蓝蓝","23:00","01:00",NULL};

xiaohong.next  = &xiaohuang;//设置下一个节点
xiaohuang.next = &xiaolan;

展示出有过深度交流的小姐姐姓名

1
2
3
4
5
6
7

chick *i = start;//递归这个链表

for (;i!= NULL;i=i->next) {
    printf("%s\n",i->name);
}

来一串完整版的输出打印

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 定义一个小姐姐的结构体
 */
typedef struct chick{
    char *name;
    char *opens;
    char *closes;
    struct chick *next;
} chick;

/**
 * 递归打印一个链表
 * @param start
 */
void display(chick *start)
{
    chick *i = start;//

    for (;i!= NULL;i=i->next) {
        printf("%s\n",i->name);
    }

}


int main()
{
    chick xiaohong = {"小红红","23:00","01:00",NULL};
    chick xiaohuang = {"小晃晃","23:00","01:00",NULL};
    chick xiaolan = {"小蓝蓝","23:00","01:00",NULL};

    xiaohong.next  = &xiaohuang;//设置下一个节点
    xiaohuang.next = &xiaolan;

    display(&xiaohong);

    return 0;
}

结果

输出结果1

可以看到我们通过结构体声明了3个小姐姐的变量，并且用指针把她们关联了起来，然后用一个流程控制语句for打印出了这个链表里的信息

动态链表

在一些批量化的赋值中，并且想把数据存放到堆上，这样我们可以考虑下使用动态链表的形式。

创建一个小姐姐生成器,在这个生成器里面我们用malloc动态的分配了一个放chick变量的堆空间

1
2
3
4
5
chick *i = malloc(sizeof(chick));
i->name = name;
i->opens =  "23:00";
i->closes = "01:00";
i->next = 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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 定义一个小姐姐的结构体
 */
typedef struct chick{
    char *name;
    char *opens;
    char *closes;
    struct chick *next;
} chick;

/**
 * 递归打印一个链表
 * @param start
 */
void display(chick *start)
{
    chick *i = start;//

    for (;i!= NULL;i=i->next) {
        printf("%s\n",i->name);
    }

}

chick* create(char *name)//返回一个chick类型指针
{

    chick *i = malloc(sizeof(chick));
    i->name = name;
    i->opens =  "23:00";
    i->closes = "01:00";
    i->next = NULL;
    return i;
}

int main()
{
    chick *xiaohong = create("小红红");//声明结构体指针
    chick *xiaohuang = create("小晃晃");
    chick *xiaolan = create("小蓝蓝");

    xiaohong->next  = xiaohuang;//设置下一个节点，这和前面略微不一样。放指针地址
    xiaohuang->next = xiaolan;

    display(xiaohong);

    return 0;
}

用户手动输入创建链表结构

上面那个列子是人肉手工定义的链表的逻辑关系，我们可以让程序智能点，让用户自己输入小姐姐名单，并用链表的方式保存下来。这里strdup是一个新的知识点， 将串拷贝到新建的位置处用了记得free掉

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 定义一个小姐姐的结构体
 */
typedef struct chick{
    char *name;
    char *opens;
    char *closes;
    struct chick *next;
} chick;

/**
 * 递归打印一个链表
 * @param start
 */
void display(chick *start)
{
    chick *i = start;//

    for (;i!= NULL;i=i->next) {
        printf("%s\n",i->name);
    }

}

chick* create(char *name)//返回一个chick类型指针
{

    chick *i = malloc(sizeof(chick));
    i->name = strdup(name);
    i->opens =  "23:00";
    i->closes = "01:00";
    i->next = NULL;
    return i;
}

int main()
{
    chick *i = NULL;//链表当前位置 注：这里定义的变量全是反自定义结构体的所以要chick声明
    chick *next = NULL;//下一个节点
    chick *start = NULL;//链表头

    char name[80];

    for (; fgets(name,80,stdin) != NULL; i = next) {//i保留上一个节点

        next = create(name);//创建下一链

        if(start == NULL){//找到链表头位置
            start = next;
        }

        if(i != NULL){
            i->next = next;//下一个节点赋值
        }

    }
    display(start);

    return 0;
}

运行结果

ctrl+d中断输入，可以看见正常输出，大吉大利~

运行结果

释放储存器

和打印方法一样，递归这个链表结构。需要注意的是必须先释放掉之前我们strdup声明的堆空间，否则后面就会再也无法释放掉它了。

1
2
3
4
5
6
7
8
9
10
11
12
void clear(chick *start)
{
    chick *i = NULL;

    i = start;
    for (; i != NULL ; i = i->next) {

        free(i->name);//用strdup新开堆空间，需要先释放掉否则就再也释放不了了
        free(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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 定义一个小姐姐的结构体
 */
typedef struct chick{
    char *name;
    char *opens;
    char *closes;
    struct chick *next;
} chick;

/**
 * 递归打印一个链表
 * @param start
 */
void display(chick *start)
{
    chick *i = start;//

    for (;i!= NULL;i=i->next) {
        printf("%s\n",i->name);
    }

}

chick* create(char *name)//返回一个chick类型指针
{

    chick *i = malloc(sizeof(chick));
    i->name = strdup(name);
    i->opens =  "23:00";
    i->closes = "01:00";
    i->next = NULL;
    return i;
}

/**
 * 释放堆空间
 * @param start
 */
void clear(chick *start)
{
    chick *i = NULL;

    i = start;
    for (; i != NULL ; i = i->next) {

        free(i->name);//用strdup新开堆空间，需要先释放掉否则就再也释放不了了
        free(i);

    }
}

int main()
{
    chick *i = NULL;//链表当前位置 注：这里定义的变量全是反自定义结构体的所以要chick声明
    chick *next = NULL;//下一个节点
    chick *start = NULL;//链表头

    char name[80];

    for (; fgets(name,80,stdin) != NULL; i = next) {//i保留上一个节点

        next = create(name);//创建下一链

        if(start == NULL){//找到链表头位置
            start = next;
        }

        if(i != NULL){
            i->next = next;//下一个节点赋值
        }

    }
    display(start);
    clear(start);
    return 0;
}
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

请我喝杯咖啡吧~