单链表（C语言）

蔡家的小作精

创建单链表：

准备：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef int Date;
typedef struct Node
{
        Date date;//数据域
        struct Node* next;//指针域
}Node;    我们首先需要创建一个头节点，这里将头节点的创建封装成为一个函数。
Node* creatlinklist()
{
    Node* head = malloc(sizeof(Node));
    if (!head)
    {
        printf（“创建失败”）;
        return NULL
    }
    memset(head,0, sizeof(Node));//将头结点初始化为0，使用这个要包含<string.h>
    return head;
}头结点的数据域可以不储存任何数据，但头结点的指针域储存指向第一个节点的指针。
头插法：

头插法会将数据插入在表头，比如依次输入0，1，2，3那么在链表中从第一个节点到最后一个节点保存的数据分别是3，2，1，0  。
使用头插法，要先创建一个新节点，这里将创建新节点封装成一个函数。
Node* creatNode(Date val)//val是数据域要保存的值
{
    Node* newNode = malloc(sizeof(Node));
    if (!newNode)
    {
        printf（“创建失败”）;
        return NULL;
    }
    newNode->date = val;
    newNode->next = NULL;
    return newNode;
}新节点创建成功后我们要将这个节点插入到第一个节点和头节点之间。当链表没有第一个节点时，也就是刚开始创建链表时，我们可以把NULL（head->next）看成是第一个节点 , 其实不管有没有第一个节点都是head->next。插入的操作是先建立新节点和第一个节点之间的连接newNode->next=head->next，再建立头节点和新节点之间的连接head->next=newNode。
将头插法封装成一个函数
void frontinsert(Node* list, Date val)
{
    Node* newNode = creatNode(val);
    newNode->next = list->next;
    list->next = newNode;

}


头插法演示图

尾插法:

尾插法将数据插入在表尾，比如依次插入0，1，2，3那么从链表的第一个节点到最后一个节点保存的数据分别是0，1，2，3  。
使用尾插法同样要创建一个新节点，这里只要调用creatNode()函数就可以了。然后我们要找到链表的尾节点，这里可以用一个while循环来实现这个操作，但在循环之前我们还要定义一个指针（Node*curNode=creatlinklist()），进入循环前先让这个指针指向头节点。在循环中让curNode不断的指向下一个节点curNode=curNode->next，那循环结束的条件是什么？当然是curNode指向最后一个节点，因为链表的最后一个节点保存的指针是指向空的，所以当curNode->next=NULL时就表明找到了最后一个节点。既然找到了最后一个节点，就把新节点连接上就可以了curNode->next=newNode。
将尾插法封装成一个函数
void bakeinsert(Node* list, Date val)
{
    Node* curNode = list;
    while (curNode->next)
        curNode = curNode->next;
    Node* newNode = creatNode(val);
    curNode->next = newNode;
}


尾插法示意图

输出单链表：

单链表的输出方式是从头到尾的输出，实现对单链表的输出的思路和我们用尾插法创建链表时找最后一个节点有些相似。先展示代码，把输出链表封装成了一个函数。
void printlist(Node* list)
{
    Node* curNode = list->next;
    while (curNode)
    {
        printf("%d  ", curNode->date);
        curNode= curNode->next;
    }
}需要注意的是Node*curNode=list->next不要写成Node*curNode=list，这样在进入循环是第一次执行printf会输出头结点保存的数据，这个数据似乎并没有什么意义。还需要注意的是printf（）和curNode=curNode->next的先后顺序，如果你弄反了的话就会漏掉了第一个节点保存的值，因为第一次进入循环时（在printf执行之前）curNode就由指向第一个节点变成指向第二个节点。
主函数：
最后,在主函数里我们可以用类似这样一段代码来创建并输出单链表。
int main()
{
        int val;
        int count=0;
        Node* list = creatlinklist();
        for (int i = 0; i <= 5; ++i)
        {
                scanf_s("%d", &val);
                frontinsert(list, val);
                ++count;
              //bakeinsert(list,val);
        }
        printlist(list);
        return 0;
}创建了单链表之后的操作

插入：

这是执行插入操作的代码。
/*1*/newNode->next = curNode->next;
/*2*/curNode->next = newNode；这两行代码可不可以交换顺序？我们来试一试，假设先执行代码2，再执行代码1 。
/*2*/curNode->next = newNode；
/*1*/newNode->next = curNode->next;那么在代码1里相当于newNode->next=newNode，newNode保存了指向newNode的指针！！用图表示就是这样的。



错误的插入顺序

这里讨论的插入有两种，一种是指定位置插入，一种是指定值插入。这里先讲指定位置插入。
指定位置插入：
先做一个约定，第一个节点是位置0，第二个节点是位置1，就像数组一样，以0~n-1标记n个节点的位置，新的节点将插入在指定位置的前面。
我们需要一个指针curNode和一个for循环来帮我们找到指定的位置（pos）的那个节点，但我们并不用让指针curNode指向那个位置，只要curNode->next指向这个节点就可以了。接下来的操作就和我们最开始讲的头插法类似了。我们要将新节点newNode插入到curNode和位置为pos的节点之间，可以把curNode想象成头节点，位置为pos的节点为第一个节点，那么这个插入操作是不是和头插法的那个插入操作时一样的。先是newNode->next=curNode->next再是curNode->next=newNode。如果这个位置是最后一个节点就和尾插法一样了。代码如下
void posinsert(Node* list, int pos, Date val)
{
    Node* curNode = list;
    for (int i = 0; i < pos&&curNode->next; i++)
    {
        curNode = curNode->next;
    }
    Node* newNode = creatNode(val);
    newNode->next = curNode->next;
    curNode->next = newNode;
}值得注意的是，循环进行的条件这里除了i<pos之外还有一个curNode->next不为空。这是考虑到类似这样的一个情况，如果链表只有10个节点，但pos是20，这很显然i=16，17 .........这些值是没有意义的。



指定位置插入

指定值插入：
和指定位置插入差不多，我们先要找到指定的那个值所在的节点，再次请指针curNode来帮助我们寻找这个节点。这需要一个while循环，在循环中要让curNode依次访问每一个节点，如果这个节点保存的值等于我们要找的值就跳出这个循环，此时curNode已经指向了这个节点。跳出循环后我们要做的就是插入新节点。先来试试插入到curNode的前面，先执行newNode->next=curNode,再将curNode前一个节点连接上newNode。但是，curNode前一个节点该怎么表示？在单链表中每一个节点中并没有保存指向前一个节点的指针，所以插入在curNode的前面不太可行。我们再试试插入在curNode后面，这个操作应该不陌生了吧，就和指定位置插入的插入方法一样，如果这个指定的值在最后一个位置，就和尾插法一样了。代码如下
void objvalinsert(Node* list, int objval, Date val)
{
    Node* curNode = list;
    while(curNode->next)
    {
        curNode = curNode->next;
        if (curNode->date== objval)
            break;

    }
    Node* newNode = creatNode(objval);
    newNode->next = curNode->next;
    curNode->next = newNode;
}这段代码还是有一点问题的，就是如果创建的链表中没有指定的那个值（objval),还是会把保存objval的节点插入在表尾。当然如果这是你希望的结果那也没有问题。
问题讨论：
这里提一个小小的问题，为什么while的条件是curNode->next不为空而不是curNode不为空。
介绍完了插入，我们现在来看看删除操作。
删除：

假设现在有三个节点a->b->c。现在我们要删除节点b，其实就是将节点a的保存的指针绕过b指向a就可以了。
a->next=a->next->next;
free(b);


删除节点

删除链表中第i个节点的思路如下：
这里还是需要指针curNode来帮助我们找到第i个节点(其实是让curNode指向第i-1个也就是节点a)，还需要一个变量j来记录已经遍历寻找过的节点数，j初始化为0，如果遍历到了链表的末尾则说明节点i是不存在的，否则就执删除操作。
void deletNode(Node* list, int i)
{
    int j = 0;
    Node* curNode = list;
    Node* temp = NULL;
    while (curNode->next && j < i-1)
    {
        curNode = curNode->next;
        ++j;
    }
    if (!(curNode->next) || j > i)
        return;
    temp = curNode->next;
    curNode->next = temp->next;
    free(temp);

}这里还用了一个指针tem来保存节点b,这是因为如果没有保存节点b的话执行了curNode->next =curNode->next ->next操作之后就没办法在找到b了，那么我们就没有办法释放掉节点b。
如果你不知道要删除的节点是第几个节点，但是知道要删除的节点保存了什么值，将上面的代码稍微改一下就可以了。
void deletvalNode(Node* list, int val)
{
    Node* curNode = list;
    Node* temp = NULL;
    while (curNode->next )
    {
        curNode = curNode->next;
        if(curNode->next->date==val)
            break;
    }
    if (!(curNode->next))
        return;
    temp = curNode->next;
    curNode->next = temp->next;
    free(temp);

}这段代码的目的就是指向节点a，因为如果直接判断curNode->date==val就是指向节点b,那就没办法对节点a和节点c进行连接了。
if(curNode->next->date==val)
     break;销毁整个单链表：

当一个单链表不打算使用的时候我们要将他销毁，也就是在内存中将这个链表释放。销毁单链表的思路就是通过一个循环将节点逐次释放掉。
void destructlinklist(Node* list)
{
    Node* curNode = list->next;
    Node* temp = NULL;
    while (curNode)
    {
        temp = curNode->next;
        free(curNode);
        curNode = temp;
    }
    list->next = NULL;
}这里我们也引入了一个指针temp，这个指针的存在非常有必要，因为如果没有这个指针保存curNode，那么我们执行完free(curNode)后就没有办法找到curNode的下一个节点了。
完整的代码

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

typedef int Date;
typedef struct Node
{
    Date date;
    struct Node* next;
}Node;

Node* creatlinklist();
void frontinsert(Node* list, Date val);
void bakeinsert(Node* list, Date val);
void posinsert(Node* list, int pos, Date val);
void valinsert(Node* list, Date objvall, Date val);
void deletNode(Node* list, int i);
void deletvalNode(Node* list,Date val);
void des(Node* list);
void showlist(Node* list);

int main()
{
        Node* list = creatlinklist();
        return 0;
}

Node* creatlinklist()
{
    Node* head = malloc(sizeof(Node));
    if (!head)
    {
        printf("创建失败");
        return NULL;
    }
    memset(head, 0, sizeof(Node));
    return head;
}

Node* creatNode(Date val)
{
    Node* newNode = malloc(sizeof(Node));
    if (!newNode)
    {
        printf("创建失败");
        return NULL;
    }
    newNode->date = val;
    newNode->next = NULL;
    return newNode;
}

void frontinsert(Node* list, Date val)
{
    Node* newNode = creatNode(val);
    newNode->next = list->next;
    list->next = newNode;

}

void bakeinsert(Node* list, Date val)
{
    Node* curNode = list;
    while (curNode->next)
        curNode = curNode->next;
    Node* newNode = creatNode(val);
    curNode->next = newNode;
}

void posinsert(Node* list, int pos, Date val)
{
    Node* curNode = list;
    for (int i = 0; i < pos && curNode->next; i++)
    {
        curNode = curNode->next;
    }
    Node* newNode = creatNode(val);
    newNode->next = curNode->next;
    curNode->next = newNode;
}

void objvalinsert(Node* list, Date objval, Date val)
{
    Node* curNode = list;
    while (curNode->next)
    {
        curNode = curNode->next;
        if (curNode->date == objval)
            break;
    }
    Node* newNode = creatNode(objval);
    newNode->next = curNode->next;
    curNode->next = newNode;
}

void deletNode(Node* list, int i)
{
    int j = 0;
    Node* curNode = list;
    Node* temp = NULL;
    while (curNode->next && j < i - 1)
    {
        curNode = curNode->next;
        ++j;
    }
    if (!(curNode->next) || j > i)
        return;
    temp = curNode->next;
    curNode->next = temp->next;
    free(temp);
}

void deletvalNode(Node* list, int val)
{
    Node* curNode = list;
    Node* temp = NULL;
    while (curNode->next)
    {
        curNode = curNode->next;
        if (curNode->next->date == val)
            break;
    }
    if (!(curNode->next))
        return;
    temp = curNode->next;
    curNode->next = temp->next;
    free(temp);
}

void destructlinklist(Node* list)
{
    Node* curNode = list->next;
    Node* tem = NULL;
    while (curNode)
    {
        tem = curNode->next;
        free(curNode);
        curNode = tem;
    }
    list->next = NULL;
}

void showlist(Node* list)
{
    Node* curNode = list->next;
    while (curNode)
    {
        printf("%d  ", curNode->date);
        curNode = curNode->next;
    }
}