计算机软件技术基础-课件 02ch2(1)-DS 线性结构

第2章线性结构2.1线性表2.2栈和队列2.3串2.4数组、特殊矩阵和广义表线性结构（线性表、栈、队、串、数组）数据结构逻辑结构物理（存储）结构数据运算非线性结构树结构图结构顺序结构链式结构插入运算删除运算修改运算查找运算排序运算数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构

若结构是非空有限集，则有且仅有一个起始元素和一个终点元素，并且所有的数据元素最多只有一个直接前驱和一个直接后继。→可表示为：（a1,a2,……,an）

线性数据结构有且仅有一个起始元素，无直接前驱仅有一个直接后继；有且仅有一个终点元素，无直接后继仅有一个直接前驱；除起始元素和终点元素外，其它元素只有一个直接前趋和一个直接后继。线性结构的逻辑特征：

简言之，线性结构反映元素间的逻辑关系是

的。一对一(1:1)线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是------线性表用线性序列来表示线性结构

（a1,a2,…,ai

,…,an）

a1

为起始元素，an

为终点元素，

ai

为索引号为i

的内部元素线性数据结构II2.1线性表2.1.1线性表的逻辑结构2.1.2线性表的顺序存储及运算2.1.3线性表的链式存储及运算2.1.4顺序表和链表的比较2.1.1线性表的逻辑结构1.线性表的定义2.线性表的基本操作（a1,a2,…ai-1，ai,ai＋1

，…,an）1.线性表的定义

定义：线性表是n（n≥0）个相同类型的数据元素a1,a2,…,an所构成的有限线性序列。n=0时称为空表n>0时称为非空表数据元素线性起点ai的直接前驱ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长线性终点

其中数据元素ai（1≤i≤n）只是一个抽象的符号，其具体含义在不同的情况下可以不同。例126个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级2008011810205于春梅女182008级电信016班2008011810260何仕鹏男182008级电信017班2008011810284王爽女182008级通信011班2008011810360王亚武男182008级通信012班：：：

：：例2

学生情况登记表分析：数据元素都是记录；元素间关系是线性的。分析：数据元素都是字母；元素间关系是线性的。注意：同一线性表中的元素必定具有相同数据类型！2.线性表的基本操作1.置空表：Init_List（L）将线性表L置成空表2.求长度：Length_List（L）求给定线性表L的长度3.取元素：Get_List（L，i)若1≤i≤length(L)，则取第i个位置上的元素，否则取得的元素为NULL（空元素）。4.定位函数：Locate_List（L，X）在线性表L中查找值为X的元素的位置。5.插入：Insert_List（L，i，X）在线性表L中第i个位置上插入值为X的元素。6.删除：Delete_List（L，i）删除线性表L中第i个位置上的元素。

例：假设线性表L=(23,56,89,76,18)，i=3，x=56，y=88，则对L的一组操作及结果如下：

所得结果//5//89//2//(23,56,88,89,76,18)//(23,56,88,76,18)(1)Length(L)(2)Get(L,i)(3)Locate(L,x)(4)Insert(L,i,y)(5)Delete(L,i+1)

线性表的分类根据数据元素在计算机内的存储结构，可分成两类：顺序存储结构——顺序表（向量表）链式存储结构——链表2.1.2线性表的顺序存储及运算1.顺序表的定义及C语言描述2.顺序表基本操作的实现3.顺序表应用举例顺序表线性表的顺序表示又称为顺序存储结构或顺序映像。

顺序表的定义：用一组物理地址连续的存储单元顺序存储在逻辑上相邻的线性表数据元素。

顺序存储方法：用一组地址连续的存储单元依次存储线性表的元素。1.顺序表的定义及C语言描述可以用

类型来实现数组线性表顺序存储特点：逻辑上相邻的数据元素，其物理上也相邻；若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）。注意：C语言中的数组的下标从0开始，即：data[n]的有效范围是V[0]～V[n-1]

设首元素a1的存放地址为LOC(a1)（称为首地址），设每个元素占用存储空间（地址长度）为D字节，则表中任一数据元素ai的存放地址为：LOC(ai)=LOC(

a1

)+D*（i-1）上述公式的解释如图所示a1a2……aiai+1……an

地址内容元素在表中的位序1i2n空闲区i+1Db=LOC(a1)b+Db+(i-1)Db+(n-1)Db+(max-1)DLOC(ai)=LOC(a1)+D*（i-1）线性表的顺序存储结构示意图注：顺序表中任意一个元素的存取时间都相等，它是一个随机存取结构。因此：LOC(M[3])=98+5×(3-0)=113此题要注意下标起点的不同解：地址计算通式为：LOC(ai)=LOC(a1)+L*（i-1）例：设有一维数组Ｍ，下标的范围是0到9，每个数组元素用相邻的5个字节存储。存储器按字节编址，设存储数组元素Ｍ[0]的第一个字节的地址是98，则Ｍ[3]的第一个字节的地址是多少？113元素a1元素a2……..元素ai+1……..01i

可用C语言中的一维数组来描述:#defineM100

/*定义M为常数100，M的值作为数组的最大容量*/

intV[M];

/*V是数组的名字，假设数组中的元素是整型类型*/第i个元素的ai存储地址：Loc(ai)=Loc(a1)+(i-1)*DV[０]V[１]V[i]V[M-1]顺序表的存储结构由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。【？缺少什么信息？】又因为除了用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。

顺序表的存储结构#defineMAXSIZE100

/*线性表可能达到的最大长度为100*/typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];

/*线性表占用的数组空间*/intcnt;/*线性表实际长度，空表置0。线性表中最后一个元素在数组data[]中的下标为cnt-1*/}SeqList;

顺序表的存储结构

顺序表的存储结构 #defineMAXSIZE100 typedefintElemType;typedefstruct { ElemTypedata[MAXSIZE]; intcnt; }SeqList;2.顺序表基本操作的实现在顺序表存储结构中，很容易实现线性表的一些操作，如线性表的构造、第i个元素的访问。注意：C语言中的数组下标从“0”开始，因此，若L是SeqList类型的顺序表，则表中第i

个元素是L.data[i-1]。顺序表的表长cnt，最后一个元素为L.data[cnt-1]。

2.顺序表基本操作的实现顺序表的运算：主要有存取、插入、删除、合并、分解、复制、检索（查找）、排序（分类）、求长度等常用的指针基本操作（设指针变量p、q的定义为SeqList*p,*q）q=(SeqList*)malloc(sizeof(SeqList));//stdlib.hp=q;free(p);2.顺序表基本操作的实现顺序表的初始化：(指针形式)顺序表的初始化即构造一个空表。将L设为指针参数，首先动态分配存储空间，然后，将表中cnt置为0，表示表中没有数据元素。算法如下：

SeqList*Init_SeqList(){ SeqList*L; L=(SeqList*)malloc(sizeof(SeqList)); L->cnt=0;returnL;}设调用函数为主函数，主函数对初始化函数的调用如下：

main(){ SeqList*L; L=Init_SeqList(); …

}顺序表的初始化2.顺序表基本操作的实现按序号查找：注意：元素标号与数组的下标之间的关系时间复杂度为?

O(1)元素an……..元素ai……..元素a2元素a1data[0]data[1]data[i-1]data[n-1]2.顺序表基本操作的实现按内容查找：Locate（L，x）：查找顺序表中是否含有与x值相同的元素。ai-1…..a2a1an…ai+1aix2.顺序表基本操作的实现按内容查找：Locate（L，x）：查找顺序表中是否含有与x值相同的元素。ai-1…..a2a1an…ai+1aix2.顺序表基本操作的实现按内容查找：ai-1…..a2a1an…ai+1aix如果x和ai-1相同，则找到并停止查找；否则按照前面的步骤继续下去2.顺序表基本操作的实现按内容查找：ai-1…..a2a1an…ai+1aix如果此时仍然没有找到，返回错误并停止有关算法及程序在“查找与排序”一章中介绍2.顺序表基本操作的实现按内容查找Locate（L，x）：intLocate_SeqList(SeqList*L,ElemTypex){ inti=1;//i为逻辑序号 while(i<=L->cnt&&L->data[i-1]!=x) i++; if(i>L->cnt)return-1; elsereturni;/*返回数据元素逻辑序号*/}2.顺序表基本操作的实现以下主要讨论线性表的插入和删除两种运算。1)顺序表的插入：顺序表的插入是指在长度为n的线性表（a1，a2，…，ai，…，an）的第i－1个元素ai－1之后和第i个元素ai之前插入一个新元素ax。设插入后的线性表中的数据元素为，则插入操作示意图…..a2a1an…..ai+1ai01i-1iai-1…..a2a1an…ai+1ai

axai-1…..a2a1

aiai+1…an

an……ai+1ai

axn-1插入操作示意图动画顺序表上完成这一运算通过以下步骤进行：

(1)将ai～an顺序向后移动，为新元素让出位置,向后移动的结点个数为（n－i＋1）

(2)将x置入空出的第i个位置；

(3)修改表长。在第i个结点之前插入数据元素时，移动元素次数的平均值为：2.顺序表基本操作的实现其中，注：时间复杂度为O(n)插入运算intInsert_SeqList(SeqList*L,inti,ElemTypex){/*在线性表L中第i个元素之前插入x，

i的合法值为1

i(L->cnt+1)*/intj;if((i<1)||(i>L->cnt+1)){ printf(“位置错LocateError!”); return0;} /*位置i值不合法*/if(L->cnt==MAXSIZE){printf(“表满Filled!");return(ERROR);}for(j=(L->cnt-1);j>=(i-1);j--) L->data[j+1]=L->data[j];/*插入位置后的元素依次右移*/L->data[i-1]=x;/*插入x*/L->cnt++;/*表长加1*/return1;}示例：2.顺序表基本操作的实现2)顺序表的删除：顺序表的删除是指在长度为n的线性表（a1，a2，…，ai，…，an）中删除第i个元素ai，则其长度变为n-1。设删除后的线性表中的数据元素为，则删除操作示意图ai-1…..a2a1alen

…ai+1aiai-1…..a2a1aiai+1…alen

ai+1alenai+1…ai+1

…alen

…..a2a1an…..ai+1ai01i-1in-12.顺序表基本操作的实现2)顺序表的删除：删除第i个元素，移动结点的个数为（n-i），则移动次数的平均值为其中，注：时间复杂度为O(n)例：下图(a)是一个长度为7的有序线性表，若要删除表中值为24的元素，则必须把值为28到77的所有元素依次向前移动一个位置。算法流程图→(,a1,a2,…,ai-1,ai+1,...,an)3.顺序表应用举例例

将顺序表(a1,a2,…,ai-1,ai,ai+1,...,an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大(这里假设数据元素的类型具有可比性,不妨设为整数型)，操作过程如图2.5所示。这一操作称为划分。a1也称为基准。基本思路：从第二个元素开始到最后一个元素，逐一向后扫描：(a)当前数据元素ai比a1大(>=)时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个。(b)若比a1小，说明它应该在a1的前面，此时将它前面的元素都依次向后移动一个位置，然后将它置入最前面。

(a1,a2,…,ai-1,ai,ai+1,...,an)ai

↑

2515301020206025103035601535……

(a)划分前

(b)划分后图2.5顺序表的划分算法描述如下：

voidpart(SeqList*L){ inti,j;//i是逻辑序号，j是循环变量 ElemTypex,y; x=L->data[0];//将基准置入x中 for(i=2;i<=L->cnt;i++) {