[数据结构与算法]再探C语言链表—TypeDef Struct模式声明链表节点

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头文件
}

?结果

2.?头插法示意图

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

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

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

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

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

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

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

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

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

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

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

5.?关于链表的地址

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

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

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

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

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

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

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

?6.?关于next指向NULL

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

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

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