数据结构预算法------链表
目录
数据结构预算法------链表
01、链表的定义
02、链表的优缺点
03、单链表的基本操作（代码实现）
04、理论知识参考文献
01、链表的定义
链表（Linked List）：一种线性表数据结构。它使用一组任意的存储单元（可以是连续的，也可以是不连续的），来存储一组具有相同类型的数据。
简单来说，链表就是实现线性表链式存储结构的基础。
链表是由链节点通过 next 指针链接而构成的，我们可以先定义一个简单的「链节点类」，再来定义完整的「链表类」。
链节点类（即 Node 类）：使用成员变量 data 表示数据元素的值，使用指针变量 next表示后继指针。
链表类（即 LinkedList 类）：使用一个链节点变量 head 来表示链表的头节点。
我们在创建空链表时，只需要把相应的链表头节点变量设置为空链接即可。
图解：
链表通过将一组任意的存储单元串联在一起。其中，每个数据元素占用若干存储单元的组合称为一个「链节点」。为了将所有的节点串起来，每个链节点不仅要存放一个数据元素的值，还要存放一个指出这个数据元素在逻辑关系上的直接后继元素所在链节点的地址，该地址被称为「后继指针 nextnext」。
02、链表的优缺点
优点：存储空间不必事先分配，在需要存储空间的时候可以临时申请，不会造成空间的浪费；一些操作的时间效率远比数组高（插入、移动、删除元素等）。
缺点：不仅数据元素本身的数据信息要占用存储空间，指针也需要占用存储空间，链表结构比数组结构的空间开销大。
03、单链表的基本操作（代码实现）
定义链节点类
#include <cstdlib>struct NODE {int data; // 数据NODE *next; // 后继};定义单链表的抽象数据结构
struct LinkList {NODE *head; //头[链表的第0个元素]bool IsEmpty(); //判断链表是否为空void Init(); // 初始化链表void HeadCreate(int c); // 插入：头插法void TailCreate(int c); // 插入：尾插法void Traverse(); // 链表迭代器void Insert(int i, int data); // 在i的位置插入一个node节点,数据为databool Delete(int i, int &e); // 删除链表中第i个位置的节点，并将数据赋值给evoid Modify(int x, int y); // 将单链表中值为x的数据改为 yvoid Replace(int i, int x); // 将i位置上的数据替换为 xint Seek(int x); // 查找单链表是否有值为x的节点，若有则返回值为x的位置，若没有则返回 -1int Count(int x);// 统计单链表节点值为x的数据的个数int Length(); // 求单链表的长度void Sort(); //链表排序NODE *Unsortfind(int x); // 无序查找bool GetElem(int i, int &e); // 取第i位置上的数据并保存在e中void Destroy(); // 销毁单链表};头插法图解
链表头部插入元素：在链表第 1个链节点之前插入值为 valval 的链节点。
先创建一个值为 value 的链节点 newNode。然后将 newNode的 next 指针指向链表的头节点 head -> next。再将链表的头节点head -> next指向 newNode。
中间位置插入节点图解
链表中间插入元素：在链表第 i个链节点之前插入值为 data的链节点。
使用指针变量 cur (代码实现中使用p) 和一个节点变量node来申请新节点的空间，并存放数据。令 cur 指向链表的头节点。沿着链节点的 next 指针遍历链表，指针变量 cur每指向一个链节点，计数器就做一次计数。当遍历到第（i-1）个链节点时停止遍历。创建一个值为 data 的链节点 node。将 node ->next 指向 cur ->next。然后令cur ->next 指向 node。
具体算法实现
/** * @brief 统计单链表节点值为x的数据的个数 * * @param x 需要对比的数据 * * @return 值为X的数量 */int LinkList::Count(int x) {NODE *p;int count = 0;p = head ->next;for (int i = 0; i < Length(); i++) {if (x == p ->data) {count++;}p = p ->next;}return count;}/** * @brief 将i位置上的数据替换为 x * * @param i 链表的节点位置 * @param y 给该节点替换的数据 */void LinkList::Replace(int i, int y) {if (i < 0 || IsEmpty() || i > Length()) return;NODE *p;p = head ->next;for (int j = 0; j < i - 1; j++) {p = p ->next;}p ->data = y;}/** * @brief 查找单链表是否有值为x的节点， * * @param x 需要对比的数据 * * @return 若有则返回值为x的位置，若没有则返回 -1 */int LinkList::Seek(int x) {NODE *p;p = head ->next;for (int i = 0; i <= Length() - 1; i++) {if (x == p ->data) {return i;}p = p ->next;}return -1;}/** * @brief 将单链表中值为x的数据改为 y * * @param x 需要查找的数据 * @param y 用于替换的数据 */void LinkList::Modify(int x, int y) {NODE *p;p = head ->next;int j = Seek(x);if (j == -1) return;for (int i = 0; i < j; i++) {p = p ->next;}p ->data = y;Modify(x, y);}/** * @brief 求单链表的长度 * * @return 链表的长度 */int LinkList::Length() {NODE *p;int length = 0;p = head ->next;while (p) {p = p ->next;length++;}return length;}/** * @brief 删除链表中第i个位置的节点，并将数据赋值给 * * @param e 被删除节点的数据 * @param i 被删除节点的位置 * * @return 删除成功返回true，否则返回false */bool LinkList::Delete(int i, int &e) {if (i < 0 || IsEmpty()) return false;NODE *p,*q;p = head ->next;for (int j = 0; (j < i - 1 ) && (p ->next != NULL); j++) {p = p ->next;}e = p ->next ->data;q = p ->next ->next;p ->next = q;if (p ->next == NULL) {return false;}return true;}/** * @brief 在i的位置插入一个node节点,数据为data * * @param data 插入节点的数据 * @param i 插入节点的位置 */void LinkList::Insert(int i, int data) {NODE *p,*node;p = head ->next;node = (NODE *) malloc(sizeof(NODE));node ->data = data;node ->next = NULL;if (i <= 0) {node ->next = head -> next;head ->next = node;return;}for (int j = 0; j < i - 1 && p ->next != NULL; j++) {p = p ->next;}node ->next = p ->next;p ->next = node;if (p ->next == NULL) {p ->next = node;return;}}/** * @brief 链表的迭代器，返回每个链表中每个NODE的值 */void LinkList::Traverse() {NODE *p;p = head ->next;//int countSize = sizeof(NODE);//printf("每个NODE的大小：%d", countSize);while (p) {printf("%5d", p->data);p = p ->next;}printf("\n");}/** * 尾插法 * @param c(count) 插入数据的数量 */void LinkList::TailCreate(int c) {if (c <= 0) return;NODE *q,*node;q = head;int x = 1;for (int i = 0; i < c; i++) {node = (NODE *)malloc(sizeof(NODE));//x = rand() % 300;node ->data = x++;node ->next = NULL;// 连接q ->next = node;q = node;}}/** * 头插法 * @param c(count) 插入数据的数量 */void LinkList::HeadCreate(int c) {if (c <= 0) return;NODE *p;int x = 1;for (int i = 0; i < c; i++) {p = (NODE *)malloc(sizeof(NODE));p ->data = x++;p ->next = NULL;// 连接p ->next = head ->next;head ->next = p;}}/** * 初始化链表 */void LinkList::Init() {head = (NODE *)malloc(sizeof(NODE));head ->next = NULL;}/** * 判断链表是否为空 */bool LinkList::IsEmpty() {if (head ->next == NULL) {return true;}return false;}最后三个实现（无序查找、查找某一个并保存在变量e中、销毁线程表）
/** * @brief 销毁单链表（将每个节点动态分配的空间释放） */void LinkList::Destroy() {if (IsEmpty()) return;NODE *p,*p_next;p = head ->next;p_next = p;int i = 1;while (p_next) {p_next = p_next ->next;printf("\n销毁前的值：%d", p ->data);if (p != NULL) {free(p);printf("\n销毁%d个节点！", i++);}printf("\n销毁后的值：%d", p ->data);p = p_next;}head ->next = NULL;printf("\n销毁成功！");}/** * @brief 取第i位置上的数据并保存在e中 * * @param e 获取到的数据 * @param i 获取的链表位置 * * @return true / false */bool LinkList::GetElem(int i, int &e) {if (i < 0 || IsEmpty() || i >= Length()) return false;NODE *p;p = head ->next;for (int j = 0; j < i - 1; j++) {p = p ->next;}e = p ->data;return true;}/** * @brief 返回节点的值为x的第一个节点的地址，无值为X节点时，返回NULL * * @param x * * @return *x / NULL */NODE *LinkList::Unsortfind(int x) {NODE *p;p = head ->next;for (int i = 0; i < Length(); i++) {if (p ->data == x) {return p;}p = p->next;}return NULL;}04、理论知识参考文献
算法通关手册（LeetCode） | 算法通关手册（LeetCode） (itcharge.cn)
本次内容到此结束，没有任何商业行为，主要用于学习，如有不正确的地方，麻烦给位大佬多多提点，鄙人必当认真改正！！！谢谢大家，祝诸位天天开心，学习进步！