数据结构与算法 课件 第二章线性表

全国高等教育自学考试指定教材

计算机及应用专业（本科段）数据结构与算法第二章线性表学习目标理解线性表的相关概念，了解其逻辑定义及基本操作，理解线性表数据元素之间的逻辑关系掌握线性表的顺序存储方式和链式存储方式，了解各自的特点掌握顺序表及链表基本操作的实现，并能进行复杂度分析掌握静态链表基本操作的实现，并能进行复杂度分析能够设计与线性表相关的数据结构，灵活运用线性表的基本操作，设计算法解决与线性表相关的实际问题本章主要内容线性表的定义和基本操作12线性表的链式存储及实现3线性表的顺序存储及实现进一步讨论两种基本实现方式4单链表的应用5第一节

线性表的定义和基本操作线性表是一种线性结构。在这种结构中，存在着唯一的“第一个”元素、唯一的“第二个”元素，依此类推线性表中各个元素依次排列例1-1中给出的某班30名同学的基本信息（表1-1），就可以组成一个线性表，可以按照学号排列名单

定义定义2-1一个线性表（linearlist）是由同类型数据元素构成的有限序列由n(n≥0)个元素组成的线性表L，可以表示为L=(a0,a1,…,an-1)这里，ai(0≤i≤n-1)即是线性表中的数据元素，也称为表项线性表中所有数据元素都必须是相同类型的数据元素的次序就是它们在表中的排列次序第一个元素是a0，称为表头或开始元素第n个也即最后一个元素是an-1，称为表尾或终端元素元素的个数n称为表长n=0时称为空表，记为()

示例

例2-1将例1-1的学生基本信息表表示为线性表StudentStudent=

((M2022103001王义平男2004.11.22山东),

(M2022103002陆东男2004.02.05河南),…,

(M2022103030杨志强男2004.10.30陕西))

线性表中常使用非负整数表示各元素的位置表头a0的位置为0a1的位置为1ai(0≤i≤n-1)的位置为i对于元素ai(1≤i≤n-1)，元素aj(0≤j<i)称为ai的前驱，其中元素ai-1称为ai的直接前驱对于元素ai(0≤i≤n-2)，元素aj(i<j≤n-1)称为ai的后继，其中元素ai+1称为ai的直接后继

在不引起歧义的情况下，直接前驱可以简称为前驱，直接后继可以简称为后继“线性”的含义和特点除表头a0外，每个元素有且仅有一个直接前驱除表尾an-1外，每个元素有且仅有一个直接后继线性表中各元素的次序是固有的，即元素ai(1≤i≤n-2)排在ai-1之后，且排在元素ai+1之前

如果线性表中各元素的值可以进行比较，并且表中元素的值按位置顺序递增或递减排列，即按值的“大小”有序排列，则线性表称为有序表表中元素的值不满足按位置顺序递增或递减关系的线性表称为无序表

线性表有3个特点，分别是各元素属于同一个类型元素个数是有限的各元素之间不一定有大小关系，但一定有次序关系

例2-2写出10以内（不含10）的非负偶数组成的线性表10以内（不含10）的非负偶数共有5个，可以写出如下的不同形式L1=(0,2,4,6,8) //递增有序表L2=(8,6,4,2,0) //递减有序表L3=(2,6,4,0,8) //无序表线性表的基本操作线性表中有几个基本操作会涉及到位置position

LinearList中定义的函数都有返回值LinearList中定义的操作都有返回值，有些返回值代表操作的执行结果，另外一些仅表示操作是否已正确执行。例如length返回的是线性表的当前长度，即线性表所含元素的个数find返回的是要查找的元素x在表中第一次出现的位置。如果表中不包含x，则返回-1当表为空时，isEmpty返回1，否则返回0。当表已满时，isFull返回1，否则返回0操作的几个示例序号操作操作结果解释1initList(&s)()创建空线性表s2for(i=0;i<6;i++)insertList(&s,i,2*i)(0,2,4,6,8,10)在空表s的表尾处依次插入6个值3removeList(&s,3,&x)(0,2,4,8,10)删除位置3的值并由x返回该值4setValue(&s,3,-10)(0,2,4,-10,10)给位置3的元素赋值-105find(&s,10)返回值是4在s中查找10，10在位置46find(&s,9)返回值是-1在s中查找9，查找失败第二节

线性表的顺序存储及实现操作的具体实现需要依赖于线性表的存储结构。可以使用顺序存储方式和链式存储方式保存线性表，从而得到线性表的顺序存储结构和链式存储结构顺序存储结构使用数组保存线性表中的各元素，相应的线性表称为顺序表链式存储结构使用链表保存线性表中的各元素，相应的线性表称为链表顺序表顺序存储的基本思想是使用一组连续的存储单元依次存储各个元素，将线性表中的各数据元素，按照其逻辑次序，依次保存在数组的各个单元中线性表中逻辑上相邻的两个元素，保存在数组相邻的两个单元中

分配一个多大的数组是个挑战顺序表的显著特点

分配了数组空间后，将线性表中的n个元素依次保存在数组中，从表头至表尾的各个元素分别对应下标0到下标n-1的位置数组是内存中一片连续的空间，相邻的两个单元在内存中的实际地址也是相邻的，这表明，线性表中逻辑上相邻的两个元素，其存储地址也是相邻的存储示意图假设线性表L=(a0,a1,a2,a3,a4,a5)，每个元素需要占用2个字节，分配一个含8个元素的数组A保存LA在内存中的示意图数组下标与线性表元素的位置相对应线性表元素依次存放的特性，决定着表中元素i（i≥0）存储在数组的下标i处表头元素保存在位置0处，这个位置也称为数组的首地址只要给定数组下标，就能立即计算出相应元素的存储地址，并据此访问该元素地址计算

设LOC(ai)表示元素ai的存储首地址，每个元素需占用d个存储单元，则有 LOC(ai)=LOC(ai-1)+d进一步地有 LOC(ai)=LOC(a0)+i

dLOC(a0)即是数组的首地址例2-4

设顺序表的每个元素占8个存储单元。第1个元素的存储首地址为100，则第6个元素占用的最后一个存储单元的地址是（）A．132 B．139 C．140 D．147解：答案是Dd=8，LOC(a0)=100，第6个元素是a5LOC(a5)=LOC(a0)+5

8=100+40=140即第6个元素占用从140开始的8个存储单元，那么最后一个存储单元是147插入和删除设给定一个顺序表，初始时含有5个元素。在位置2插入元素27，然后删除位置3的元素初始顺序表在位置2插入元素27删除位置3的元素

11523196

…

1152723196

…

11527196

…

程序中使用的常量#defineTRUE1#defineFALSE0#defineERROR-1#ifndefmaxSize#definemaxSize100#endif顺序表基本运算的实现顺序表的定义构造空表及清空表判表空、判表满、求表长插入新元素插入操作中移动元素的平均次数为n/2删除操作删除操作中移动元素的平均次数为(n-1)/2赋值、取值操作查找测试例2-5设有顺序表L，表长为n，保存在数组A中。实现算法将L逆置，即 L=(a0,a1,…,an-2,an-1)变为 L=(an-1,an-2,…,a1,a0)将A[0]与A[n-1]进行交换，然后将A[1]与A[n-2]进行交换，依此类推，当交换到L中间元素时，算法结束算法实现第三节

线性表的链式存储及实现线性表还可以使用链式存储方式保存，即线性表中的各个元素保存在各自的存储空间中，形成一个个的结点这些结点在内存中的地址不要求是相邻的，它们之间通过指针连接起来以这种方式保存的线性表称为链表每个结点中包含元素值和指向其他结点的指针，指针的个数可以是一个，也可能是两个，从而形成不同形式的链表链式存储结构是一种动态灵活的存储方式，它不要求预先分配一块连续的存储空间，而是按需分配，随时需要随时分配同时不要求分配的空间必须是相邻的，而是由系统决定分配的具体位置，既可以相邻也可以不相邻所以在执行插入及删除操作时，不再需要移动元素以保证存储空间的相邻性单链表单链表是由一组动态分配的结点形成的链表，每个结点保存线性表中的一个元素及一个指针，指针指向保存其后继元素的结点保存L的单链表示意图结点定义单链表中结点及链表的定义示例要在上图所示的单链表L的位置2处插入元素E。当前指针为p，指向位置2操作步骤是创建一个新结点，新结点中保存值E让新结点的next指针指向指针p指向的结点，这个结点是当前结点让当前结点的前驱结点的next指针指向新结点另一种定义方式

带头结点的单链表插入在带头结点的单链表中实现插入操作删除在带头结点的单链表L中进行删除例2-6在单链表L中，已知q所指结点是p所指结点的前驱结点，next是结点的指针域，若在q和p之间插入s所指结点，则执行的操作是（）。A．s->next=p->next;p->next=s;B．p->next=s->next;s->next=p;C．p->next=s;s->next=q;D．q->next=s;s->next=p;答案是D。例2-7在带头结点的单链表中，若删除指针p所指结点的后继结点，则执行的操作是（）。A．p->next=p->next->next;B．p=p->next;p->next=p->next->next;C．p->next=p->next;D．p=p->next->next;答案为A。例2-8线性表若采用链式存储结构保存，则要求内存中可用存储单元的地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以答案为D。单链表基本操作的实现带头结点的单链表中，始终会有一个头结点，这个结点在初始化时创建清空单链表判空单链表需要判空，通常不需要判满求长度的两种实现位置值与指针的转换插入新元素删除元素赋值、取值查找例2-9返回指针curr指向结点的位置效率分析如果给定了当前指针，则插入操作和删除操作的时间复杂度均为O(1)判定链表是否为空的时间复杂度也为O(1)清空表操作的时间复杂度是O(n)求表长，两种实现分别是O(1)和O(n)查找操作的时间复杂度是根据查找目标在链表中的位置而定的最优情况下为O(1)最坏的情况下为O(n)平均来看是O(n)查找失败是O(n)循环链表修改单链表的定义，将表尾结点的指针指回头结点，从而形成一类新链表这样的链表中，从任何一个结点出发沿着指针域的指示可以再回到这个结点，好象转了一个圈一样，形象地称这样的链表为循环链表双向链表双向链表中，表结点及链表的定义typedefintELEMType;typedefstructnode{ //双向链表结点 ELEMTypedata; structnode*next; //指向后继结点 structnode*prev; //指向前驱结点}DouLinkNode;typedefDouLinkNode*DouLinkList; //双向链表typedefintPosition;双向链表双向链表的初始化辅助函数setCurr插入新元素删除元素双向循环链表例2-11在双向循环链表中，在指针p所指向的结点（非尾结点）之后插入指针s指向的结点，下列选项中，正确的修改指针的语句序列是（）。A．p->next=s;s->prev=p;p->next->prev=s;s->next=p->next;B．p->next->prev=s;p->next=s;s->prev=p;s->next=p->next;C．s->prev=p;s->next=p->next;p->next=s;p->next->prev=s;D．s->prev=p;s->next=p->next;p->next->prev=s;p->next=s;答案是D。第四节进一步讨论两种基本实现方式线性表有两种基本的实现方式，分别是顺序实现和链式实现简单地说，这两种实现方式各有优势。在不同的情况下，对应于不同的操作，某一种方式可能会优于另外一种。但是哪种方式都不能适用于所有情况示例将下列特性对应到顺序表和链表中，对号入座A．逻辑上相邻的元素，在内存中的存储位置也相邻B．不必事先估计存储空间C．所需空间与元素个数成正比D．插入、删除时不需要移动元素E．支持随机存取F．支持顺序存取顺序表具有的特性有：A、E和F链表具有的特性有：B、C、D和F对比存储每个数据元素时空间比较紧凑，并且是占用连续的空间数组的每个单元中只需要保存数据本身，没有额外的开销链表在每个结点上除存储数据元素外，还要留出空间存放指针。单链表中每个结点包含一个指针，双向链表中每个结点包含两个指针。这些指针占用的空间称为结构性开销为顺序表分配的数组，通常要宽松一些。通常数组中会有空闲的空间，此时并没能充分利用数组的全部空间链表中占用的空间大小与链表中的元素个数成正比，分配的结点是全部使用的当线性表的元素个数相对较少时，链表的实现比顺序表的实现更节省空间当线性表中的元素个数接近分配的最大个数，数组的空间存储效率很高设n表示线性表中当前元素的个数，D表示最多可以在数组中存储的元素个数，也就是数组的大小，P表示指针的存储单元大小，E表示数据元素的存储单元大小顺序表的空间需求为D

E单链表的空间需求为n

(P+E)n的临界值n=D

E/(P+E)双向链表比单链表中每个结点的指针数多1个。所以双向链表的结构性开销是单链表的2倍例2-12设保存线性表L的每个元素需要的空间为10个字节，指针占2个字节。若采用单链表或含30个元素的数组保存L。试分析采用哪种方式空间存储效率更高，仅需要考虑L中元素根据题意，采用单链表保存L时，每个结点占用的空间为12个字节例2-12如果采用数组保存，则需要的空间是30

10=300个字节。使用这些空间保存单链表中的结点的话，可以保存300/12=25在不考虑表头结点占用的空间的前提下，如果L中元素个数少于25个，则采用单链表更省空间如果多于25个元素，则采用数组更省空间如果正好是25个元素，则单链表和数组占用的空间是一样大的如何选择当线性表元素个数变化较大或者未知时，最好使用链表实现如果用户事先知道线性表的大致长度，则使用顺序表的空间效率会更高些还要考虑到，顺序表占用的空间是连续的，而链表占用的空间可能是零散的，并且还需要程序员来管理空间的分配及释放操作的时间复杂度也要考虑在顺序表中是直接定位的，可以实现随机访问，操作的时间复杂度是O(1)单链表不能随机访问指定的元素，平均时间复杂度和最差时间复杂度均为O(n)在给出指向链表的当前指针后，在单链表内进行插入和删除操作的时间复杂度也可以达到O(1)顺序表的插入和删除操作，平均和最差时间复杂度均为O(n)空闲单元链表链表中，当需要在链表中插入一个结点时，需要调用malloc函数分配相应的空间当在链表中删除一个结点时，需要调用delete函数释放空间。如果在链表中频繁进行插入、删除结点的操作，则频繁调用这些函数的时间开销会是非常可观的可以针对实际应用的每类链表，定义一个“伙伴链表”，表结点的结构与所使用的链表结构一致伙伴链表用来管理暂时不用的结点，可以将伙伴链表称为空闲单元链表假设，保存数据的单链表为L当从链表L中删除一个结点时，将这个结点插入到freelist中当需要申请新的结点空间时，先查看链表freelist。如果freelist不空，则从freelist中获取一个结点，结点中保存相应的值，并将该结点插入到L的相应位置，否则调用malloc函数分配新的空间，并完成后续的插入操作插入操作的实现删除操作的实现清空表的操作静态链表静态链表的特点保存在数组中兼具顺序表和链表特性，空间不零碎，插入删除不需要移动元素链表及静态链表在前一个静态链表中插入元素E后的静态链表删除元素D后的静态链表类型定义初始化静态链表清