单链表的基本操作-插入结点、删除结点、新建链表、查找结点位置

C语言新手小白的学习笔记-------------目前持续更新中

**
本人90后电气工程及其自动化大学生，大二开始接触C语言，写过前端，Python，但是都不精通，通过许多认识后明白了自身的许多不足，因此，想通过博客与大家分享我的学习过程和认识，如果有哪位大佬有更好的意见和认识，请你们一定要积极留言，如果有错误的地方，请大家能第一时间帮我指出，谢谢各位了，大家一起进步，每天进步一点点，加油，热爱技术的各位。

第一期单链表的基本操作

下面是我根据单链表的结构特点和自己的理解以及借鉴其他博客大佬（MING.MING）的代码写出的代码：

#include <stdio.h>
#include <stdlib.h>
#include <windows.h>#define OK 100
#define NO 404
#define LENGTH 10
#define NUM 0typedef struct Linklist{ /*定义链表的结点的数据结构体，链表的结点包含元素和指向。*/int element;struct Linklist *next;
}Node;int CreateLinklist(Node *head,int len){   /*创建一个新的具体长度的链表，并返回是否成功创建。*/int i;Node *h=head;for(i=0;i<len;i++){Node *newnode=(Node*)malloc(sizeof(Node)); /*为新建的结点分配新的空间。*/newnode->next=NULL; /*初始化新建结点*/scanf("%d",&newnode->element);h->next=newnode; /*将头指针指向新建的结点，形成头节点。*/h=newnode; /*将头指针指向新建的结点。*/}if(h->next!=NULL){return OK;}else{return NO;}return len;
}int TraveLinklist(Node *head){  /*遍历整个链表的所有结点，并返回相应的状态*/Node *p=head->next;   /*将头指针赋给结点p*/while(p!=NULL){  /*判断头结点是否为空*/printf("%d\t",p->element);p=p->next;}if(p->next==NULL){return OK;}else{return NO;}
}int Forwordindexof(Node *head,int data){    /*查找链表的某个结点，并返回该节点所在的位置，如果不存在该结点，则返回状态NO*/int index=1;    /*链表位置参数初始化*/Node *p=head->next;while(p!=NULL){if(p->element==data){printf("目标结点的位置为：%d\t",index);}index++; /*结点位置参数增加，直到找到目标结点*/p=p->next;    /*将指向不断右移*/}return index;
}void Isempty(Node *head){    /*判断链表是否为空*/Node *p=head->next;    /*定义头结点*/if(p!=NULL){    /*头结点不为空则表明该链表不为空*/printf("该链表不为空！\n");}else{printf("该链表为空！");}
}int Insertinedxof(Node *head,int index,int data){    /*在链表的某一个结点插入元素，插入成功返回OK，否则NO*/int i=1;Node *newnode=(Node*)malloc(sizeof(Node));   /*定义一个新的结点*/Node *p=head;    /*定义头结点*/newnode->next=NULL;    /*初始化新结点*/newnode->element=data;    /*将数据指向data*/while(p->next!=NULL){    /*头结点不为空*/if(i==index){     /*如果定位到指定的位置*/newnode->next=p->next;     /*将结点指向赋给新的结点*/p->next=newnode;     /*将新结点赋给原来结点的指向*/newnode=newnode->next;    /*新的结点不断向后移动*/}p=p->next;   /*结点向后遍历*/i++;   /*结点位置不断向后移动*/}return OK;
}void deleteLinklist(Node *head){     /*删除整个链表*/Node *pre;          /*定义一个结点用以保存待删除结点*/while(head->next!=NULL){pre=head->next;   /*将头结点指向pre*/head->next=pre->next;    /*将pre指向头结点*/free(pre);     /*释放原头结点*/}
}void deleteindexof(Node *head,int index){     /*删除链表某个位置的结点*/Node *now;Node *p=head;int i=1;while(p->next!=NULL){if(i==index){now=p->next;p->next=now->next;free(now);}p=p->next;i++;}   
}void ReverseLinklist(Node *head){Node *pre=NULL;Node *curr;while(head->next!=NULL){curr=head->next;head->next=curr->next;curr->next=pre;pre=curr;}head->next=pre;
}int main()
{Node *head =(Node*)malloc(sizeof(Node));     /*为头指针分配空间*/head->next=NULL;                             /*初始化头结点*/CreateLinklist(head,LENGTH);    /*创建链表*/Insertinedxof(head,2,111);      /*在链表的第二个结点处插入一个新的结点*/ReverseLinklist(head);          /*倒置链表*/deleteindexof(head,5);          /*删除链表中第5个位置的结点*/Forwordindexof(head,NUM);       /*在链表中查找元素*/TraveLinklist(head);            /*遍历链表*/Sleep(1000);                    /*延时函数*/ deleteLinklist(head);           /*删除结点*/Isempty(head);                  /*判断链表是否为空*/return 0;
}

1.1 创建新的链表

首先，我们应该都知道，链表是依靠指针指向来将前驱结点和后继结点连接起来的，头结点无前驱，尾结点无后继，所以，我们应先创建一个关于结点的数据结构：

typedef struct Linklist{ /*定义链表的结点的数据结构体，链表的结点包含元素和指向。*/int element;struct Linklist *next;
}Node;

一个链表的结点包括数据和指针域，因此，我们用element整型变量来存储结点的数据，结构体指针next表示结点的指向。
接下来，我们来创建一个新的链表：

int CreateLinklist(Node *head,int len){   /*创建一个新的具体长度的链表，并返回是否成功创建。*/int i;Node *h=head;for(i=0;i<len;i++){Node *newnode=(Node*)malloc(sizeof(Node)); /*为新建的结点分配新的空间。*/newnode->next=NULL; /*初始化新建结点*/scanf("%d",&newnode->element);h->next=newnode; /*将头指针指向新建的结点，形成头节点。*/h=newnode; /*将头指针指向新建的结点。*/}if(h->next!=NULL){return OK;}else{return NO;}return len;
}

由于链表由头指针指向的头结点开始，自NULL结束。CreateLinklist函数的功能是创建一个长度为len，头指针为head的链表，所以，我们应该首先定义一个头指针h（将head指向它），通过for循环循环次数为len，同时为新建的结点newnode分配动态空间，将新建的结点指向NULL，（这里我理解为初始化过程），使用scanf函数通过键盘输入数据，为每个新建的结点写入数据。然后将头指针指向头结点即新建的结点，最后让头指针链接到新的结点。我认为创建链表需要注意的是：新结点之间的指向以及数据的输入，由于最后我们将头指针与第一个新的结点链接起来，所以，接下来的指针指向，是以第一个结点为起点开始的，直到指向NULL。

1.2 遍历链表

我们可以利用链表从头结点到NULL为条件，使用while循环来对链表的每个结点进行访问，下面是具体的代码：

int TraveLinklist(Node *head){  /*遍历整个链表的所有结点，并返回相应的状态*/Node *p=head->next;   /*将头指针赋给结点p*/while(p!=NULL){  /*判断头结点是否为空*/printf("%d\t",p->element);p=p->next;}if(p->next==NULL){return OK;}else{return NO;}}

首先我们定义一个结构体变量p用来定义头结点，设置条件结点是否为空，只要结点指向不为空，则循环输出结点的数据，并且不断使结点后移，直到结点指向NULL，退出循环。遍历时，我们应该注意的是：每循环一次，都需要将结点向后移动，即改变结点指针的指向，使得每个结点的数据能正确被输出。

1.3 查找结点位置

对于常见的几种的数据结构，一般的几种基本操作：增、删、查、改，虽然一般链表、数组的初始位置都为0，但是为了便于符合大家的习惯，我把初始位置定为1，查找函数的功能是：通过输入数据，来查找该链表中与其相对应的数据的位置，并输出显示，下面是详细的代码：

int Forwordindexof(Node *head,int data){    /*查找链表的某个结点，并返回该节点所在的位置，如果不存在该结点，则返回状态NO*/int index=1;    /*链表位置参数初始化*/Node *p=head->next;while(p!=NULL){if(p->element==data){printf("目标结点的位置为：%d\t",index);}index++; /*结点位置参数增加，直到找到目标结点*/p=p->next;    /*将指向不断右移*/}return index;
}

定义一个存储链表结点位置的变量index，初始化值为1，即头结点的位置，其次，将头结点赋与结构体变量p。首先判断p是否为空，如果不为空，就进入循环。如果结点p的数据与待查找的数据相等时，输出index的值，当然，index的值会随着结点的遍历增加。其实，查找结点位置时，可以采用其他的查找算法，这里不再赘述（主要是我不会呀！wuwuwuwu，难受）。

1.4 判断链表是否为空

我们在对链表进行增、删、查、改等操作、新建链表后，我们需要对链表是否为空进行判断，即判断链表头结点是否为空，下面是具体代码实现：

void Isempty(Node *head){    /*判断链表是否为空*/Node *p=head->next;    /*定义头结点*/if(p!=NULL){    /*头结点不为空则表明该链表不为空*/printf("该链表不为空！\n");}else{printf("该链表为空！");}
}

这里，不再赘述了，见注释即可，好渴，让我喝口水了再说。。。。。。

1.5 插入新结点

函数Insertindexof的功能是在期待位置index插入新的结点。原来的结点向后移动，链表的插入新的结点与数组插入新元素的方法不同，因为数组的长度大小被确定，不能增加，所以一般需要进行新增数组元素，将采用动态数组的方法实现。下面是链表插入新结点的具体实现：

int Insertinedxof(Node *head,int index,int data){    /*在链表的某一个结点插入元素，插入成功返回OK，否则NO*/int i=1;Node *newnode=(Node*)malloc(sizeof(Node));   /*定义一个新的结点*/Node *p=head;    /*定义头指针*/newnode->next=NULL;    /*初始化新结点*/newnode->element=data;    /*将数据指向data*/while(p->next!=NULL){    /*头结点不为空*/if(i==index){     /*如果定位到指定的位置*/newnode->next=p->next;     /*将结点指向赋给新的结点*/p->next=newnode;     /*将新结点赋给原来结点的指向*/newnode=newnode->next;    /*新的结点不断向后移动*/}p=p->next;   /*结点向后遍历*/i++;   /*结点位置不断向后移动*/}return OK;
}

首先，我们为一个新的结构体变量newnode分配动态存储空间，同时定义一个头指针p，初始化newnode，使它的指针域指向NULL，数据域指向data，定义一个位置变量i，用以存储链表每一个结点的位置。其次，我们对结点进行判断是否为空，如果结点不为空时，遍历链表，判断当前位置是否与指定位置index相等，如果是，则将结点指向新的结点，并将新结点指向原来的结点，说的简单一点就是，新节点占了原来呆在这个位置的结点的地方，原来的结点跑到了新结点的后面，所以，需要将新节点指向原来的结点，这样才能使整个链表重新链接起来，然后使新结点不断向后移动。当然，不要忘记遍历整个链表时，需要将结点不断后移，使位置参数i的值改变。

1.6 删除整个链表

当我们对不再需要的链表进行删除操作时，即是对动态空间的释放，可以使用free函数，对每个结点的空间进行释放，即完成删除的操作。下面是具体代码实现：

void deleteLinklist(Node *head){     /*删除整个链表*/Node *pre;          /*定义一个结点用以保存待删除结点*/while(head->next!=NULL){pre=head->next;   /*将头结点指向pre*/head->next=pre->next;    /*将pre指向头结点*/free(pre);     /*释放原头结点*/}
}

首先，我们定义一个结构体变量pre用来保存待删除结点，并且开始遍历结点，由于首先从头结点开始进行删除，那么先将头结点指向pre，再将pre的下一个指向结点定义为新的头结点，最后释放头结点的空间，以此类推，直到整个链表为空。

1.7 删除指定位置的结点

当需要对某个位置的结点进行删除操作时，我们依然采用与deleteLinklist函数一样的操作，但是我们不是要删除整个链表，而是只删除一个结点，所以，需要改动，下面是具体的操作：

void deleteindexof(Node *head,int index){     /*删除链表某个位置的结点*/Node *now;Node *p=head;int i=1;while(p->next!=NULL){if(i==index){now=p->next;p->next=now->next;free(now);}p=p->next;i++;}   
}

首先，我们分别定义一个存储待删除结点的结构体变量now、头指针p，以及存储链表结点位置的变量i，依旧是采用遍历链表的方法，判断结点是否为空，不为空则遍历整个链表，查找对应位置的结点。当遍历到对应位置后，将待删除结点指向now，然后将它指向下一个结点，接着释放now的空间。同时，遍历链表的基本：结点不断向后指向，位置参数i的值增加。

1.8 链表的倒置

说的简单一点就是对链表的结点进行翻转，改变结点的指向，但是链表的倒置不像数组的倒置，由于需要对结点的指向进行改变，所以，比较难以理解，在借鉴博主MING.MING的代码后，才明白，主要是大佬的水平太高，小白桑不起。。。。下面是博主MING.MING的链表倒置具体代码实现：

void ReverseLinklist(Node *head){Node *pre=NULL;Node *curr;while(head->next!=NULL){curr=head->next;head->next=curr->next;curr->next=pre;pre=curr;}head->next=pre;
}

当时是借鉴的代码，所以只分析了代码的运行原理，没有写注释（其实就是忘了），首先定义一个空结点pre，一个存储结点的结构体变量curr。同时遍历链表，首先，将头结点赋予curr（curr=head->next），同时，将curr的下一个指向结点定义为头结点，将头结点从链表中取出（curr->next=pre），并将curr指向pre，以此类推，将结点的指向不断改变，即指向它的上一个结点，直到最后，遍历完成后，将原来的尾结点定义为头结点（head->next=pre）。
效果就是：
在这里插入图片描述

总结

虽然本人的代码写的很烂，但是我还是想通过这样的方式与各位大佬与技术爱好者一起交流，学习，进步。关于运行程序，其中的插入函数运行时，不能在末尾插入元素，比如不能在长度为10的末尾，即第11位插入结点，只能实现头插，无法实现尾插，后来查看程序，可能是因为没有考虑到最后结点是指向NULL的，导致遍历到最后一个结点时，结束了遍历，不能实现尾插，希望能有大佬能指出解决方法，谢谢。另外在主函数中无法运行删除整个链表的函数，查了很久都没有查到问题，有大神知晓的吗，还望指出，感激不尽。
接下来的时间里，我会持续更新关于C语言实现的常用的数据结构的操作，希望大家能给我一些好的代码改进建议，谢谢大家。