单链表（C语言）

今晚睇李

创建单链表：

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;
        Node* list = creatlinklist();
        for (int i = 0; i <= 5; i++)
        {
                scanf_s("%d", &val);
                frontinsert(list, val);
              //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不为空。