第2章线性表 从第2章至第4章将讨论线性结构。线性结构的特点是:在数据元素的非空有限集 中,(1)存在唯一的一个被称做“第一个"的数据元素;(2)存在唯一的一个被称做“最后 个”的数据元素;(3)除第一个之外,集合中的每个数据元素均只有一个前驱;(4)除 最后一个之外集合中每个数据元素均只有一个后继。 21线性表的类型定义 线性( linear.List)是最常用且最简单的一种数据结构。简言之,一个线性表是n 个数据元素的有限序列。至于每个数据元素的具体含义,在不同的情况下各不相同,它可 以是一个数、或一个符号也可以是一页书,甚至其它更复杂的信息。例如,26个英文字 母的字母表: (A,B,C,……,Z) 是一个线性表,表中的数据元素是单个字母字符。又如,某校从1978年到1983年各种型 号的计算机拥有量的变化情况,可以用线性表的形式给出: (6,17,28,50,92,188) 表中的数据元素是整数。 在稍复杂的线性表中,一个数据元素可以由若干个数据项(Iem)组成。在这种情况 下,常把数据元素称为记录(Ror),含有大量记录的线性表又称文件(Fil) 例如,一个学校的学生健康情况登记表如图21所示表中每个学生的情况为一个记 录,它由姓名、学号性别、年龄、班级和健康状况等六个数据项组成。 姓名学号{性别年龄|班级|键康状况 王小林790631男 18计9健康 陈红790632女 20计91 般 刘建平790633男 计91健康 张立立790634男 17计91神经囊弱 图21学生健康情况登记表 综合上述三个例子可见线性表中的数据元素可以是各种各样的但同一线性表中的 元素必定具有相同特性,即属同一数据对象,相邻数据元素之间存在着序偶关系。若将线 性表记为 (a1,…,a2-1,a,a1+t,…,an (2-1) 18
则表中a;-领先于a,a领先于a+1,称a1-1是a,的直接前驱元素,a1+1是a1的直接后 继元素。当i=1,2,…,n-1时,a,有且仅有一个直接后绻,当i=2,3,…,n时,a有且 仅有一个直接前驱。 线性表中元素的个数n(n≥0)定义为线性表的长度,n=0时称为空表。在非空表 中的每个数据元素都有一个确定的位置,如a1是第一个数据元素,an是最后一个数据元 素,a;是第;个数据元素,称为数据元素a1在线性表中的位序。 线性表是一个相当灵活的数据结构,它的长度可根据需要增长或缩短即对线性表的 数据元素不仅可以进行访问,还可进行插入和删除等。 抽象数据类型线性表的定义如下: ADrM毗 数据对象:D={a1a∈ GensEt,i=1,2,…,n,D>0 数据关系={<a1-1,a>|a-t,a∈D,i=2,,n 葚本操作 InitList( &L) 操作结果:构造一个空的线性表L DestroyList( &L) 初始条件:线性表L已存在。 操作结果:销毁线性表L ClearList( &L 初始条件:线性表L已存在。 操作结果:将L重置为空表。 ListEmpty( L) 初始条件:线性表L已存在。 操作结果若L为空表,则返回TRE,否则返回 FALSE ListLength( L) 初始条件:线性表L已存在。 操作结果:返回L中数据元素个数。 GetElem(Li,是e) 初始条件:线性表L已存在1≤ ListLebgtht。 操作结果:用e返回L中第i数据个元素的值。 LocateElem( L, e, compare() 初始杂件:线性表L已存在, compare()是数据元素判定函数。 操作结果:返回L中第1个与e满足关系 co pare()的数据元素的位序。若这样的数据元素 不存在则返回值为0 PriorElen( L, cur e, &pre. e 初始条件线性表L已存在。 操作结果:若cre是L的数据元素,且不是第一个,则用pre.e返回它的前驱否则操作 失败,pre-e无定义。 NextElen( L, cure, &next.e) 初始条件:线性表L已存在 操作结果若cu.e是L的数据元素,且不是最后一个,则用next.e返回它的后继,否则操 作失败,next.e无定义。 ListInsert( &1 i, e) 初始条件:线性表工巳存在,1≤i≤ ListLength(L)+1 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1。 ListDelete ( &L, i, &e)
初始条件:线性表L已存在且非空1≤还 ength(L 操作结果:删除L的第主个数据元素,并用返回其值L的长度减1。 ListTraverse (L, visito) 初始条件:线性表已存在 操作结果:依次对L的每个数据元素调用函数vist(。…一旦ⅵgit()失败则操作失败。 I NE List 对上述定义的抽象数据类型线性表还可进行一些更复杂的操作。如:将两个或两个 以上的线性表合并成一个线性表;把一个线性表拆开成两个或两个以上的线性表重新复 制一个线性表等等。 例21假设利用两个线性表LA和LB分别表示两个集合A和B(即:线性表中的 数据元素即为集合中的成员),现要求一个新的集合A=A∪B。这就要求对线性表作如 下操作;扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插 入到线性表LA中去。只要从线性表LB中依次取得每个数据元素,并依值在线性表LA 中进行查访若不存在则插入之。上述操作过程可用下列算法描述之 void union( List &La, List Lb) ∥将所有在线性表中但不在La中的数据元素插入到L中 Ia.len= Listlength(La);h.len= steNgth(I);∥求线性表的长度 for(ia 1i i<= Lb len; i++)I GetRlen(ib,i, e) ∥取Lb中第i个数据元素赋给e if(! LocateElen(La, e, equal))ListInsert(La, + La len(, e); ∥LA中不存在和e相同的数据元素则插入之 nion 算法2.1 例22已知线性表LA和LB中的数据元素按值非递减有序排列,现要求将LA和 LB归并为一个新的线性表LC,且LC中的数据元素仍按值非递减有序排列。例如设 LA=(3,5,8,11) LB=(2,6,8,9,1,15,20) 则 LC=(2,3,5,68,8,9,11,11,15,20) 从上述问题要求可知LC中的数据元素或是LA中的数据元素或是LB中的数据 元素则只要先设LC为空表然后将LA或LB中的元素还个插入到LC中即可。为使 LC中元素按值非递减有序排列,可设两个指针i和分别指向LA和LB中某个元素若 设i当前所指的元素为a,当前所指的元素为b,则当前应插入到LC中的元素c为 a当a≤b时 b当a>b时 ①++LA.en表示,参数 L a. len的值先增1,然后再传递给函数。若嫩学符号++在参堂名之后则表示先将 参数传递给函教然后参数的值再增1。以后均类同。 20
显然指针i和j的初值均为1,在所指元素插入LC之后,在LA或LB中顺序后移。上 述归并算法如算法22所示。 void MergeList(List La, List Lb, List &Lc)i ∥已知线性表La和中的数据元素按值非递减排列。 ∥归并Ia和功得到新的线性表Lc,L的数据元素也按值非递减排列 Initlist(Lc); ixj-1;k=0; La.len Listlength( La); Lb. len= List Length( Lb); hil(i<=La.1en)&&(<=劻.1en)b∥和L均非空 dLa, i, ai); GetBlem(Lb, j, bj): if(ai < bj)llistinsert(Le, ++k, ai); ++ i; I else ListInsert(Lc, ++k, bj);++j; while(i<= La. len) Getelea(La, i++, ai); ListInsert(Lc, ++k, ai) hil(j<=功,1en)」 Getelem(Lb, j++, bj): ListInsert(Le, ++k, bj) ∥ edgeList 算法2.2 上述两个算法的时间复杂度取决于抽象数据类型Lit定义中基本操作的执行时间。 假如 GetElem和 Listinsert这两个操作的执行时间和表长无关, Locater!em的执行时间和 表长成正比则算法21的时间复杂度为O( ListLength(LA) X List Length(LB),算法 22的时间复杂度则为O( ListLength(LA)+ List length(LB)2虽然算法22中含三个 (whe〕循环语句,但只有当i和j均指向表中实际存在的数据元素时,才能取得数据元素 的值并进行相互比较;并且当其中一个线性表的数据元素均已插入到线性表LC中后,只 要将另外一个线性表中的剩余元素依次插入即可。因此对于每一组具体的输入(LA和 LB),后两个whe)循环语句只执行一个循环体。 22线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 假设线性表的每个元素需占用l个存储单元,并以所占的第一个单元的存储地址作 为数据元素的存储位置。则线性表中第计+1个数据元素的存储位置LOC(a;+1)和第i 个数据元素的存储位置LOC(a)之间满足下列关系: LOC(a; =LOC(ai )+l 般来说,线性表的第i个数据元素a的存储位置为 LOC(a: )=LoC(ay)+(i-1)* 式中LOC(a1)是线性表的第一个数据元素a1的存储位置通常称做线性表的起始位置
或基地址。 线性表的这种机内表示称做线性表的顺序存储结构或顺序映象( Sequential Map ping),反之称这种存储结构的线性表为顺序表。它的特点是,为表中相邻的元素a:和 a1+;赋以相邻的存储位置L0C(a;)和DOC(a;+1)。换句话说以元素在计算机内“物理 位置相邻”来表示线性表中数据元素之间的逻辑关系。每一个数据元素的存储位置都和 线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数(见图2.2)。由 此,只要确定了存储线性表的起始位置,线性表中任一数据元素都可随机存取,所以线性 表的顺序存储结构是一种随机存取的存储结构。 存储地址 内存状态数据元素在线性 表中的位序 b+L (-1)l b+(-| 空闲 b+(maxlen-l) 图22线性表的顺序存储结构示意图 由于高级程序设计语言中的教组类型也有随机存取的特性,因此通常都用数组来描 述数据结构中的顺序存储结构。在此由于线性表的长度可变,且所需最大存储空间随问 题不同而不同,则在C语言中可用动态分配的一维数组如下描述。 ∥ 线性表的动态分配顺序存储结构 # define LIST.IT.SIrz100∥线性表存储空间的初始分配量 # ofine LISTINCREMENT10∥线性表存储空间的分配增量 Elen Type t elen ∥存储空间基址 ∥当前长度 nt1stie;∥当前分配的存储容量(以 size( Elenlype)为单位) solisti 在上述定义中,数组指针eem指示线性表的基地址, length指示线性表的当前长度。 顺序表的初始化操作就是为顺序表分配一个予定义大小的数组空间并将线性表的当前 长度设为“0°(参见算法23) listsize指示顺序表当前分配的存储空间大小,一旦因插入 元素而空间不足时可进行再分配即为顺序表增加一个大小为存堵 LISTINCREMENT