再探C语言链表—TypeDef Struct模式声明链表节点

青旅半醒 2022-08-28 06:53 115阅读 0赞

# 0. 序 #

之前看到的网上的书上的都是Struct直接创建节点。

我记得typedef struct是大学时候数据结构课本上用来声明链表结点的方法，这个方法让人容易操作链表。后来书本扔了，再买了盗版书不知道是版本问题还是什么问题，包括网上大多数博客都是直接struct声明。struct直接声明对后面链表的增删改查都稍微增加了难度。

今天在查资料时候突然看到这个写法，操作了一遍发现很容易实现链表的一些基本操作，因此完善一下贴上来

# 1. 代码 #

代码比较简单，重要的地方注释了

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    
    typedef struct List
    {
        int val;
        struct List *next;
    } link;
    
    /*------------------------------初始化节点--------------------------------*/
    link *InitNode()
    {
        printf("开始初始化结点\n");
        link *head = (link *)malloc(sizeof(link)); //初始化头结点
        head->next = NULL;                         //初始化时候头结点的下一个结点一定要指向空，否则会指向随机地址
        printf("初始化结点已完成\n");
        return head;
    }
    
    /*------------------------------遍历节点--------------------------------*/
    void PrintNode(link *head)
    {
        while (head->next != NULL)
        {
            head = head->next; //因为有头结点，但是头结点没有存数据，所以从头结点的下一个结点开始遍历
            printf("%d\n", head->val);
        }
    }
    
    /*------------------------------尾插法添加节点--------------------------------*/
    void AppendNodeR(link *head, int t)
    {
        link *a = (link *)malloc(sizeof(link));
        a->val = t;
        a->next = NULL;
        printf("开始尾插法添加结点 %d\n", t);
        while (head->next != NULL)
        {
            head = head->next;
        }
        head->next = a;
        printf("尾插法添加结点已完成\n");
    }
    
    /*------------------------------头插法添加节点--------------------------------*/
    void AppendNodeL(link *head, int t)
    {
        link *a = (link *)malloc(sizeof(link));
        a->val = t;
        a->next = NULL;
        printf("开始头插法添加结点 %d\n", t);
        a->next = head->next;
        head->next = a;
        printf("头插法添加结点已完成\n");
    }
    
    /*------------------------------删除节点--------------------------------*/
    void DeleteNode(link *head, int t)
    {
        link *temp = (link *)malloc(sizeof(link)); //初始化头结点
        link *d = head;
        printf("开始删除目标结点: %d\n", t);
        while (d->next != NULL)
        {
            temp = d;
            d = d->next; //因为有头结点，但是头结点没有存数据，所以从头结点的下一个结点开始遍历
            if (d->val == t)
            {
                temp->next = d->next; //d在这里已经后移一位
                printf("已删除结点： %d\n", d->val);
            }
        }
    }
    
    int main()
    {
        link *head = InitNode(); //因为这个头结点在后面都用上了，所以需要返回一个头结点
    
        AppendNodeR(head, 0); //因为我们是以指针也就是地址的方式传过去，所以不需要重新返回链表
        AppendNodeR(head, 1);
        AppendNodeR(head, 2);
        AppendNodeR(head, 3);
        AppendNodeR(head, 4);
        AppendNodeR(head, 5);
        AppendNodeR(head, 6);
        AppendNodeR(head, 7);
        AppendNodeR(head, 8);
        AppendNodeR(head, 9);
        AppendNodeR(head, 10);
        PrintNode(head);
    
        DeleteNode(head, 3);
        PrintNode(head);
    
        AppendNodeL(head, 20);
        AppendNodeL(head, 21);
        AppendNodeL(head, 22);
        PrintNode(head);
    
        system("pause"); //shell暂停函数，不加的话黑框一闪而过。调用system需要加stdlib头文件
    }

结果

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16][]

# 2. 头插法示意图 #

因为头插法稍微拐了个弯，我之前也没搞明白，画个图就明白了

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

链表的头节点是指向下一个节点，因此在插入新节点时候，首先是把待插入节点指向头结点的下一个节点，然后再把头结点地址指向待插入节点。

如下，a是待插入节点，head是head的下一个节点。

a->next = head->next;
        head->next = a;

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

# 3. 关于我代码里面的很多head #

可能我这里很多都是head，但是这个是传入的head的地址，因此虽然看着他们重新声明了好多次，但是在main函数里面传入的是同一个head，因此这里的head实际上地址都是一样的。

后面我再讲一下遍历里面的head可能会更清楚点

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

# 4. 关于遍历函数里面的head #

我这里算是故意写了head，如果你能把这个head弄懂，就说明真的弄懂链表了

我们这里的head=head.next就是移动指针。

又因为这里的head实际上是一个新的局部地址(指针)变量，所以我们改变这里的值，对main函数里面的head是没有影响的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

# 5. 关于链表的地址 #

实际上我们在用malloc申请内存时候，就已经在内存里面开辟了一块地址。

是保存在堆里面还是在栈里面，我们下次再讨论。

如图我们看到三个地址，这就是head、p、t所在的位置。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 5][]

当我们把next给指向（赋值，让next等于指向的节点的地址）所在节点的地址后，地址就变成指向节点的地址，新手往往在指向地址的时候懵了，不知道是谁指谁。

这里明确说明，是next=想要指向的节点的地址。

如下图就是让next指向下一个节点的示意图

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

如下图就是在指向节点之后各个地址值

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

# 6. 关于next指向NULL #

这张图里面我们可以看到，在我们使用malloc创建了一个结构体指针变量之后，他的值是一个明确的地址。而我们的结构体里面的结构体指针因为没有使用malloc，所以他指向的是一个随机值，如下图在指向地址之前是一个相同的值，他们都指向了同一个地方。

因此在初始化和添加节点的时候next指向NULL是非常重要的，如果没有指到NULL，我们在遍历的时候就找不到尾结点在什么地方。对了，这里说明一下，我们判断尾结点的方式就是判断当前结点的next是不是指向NULL，如果指向NULL就说明他是尾结点。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

因此一定要注意新建的节点的next一定要指向NULL

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/73b9d1d1646048f08366c88fee8c49c1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/9b82b2a34ff84f92862a7b0929809761.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/eca2f61307ca40a4ab88f4705a72567f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/97fb54891f7a4ae0a33dc43cd90a7ea7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/91744d6175ed4345be80a757c5bffddb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/19159c7fd2574369ac7590ed6170a550.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/850554695ead4daba22f1a417c2f2f97.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/31205b65e92a45379d9dc2f5acb5064b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAbGl1X2VuZG9uZw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/e24ae31a63ad4f08bd0c715d79cf86fb.png