前言
今天，我们来学习，数据结构中的链表
链表是什么
链表，就是多个结构体变量之间，通过结构体指针连接在一起的一种数据结构
提示：
本篇文章主要讲解动态链表，对于静态链表不做过多介绍
链表的分类
链表可分为静态链表和动态链表
静态链表
只是初步了解，更详细的操作（比如插入节点、删除节点）在这篇文章中不做说明
静态链表，实际上就是一个结构体数组
分配一整片连续的内存空间，各个结构体变量集中安置，逻辑结构上相邻的数据元素，存储在指定的一块内存空间中，数据元素只允许在这块内存空间中随机存放，这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构
下面，给出一段例子
这就是静态链表的定义和初始化
#include<iostream> using namespace std; struct Node { int data;//数据域 int next;//指针域 //注释1 //静态链表的节点是索引值 不是结构体指针 }; int main() { struct Node n[10]; for (int i = 0; i < 10; i++) { n[i].data = i; n[i].next = i + 1;//每个节点的下一个节点位当前索引值+1 } n[9].next = -1; //注释2 return 0; }
注释1：
相信大家都知道，链表这种数据结构，前面一部分存储的是数据，后面一部分存储的是指向下一个变量（一般称为节点）的指针
存储数据的区域，就称为数据域
存储指针的区域，就称为指针域
注释2：
n[9].next = -1;
这行代码的意思是：将这个链表的最后一个节点 的指针（索引值）赋为-1
为什么要这么做呢？
首先：
当我们已经遍历到最后一个节点时，没有下一个节点了，那么此时的next指针指向的就是一个随机值，这可能会导致发生不可预期的行为，比如程序崩溃
其次，将最后一个节点的指针赋为-1，有便于我们检查对于链表的遍历是否结束，这一点在后面会详细说明
最后，当我们在处理链表的最后一个字节时，可以通过-1来直接找到它
静态链表的特点
静态链表需要预先开辟一块空间来存储，并且，静态链表的大小是固定的，（毕竟它没用到动态内存分配 没法变大），以及，静态链表在存储时，在内存中是连续存储的
静态链表也有一些好处，比如：
静态链表可以直接通过索引访问，不需要指针（好像这二者差不多）
动态链表
接下来，就进入到我们这篇文章的重头戏：动态链表了
要实现动态链表，有两个东西比较重要：
动态内存的申请，是动态链表之所以被称为动态链表的原因
模块化设计，可以使代码可读性和简洁性提升（当然，都写在一起也不是不行…）
下文为了便于理解，对于数据域只使用一个int类型的变量
动态链表的实现思路
本篇文章将动态链表的实现分为五个步骤，
1.创建链表表头
2.创建节点
3.插入节点
4.删除节点
5.打印链表
前四步比较关键，最后一步一般用于测试自己创建的链表是否符合自己的预期
创建链表表头
要创建链表，我们首先需要创建一个表头，来指向整个链表，可以将表头理解为第一个节点，
想指向一个结构体变量（也就是节点），那表头应该是结构体指针c
问题来了，如何把一个结构体指针，变成结构体变量呢
这时候，我们就要学习动态内存申请，即malloc函数
（注意：使用new也可以，会在本节的末尾附上使用new创建动态链表的代码）
给出一个示例来说明如何创建头节点
struct Node* createList() { struct Node* headNode = (struct Node*)malloc (sizeof(struct Node)); // //用malloc申请内存 headNode->next = nullptr; //注释3 return headNode; }
注释3：
有的同学可能会有疑问，为什么要将头节点初始化为空指针
首先，现在链表里只有一个变量（节点），不初始化成空指针，那不就变成野指针了
其次，初始化成空指针的话，当我们后续无论是查找头节点还是继续插入新的节点的时候，都是能很轻松的找到头节点
创建节点（一个）
/*
创建节点的这个函数
/*/
下面给出一个例子：
将创建节点的内容模块化城createNode函数
struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; //传入数据 newNode->next = nullptr; //注释4 return newNode; }
注释4：
类似的，在创建新的节点时，将next赋值为空指针，
是因为这个新节点并不知道链表中下一个节点是什么，所以只能赋值为空指针
插入节点
对于插入，有三种方式：头插法，尾插法，指定位置插入
下面给出一个使用头插法例子：
将创建节点的内容模块化城insertNodeByHead函数
(代码中给出了相应的注释）
void insertNodeByHead(struct Node* headNode, int data) { struct Node* newNode = createNode(data); //创建插入的节点 newNode->next = headNode->next; //修改指针域 headNode->next = newNode; //指向要插入的数据 }
注释5：
在编写创建节点和插入节点的时候，我感觉这两步有一些联系，在此说明一下：
这两个步骤通常是相互关联的，因为通常我们需要先创建一个新的节点，然后将其插入到链表中。
删除节点
下面给出一个例子：
将创建节点的内容模块化城deleteNodeByAppoin函数
(代码中给出了相应的注释）
//删除节点 void deleteNodeByAppoin(struct Node* headNode, int posData) //headNode只是一个传入的参数名，不是真的头节点 不要弄混 //posData是要删除的数据 { struct Node* posNode = headNode->next; struct Node* posNodeFront = headNode; //分别对于链表是否为空和posData是否存在进行判断 if (posNode == nullptr) { cout << "链表为空 操作错误" << endl; } else { while (posNode->data != posData) //遍历查找 { posNodeFront = posNode; posNode = posNodeFront->next; if (posNode == nullptr) { cout << "未找到要删除的数据" << endl; return; } } posNodeFront->next = posNode->next; //用free函数释放内存 free(posNode); } }
遍历打印链表
通过遍历打印链表
void PrintList(struct Node* headNode) { struct Node* pMove = headNode->next; while (pMove) //当pmove不为空指针时 持续遍历 //这里就可以联系到创建节点时，为什么要将next初始化为空指针 //巧妙 妙 //while这里还能这么写 学到了 学到了 { cout << pMove->data; pMove = pMove->next; } cout << endl; }
主函数
int main() { struct Node* list = createList(); insertNodeByHead(list, 1); insertNodeByHead(list, 2); insertNodeByHead(list, 3); PrintList(list); return 0; }
运行结果：
注释6：
因为用的是头插法，所以先插入的变量在遍历输出的时候，在后面
完整代码
#include<iostream> using namespace std; struct Node { int data; struct Node* next;//静态链表的节点是索引值 不是结构体指针 }; //创建表头 struct Node* createList() { struct Node* headNode = (struct Node*)malloc (sizeof(struct Node)); //用malloc申请内存 headNode->next = nullptr; //注释3 return headNode; } //创建节点（一个） struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; //传入数据 newNode->next = nullptr; return newNode; } //插入节点 void insertNodeByHead(struct Node* headNode, int data) { struct Node* newNode = createNode(data); //创建插入的节点 newNode->next = headNode->next; //修改指针域 headNode->next = newNode; //指向要插入的数据 } //删除节点 void deleteNodeByAppoin(struct Node* headNode, int posData) //headNode只是一个传入的参数名，不是真的头节点 不要弄混 //posData是要删除的数据 { struct Node* posNode = headNode->next; struct Node* posNodeFront = headNode; //分别对于链表是否为空和posData是否存在进行判断 if (posNode == nullptr) { cout << "链表为空 操作错误" << endl; } else { while (posNode->data != posData) { posNodeFront = posNode; posNode = posNodeFront->next; if (posNode == nullptr) { cout << "未找到要删除的数据" << endl; return; } } posNodeFront->next = posNode->next; //用free函数释放内存 free(posNode); } } //遍历打印链表 void PrintList(struct Node* headNode) { struct Node* pMove = headNode->next; while (pMove) //当pmove不为空指针时 持续遍历 //这里就可以联系到创建节点时，为什么要将next初始化为空指针 //巧妙 妙 //while这里还能这么写 学到了 学到了 { cout << pMove->data; pMove = pMove->next; } cout << endl; } int main() { struct Node* list = createList(); insertNodeByHead(list, 1); insertNodeByHead(list, 2); insertNodeByHead(list, 3); PrintList(list); return 0; }
使用new
使用new的话，只需要在创建节点和插入节点那里修改一下就可以了
Node* createList() { Node* headNode = new Node; headNode->next = nullptr; return headNode; } Node* createNode(int data) { Node* newNode = new Node; newNode->data = data; newNode->next = nullptr; return newNode; }
实际项目中可能会遇到的小问题
在编写如通讯录、图书馆信息管理系统的时候，data一般都是结构体，那么在输入的时候，就可能会遇到输入完数字，再输入字符串，
那么就存在需要清空缓冲区的问题
此时，我们可以用setbuf函数
使用格式如下：
setbuf(stdin,NULL);清空缓冲区函数
（在此只是介绍一下，作者也不会）
结语
算是初步把链表中的静态和动态链表了解和学习了一下，希望这篇文章对你有帮助，我们下篇文章见~~
