🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：上一章介绍了线性表的顺序表示，但对于顺序表，其插入删除操作需要移动大量元素而浪费时间。本章将介绍解决这已缺点的另一线性表的表示形式：链表，以及链表的一些初始化、增删改查等基本操作。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第三章：线性表的链式表示
📝1️⃣链式存储结构的表示与实现
定义：结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
线性表的链式表示又称为非顺序映像或链式映像。
如何实现：通过指针来实现
📝2️⃣链式存储结构的有关术语
| 结点： | 数据元素的存储映像。有数据域和指针域两部分组成。 |
| 链表： | n个结点由指针链组成一个链表。他是线性表的链式存储映像，成为线性表的链式存储结构。 |
| 单链表： | 结点只有一个指针域的链表。 |
| 双链表： | 有两个指针域的链表。 |
| 循环链表： | 首尾相接的链表。 |
| 头指针： | 指向链表中第一个结点的指针 |
| 首元结点： | 链表中存储第一个数据元素的结点 |
| 头结点： | 链表首元节点之前的结点，数据域内只放空表标志后和表长等信息。 |
编辑
结构示意图：根据头结点可有可无分为两种形式。
编辑
空表：有头结点时，当头结点的指针域为空时，表示空表。
编辑
使用头结点的好处：
- 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无须进行特殊处理。
- 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。
头结点的数据域汇中装什么
头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。
📝3️⃣链式存储结构的优缺点
特点：
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。
优点：
- 数据元素的个数可以自由扩充。
- 插入删除等操作不必移动数据，只需修改链接指针修改效率较高。
缺点：
- 存储密度小
- 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问。
📝4️⃣单链表的定义及实现
编辑
单链表的存储结构定义
typedef struct Lnode { ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; // *LinkList为Lnode类型的指针
*注意区分指针变量和结点变量两个不同的概念
- 指针变量 p：表示结点地址 LNode *p
- 结点变量 *p：表示一个结点
编辑
📝5️⃣单链表的基本操作
初始化单链表（构造一个空表）
算法步骤：
- 生成新结点作为头结点，用头指针 L 指向头结点。
- 头结点的指针域置空。
算法描述：
Status InitList_L(LinkList &L) { L=new LNode; L->next = NULL; return OK; }
销毁单链表
Status DestroyList_L(LinkList &L) { LinkList p; while(L) { p = L; : = L->next; delete p; } return OK; }
清空单链表
Status ClearList(LinkList &L) { LinkList p,q; p = L->next; //先指向第一个结点 while(p) //没到表尾 { q = p->next; delete p; p = q; } L->next = NULL; //头结点指针域置空 return OK; }
求表长度
int ListLength_L(LinkList &L) { LinkList p; p = L->next; //p指向第一个结点 i = 0; while(p) //遍历单链表，统计结点数 { i++; p = p->next; } return i; }
判断表是否为空
int ListEmpty(LinkList &L) { //若L为空表，则返回1，否则返回0 if(L->next) { return 0; } else { return 1; } }
取值（根据位置i获取相应位置数据元素的内容）
算法步骤：
- 从第 1 个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p 初值 p = L->next。
- j 做计数器，累计当前扫描到过的结点数， j 初值为1。
- 当 p 指向扫描到的下一结点是，计数器 j 加 1。
- 当 j = i 时， p 所指向的结点就是要找的第 i 个结点。
算法描述：
Status GetElem_L(LinkList &L,int i,ElemType &e) { int j = 1; ElemType p = L->next; while(p && j<i){ //向后扫描，直到 p 指向第 i 个元素或 p 为空 p = p->next; ++j; } if(!p || j > i) return ERROR; //第i个元素不存在 e = p_>data; //取第 i 个元素 return OK; }
查找（根据指定数据获取数据所在的位置）
算法步骤：
- 从第 一个结点起，依次和e相比较。
- 如果找到一个值与e相等的数据元素，则返回其所在链表中的位置 或地址。
- 如果查遍整个链表仍未找到值与e相等的数据元素，则返回 0 或 NULL。
算法描述：
//返回L中值为e的数据元素的地址，查找失败返回NULL LNode *LocateLELem_L(LinkList L, Elemtype e) { p = L->next; while(p && p->datra != e) p = p->next; return p; } //返回L中值为e的数据元素的位置序号，查找失败返回0 int LocateLELem_L(LinkList L, Elemtype e) { p = L->next; j = 1; while(p && p->datra != e){ p = p->next; j++; } if(p) return j; else return 0; }
插入（插在第 i 个结点之前）
编辑算法步骤：
- 找到第i-1个数据元素的为位置p。
- 生成一个新结点 *s。
- 将新结点*s 的数据域置为x。
- 新结点 *s的指针域指向第 i 个结点。
- 令结点 *p 的指针域指向新结点*s。
算法描述：
//在L中第i换人元素之前插入；数据元素e Status ListInsert_L(LinkList &L, int i , ElemType e) { p = L; while( p && j < i-1) //寻找第 i-1 个结点 { p = p->L; ++j; } if( !p || j > i-1) return ERROR; s=new LNode; //创建新结点s s-> data = e; //将结点s的数据域置为e s->next = p->next; //将结点s插入L中 p->next = s; return OK; }
插入（删除第 i 个结点）
编辑
算法步骤：
- 找到第 i-1个结点的存储位置p。
- 临时保存第i个结点的地址在q中，以备释放。
- 令 p->next 指向第 i 个结点的直接后继结点。
- 将第i个结点的值保留在e中。
- 释放第i个结点的空间。
算法描述：
Status ListDelete_L(LinkList &L,int i ,ElemType e) { p = L;j=0; while( p->next && j < i-1) //找到第i个结点，并将p指向其前驱。 { p = p->next; j++; } if(!(p->next) || j > i-1 ) return ERROR; //插入位置不合理 q= p->next; //临时保存被删除结点的地址 p->next = q->next; //改变删除结点的前驱结点的指针域 e = q->data; //保存删除结点的数据域 delete q; //释放删除结点的空间 return OK; }
📝6️⃣链表的运算时间效率分析
查找
因链表只能顺序存取，即在查找是要从头指针找起，查找的时间复杂度为O(n)。
插入和删除
因线性链表不需要移动元素，只需要修改指针，一般情况下时间复杂度为O(1)。
