武汉软件工程职业学院《数据结构讲义》第03讲线性表的逻辑结构和顺序存储结构

1、第三讲 线性表的逻辑结构和顺序存储结构1、线性表的定义和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。 教学重点：1、 线性表的定义；2、线性表的顺序表示和实现方法： 教学难点：线性表的顺序存储的实现方法。 授课内容第二章 线性表和数组线性表是最简单、最基本、也是最常用的一种线性结构。它有两种存储方法：顺序存储和链式存储，它的主要基本操作是插入、删除和检索等。2.1 线性表的逻辑结构2.1.1

2、线性表的定义线性表是一种线性结构。线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。在一个线性表中数据元素的类型是相同的，或者说线性表是由同一类型的数据元素构成的线性结构。在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型; 一个字符串也是一个线性表：表中数据元素的类型为字符型，等等。综上所述，线性表定义如下：线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。表中相邻元素之间存在着顺序关系。将 ai-1 称为 ai 的直接前趋

3、，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，.，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，.，n-1 时，有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。需要说明的是：ai为序号为 i 的数据元素（i=1,2,n），通常我们将它的数据类型抽象为datatype，datatype根据具体问题而定，如在学生情况信息表中，它是用户自定义的学生类型; 在字符串中，它是字符型; 等等。2.1.2 线性表的基本操作 在第一章中提到，数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，因此下面定

4、义的线性表的基本运算作为逻辑结构的一部分，每一个操作的具体实现只有在确定了线性表的存储结构之后才能完成。线性表上的基本操作有： 线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表 求线性表的长度：Length_List(L)初始条件：表L存在操作结果：返回线性表中的所含元素的个数 取表元：Get_List(L,i)初始条件：表L存在且1=i=Length_List(L)操作结果：返回线性表L中的第个元素的值或地址 按值查找：Locate_List(L,x)，是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为的数据元素，其结果返回在L中首次

5、出现的值为的那个元素的序号或地址，称为查找成功; 否则，在L中未找到值为的数据元素，返回一特殊值表示查找失败。 插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确 (1=i=n+1,为插入前的表长)。操作结果：在线性表L的第 i 个位置上插入一个值为 x 的新元素，这样使原序号为 i , i+1, . , n 的数据元素的序号变为 i+1,i+2, . , n+1，插入后表长=原表长+1。 删除操作：Delete_List(L,i)初始条件：线性表L存在，1=i=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为 i+1, i+2,., n 的元素

6、变为序号为 i, i+1,.,n-1，新表长原表长。 需要说明的是： 1. 某数据结构上的基本运算，不是它的全部运算，而是一些常用的基本的运算，而每一个基本运算在实现时也可能根据不同的存储结构派生出一系列相关的运算来。比如线性表的查找在链式存储结构中还会有按序号查找; 再如插入运算，也可能是将新元素插入到适当位置上等等，不可能也没有必要全部定义出它的运算集，读者掌握了某一数据结构上的基本运算后，其它的运算可以通过基本运算来实现，也可以直接去实现。2. 在上面各操作中定义的线性表仅仅是一个抽象在逻辑结构层次的线性表，尚未涉及到它的存储结构，因此每个操作在逻辑结构层次上尚不能用具体的某种程序语言写

7、出具体的算法，而算法的实现只有在存储结构确立之后。2.2 线性表的顺序存储结构2.2.1 顺序存储结构线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。因为内存中的地址空间是线性的，因此，用物理上的相邻实现数据元素之间的逻辑相邻关系是既简单，又自然的。如图 2.1 所示。设 a的存储地址为Loc(a)，每个数据元素占d个存储地址，则第i个数据元素的地址为： Loc(ai)=Loc(a)+(i-1)*d 1=idata ，线性表中数据元素的存储空间为： Ldata0 LdataLlast。在以后的算法中多用这种方法表示，读者在读算

8、法时注意相关数据结构的类型说明。图2.2 线性表的顺序存储示意图2.2.2 顺序表上基本操作的实现 1.顺序表的初始化 顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中 last 指针置为1，表示表中没有数据元素。算法如下： SeqList *init_SeqList( ) SeqList *L;L=malloc(sizeof(SeqList); L-last=-1; return L; 算法2.1设调用函数为主函数，主函数对初始化函数的调用如下： main() SeqList *L; L=Init_SeqList(); 2.

9、插入运算 线性表的插入是指在表的第i个位置上插入一个值为 x 的新元素，插入后使原表长为 n的表:(a1，a2，. ，ai-1，ai，ai+1，. ，an)成为表长为 n+1 表:(a1，a2，.，ai-1，x，ai，ai+1，.，an) 。i 的取值范围为1=ilast=MAXSIZE1) printf(表满); return(-1); /*表空间已满，不能插入*/ if (iL-last+2)/*检查插入位置的正确性*/ printf(位置错);return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj; /* 结点移动 */ L-datai-1

10、=x;/*新元素插入*/ L-last+; /*last仍指向最后元素*/ return (1);/*插入成功，返回*/ 算法2.2本算法中注意以下问题： (1) 顺序表中数据区域有MAXSIZE个存储单元，所以在向顺序表中做插入时先检 查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。 (2) 要检验插入位置的有效性，这里 i 的有效范围是：1=i=n+1，其中 n 为原表长。 (3) 注意数据的移动方向。a1a2 ai-1aiai+1ana1aai-1 x aiai+1an 0 1 i-2 i-1 i n-1MAXSIZE-1 插入前 插入后 图2.3 顺序表中的插入插入算法

11、的时间性能分析：顺序表上的插入运算，时间主要消耗在了数据的移动上，在第i个位置上插入 x ，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素，而 i 的取值范围为 ：1= i= n+1，即有 n1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：设：Pi=1/ (n+1) ，即为等概率情况，则：这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然时间复杂度为(n)。 3. 删除运算 DeleteList(L,i) 线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后使原表长为 n 的线性表： (a1，a2，. ，ai-1，ai，ai

12、+1，.，an)成为表长为 n1 的线性表： (a1，a2，. ，ai-1， ai+1，. ，an)。 i 的取值范围为：1=i=n 。 顺序表上完成这一运算的步骤如下： (1) 将ai+1an 顺序向上移动。 (2) 修改last指针(相当于修改表长)使之仍指向最后一个元素。a1aai-1ai+1 an0a11a2i-2ai-1i-1aiiai+1 n-1anMAXSIZE-1 删除前 删除后 图2. 4 顺序表中的删除 算法如下： int Delete_SeqList(SeqList *L;int i) int j; if(iL-last+1) /*检查空表及删除位置的合法性*/ prin

13、tf (不存在第i个元素); return(0); for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向上移动*/L-last-; return(1); /*删除成功*/ 算法2.3本算法注意以下问题： （1）删除第i个元素，i的取值为 1=ilast的值为-1，条件（iL-last+1）也包括了对表空的检查。 （3）删除 ai 之后，该数据已不存在，如果需要，先取出 ai ，再做删除。删除算法的时间性能分析：与插入运算相同，其时间主要消耗在了移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动了 n-i 个元素，所以平均移动数

14、据元素的次数： 在等概率情况下，pi =1/ n，则： 这说明顺序表上作删除运算时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。 【例21】将顺序表 (a1，a2，. ，an) 重新排列为以 a1 为界的两部分：a1 前面的值均比 a1 小，a1 后面的值都比 a1 大(这里假设数据元素的类型具有可比性, 不妨设为整型)，操作前后如图2.5所示。这一操作称为划分。a1 也称为基准。 划分的方法有多种，下面介绍的划分算法其思路简单，性能较差。 基本思路： 从第二个元素开始到最后一个元素，逐一向后扫描： （1）当前数据元素 aI 比 a1 大时，表明它已经在 a1 的后面，不必改变它

15、与 a1 之间的位置，继续比较下一个。 （2）当前结点若比 a1 小，说明它应该在 a1 的前面，此时将它上面的元素都依次向下移动一个位置，然后将它置入最上方。25302060103515.15102025306035. 划分前 划分后 图2.5 顺序表的划分算法如下： void part(SeqList *L) int i,j; datatype x,y; x=L-data0; /* 将基准置入 x 中*/ for(i=1;ilast;i+) if(L-dataidatai; for(j=i-1;j=0;j-) /*移动*/ Ldataj+1=L-dataj; L-data0=y; 算法2.

16、5本算法中，有两重循环，外循环执行n1次，内循环中移动元素的次数与当前数据的大小有关，当第个元素小于 a1 时，要移动它上面的 i-1个元素，再加上当前结点的保存及置入，所以移动 i-1+2次，在最坏情况下，a1 后面的结点都小于 a1 ，故总的移动次数为 ： 即最坏情况下移动数据时间性能为()。这个算法简单但效率低，在第章的快速排序中时我们将介绍另一种划分算法，它的性能为(n)。【例22】有顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。算法思路：依次扫描通过A和B的元素，比较当前的元素的值，将较小值的元素赋给C，如此直到

17、一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。算法如下：void merge(SeqList A, SeqList B, SeqList *C) int i,j,k; i=0;j=0;k=0; while ( i=A.last & j=B.last ) if (A.dateidatak+=A.datai+; else C-datak+=B.dataj+;while (idatak+= A.datai+;while (jdatak+=B.dataj+;C-last=k-1; 算法2.6算法的时间性能是O(m+n)，其中m是A的表长，n是B的表长。【例2.3】比较两个线性表的大小。两个线性表的比较依据下列方法：设A、B是两个线性表，均用向量表示，表长分别为m和n。 A和B分别为 A 和 B 中除去最大共同前缀后的子表。例如A=(x,y,y,z,x,z)， B=(x,y,y,z,y,x,x,z)，两表最大共同前缀为 (x,y,y,z) 。则 A=（x,z）， B=（y,x,x,z），若A=B= 空表，则A=B；若A=空表且B空表，或两者均不空且A首元素小于B首元素，则AB。 算法思路：首先找出A、B的最大共同前缀；然后求出