数据结构专升本学习笔记，线性表链表小节
前言
今天在学校学习了线性表里面的链表，老师讲解很到位，让人通俗易懂，学习嘛，总是需要记笔记的，好记性不如烂笔头，今天小编就把学到的知识捋一遍，做一个学习笔记分享给大家。不喜勿喷。。。。哈哈哈
每天一遍，防止颓废
1.让我们了解一下链表
1.1 链表有单链表，双向链表，循环链表等等，不管什么链表都得会先创建链表，创建链表我们就得知道几个关键步骤。
第一步创建结点第二步创建第二个结点第三步把第一步和第二步建立连接
1.大致步骤简单一点表达就是这样 2.要认识一些类型名: malloc(sizeof(类型)) 分配所需的内存空间，并返回一个指向它的指针。 例：(LinkList)malloc(sizeof(Node)) typedef关键字，您可以使用它来为类型取一个新的名字 例：typedef int ElemType struct 关键字用于创建结构体 例：typedef struct Node { ElemType data; struct Node *next; }Node,*LinkList; free(void *ptr) 释放之前调用 calloc、malloc 或 realloc 所分配的内存空间 认识这四个我们才能开始进行下一步 复制代码1.2 建立单链表
我们先用个图来理解一下：
把他们的恋情我们当作一个链表，小红拉着小明的手，小明拉着小王的手，小王拉着小丽的手，小丽最后一个她又只喜欢自己，它们之间手牵手就是连接（可以理解为指针域），她自己的秘密就她这个结点的数据。用老师的图就行这样 他们之间的恋情就是单链表，非常通俗易懂吧。
1.3 那么我们开始用头插法来创建吧。
先来个图，再来个小故事。
头插法小故事：美丽漂亮的小丽被malloc生成了，她有个秘密：“我只喜欢自己”，有一天媒婆注意到了她，并记录她的家的位置，为她寻找一个喜欢她的人，这天malloc又生了小王，一个帅气的小伙，他的秘密是“我喜欢小丽”，熟悉的媒婆又找到他了，发现他喜欢的人刚好是自己刚刚记录的女孩，于是告诉了小伙，小伙就记住了小丽的家的位置，媒婆此时记录了小王家的位置把小丽的位置覆盖了，malloc心情好又生了一个，小明，小明是个男生，他的秘密是“我喜欢小王”，有一天媒婆见他眉清目秀，要给他介绍对象，发现他刚好喜欢自己刚刚记录的小王，媒婆知道他们的爱情是挡不住的，于是就把小王的地址给了小明，小明记住了小王的地址，并和他牵手，媒婆此时把小明的地址记住了，malloc不愧是个好人，又生了，虽然没有做到一胎生四个，但是它做到间接生四个了，就这样一个美丽大方，非常性感的小红和她的秘密：“我喜欢小明”诞生了，媒婆接到邀请，来给小红物色男朋友，媒婆发现她喜欢的刚好是自己记录的小明，于是把小明的地址告诉了小红，小红和小明顺利牵手，此时小红的地址被媒婆记住了。哈哈哈哈媒婆就是Head头结点，只要知道她记录的地址，就可以遍历她给人牵红线的经历了。
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node { int data; struct Node *next; }link; link * creatLink(int * arc, int length) { int i; //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H link * H =(link*)malloc(sizeof(link)); H->data = arc[0]; H->next = NULL;//因为头插法第一个结点就是链表最后一个结点，所以 //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前 for (i = 1; i<length; i++) { link * a = (link*)malloc(sizeof(link)); a->data = arc[i]; //插入元素时，首先将插入位置后的链表链接到新结点上 a->next = H; //然后再链接头指针 H H = a; } return H; } //有头结点链表的头插法实现函数 link * HcreatLink(int * arc, int length) { int i; //创建头结点 H，其链表的头指针也是 H link * H = (link*)malloc(sizeof(link)); H->data = 0;//有头结点的，我这里把H的data赋值了，其实一般都是用NULL，然后要遍历的话在赋值时直接赋值p = H->next; H->next = NULL; //采用头插法创建链表 for (i = 0; i<length; i++) { link * a = (link*)malloc(sizeof(link)); a->data = arc[i]; //首先将插入位置之后的链表链接到新结点 a 上 a->next = H->next; //将新结点 a 插入到头结点之后的位置 H->next = a; } return H; } void display(link *p) { //链表的输出函数,遍历链表 while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { int a[3] = { 1,2,3}; //采用头插法创建无头结点链表 link * H = creatLink(a, 3); display(H); //采用头插法创建有头结点链表 link * head = HcreatLink(a, 3); display(head); //使用完毕后，释放即可 free(H); free(head); return 0; } 复制代码1.4 现在再试试尾插法插法来创建吧
尾插法和头插法区别不大，头插法是每次插入都在第一个，尾插法就是每次插入都在最后一个。 尾插法需要的
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node { int data; struct Node *next; }link; link * creatLink(int * arc, int length) { int i; //最初状态下，头指针 H 没有任何结点，所以，插入第一个元素，就相当于是创建结点 H link * H =(link*)malloc(sizeof(link)); H->data = arc[0]; H->next = NULL; //如果采用头插法插入超过 1 个元素，则可添加到第一个结点 H 之前 for (i = 1; i<length; i++) { link * a = (link*)malloc(sizeof(link)); a->data = arc[i]; //插入元素时，首先将插入位置后的链表链接到新结点上 a->next = H; //然后再链接头指针 H H = a; } return H; } link * creattail(int * arc, int length) {//这里我们采用尾插法 ,来创建链表 int i; link * q ; //q用来标记上个结点的位置，然后q和下一个新建结点连接 link * H =(link*)malloc(sizeof(link));//创建第一个结点 H->data = arc[0]; H->next = NULL; q = H; //q要记住第一个结点 for (i = 1; i<length; i++) { link * a = (link*)malloc(sizeof(link));//创建新结点 q->next = a; //上个结点连接新建立的结点，从而产生每次新建结点在最后一个 a->data = arc[i]; //给新建立的结点赋值 a->next = NULL; //因为新建立的结点是最后一个，所以它的指针域是NULL q = a; //q 现在标记新建立的结点，作为最后一个结点，方便后面新建立的结点连接q } return H;//返回第一个结点 } //有头结点链表的头插法实现函数 //link * HcreatLink(int * arc, int length) { // int i; // //创建头结点 H，其链表的头指针也是 H // link * H = (link*)malloc(sizeof(link)); // H->data = 0; // H->next = NULL; // //采用头插法创建链表 // for (i = 0; i<length; i++) { // link * a = (link*)malloc(sizeof(link)); // a->data = arc[i]; // //首先将插入位置之后的链表链接到新结点 a 上 // a->next = H->next; // //将新结点 a 插入到头结点之后的位置 // H->next = a; // } // return H; //} void display(link *p) { //链表的输出函数,遍历链表 while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { int a[3] = { 1,2,3}; //采用头插法创建无头结点链表 link * H = creatLink(a, 3); display(H); // //采用头插法创建有头结点链表 // link * head = HcreatLink(a, 3); // display(head); //采用尾插法 link * tail = creattail(a, 3); display(tail); //使用完毕后，释放即可 free(H); free(tail); //free(head); return 0; } 复制代码因为头插法每次插入在链表的前面，我们都是从第一个结点遍历，所以数组a的值就是一个倒序输出 而尾插法是每次插入在链表的后面，所以数组a的值是一个顺序输出。
1.5 插入结点和删除结点
我们先了解一下插入，先上个图，前面我们了解了小红他们的爱情故事，现在他们的爱情出现了问题，他们的和谐的生活，被一个女生给干扰了，他们之间有人出轨了。
小故事：媒婆每天给别人介绍对象，自己却孤苦伶仃，她于是对小明下手了，于是小明喜欢媒婆，小明就和媒婆牵手了，媒婆喜欢小王，所以媒婆和小王牵手了。（哈哈哈，小故事虽好不要当真，讲人话就是：我们要找到我们要插入上一个的位置，然后把上一个位置和我们要插入的结点连接，我们插入的结点连接下一个结点就完成了。） 话不多说上代码：
void insert(int arc,link *p) {//假设我们要插入4插入在arc的后面 link * a = (link*)malloc(sizeof(link));//创建要插入的结点 a->data = 4; //插入的值4进行赋值 a->next = NULL; int i=1; while(p!=NULL&&i!=arc) { i++; p = p->next;//向下遍历找到直到找到arc的值 } if(p==NULL)//没找到 { printf("没找到插入失败"); } else{//找到了 a->next =p->next;//我们要插入的结点的指针域要和当前结点指针域的下一个结点连接 p->next = a; //然后当前结点和我们插入结点连接 } }//调用这个函数就可以插入啦 复制代码效果就是这样啦：
1.5.1 删除结点
删除结点的思想就是找到要删除结点的位置，然后要提前标记要删除结点的上一个结点，上一个结点和当前下一个结点连接，然后释放当前结点从而实现删除。 上个图：
代码如下：
void delete1(int arc,link *p) {//假设我们要arc位置的结点 int i=1; link * q; //用来标记当前删除的结点的上一个结点 while(p!=NULL&&i!=arc) { i++; q = p;//记住上一个结点 p = p->next;//向下遍历找到直到找到arc的值 } if(p==NULL)//没找到 { printf("没找到删除失败"); } else{//找到了 q ->next = p->next; //上一个结点连接下一个结点 free(p);//释放当前结点 } } 复制代码2.循环链表的创建
循环链表，顾名思义它是一个环，首尾连接，讲人话就是：最后一个尾结点指向头结点实现首尾相接，中间就是单链表。 上个图让大家了解一下：
循环链表小故事： 前面我们知道了红明王丽的唯美爱情故事，身在最后一个的小丽觉得自己有点孤单，于是她就追求小红，并和小红幸福的牵手了，他们之间的爱情，用一个词来形容就是四角恋，所以循环链表通俗的讲就是四角恋或者三角恋再或者就是多角恋。哈哈哈哈 话不多说来个小漩涡：
link * creatcycle (int * arc, int length) {//这里我们采用尾插法 ,来创建链表 int i; link * q ; //q用来标记上个结点的位置，然后q和下一个新建结点连接 link * H =(link*)malloc(sizeof(link));//创建第一个结点 H->data = arc[0]; H->next = NULL; q = H; //q要记住第一个结点 for (i = 1; i<length; i++) { link * a = (link*)malloc(sizeof(link));//创建新结点 q->next = a; //上个结点连接新建立的结点，从而产生每次新建结点在最后一个 a->data = arc[i]; //给新建立的结点赋值 a->next = NULL; //因为新建立的结点是最后一个，所以它的指针域是NULL q = a; //q 现在标记新建立的结点，作为最后一个结点，方便后面新建立的结点连接q } q ->next = H; //最后一个结点指向头结点形成循环结点 这代码就是尾插法加这句话。 return H;//返回第一个结点 } void displaycycle(link *p,int a) { // 因为是循环链表不管那个结点都可以遍历整个表，所要传遍历次数 a int i=0; while (i<a) { i++; printf("%d ", p->data); p = p->next; } printf("\n"); } { int a[3] = { 1,2,3}; link * cycle = creatcycle(a, 3); displaycycle(cycle,5); //这个是main函数调用 } 复制代码效果展示：
总结：
这篇文章，是博主在学校前天课上的知识，博主进行了整理，分析，写一篇自己的学习笔记，方便自己往后复习，并分享给大家一起学习，如有错误，请及时指点，这篇文章只讲了单链表和循环链表，后面博主学习到的知识会及时更文，希望大家喜欢，不喜勿喷，创作不易，大家点赞，关注，评论，收藏。（另外博主讲的故事纯属虚构，如有冒犯，请多多包含）。
作者：IC00
链接：https://juejin.cn/post/7022789985589788709