#|《大话数据结构》从零开始 —— 第三章（线性表之链式存储结构（单链表、静态链表、双向链表、循环链表））单链表|数据结构|链表|算法|

文章目录

链式存储结构
- 单链表
- - 单链表的读取
  - 插入删除
  - 整表创建整表删除
  - 单链表与顺序存储结构的优缺点
- 静态链表
- 循环链表
- 双向链表
- 总结

链式存储结构

为了表示每个数据 ai 与其直接后继数据元素 a_(i+1) 之间的逻辑关系，对于数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。
存储数据元素信息的域称为数据域
存储直接后继位置的域称为指针域
指针域中存储的信息称作指针或链
两部分组成的数据元素 ai 的存储映像，称为结点（Node）

文章图片

n 个结点（ai 的存储映像）链结成一个链表，即为线性表的链式存储结构

单链表上图的链表的每个结点只包含一个指针域，称单链表

链表中第一个结点的存储位置称头指针，整个链表的存取必须从头指针开始进行
最后一个结点指针为空（用 NULL 或 ^ 表示）
有时会在单链表的第一个结点前附设一个结点，称头结点。数据域可不存储信息，指针域存储指向第一个结点的指针
头指针头结点的异同：

头指针	头结点
链表指向第一个结点的指针，若链表有头结点，则为指向头结点的指针	为了操作的统一与方便设立，放在第一个元素的结点之前，其数据域一般无意义
具有标识作用，常用头指针冠以链表的名字	可像对待其它结点一样增删第一结点，统一操作
无论链表是否为空，头指针均不为空。头指针是链表的必要元素	不必要

【#|《大话数据结构》从零开始 —— 第三章（线性表之链式存储结构（单链表、静态链表、双向链表、循环链表））】

文章图片

结点由存放数据元素的数据域以及存放后继结点地址的指针域组成

文章图片

单链表的读取

时间复杂度为 O(n)
读取的主要思想：工作指针后移

插入删除

插入核心代码：s->next = p->next; p->next = s;
把 p 的后继结点改成 s 的后继结点，再把 p 的后继结点改成 s
删除核心代码：q = p->next; p->next = q->next;
把p的后继的后继结点改成p的后继结点

核心代码顺序绝对不可以调换！！！

时间复杂度都为 O(n)
对于插入删除数据越频繁的操作，单链表的优势就越明显

整表创建整表删除

创建链表是一个动态生成链表的过程，有头插法和尾插法
删除链表从第一个结点开始拆解，最后头结点指空

单链表与顺序存储结构的优缺点

存储分配方式	时间性能	空间性能
顺序存储结构用一段连续的存储单元，依次存储线性表的数据元素	查找：顺序存储结构 O(1) 单链表O(n)	顺序存储结构需要预分配空间
单链表采用链式存储结构，用一组任意的存储单元存放线性表元素	插入和删除：顺序存储结构 O(n) 单链表O(1)	单链表不需要预先分配存储空间，元素个数不受限制

#include #include using namespace std; typedef int ElemType; // 定义结点，由数据域和指针域组成 typedef struct Node { ElemType data; // 数据域 struct Node* next; // 指针域 }Node; typedef struct Node* LinkList; // 定义结点指针类型// 读取数据元素 bool GetElem(LinkList L, int i, ElemType* e) { LinkList p = L->next; int j = 1; // 遍历查找所求位置元素 while (p && j < i) { p = p->next; ++j; } // 判断是否已到链表末 if (!p || j > i) { return false; } *e = p->data; return true; }// 插入数据元素 bool ListInsert(LinkList* L, int i, ElemType e) { LinkList p, s; p = *L; int j = 1; // 遍历查找所求位置元素 while (p && j < i) { p = p->next; ++j; } // 判断是否已到链表末 if (!p || j > i) { return false; } s = (LinkList)malloc(sizeof(Node)); // 开辟新结点 s->data = https://www.it610.com/article/e; s->next = p->next; // 链接下一结点 p->next = s; // 上一结点链接本节点 return true; }// 删除数据元素 bool ListDelete(LinkList* L, int i, ElemType* e) { int j = 1; LinkList p, q; p = *L; // 查找目标结点 while (p->next && j < i) { p = p->next; ++j; } // 判断是否到链表末尾 if (!(p->next) || j > i) { return false; } q = p->next; // 总要有一个指针指向这个未释放的空间 p->next = q->next; // 上一个结点指向下一个 *e = q->data; free(q); return true; }// 创建整链表 --- 头插法 void CreateListHead(LinkList* L, int n) { LinkList p; srand((unsigned int)time(NULL)); // 创建头结点 *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; // 在头结点与第一结点之间连续插值，即头插法 for (int i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = https://www.it610.com/article/rand() % 100 + 1; p->next = (*L)->next; (*L)->next = p; } }// 创建整链表 --- 尾插法 void CreateListTail(LinkList* L, int n) { LinkList p, r; srand((unsigned int)time(NULL)); // 创建头结点 *L = (LinkList)malloc(sizeof(Node)); r = *L; for (int i = 0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); p->data = https://www.it610.com/article/rand() % 100 + 1; r->next = p; r = p; } r->next = NULL; }// 删除整表 bool DeleteList(LinkList* L) { LinkList p, q; p = (*L)->next; // 找到第一结点，从此处开始向后拆解 while (p) { q = p->next; free(p); p = q; } (*L)->next = NULL; // 头结点指针域置空 return true; }// 打印整表 void PrintList(LinkList L) { LinkList p = L->next; while (p) { cout << p->data << " "; p = p->next; } cout << endl; }int main() { LinkList L; CreateListTail(&L, 10); PrintList(L); return 0; }

静态链表

使数组由两个数据域组成，data 和 cur 。数组的每一个下标都对应一个 data 和 cur 。数据域 data 用于存放数据元素；游标 cur 相当于单链表中的 next 指针，存放后继元素的下标
优缺点

优点	缺点
在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中，插入删除元素需要移动大量元素的缺点	没有解决连续存储分配带来的表长难以确定的问题
	失去了顺序存储结构随机存取的特性

静态链表其实是为了给没有指针的高级语言设计的一种能实现单链表能力的方法

感觉书上的代码自己写来写去有点问题，就不贴出来了，后面用C++实现的时候自己再捯饬捯饬看下能不能解决，然后再贴出来

循环链表

将单链表中终端节点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表（circular linked list）

文章图片

与单链表的主要差异：循环的判断条件，原来是判断 p->next 是否为空，而循环链表是判断 p->next 是否为头结点
使用指向终端节点的尾指针可以以 O(1) 的时间查找开始结点和终端节点

文章图片

// 合并A、B两表 p = rearA->next; // 保存 A 表的头结点 rearA->next = rearB->next->next; // 将本指向 B 表的第一个结点赋值给 A 表终端结点 rearB->next = p; // 将 A 表的头结点赋值给 B 表的终端节点 free(p);

双向链表