期末复习，408考研数据结构：线性表与顺序表实现（概念、C代码及时间复杂度全解析）

数据结构基础线性表与顺序表完全指南前言在计算机科学的学习道路上数据结构是构建高效算法的基石。无论是准备考研如408计算机学科专业基础综合、面试求职还是日常开发实践对数据结构的深入理解都至关重要。线性表作为最基本、最常用的数据结构之一是许多高级数据结构如栈、队列、字符串等的基础。而顺序表作为线性表最直观的实现方式更是理解内存连续存储、随机存取等核心概念的绝佳范例。本文将从零开始系统讲解线性表与顺序表的核心概念、原理、代码实现及复杂度分析帮助你建立清晰的概念体系区分逻辑结构与存储结构理解线性表的抽象定义掌握顺序表的实现细节从静态分配到动态分配从插入删除到查找操作深入时间复杂度分析推导各种操作的最好、最坏和平均情况应对考试与面试通过经典题目解析掌握常见考点和易错点无论你是数据结构初学者还是需要复习巩固的进阶者本文都将为你提供全面而深入的学习路径。让我们从线性表的基本概念出发一步步揭开顺序表的神秘面纱。1. 线性表的基本概念1.1 线性表的定义与逻辑特性线性表是具有相同数据类型的nnnn≥0n \ge 0n≥0个数据元素的有限序列。当n0n 0n0时称为空表。一般形式表示为L(a1,a2,…,ai,ai1,…,an) L (a_1, a_2, \dots, a_i, a_{i1}, \dots, a_n)L(a1​,a2​,…,ai​,ai1​,…,an​)线性表的逻辑特性有限性表中的数据元素个数是有限的。有序性一对一表中元素具有逻辑上的先后顺序每个元素有且仅有一个直接前驱第一个元素除外和一个直接后继最后一个元素除外。同质性表中元素的数据类型都相同即每个元素占用相同大小的存储空间。抽象性我们在讨论线性表时只关心元素之间的逻辑关系而不关心它具体表达什么数据。线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。线性表是一种逻辑结构它是纯概念层面的“一对一”关系。顺序表和链表则是两种具体的存储结构。1.2 线性表的基本操作我们需要掌握线性表上最核心、最基本的操作集合通常用ADT抽象数据类型来描述。常见的接口如下操作名功能描述InitList(L)初始化表。构造一个空的线性表。Length(L)求表长。返回线性表的长度。LocateElem(L, e)按值查找。在表中查找值为e的元素返回其位置。GetElem(L, i)按位查找。获取表中第i个位置的元素值。ListInsert(L, i, e)插入操作。在表L的第i个位置插入指定元素e。ListDelete(L, i, e)删除操作。删除表L中第i个位置的元素并用e返回被删元素的值。PrintList(L)输出操作。Empty(L)判空操作。DestroyList(L)销毁操作。注意基本操作的具体实现完全取决于底层的存储结构是数组还是链表。这里的表示 C 的引用传参如果考场上用 C 语言可以通过指针来实现同样的效果。2. 顺序表的原理与存储结构2.1 顺序表的定义与随机存取特性顺序表是线性表的顺序存储结构。简单来说就是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的核心特点物理相邻 逻辑相邻逻辑上相邻的元素在物理内存地址上也是相邻的。随机存取O(1)O(1)O(1)顺序表最大的优势。假设顺序表起始地址为LOC(A)\text{LOC}(A)LOC(A)每个元素占sizeof(ElemType)\text{sizeof(ElemType)}sizeof(ElemType)个字节那么第iii个元素的存储地址计算公式为LOC(Ai)LOC(A)(i−1)×sizeof(ElemType) \text{LOC}(A_i) \text{LOC}(A) (i - 1) \times \text{sizeof(ElemType)}LOC(Ai​)LOC(A)(i−1)×sizeof(ElemType)因为公式是线性的所以无论iii是多少我们都可以直接在O(1)O(1)O(1)的时间内访问到它。2.2 顺序表的静态分配与动态分配在具体的代码实现中顺序表一般分为两种实现方式。1. 静态分配顺序表定长数组数组的大小在编译时就已固定。如果插入元素时空间满了将直接导致程序溢出异常无法自动扩容。#defineMaxSize50// 定义线性表的最大长度typedefstruct{ElemType data[MaxSize];// 静态分配的数组intlength;// 顺序表的当前长度}SqList;2. 动态分配顺序表动态指针采用malloc或new在程序运行时堆区申请内存。最大的优势是空间占满时可以动态扩容即重新开辟一块更大的内存空间将原表中的元素全部复制过去释放旧空间从而实现容量的扩充。#defineInitSize100// 表长度的初始定义typedefstruct{ElemType*data;// 指示动态分配数组的指针intMaxSize;// 数组的最大容量intlength;// 数组的当前个数}SeqList;动态分配初始化代码L.data(ElemType*)malloc(sizeof(ElemType)*InitSize);L.length0;L.MaxSizeInitSize;动态分配并不是链式存储它依然是顺序存储结构。它的逻辑结构没有变依然支持O(1)O(1)O(1)的随机存取只不过物理空间是动态申请的变得更灵活了而已。3. 顺序表核心操作的代码实现与复杂度推导3.1 顺序表的初始化静态分配数组空间已由编译器分配只需要将length置为0即可。动态分配如上文所述需要执行malloc申请空间并初始化变量。3.2 插入操作重点逻辑在表L的第i个位置上插入新元素e。如果i超出合法范围合法位置是1到L.length1或者存储空间已满则返回false。否则将第i个元素及其后的所有元素统一向后移动一位腾出空位后插入。boolListInsert(SqListL,inti,ElemType e){// 1. 判断插入位置 i 是否合法if(i1||iL.length1)returnfalse;// 2. 判断当前存储空间是否已满if(L.lengthL.MaxSize)returnfalse;// 3. 将第 i 个元素及之后的元素后移注意位序 i 对应数组下标 i-1for(intjL.length;ji;j--){L.data[j]L.data[j-1];}// 4. 在位置 i 放入新元素 eL.data[i-1]e;// 5. 表长加 1L.length;returntrue;}【时间复杂度推导必背】最好情况在表尾插入 (in1i n1in1)无需移动元素时间复杂度O(1)O(1)O(1)。最坏情况在表头插入 (i1i 1i1)需移动全部nnn个元素时间复杂度O(n)O(n)O(n)。平均情况假设在第iii个位置插入的概率均等 (pi1/(n1)p_i 1/(n1)pi​1/(n1))平均移动元素次数为1n1∑i1n1(n−i1)1n1⋅n(n1)2n2 \frac{1}{n1}\sum_{i1}^{n1}(n-i1) \frac{1}{n1} \cdot \frac{n(n1)}{2} \frac{n}{2}n11​i1∑n1​(n−i1)n11​⋅2n(n1)​2n​因此插入操作的平均时间复杂度为O(n)O(n)O(n)。3.3 删除操作重点逻辑删除表L中第i个位置的元素并用引用参数e返回其值。若i超出合法范围返回false。否则将被删元素赋给e并将第i个元素之后的所有元素依次向前移一位表长减一。boolListDelete(SqListL,inti,ElemTypee){// 1. 判断删除位置 i 是否合法if(i1||iL.length)returnfalse;// 2. 将被删除的元素赋值给 eeL.data[i-1];// 3. 将第 i 个位置之后的元素前移for(intji;jL.length;j){L.data[j-1]L.data[j];}// 4. 表长减 1L.length--;returntrue;}【时间复杂度推导必背】最好情况删除表尾元素 (ini nin)无需移动元素时间复杂度O(1)O(1)O(1)。最坏情况删除表头元素 (i1i 1i1)需移动其余n−1n-1n−1个元素时间复杂度O(n)O(n)O(n)。平均情况设删除第iii个元素的概率均为pi1/np_i 1/npi​1/n平均移动元素次数为1n∑i1n(n−i)1n⋅n(n−1)2n−12 \frac{1}{n}\sum_{i1}^{n}(n-i) \frac{1}{n} \cdot \frac{n(n-1)}{2} \frac{n-1}{2}n1​i1∑n​(n−i)n1​⋅2n(n−1)​2n−1​因此删除操作的平均时间复杂度为O(n)O(n)O(n)。3.4 按值查找逻辑在顺序表中查找第一个值为e的元素返回其位序注意是从1开始的序号不是数组下标若未找到则返回0。intLocateElem(SqList L,ElemType e){for(inti0;iL.length;i){if(L.data[i]e){returni1;// 返回位序注意加 1}}return0;// 查找失败}【时间复杂度推导】最好情况目标元素在表头查找1次时间复杂度O(1)O(1)O(1)。最坏情况目标元素在表尾或不存在查找nnn次时间复杂度O(n)O(n)O(n)。平均情况平均查找次数为(n1)/2(n1)/2(n1)/2按值查找的平均时间复杂度为O(n)O(n)O(n)。补充提示按位查找GetElem(L, i)在顺序表中非常简单直接返回L.data[i-1]即可是O(1)O(1)O(1)的随机存取4. 相关题目讲解4.1 练习1✅ 为什么 C 是正确的顺序表支持随机存取顺序表是用一段地址连续的存储单元来存放元素的底层就是数组。因为地址连续我们可以通过公式地址起始地址(i−1)×元素大小 \text{地址} \text{起始地址} (i-1) \times \text{元素大小}地址起始地址(i−1)×元素大小直接计算出第iii个元素的地址从而在O(1)O(1)O(1)的时间复杂度内直接访问任意位置的元素。这就是随机存取。一维数组也支持随机存取数组在内存中也是连续存放的天生具备通过下标直接找到元素的能力。考研常考对比“顺序表是随机存取链表是顺序存取。”链表要想找第iii个元素必须从头往后一步一步找O(n)O(n)O(n)这就是顺序存取。❌ 为什么 A、B、D 是错的【A选项】陷阱在于“逻辑结构”与“存储结构”的混淆理由顺序表属于“数据结构”的范畴包含了逻辑结构存储结构运算。而一维数组仅仅是代码层面的一种“存储结构物理实现”。本质区别顺序表是逻辑上具有“一对一”关系的线性表而一维数组本质上只是一块连续内存空间的名字。两者在逻辑结构上绝对不能说“相同”比如顺序表可以动态扩容而传统的定长数组大小固定。【B选项】违背了顺序表的“基本身份证”理由“逻辑上相邻物理地址也必须相邻”是顺序表最核心、最本质的特征。拓展这个选项把顺序表和链表搞混了。在链表中逻辑上相邻的元素物理地址可以相隔十万八千里靠指针连接。【D选项】违背了线性表的“同质性”理由线性表定义中明确规定了“表中元素的数据类型都相同”同质性。如果存储的类型不同就无法用统一的公式计算地址偏移量因为每个元素占用的空间大小不一样也就根本无法实现顺序存储了。4.2 练习24.3 练习34.4 练习4 总结与对比特性线性表逻辑结构顺序表存储结构本质数据元素之间的“一对一”逻辑关系用连续内存单元实现的线性表存储方式抽象概念无具体存储物理相邻 逻辑相邻随机存取不支持支持O(1)O(1)O(1)插入/删除抽象操作平均O(n)O(n)O(n)需移动元素空间分配无静态分配固定大小或动态分配可扩容核心要点回顾线性表是逻辑结构顺序表是存储结构二者不可混淆。顺序表的核心优势是随机存取时间复杂度为O(1)O(1)O(1)。顺序表的插入、删除、按值查找操作的平均时间复杂度均为O(n)O(n)O(n)主要开销在于元素的移动。动态分配的顺序表依然是顺序存储只是内存空间在运行时动态申请。掌握这些基础概念和代码实现是深入学习链表、栈、队列等更复杂数据结构的重要基石。