第2章 线性表1-顺序表示

1、 线性结构线性结构是最常用、最简单的一种数据结是最常用、最简单的一种数据结构。而构。而线性表线性表是一种典型的线性结构。其基本是一种典型的线性结构。其基本特点是线性表中的数据元素是特点是线性表中的数据元素是有序有序且是且是有限有限的。的。在这种结构中：在这种结构中：u 存在一个唯一的被称为存在一个唯一的被称为“第一个第一个”的数据元素；的数据元素；u 存在一个唯一的被称为存在一个唯一的被称为“最后一个最后一个”的数据元素；的数据元素；u 除第一个元素外，每个元素均有唯一一个直接前除第一个元素外，每个元素均有唯一一个直接前驱；驱；u 除最后一个元素外，每个元素均有唯一一个直接除最后一个元素外，每

2、个元素均有唯一一个直接后继。后继。l线性表线性表(Linear List) ：是由：是由n(n0)个数个数据元素据元素(结点结点)a1，a2， an组成的有限序组成的有限序列。该序列中的所有结点具有列。该序列中的所有结点具有相同的数相同的数据类型据类型。其中数据元素的个数。其中数据元素的个数n称为线性称为线性表的长度。表的长度。l当当n=0时，称为空表。时，称为空表。 l当当n0时，将非空的线性表记作：时，将非空的线性表记作： (a1，a2，an) la1称为线性表的第一个称为线性表的第一个(首首)结点，结点，an称为称为线性表的最后一个线性表的最后一个(尾尾)结点。结点。la1，a2，ai-

3、1都是都是ai(2in)的的前驱前驱，其，其中中ai-1是是ai的的直接前驱直接前驱;lai+1，ai+2，an都是都是ai(1i n-1)的的后后继继，其中其中ai+1是是ai的的直接后继直接后继。（a1, a2, ai-1，ai, ai1 ，, an）线性表的定义：线性表的定义：是是n个数据元素的有限序列个数据元素的有限序列n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点l线性表中的数据元素线性表

4、中的数据元素ai所代表的具体含义所代表的具体含义随具体应用的不同而不同，在线性表的随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。定义中，只不过是一个抽象的表示符号。u 线性表中的线性表中的结点结点可以是可以是单值元素单值元素(每个元素每个元素只有一个数据项只有一个数据项) 。 例例1: 26个英文字母组成的字母表：个英文字母组成的字母表： (A，B，C、Z）例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188）例3 ： 一副扑克的点数 (2，3，4，J，Q，K，A)u 线性表中的结点可以是记录型元素，每个元素含有多

5、个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。例4 ： 某校2001级同学的基本情况： (2001414101，张里户，男，06/24/1983)， (2001414102，张化司，男，8/12/1984) ， (2001414102，李利辣，女，08/12/1984) 若线性表中的结点是按值(或按关键字值)由小到大(或由大到小)排列的，称线性表是有序的。 线性表是一种相当灵活的数据结构，其线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短。长度可根据需要增长或缩短。 对线性表的数据元素可以访问、插入和对线性表的数据元素可以访问、插入和

6、删除。删除。 ADT List数据对象：数据对象：D = ai | aiElemSet, i=1,2,n, n0 数据关系：数据关系：R = | ai-1, aiD, i=2,3,n 基本操作：基本操作：InitList( &L )操作结果：构造一个空的线性表操作结果：构造一个空的线性表L；ListLength( L )初始条件：线性表初始条件：线性表L已存在；已存在；操作结果：若操作结果：若L为空表，则返回为空表，则返回TRUE，否则返，否则返FALSE；.GetElem( L, i, &e )初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L)；

7、操作结果：用操作结果：用e返回返回L中第中第i个数据元素的值；个数据元素的值；ListInsert ( L, i, &e )初始条件：线性表初始条件：线性表L已存在，已存在，1iListLength(L) ；操作结果：在线性表操作结果：在线性表L中的第中的第i个位置插入元素个位置插入元素e； ADT Listl顺序存储顺序存储 ：把线性表的结点：把线性表的结点按逻辑顺序按逻辑顺序依次存放在一组地址连续的存储单元依次存放在一组地址连续的存储单元里。里。用这种方法存储的线性表简称顺序表。用这种方法存储的线性表简称顺序表。l顺序存储顺序存储的线性表的的线性表的特点特点：u 线性表的逻辑顺序与

8、物理顺序一致线性表的逻辑顺序与物理顺序一致;u 数据元素之间的关系是以元素在计算机内数据元素之间的关系是以元素在计算机内“物理位置相邻物理位置相邻”来体现。来体现。l 设有非空的线性表：设有非空的线性表：(a1，a2，an) 。顺。顺序存储如图序存储如图2-1所示。所示。 a1 a2 ai an Loc(a1) Loc(ai)+(i-1)* l 图图2-1 线性表的顺序存储表示线性表的顺序存储表示a1a2aiai+1an 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb

9、 +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L 在具体的机器环境下：设线性表的每个元素需占用l个存储单元，以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系： LOC(ai+1)=LOC(ai)+l 线性表的第i个数据元素ai的存储位置为： LOC(ai)=LOC(a1)+(i-1)*l 在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来

10、定义顺序表类型。#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status ;typedef int ElemType ; typedef struct sqlist ElemType *Elem_array ;int length ;int listSize; SqList ;顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。1 顺序线性表初始化 Status Init_SqList( SqList *L ) L-elem_array=( Ele

11、mType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ;if ( !L - elem_array ) return ERROR ; else L-length= 0 ; L-listSize=MAX_SIZE; return OK ; 2 顺序线性表的插入 在线性表 L= (a1，a i-1，ai， ai+1，an) 中的第i(1in)个位置上插入一个新结点e，使其成为线性表： L=(a1，a i-1，e，ai，ai+1，an) 实现步骤(1) 将线性表L中的第i个至第n个结点后移一个位置。(2) 将结点e插入到结点ai-1之后。 (3) 线性表长度加1。

12、算法描述Status Insert_SqList(Sqlist *L，int i ，ElemType e) int j ;if ( iL-length-1) return ERROR ;if (L-length=MAX_SIZE) printf(“线性表溢出线性表溢出!n”); return ERROR ; for ( j=L-length1; j=i-1; -j )L-Elem_arrayj+1=L-Elem_arrayj;/* i-1位置以后的所有结点后移位置以后的所有结点后移 */L-Elem_arrayi-1=e; /* 在i-1位置插入结点 */L-length+ ;return O

13、K ; 时间复杂度分析 在线性表L中的第i个元素之前插入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。总的平均移动次数： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。 即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。3. 顺序线性表的删除 在线性表 L=(a1，a i-1，ai， ai+1，an) 中删

14、除结点ai(1in)，使其成为线性表： L= (a1，ai-1，ai+1，an) 实现步骤(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。(2) 线性表长度减1。算法描述ElemType Delete_SqList(Sqlist *L，int i) int k ; ElemType x ; if (L-length=0) printf(“线性表线性表L为空为空!n”); return ERROR; else if ( iL-length ) printf(“要删除的数据元素不存在要删除的数据元素不存在!n”) ; return ERROR ; else x=L-Elem_ar

15、rayi-1 ; /*保存结点的值保存结点的值*/for ( k=i ; klength ; k+) L-Elem_arrayk-1=L-Elem_arrayk; /* i位置以后的所有结点前移位置以后的所有结点前移 */L-length-; return (x); l时间复杂度分析时间复杂度分析 删除线性表删除线性表L中的第中的第i个元素，其时间主要耗费个元素，其时间主要耗费在表中结点的移动操作上，因此，可用结点的在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。移动来估计算法的时间复杂度。l 设在线性表设在线性表L中删除第中删除第i个元素的概率为个元素的概率为Pi，不失一

16、般性，设删除各个位置是等概率，则不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为，而删除时移动结点的次数为n-i。l则总的平均移动次数：则总的平均移动次数： Edelete=pi*(n-i) (1in)l Edelete=(n-1)/2 。l 即在顺序表上做删除运算，平均要移动表上即在顺序表上做删除运算，平均要移动表上一半结点。当表长一半结点。当表长n较大时，算法的效率相当较大时，算法的效率相当低。因此算法的平均时间复杂度为低。因此算法的平均时间复杂度为O(n)。4 顺序线性表的查找定位删除 在线性表 L= (a1，a2，an) 中删除值为x的第一个结点。实现步骤(

17、1) 在线性表L查找值为x的第一个数据元素。(2) 将从找到的位置至最后一个结点依次向前移动一个位置。 (3) 线性表长度减1。算法描述Status Locate_Delete_SqList(Sqlist *L，ElemType x) /* 删除线性表L中值为x的第一个结点 */ int i=0 , k ; while (ilength) /*查找值为x的第一个结点*/ if (L-Elem_arrayi!=x ) i+ ; else for ( k=i+1; klength; k+) L-Elem_arrayk-1=L-Elem_arrayk; L-length-; break ; if (

18、iL-length) printf(“要删除的数据元素不存在要删除的数据元素不存在!n”) ; return ERROR ; return OK; l 时间复杂度分析时间复杂度分析l 时间主要耗费在数据元素的比较和移动操作时间主要耗费在数据元素的比较和移动操作上。上。l首先，在线性表首先，在线性表L中查找值为中查找值为x的结点是否存在的结点是否存在;l其次，若值为其次，若值为x的结点存在，且在线性表的结点存在，且在线性表L中的中的位置为位置为i ，则在线性表，则在线性表L中删除第中删除第i个元素。个元素。l 设在线性表设在线性表L删除数据元素概率为删除数据元素概率为Pi，不失，不失一般性，设各

19、个位置是等概率，则一般性，设各个位置是等概率，则Pi=1/n。u 比较的平均次数比较的平均次数： Ecompare=pi*i (1in)l Ecompare=(n+1)/2 。u 删除时平均移动次数删除时平均移动次数：Edelete=pi*(n-i) (1in)l Edelete=(n-1)/2 。 平均时间复杂度：平均时间复杂度：Ecompare+Edelete=n ，即为，即为O(n)一个一维数组，下标的范围是到一个一维数组，下标的范围是到，每个数组元素用相邻的，每个数组元素用相邻的个字节个字节存储。存储。存储器按字节编址，设存储数组元素存储器按字节编址，设存储数组元素 的第一个字节的地址

20、是的第一个字节的地址是9898，则，则 的第一个字节的地址是（的第一个字节的地址是（ ）因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113解：解：地址计算通式为：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）l一条记录有学号和成绩两个数据项，依一条记录有学号和成绩两个数据项，依次输入数据建立一个有序顺序表（按成次输入数据建立一个有序顺序表（按成绩由大到小）。其中输入的数据如下绩由大到小）。其中输入的数据如下（学号，成绩）：（学号，成绩）：(1,70),(2,85),(3,75), (1,70),(2,85),(3,75), (4,90),(5,60),(6,80),(7,76),(8,50)(4,90),(5,60),(6,80),(7,76),(8,50)等等。等等。线性表的顺序存储结构线性表的顺序存储结构#define MAXSIZE 100typedef struct ElemType *elem; int length; int listsize;SqList;typedef struct int no; int grade;ElemType;线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的：逻辑关系上相邻的两个元素在物理存储位置上