考研复习 Day13| 数据结构与算法--线性表

一、线性表的定义和基本操作1.1 线性表的定义线性表由n(n≥0)个相同数据类型的元素组成的有限序列。表示形式L (a₁, a₂, ···, aᵢ, aᵢ₊₁, ···, aₙ)术语说明n表长n0 时为空表a₁表头元素唯一的“第一个”元素aₙ表尾元素唯一的“最后一个”元素直接前驱除第一个元素外每个元素有且仅有一个直接后继除最后一个元素外每个元素有且仅有一个线性表的特点特点说明元素个数有限—逻辑上的顺序性元素之间存在明确的先后次序元素不可分割每个元素是独立单位数据类型相同每个元素占有相同大小的存储空间抽象性只讨论逻辑关系不考虑具体内容注线性表是逻辑结构顺序表和链表是存储结构二者属于不同层面的概念不要混淆。1.2 线性表的基本操作操作描述InitList(L)初始化表构造空线性表Length(L)求表长返回元素个数LocateElem(L, e)按值查找返回元素位置GetElem(L, i)按位查找获取第i个元素值ListInsert(L, i, e)插入操作在第i个位置插入eListDelete(L, i, e)删除操作删除第i个元素并用e返回PrintList(L)输出操作按顺序输出所有元素Empty(L)判空操作DestroyList(L)销毁操作释放内存空间注① 基本操作的具体实现取决于存储结构② 符号表示C引用调用C语言中可通过指针实现第二部分顺序表线性表的顺序存储2.1 顺序表的定义顺序表用一组地址连续的存储单元依次存储线性表中的数据元素逻辑上相邻的元素在物理位置上也相邻。存储地址计算设顺序表L的起始地址为LOC(A)每个元素占sizeof(ElemType)字节则第i个元素的存储地址为LOC(aᵢ) LOC(A) (i-1) × sizeof(ElemType)随机存取可在 O(1) 时间内直接访问任意位置的元素。存储结构描述1静态分配#define MaxSize 50 typedef struct { ElemType data[MaxSize]; int length; } SqList;静态分配时数组大小在编译时固定空间占满后无法插入新元素。2动态分配#define InitSize 100 typedef struct { ElemType *data; int MaxSize, length; } SeqList;C语言动态分配L.data (ElemType*)malloc(sizeof(ElemType) * InitSize);C动态分配L.data new ElemType[InitSize];注意动态分配仍然是顺序存储结构支持随机存取只是存储空间可动态调整。顺序表的优缺点优点缺点① 随机访问O(1)时间① 插入删除需移动大量元素O(n)② 存储密度高无额外指针开销② 需要连续存储空间不够灵活2.2 顺序表上基本操作的实现考点追踪顺序表上操作的时间复杂度分析20231. 顺序表的初始化静态分配void InitList(SqList L) { L.length 0; }动态分配void InitList(SeqList L) { L.data (ElemType*)malloc(InitSize * sizeof(ElemType)); L.length 0; L.MaxSize InitSize; }2. 插入操作可以就像一个排好队的一排人要往其中某个位置插入一人新元素因此在插入位置后面的人要从尾部开始依次退后不然就会踩脚导致插入数据出现错误在第i个位置1≤i≤L.length1插入新元素e。bool ListInsert(SqList L, int i, ElemType e) { if (i 1 || i L.length 1) return false; if (L.length MaxSize) return false; for (int j L.length; j i; j--) L.data[j] L.data[j - 1]; L.data[i - 1] e; L.length; return true; }时间复杂度分析情况移动次数时间复杂度最好表尾插入in10O(1)最坏表头插入i1nO(n)平均n/2O(n)注意位序从1开始数组下标从0开始注意转换。3. 删除操作删除第i个位置1≤i≤L.length的元素用e返回其值。bool ListDelete(SqList L, int i, ElemType e) { if (i 1 || i L.length) return false; e L.data[i - 1]; for (int j i; j L.length; j) L.data[j - 1] L.data[j]; L.length--; return true; }时间复杂度分析情况移动次数时间复杂度最好删除表尾in0O(1)最坏删除表头i1n-1O(n)平均(n-1)/2O(n)4. 按值查找顺序查找int LocateElem(SqList L, ElemType e) { for (int i 0; i L.length; i) if (L.data[i] e) return i 1; return 0; }时间复杂度平均比较次数 (n1)/2 →O(n)第三部分线性表的链式表示3.1 单链表的定义考点追踪单链表的应用2009、2012、2013、2015、2016、2019结点结构结点类型定义typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;头指针与头结点类型空表判断带头结点L-next NULL不带头结点L NULL引入头结点的优点方便操作操作统一性首部插入/删除与其他位置逻辑一致空表与非空表处理统一头指针始终非空3.2 单链表上基本操作的实现注默认链表带头结点1. 单链表的初始化bool InitList(LinkList L) { L (LNode*)malloc(sizeof(LNode)); L-next NULL; return true; }2. 求表长int Length(LinkList L) { int len 0; LNode *p L-next; while (p ! NULL) { len; p p-next; } return len; }时间复杂度O(n)3. 按序号查找LNode *GetElem(LinkList L, int i) { LNode *p L; int j 0; while (p ! NULL j i) { p p-next; j; } return p; }4. 按值查找LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) p p-next; return p; }时间复杂度O(n)5. 插入结点操作考点追踪单链表插入操作的过程2016、2024bool ListInsert(LinkList L, int i, ElemType e) { LNode *p L; int j 0; while (p ! NULL j i - 1) { p p-next; j; } if (p NULL) return false; LNode *s (LNode*)malloc(sizeof(LNode)); s-data e; s-next p-next; // 1 新结点指向原后继 p-next s; // 2 前驱指向新结点 return true; }重要步骤①和②的顺序不可颠倒否则会丢失后继地址。时间复杂度O(n)主要开销在查找前驱。若已知结点指针后插操作O(1)。前插操作的技巧O(1)时间将新结点*s插入目标结点*p之后再交换*p与*s的数据域逻辑上等效于前插s-next p-next; p-next s; // 交换数据域 ElemType temp p-data; p-data s-data; s-data temp;6. 删除结点操作bool ListDelete(LinkList L, int i, ElemType e) { LNode *p L; int j 0; while (p-next ! NULL j i - 1) { p p-next; j; } if (p-next NULL) return false; LNode *q p-next; e q-data; p-next q-next; free(q); return true; }时间复杂度O(n)删除给定结点*p的技巧O(1)时间不能用于尾结点将*p后继结点的数据值复制到*p中然后删除其后继结点。LNode *q p-next; p-data p-next-data; p-next q-next; free(q);7. 头插法建立单链表LinkList List_HeadInsert(LinkList L) { LNode *s; int x; L (LNode*)malloc(sizeof(LNode)); L-next NULL; scanf(%d, x); while (x ! 9999) { s (LNode*)malloc(sizeof(LNode)); s-data x; s-next L-next; L-next s; scanf(%d, x); } return L; }每插入一个结点O(1)总时间复杂度O(n)。元素顺序与输入顺序相反。8. 尾插法建立单链表LinkList List_TailInsert(LinkList L) { int x; L (LNode*)malloc(sizeof(LNode)); LNode *s, *r L; scanf(%d, x); while (x ! 9999) { s (LNode*)malloc(sizeof(LNode)); s-data x; r-next s; r s; scanf(%d, x); } r-next NULL; return L; }附设尾指针时间复杂度O(n)。元素顺序与输入顺序一致。类比CSTL库中的vector的push_back尾插操作。3.3 双链表结点类型定义typedef struct DNode { ElemType data; struct DNode *prior, *next; } DNode, *DLinkList;插入操作在结点p之后插入s考点追踪双链表中插入操作的实现2023s-next p-next; // 1 p-next-prior s; // 2 s-prior p; // 3 p-next s; // 4步骤①必须在步骤④之前否则会丢失后继地址。这让我想到了一句话干事之前要先安排好后路即先要指向后继结点防止丢失后继地址也就是步骤1删除操作删除结点p的后继q考点追踪双链表中删除操作的实现2016p-next q-next; q-next-prior p; free(q);3.4 循环链表循环单链表尾结点的next指向头结点判空条件L-next L从任意结点出发可遍历整个链表考点追踪循环单链表中删除首元素的操作2021循环双链表头结点的prior指向尾结点尾结点的next指向头结点3.5 静态链表用数组模拟链式存储指针用数组下标游标表示。#define MaxSize 50 typedef struct { ElemType data; int next; // 下一个元素的数组下标 } SLinkList[MaxSize];结束标志next -13.6 顺序表和链表的比较比较维度顺序表链表存取方式随机存取 O(1)顺序存取 O(n)逻辑与物理结构逻辑相邻⇔物理相邻逻辑相邻≠物理相邻按值查找无序O(n)有序O(log₂n)O(n)按序号查找O(1)O(n)插入/删除需移动约一半元素 O(n)修改指针 O(1)已知位置空间分配需预分配容量按需扩展但每结点有指针开销存储密度高1低1选择建议场景推荐结构规模稳定、以随机访问为主顺序表动态性强、频繁插入删除链表思考1. 顺序表 ≈ 数组连续内存、随机访问、插入删除慢——就是它的全部特点。2. 链表每个结点“拿着”下一个结点的地址。就像寻宝游戏每张纸条写着下一个线索的位置。尾插法莫名得让我想到了“人体蜈蚣”《十宗罪》看多了3. 头结点的意义 ≈ 哨兵在链表头部加一个不存数据的“哨兵”让空链表和非空链表的操作统一减少边界判断。这和编程中在数组前后加“哨兵”简化循环的逻辑是一样的。4. 类比学习学习这些数据结构时让我很容易地就想到了CSTL库中已封装好的listvector等其他容器其实本质是同一套只不过C中的更方便使用。注以上内容参考 2027年数据结构考研复习指导 王道论坛 组编其中有一些个人想法如有任何错误或不妥欢迎各位大佬指出如果各位有一些有意思的想法也可以和我交流一下~感谢明日计划栈和队列与数组