冯毅《数据结构》ch-1

Chapter02·LinearList数据结构第二章线性表冯毅|计算机科学与技术专业核心课程Contents本章内容框架线性表的基本理论、存储结构与典型应用01线性表基本概念与ADT定义02顺序存储结构及其实现03链式存储结构及其实现04线性表的典型应用CHAPTER01线性表基本概念与ADT定义从逻辑结构到抽象数据类型的完整认知DATASTRUCTURE线性表的定义与结构特点线性表是n(n≥0)个数据元素的有限序列，元素间存在一对一的线性关系。每个元素（除首尾）都有唯一的直接前驱和直接后继，这种"前驱-后继"的链式关系是线性结构区别于树、图等非线性结构的根本特征。01数学定义：线性表是n个数据元素a₁,a₂,...,aₙ的有限序列，n称为表长度，n=0时为空表。元素之间具有确定的先后次序关系，构成一个逻辑上的线性序列。n≥002结构特点：a₁无前驱，aₙ无后继；中间元素aₖ有唯一前驱aₖ₋₁和唯一后继aₖ₊₁。这种一对一的邻接关系保证了线性结构的简单性和可操作性。一对一关系03元素类型：可以是简单类型（整数、字符）或复杂类型（记录、对象），如航班信息表中的每条航班记录。同一线性表中所有元素必须具有相同的数据类型。简单/复杂类型04位序概念：元素aᵢ在线性表中的位置称为位序，位序从1开始计数，是后续操作的基础。位序反映了元素在表中的逻辑位置，与物理存储位置可能不同。从1开始计数CHAPTER01·DATASTRUCTURE线性表的生活实例线性表广泛存在于日常数据管理场景中：学生学籍表、职工档案表、图书馆书目表、医院病历表等都是线性表的具体应用。理解这些场景中的数据操作需求（增删改查），是选择合适存储结构的前提。典型应用场景01学生学籍表——按学号存储学生信息，支持插入新生、删除毕业生、查找学生、修改成绩增删改查02图书馆书目表——按索书号存储图书信息，支持新书入库、图书借出、书目查询、信息更新索书号03航班信息表——按航班号存储航班记录，每条记录包含目的地、起飞时间、票价等多个数据项航班号图书馆书目管理系统实景AbstractDataType线性表的抽象数据类型定义线性表的ADT定义包含数据对象、数据关系和基本操作，屏蔽底层存储细节，为上层应用提供统一接口，是"抽象-实现"分层思想的体现。01数据对象D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}，ElemSet是某个数据对象的集合，表示线性表中所有数据元素的取值范围。ElemSet02数据关系R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}，描述元素间的前驱-后继关系，体现线性结构的逻辑特性。Predecessor03基础操作InitList(&L)初始化空表；ListLength(L)返回长度；ListEmpty(L)判空。用于表的创建与状态查询。Init&Query04增删操作ListInsert(&L,i,e)在第i位前插入元素e；ListDelete(&L,i,&e)删除第i个元素并返回其值。Insert&Delete05查找操作GetElem(L,i,&e)按位获取第i个元素；LocateElem(L,e)按值查找元素位置，支持随机访问与顺序查找。Get&Locate核心操作语义线性表基本操作详解线性表的基本操作涵盖初始化、增删改查和销毁等完整生命周期。理解这些操作的语义是正确实现算法的前提。INSERTListInsert(&L,i,e)在位序i前插入元素e，原i及之后元素后移；合法范围1≤i≤n+1DELETEListDelete(&L,i,&e)删除位序i的元素并用e返回其值，后续元素前移；合法范围1≤i≤nACCESSGetElem(L,i,&e)按位序获取元素，顺序表O(1)直接访问，链表O(n)顺序遍历SEARCHLocateElem(L,e,compare)按值查找首个满足条件的元素位序，需遍历整个表，平均O(n)CHAPTER02顺序存储结构及其实现用连续内存空间实现高效的随机访问LinearStructure顺序表的定义与存储特点顺序表用一组地址连续的存储单元依次存储线性表元素，逻辑相邻的元素物理位置也相邻。地址计算公式LOC(ai)=LOC(a1)+(i-1)×L实现了O(1)的随机访问，这是顺序表最大的优势，但同时也带来了插入删除需要移动元素的代价。存储特点用连续内存空间存储元素，逻辑相邻则物理相邻，支持随机访问地址计算LOC(ai)=LOC(a1)+(i-1)×LL为每个元素占用的存储单元数随机访问优势访问任意位序元素的时间复杂度为O(1)，无需遍历，直接计算地址O(1)存储密度高顺序表只存储数据元素本身，无需额外存储指针等辅助信息NoPointersDATASTRUCTURE顺序表的C语言实现顺序表的C语言实现使用结构体封装数据数组、最大容量和当前长度三个属性。静态分配方式简单直接但容量固定，动态分配方式可灵活扩展但增加了内存管理复杂度。01结构体定义#defineMaxSize100typedefstruct#defineMaxSize100定义最大容量；通过typedefstruct封装data数组与length属性，构成SqList类型。02初始化操作InitList(&L)调用InitList(&L)将L.length置为0，创建空表；时间复杂度O(1)，为后续插入、删除等操作做准备。03静态分配数组大小在编译时确定，空间不足时无法扩展；可能造成内存浪费或溢出风险，适用于数据量已知且固定的场景。04动态分配使用malloc申请内存，可通过realloc灵活扩展容量；需手动调用free释放内存，避免内存泄漏问题。LinearList·Insert顺序表插入算法顺序表插入操作需要将第i位及之后的元素依次后移，为新元素腾出空间。平均移动元素次数为n/2，时间复杂度O(n)。合法性检查判断1≤i≤n+1且表未满（length<MaxSize），不满足则返回错误1≤i≤n+1元素后移for(j=length;j>=i;j--)执行data[j]=data[j-1]，从后往前依次后移j--插入元素data[i-1]=e，length++；数组下标从0开始，位序i对应下标i-1i-1时间分析最好O(1)表尾插入，最坏O(n)表头插入，平均移动n/2个元素O(n)SequentialList·Delete顺序表删除算法顺序表删除操作需要将第i+1位及之后的元素依次前移，填补被删除元素的空位。与插入操作对称，平均移动元素次数为(n-1)/2，时间复杂度O(n)。删除表头代价最大，删除表尾效率最高。01合法性检查—判断1≤i≤n且表非空（length>0），不满足则返回错误02保存元素—e=data[i-1]，将被删除元素的值保存到变量e中以便返回03元素前移—for(j=i;j<length;j++)data[j-1]=data[j]，从前往后依次前移填补空位04更新长度—length--；最好情况O(1)表尾删除，最坏情况O(n)表头删除SEARCHALGORITHM顺序表查找算法顺序表支持两种查找方式：按位查找直接通过数组下标访问，时间O(1)；按值查找需顺序遍历，平均时间O(n)。对于有序顺序表，可使用二分查找将按值查找复杂度降至O(logn)，这是顺序表的重要优化技巧。按位查找GetElem(L,i,&e)：直接返回data[i-1]，是顺序表的核心优势O(1)按值查找LocateElem(L,e)：顺序遍历比较，找到返回位序，未找到返回0O(n)二分查找有序表专属优化：每次将搜索范围减半，远优于顺序查找O(logn)二分查找前提表必须有序；仅适用于顺序存储，链表无法随机访问中间元素有序·顺序存储DATASTRUCTURE·LINEARLIST顺序表的优缺点分析顺序表以连续存储实现高效随机访问，但牺牲了插入删除的效率。它适合元素数量稳定、读多写少的场景；对于频繁增删或表长变化大的场景，应考虑链式存储。选择存储结构需要权衡访问效率与修改代价。顺序表优缺点对比维度优点缺点访问效率支持随机访问，按位查找O(1)按值查找需遍历O(n)存储空间存储密度高，无额外指针开销需预分配连续内存，可能浪费插入操作表尾插入O(1)平均移动n/2元素，O(n)删除操作表尾删除O(1)平均移动(n-1)/2元素，O(n)容量扩展实现简单静态分配无法扩展，动态分配需复制顺序表适合读多写少、表长稳定的场景Chapter03链式存储结构及其实现用指针链接实现灵活的动态增删DATASTRUCTURE·链式存储单链表的定义与特点单链表用节点存储元素，每个节点包含数据域和指针域。节点间通过指针链接，逻辑相邻但物理位置可以分散。01typedefstructLNode{ElemTypedata;structLNode*next;}节点结构：typedefstructLNode{ElemTypedata;structLNode*next;}通过结构体定义链表节点，data存储实际数据，next指向下一个节点，形成链式连接的基础结构。02datanext双域设计：数据域data存储元素值，指针域next存储后继节点地址双域分离设计使节点既能保存业务数据，又能维护节点间的逻辑关系，无需连续内存空间。03next=NULL首尾标识：头指针L指向第一个节点，尾节点next=NULL作为结束标志头指针是访问链表的入口，空指针标记链表终止，遍历算法依此判断边界条件。04核心特点：逻辑相邻物理可不邻，插入删除不需移动元素，但按位查找需顺序遍历O(n)动态存储带来灵活性，增删操作仅需修改指针，但失去随机访问能力，需权衡应用场景。LINKEDLIST·DESIGNPATTERN头节点的作用与意义头节点是链表中不存储数据的特殊节点，它的引入统一了空表与非空表、首元节点与其他节点的处理逻辑。虽然占用一个节点空间，但显著简化了插入删除算法的边界条件判断，是链表设计中的重要技巧。统一空表处理空表时头节点next=NULL，与非空表结构一致，无需对空表做特殊判断，消除了最常见的边界分支。next=NULL统一首元节点操作在首元节点前插入或删除时，操作与其他节点完全相同，无需修改头指针，消除了首节点的特殊处理路径。头指针不变简化算法逻辑减少边界条件判断，代码更简洁、更不易出错，插入与删除操作可用同一套逻辑统一实现。一套逻辑代价可接受占用一个节点的存储空间，但对于大多数应用场景完全可以接受，是空间换时间复杂度的经典权衡。1NodeDATASTRUCTURE单链表的建立方法头插法和尾插法是建立单链表的两种基本方法。头插法代码简洁但元素逆序，尾插法保持输入顺序但需维护尾指针。两种方法的时间复杂度都是O(n)。头插法每次将新节点插入到链表头部（头节点之后）算法简洁，无需维护尾指针生成的链表元素顺序与输入顺序相反尾插法每次将新节点插入到链表尾部需要维护尾指针r指向当前最后一个节点生成的链表元素顺序与输入顺序相同LINKEDLIST单链表的查找操作单链表查找必须从头节点开始顺序遍历，按位查找和按值查找的时间复杂度都是O(n)。这是链表失去随机访问能力的代价，但在频繁增删的场景下，链表的插入删除优势可以弥补查找的劣势。按位查找GetElem(L,i)：从头指针出发，p=L->next,j=1，循环p=p->next直至j==i，返回当前节点指针p。适用于需要访问特定位置元素的场景按值查找LocateElem(L,e)：从首元节点开始，逐个比较p->data与目标值e，匹配则返回指针，遍历完未找到返回NULL。适用于按内容检索元素的应用场景时间复杂度平均时间复杂度O(n)，最坏情况下需遍历整个链表；查找效率与目标元素位置线性相关。空间复杂度为O(1)，仅需常数额外空间与顺序表对比顺序表按位查找O(1)，链表O(n)；但链表在已知位置时插入删除为O(1)，以查找代价换取增删优势。频繁增删场景优先选择链表结构DATASTRUCTURE·LINKEDLIST单链表的插入操作后插法在已知节点后插入新节点，只需修改两个指针，时间O(1)，是链表的核心优势。前插法需先找前驱节点，时间O(n)；但可通过"先后插再交换数据"的技巧优化为O(1)。后插法O(1)01在已知节点p之后插入新节点s，直接操作p的指针即可完成02s→next=p→next

;

p→next=s03只需修改两个指针，无需移动任何元素，效率极高前插法优化01原方法需遍历找到p的前驱节点q，在q后插入，耗时O(n)02优化：先将s后插到p之后，再交换p与s的数据域03等效实现前插操作，时间复杂度降为O(1)LinkedList·Deletion单链表的删除操作单链表删除需要找到被删除节点的前驱，修改其next指针跳过被删节点。找前驱的时间O(n)是主要开销，指针修改本身只需O(1)。删除后必须free释放被删节点的内存，避免内存泄漏。按位置删除找第i−1个节点p，令q=p→next，将p→next指向q→next，最后free(q)释放被删节点。p→next=q→next;free(q)按值删除先顺序查找值为e的节点及其前驱节点，定位成功后再执行与按位置删除相同的指针修改操作。Search→Locate→Delete前驱约束删除操作必须找到被删节点的前驱。单链表只有后继指针，无法直接获取某节点的前驱节点。单向遍历限制时间分析查找前驱耗时O(n)，指针修改仅需O(1)。删除后必须调用free释放内存，避免内存泄漏。O(n)+O(1)DATASTRUCTURE·LINKEDLIST循环链表循环链表将尾节点的next指向头节点形成环状结构，从任意节点出发都可遍历整个链表。结构特点尾节点next指向头节点，形成环状；从任意节点可遍历全表next→head判断条件遍历结束条件从p==NULL改为p==L（回到头节点）p==L应用场景约瑟夫问题、轮转调度、循环队列等需要循环遍历的场景约瑟夫问题与单链表对比操作逻辑基本相同，仅结束条件不同；可设置尾指针优化尾部操作尾指针优化DataStructure双向链表与双循环链表双向链表增加prior指针支持双向遍历，解决了单链表无法访问前驱的问题。双循环链表进一步形成双向环，操作更加灵活。代价是每个节点多一个指针的空间开销，适合需要频繁双向遍历或前驱访问的场景。01节点结构typedefstructDNodetypedefstructDNode{ElemTypedata;structDNode*prior,*next;}DNode;02双向遍历可沿next向后，也可沿prior向前，操作更灵活03插入操作s→prior=p;s→next=p→next需同时修改prior和next指针：s→prior=p;s→next=p→next04双循环链表头prior指向尾，尾next指向头，形成双向环，任意节点可双向遍历全表DATASTRUCTURE静态链表静态链表用数组模拟链表结构，数组元素包含数据和游标（下标）。它结合了顺序存储和链式存储的特点：不需要指针、支持不支持指针的语言；插入删除不移动元素。缺点是容量固定，适合嵌入式等特殊场景。01结构定义typedefstruct{ElemTypedata;intcur;}SLinkList[MaxSize];数组实现游标替代指针02游标机制游标cur替代指针，存储下一个节点的数组下标，-1表示链表结束，0通常表示备用链表头逻辑连续物理离散03核心优势不需动态内存分配，适合不支持指针的语言；插入删除操作不需移动元素，时间复杂度为O(1)内存安全高效操作04主要局限数组大小固定，无法动态扩展；空间利用率可能不如动态链表，需要维护备用链表容量受限管理复杂DATASTRUCTURE顺序表与链表的全面对比顺序表与链表各有优劣：选择存储结构需根据具体应用场景权衡——读多写少选顺序表，写多读少选链表。对比维度顺序表链表存储方式连续内存空间离散内存空间按位查找O(1)随机访问O(n)顺序遍历按值查找O(n)，有序可二分O(logn)O(n)顺序遍历插入操作平均O(n)移动元素O(1)已知位置时删除操作平均O(n)移动元素O(1)已知位置时存储空间密度高，需预分配有指针开销，动态分配适用场景读多写少，表长稳定写多读少，表长变化大SUMMARY·根据应用场景选择合适的存储结构，没有绝对的好坏，只有适合与否CHAPTER04线性表的典型应用从理论到实践，用数据结构解决实际问题CLASSICALPROBLEM约瑟夫问题n人围成环，从某位置开始报数，每数到m出列，求最后剩余者的编号。可用循环链表或数学递推公式求解，是理解循环结构和递归思想的经典案例。问题描述n人围成一圈，编号1~n，从第k人开始报数，每数到m出列，求最后剩下的人1~n编号历史背景源自犹太历史学家约瑟夫的真实故事，是数学与计算机科学的经典问题犹太历史循环链表解法用循环链表模拟报数过程，删除出列节点，直到剩最后一个O(n)数学递推解法f(n,m)=(f(n-1,m)+m)%n，时间O(n)，空间O(1)，效率更高O(1)Algorithm·LinkedList约瑟夫问题的循环链表实现循环链表求解约瑟夫问题的核心是模拟报数和出列过程：建立循环链表→定位起始位置→循环数m步删除节点→直到剩最后一个。时间复杂度O(n×m)，直观易懂但效率不如数学递推公式。01建表创建n个节点的循环链表，节点数据域存储编号1~n1~n02定位找到第k-1个节点p，p->next即为第一个报数的人k-103报数出列循环执行m-1次p=p->next，然后删除p->next节点m-104终止条件当p->next==p时，链表只剩一个节点，即为最后幸存者O(n×m)DATASTRUCTURE一元多项式的链表表示一元多项式用链表存储时，每个节点表示一个非零项，包含系数、指数和指针三个域。链表按指数有序排列，只存储非零项，空间效率高。01节点定义typedefstructPNode{floatcoef;intexp;structPNode*next;}PNode,*Polynomial;PNode02存储规则每个节点存储一个非零项，coef为系数，exp为指数，链表按exp递增排列exp↑03示例3x²+5x⁵−2x⁸→

(3,2)→(5,5)→(−2,8)3项04优势只存非零项节省空间；指数稀疏时优势明显；便于合并同类项稀疏友好Algorithm·LinkedList一元多项式相加算法多项式相加通过同时遍历两个有序链表实现：指数相同则系数相加，指数不同则取较小者。时间复杂度O(m+n)，空间复杂度O(1)。STEP01算法思路同时遍历两个多项式链表，逐项比较当前节点的指数expTRAVERSESTEP02指数相同系数相加coef1+coef2，若非零则加入结果链表，两指针同时后移MERGESTEP03指数不同取指数较小的项直接加入结果链表，该链表指针后移一位COMPARESTEP04处理剩余一个链表遍历完后，将另一个链表剩余