前言
今天在学校学习了线性表里面的链表，老师讲解很到位，让人通俗易懂，学习嘛，总是需要记笔记的，好记性不如烂笔头，今天小编就把学到的知识捋一遍，做一个学习笔记分享给大家。不喜勿喷。。。。哈哈哈
每天一遍，防止颓废
1.让我们了解一下链表
1.1 链表有单链表，双向链表，循环链表等等，不管什么链表都得会先创建链表，创建链表我们就得知道几个关键步骤。
graph TD第一步创建结点 --> 第二步创建第二个结点-->第三步把第一步和第二步建立连接
复制代码
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函数调用}
复制代码
效果展示：
总结：
这篇文章，是博主在学校前天课上的知识，博主进行了整理，分析，写一篇自己的学习笔记，方便自己往后复习，并分享给大家一起学习，如有错误，请及时指点，这篇文章只讲了单链表和循环链表，后面博主学习到的知识会及时更文，希望大家喜欢，不喜勿喷，创作不易，大家点赞，关注，评论，收藏。（另外博主讲的故事纯属虚构，如有冒犯，请多多包含）
评论