[笔记]指针与单向链表
前言：妈的老子终于写到链表来了！！！！进入数据结构了！！！卧槽我好想快点写完然后写Linux啊！！！！此文引用了CSDN的部分文章，进行整理，侵权立删
本文重点，请认真阅读！
为什么要使用链表
在未学习链表时，我们常用的存储数据的方式无非就是数组。使用数组存储数据的好处就是查询快，但是它的弊端也很明显：
- 使用前需声明数组的长度，一旦声明长度就不能更改
- 插入和删除操作需要移动大量的数组元素，效率慢
- 只能存储一种类型的数据.
而链表则可以实现以上这些数组所不具备的功能，此时引入了结构体来实现创建链表的操作。
链表的特点：
- n个节点离散分配
- 每一个节点之间通过指针相连
- 每一个节点有一个前驱节点和一个后继节点
- 首节点没有前驱节点，尾节点没有后继节点
首先先定义一个简单的结构体
struct link
{
int data;//声明数据域
struct link* p; //定义指针域，存储直接后继的节点信息
};数据域的内容可以自己指定，指针域用来存放下一个节点的地址。
单向链表：只能单方向进行（补充笔记）
首节点：存放第一个有效数据的节点
头节点：在单链表的第一个结点之前附设一个结点，它没有直接前驱，称之为头结点，头结点的数据域可以不存储任何信息，指针域指向第一个节点（首节点）的地址。头结点的作用是使所有链表（包括空表）的头指针非空
头指针：指向头节点的指针
尾节点：存放最后一个有效数据的节点
尾指针：指向尾节点的指针
这张图可以全部说明单向链表惹
其实在咱们学习结构体自引用的时候就接触到了链表 ，只不过在自引用的同时多出了头指针。在等待用户输入值前，头指针指向空，待用户输入值后，头指针指向该节点，判断该结点的指针域是否还有数据，若为NULL，则将它设为尾结点。
每一次的添加数据，指针都将在堆内申请一片对应结构体的内存空间，将此次存储的值存入此内存空间内，由于在堆内，程序结束之前，不释放会会一直存在，在增改删查里边就很好理解了：利用循环遍历链表，实现不同的操作
结构体一般为全局变量类型，因为在实现不同功能的时候，都需要调用它，结构体分为数据域和指针域两个区域，利用指针申请节点
当类型名过长时，一般使用typedef为结构体创建别名，方便调用
还是利用代码讲解通俗易懂：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
/*------------声明功能函数----------------*/
void insere_func(void);
void sort_func(void);
void delete_func(void);
void display_func(void);
void modify_func(void);
void anykey_func(void);
/*-----------创建结构体与链表节点----------*/
struct student
{
char name[20];
int score;
struct student* next;
};
struct student* ptr,
* head,
* current,
* prev;
/*---------------定义主函数----------------*/
int main()
{
char option1;
/*定义头指针，头指针指针域指向NULL*/
head = (struct student*)malloc(sizeof(struct student));
head->next = NULL;
/*创建一个死循环*/
while (1)
{
printf("\n");
printf("***********************\n");
printf("1.插入\n");
printf("2.删除\n");
printf("3.查看\n");
printf("4.修改\n");
printf("5.退出\n");
printf("***********************\n");
printf("请输入序号后按下回车");
option1 = _getche();
switch (option1)
{
case '1':
insere_func();
break;
case '2':
delete_func();
break;
case '3':
display_func();
break;
case '4':
modify_func();
break;
case '5':
printf("欢迎使用\n");
return 0;
}
}
}
/*---------------定义功能函数-------------------*/
/*添加是以分数的高低加以排序*/
void insere_func(void)
{
char s_temp[4];
ptr = (struct student*)malloc(sizeof(struct student));
printf("\n");
printf("Student name:");
gets(ptr->name);
printf("Student score:");
gets(s_temp);
ptr->score = atoi(s_temp);
prev = head;
current = head->next;
while ((current != NULL) && (current->score>ptr->score))
{
prev = current;
current = current->next;
}
ptr->next = current;
prev->next = ptr;
printf("添加成功\n");
}
void delete_func(void)
{
char del_name[20], ans;
printf("删除学生姓名：");
gets(del_name);
prev = head;
current = head->next;
while ((current != NULL) && (strcmp(current->name, del_name) != 0))
{
prev = current;
current = current->next;
}
if (current != NULL)
{
printf("是否确定删除（Y/N）");
ans =_getche();
if (ans == 'Y' || ans == 'y')
{
prev->next = current->next;
free(current);
}
}
else
{
printf("没找到关于%s的信息", del_name);
}
}
void modify_func(void)
{
char n_temp[20], s_temp[4];
printf("需要调整的学生姓名：");
gets(n_temp);
current = head->next;
while ((current != NULL) && (strcmp(current->name, n_temp)) != 0)
{
prev = current;
current = current->next;
}
if (current != NULL)
{
printf("\n");
printf("\n*****************************\n");
printf("学生姓名：%s\n", current->name);
printf("学生分数：%d\n", current->score);
printf("\n*****************************\n");
printf("请输出新的分数：%d");
gets(s_temp);
current->score = atoi(s_temp);
printf("修改后：\n");
printf("学生姓名：%s\n", current->name);
printf("学生分数：%d\n", current->score);
}
else
{
printf("未找到学生信息\n");
}
}
void display_func(void)
{
int count = 0;
if (head->next == NULL)
{
printf("没有记录学生");
}
else
{
printf("\n");
printf("\tNAME\tSCORE\n");
printf("-------------------\n");
current = head->next;
while (current != NULL)
{
printf("\t%-10s\t%3d\n", current->name,current->score);
count++;
current = current->next;
if (count % 20 == 0)
{
_getch();
}
}
printf("-------------------\n");
printf("总共找到%d条学生记录", count);
}
}代码较长，我们一个函数一个函数的讲，头文件和函数前置声明就不做剖析了
程序定义了一个结构体：
- 结构体类型为student（数据域）
- name为成员，char数组类型（数据域）
- socre为成员，int类型（数据域）
- next为结构体自引用，为结构体指针类型（指针域）
随后结构体又定义了四个指针变量：看图
我们给这四个指针做一个功能的分析：
- ptr：用于创建新的节点
- head：用于指向头结点
- current：用于操作下一个节点
- prev：用于操作当前节点
进入正题：
option1用于输入字符，选择功能调用函数，这个不做详细讲解
重点到它为head分配了一片student结构体的内存，并且将head的指针域指向为NULL，这时head指向的这片区域形成头结点
这时程序中抽象为图
当我们输入1时，执行insere_func();函数，这个函数是个无返回值，无参数的函数，只能用于实现功能！我们继续剖析这个函数：
我们先看函数前部分，这儿定义了一个char类型的数组s_temp咱们不管它，输入字符用的
第一次：
重点到ptr，这儿它为ptr申请了一段结构体指针类型的内存空间！
ptr = (struct student*)malloc(sizeof(struct student));
这时咱们再往下看
- 这时程序要求用户输入，分别存储进ptr的数据域中的成员：name数组与score
- 假设我们输入的为：Axuan，99
- 如下图：
输入完成后，这时ptr所指向的内存是有数据的，我们来看下面这段语句
这时将prev指向头结点的首地址，current指向头结点的指针域，如下图
在这儿比较绕了，深度剖析一下，current和prev均用于操作头结点。不同之处是prev用于操作当前节点，current用于操作下一个节点
我们来看下面的语句：
执行循环有两个要求，第一个是在头结点后有数据，第二个要求是首元节点中的score数值要大于新节点的score，显然程序的定义是头节点不存放数据，那么第一次输入，头节点是没有连接新的节点的
继续看下一个，这时将新的节点插入进去
- 第一步：将新节点的指针域指向需要插入位置的后置节点
- 第二步：将新节点的前置结点的指针域指向新节点
先看第一句，如图：
由于是第一次输入，头节点后是没链接节点的，所以current所指向为空，这时需要插入新的节点，所以将新节点的指针域指向需要插入位置的后置节点，但是后边没得了，就指向了NULL
再看第二句：
prev->next=ptr，当新节点的指针域操作完毕后，我们需要将需要插入位置的前置节点的指针域指向新节点。
红色线条是最后执行的！到这儿第一次的输入就完毕了
线条太多？我们把线条全部擦一下：
这样我们可以理解了吧！
第二次：
这时主函数中的while是一个死循环，在执行了第一次insere_func();函数后，再次执行！
除了ptr所指向的内存是因为我们动态分配，存放于堆内，其他的数据：s_temp作为一个局部变量在第一次执行结束后已经释放
那么我们这是ptr依旧是指向刚刚那片内存，但是！！它仅仅是指向，要明白，ptr是一个指针，指针是一个变量，它的值是可以改变的！！！
在这之前，它的值是刚刚分配的那片内存的地址！！我们没有释放！！也就是说，在程序结束之前，第一次的数据一直会保存于那片内存！！
再一次的定义了一个s_temp变量后，我们又到了创建新节点的这一步
看图：
看到这粉嫩的小箭头了没（它再一次的重复之前的动作分配了结构体大小的内存，并交给ptr管理）ptr指向了刚刚分配的那段内存！！
这时继续重复刚刚输入的数据，我们这次输入Bxuan，105
我们来看语句：
prev继续指向头节点，current继续指向头节点的指针域
这时进入循环，由于有了第一次创建与链接，这时头结点后是有链接节点的
但第二个条件不满足，current管理的是首元结点（第一组），第一组成员score小于第二组score，所以不执行循环（程序开头有个注释：/添加是以分数的高低加以排序/）
直接到下面的：
不满足循环，就让这个结点插入到头结点后，先让新结点链接后置节点，让新结点的指针域指向后置节点
在让当前节点的指针域指向新节点
为了更加易懂，我加上了第一组第二组
prev->next=ptr，由于第二组分数是大于第一组分数的，所以这儿让第二组成为首元节点，插入到第一组和头结点之间
到这时，第二组的添加也完成了，我们继续把图片整理下
有没有像一个小火车！~一节车厢连着一节车厢！
第三次
经过前面两次，最后一次我就直接到输入数据这儿开讲了
假设我们再次输入Cxuan，100
这儿又为ptr分配了一片同样的内存，然后将数据载入进去
一样没变，prev管理着头结点，current管理着首元节点
这时要注意了，current不为NULL，且100要小于105，进入循环
这时将两个指针向后移动，分别管理下一个结点和下一个结点的指针域
prev管理了头结点后的节点，current管理了prev的指针域
然后再次进行循环判断，这时current还是不为空，它指向第一组，头指针取到current->score就是第一组中的score作比较，结果是100>99则不执行循环！找到了正确的插入位置
然后进行下一语句：
pte->next是第三组的指针域，让他等于第二组的指针域
prev->next=ptr，然后第二组的指针域，让他指向第三组
最后我们再一次的整理！让各位了解的更加透彻
注意：内存不是连续的！
第一函数总结：
第一个函数实现了添加以及排序功能，这排序是不是很熟悉？这就是最常用最简单的插入排序，拿出一个数，对后面的每一个数做比较，如果满足，则交换两者位置，如果不满足，则将这个数放到前数后面。
与之前学的相比，之前利用数组实现是顺序结构，这次只不过利用链式结构实现，实现的原理就是在prev与current指针上，一个管理当前结点，一个管理后置节点
通俗点说就是操作指针域实现各项功能
prev作用于修改当前节点，current作用于修改下一节点！
为什么头结点数据域内不存储数据，因为头节点用于相邻其他节点，打个比方来说，头节点就和火车头一样，头结点可以使用，只是在链表节点的插入，删除操作中极为不便，尤其是双向链表，逻辑通用性不强，处理不好很容易出错
对头指针以及头节点的疑问请看：头指针与头结点补充笔记
while循环的作用是一直在寻找正确的节点进行插入，并让current指向它，如果current指向的节点满足条件，则通过prev进行修改这个节点，通过current修改下一节点
学习到这里，我对单向链表有了一个大致的了解，通过其他功能函数学习逐渐完善！
功能函数（删除节点）
我们继续着结构体声明，定义，主函数定义完头指针，头结点后，录入函数输入数据后，接上图做讲解
先看代码：
首先程序定义了两个char类型的元素，一个del_name[20]为数组，ans为普通变量，然后使用gets进行输入数据
prev指向头，current指向 头指针域，从头开始，到这里是否对头节点有点模糊的理解了？
假设，我们要删除Cxuan这个数据，这是通过名字来遍历链表，符合要求的时候执行循环体内的删除
当current->next与输入的字符串相等的时候，就不执行，如果不相等，则：
移至下一个节点，我们按图来看，不满足条件，则将指针移到下一个节点，依旧是判断current所指向的区域
再进入循环，current->name是Cxuan
则不满足条件，跳出循环
执行if语句
当我们确定删除后
prev->next就指向current->next了，我们用图了解它的运作情况
因为要删除包含Cxuan的节点，则要将Cxuan之前的节点与之后的节点相邻，按照图上来说，就是将第三组清楚，将第二组与第一组相邻
此时current还是指向第一节点的指针域，指向第三组，然后free（current）
去释放这段内存，那么就完成了删除的工作
这时这一步也就算完成了！
整体简单来说就是，先将current指向链表的第一个存放有数据的节点，接着利用while循环找出欲删除的节点，将prev指向current节点的下一个节点，并回收current节点
其实理解并不难，current指针一直在遍历链表，从头节点的指针域开始遍历，再让prev指向刚刚走过的节点，进而得以控制两节点！
功能函数（修改节点）
我们继续着结构体声明，定义，主函数定义完头指针，头结点后，录入函数输入数据后，删除一个数据，接上图做讲解
此时程序当中的走向如图所示，我们看代码：
先定义了两个数组，第一个数组我们可以从代码知道用于查找，第二个数组我们可以知道是用于存放临时数据
一样，current指向头结点的指针域，指向第一节点：
然后利用while循环来遍历链表，找到符合条件的节点，假设我们存入n_temp中的值为Axuan
进入判断条件，都满足，则进入循环
将prev和current移至下一个节点
再次进入循环，这时strcmp判断两字符串相等，则不进入循环，进入下一语句
这时你需要输入新的数据载入临时变量s_temp中，再将他转换十进制整型（atoi）存入current此时指向节点的score成员中去
这时s_temp的值会替换掉原有的值，假设我们输入78
修改后：
就完成了数据的修改
功能函数（遍历节点）
这应该是一个最简单的了，我们接着上图继续讲解
然后看代码：
这儿首先判断了头节点后节点是否存在数据，咱们是有数据的，就进入下一段，三个打印就不说了
current=head->next，这时我们可爱的current指针又登场了，它继续指向第一节点
然后进入while循环遍历链表：
输出节点内的成员后，count作为计数变量，自增一位，然后指针指向下一节点继续进行循环
如果存放到20个节点后结束运算，这一步可有可无，这儿就不细讲了。运行图：
到这儿对单向链表已经有了一个简单的理解，咱们进入双向链表