第2章线性表1-类型定义

1、线性结构线性结构的特点是：的特点是：（1）存在惟一的一个被称作）存在惟一的一个被称作“第一个第一个”的数据元素；的数据元素；在数据元素的非空有限集中，在数据元素的非空有限集中，（2）存在惟一的一个被称作）存在惟一的一个被称作“最后一个最后一个”的数据元素；的数据元素；（3）除第一个之外，集合中到每个数据元素均只有一）除第一个之外，集合中到每个数据元素均只有一个直接前驱；个直接前驱；（4）除最后一个之外，集合中到每个数据元素均只有）除最后一个之外，集合中到每个数据元素均只有一个直接后继。一个直接后继。线性结构线性结构的数据包括：的数据包括：线性表线性表 栈栈队列队列串串线性表线性表2.1 线性表

2、的类型定义线性表的类型定义2.3 线性表的线性表的链式表示和实现链式表示和实现2.2 线性表的线性表的顺序表示和实现顺序表示和实现2.1 线性表的类型定义线性表的类型定义线性表线性表（linear_list）是最常用最简单）是最常用最简单的一种数据结构。简言之，一个线性的一种数据结构。简言之，一个线性表是表是n个数据元素的有限序列。个数据元素的有限序列。线性表线性表（linear_list）的特点：）的特点：u同一线性表中的元素必定具有相同的特性，同一线性表中的元素必定具有相同的特性，即属于同一即属于同一 ；u相邻元素之间存在着相邻元素之间存在着 关系；关系；u若将线性表记为：若将线性表记为：

3、(a1,ai-1,ai,ai+1an)，则，则，ai的直接前驱为的直接前驱为 ；ai的直接后继为的直接后继为 ；u线性表中的元素个数为线性表中的元素个数为 个；个； 时为空表；时为空表；u每个元素都有一个确定的位置：每个元素都有一个确定的位置： a1为第一个为第一个元素、元素、an为最后一个元素、为最后一个元素、ai为第为第i个元素，称个元素，称i为数据元素为数据元素ai在线性表中的在线性表中的 。数据对象数据对象序偶序偶ai-1ai+1n位序位序n=0线性表线性表（linear_list）的抽象数据类型定义：）的抽象数据类型定义： ADT定义定义ADT List 数据对象数据对象：D ai

4、| ai ElemSet, i=1,2,.,n, n0 数据关系数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作：基本操作： 初始化线性表初始化线性表：InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L 。 撤销线性表撤销线性表：DestroyList(&L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：销毁线性表操作结果：销毁线性表L。(3)清空线性表清空线性表:ClearList(&L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：将操作结果：将L重置为空表。重置为空表。(4)判空线性表：判

5、空线性表：ListEmpty(L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若L为空表为空表,则返回则返回TRUE，否则返回否则返回FlASE。(5)求线性表的长度：求线性表的长度：ListLength(L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回线性表操作结果：返回线性表L中的数据元素的个数。中的数据元素的个数。(6) 取表元素：取表元素：GetElem(L,i,&e)初始条件：表初始条件：表L存在且存在且1=i=ListLength(L)。操作结果：用操作结果：用e返回线性表返回线性表L中的第个元素的中的第个元素的值。值。(7)

6、定位查找操作：定位查找操作：LocateElem (L,e,compare( )初始条件：线性表初始条件：线性表L存在存在, compare( )是数据元素是数据元素判定函数。判定函数。操作结果：返回操作结果：返回L中第一个与中第一个与e满足关系满足关系compare( )的数据元素的位序的数据元素的位序,若这样的数据元若这样的数据元素不存在，则返回素不存在，则返回0。(8)求前驱：求前驱：PriorElem(L,cur_e,&pre_e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若cur_e是是L的数据元素，且不是第一个，的数据元素，且不是第一个，则用则

7、用pre_e返回它的前驱，否则操作失败，返回它的前驱，否则操作失败，pre_e无定无定义。义。(9)求后继：求后继：NextElem(L, cur_e,&next_e)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：若操作结果：若cur_e是是L的数据元素，且不是最后一的数据元素，且不是最后一 个，则用个，则用next_e返回它的后继，否则操作失败，返回它的后继，否则操作失败，next_e无定义。无定义。(10)插入操作：插入操作：ListInsert(&L,i,e)初始条件：线性表初始条件：线性表L已存在，插入位置正确已存在，插入位置正确 (1=i=ListLen

8、gth(L)+1)。 操作结果：在操作结果：在L中第中第i个位置前插入新的数据元素个位置前插入新的数据元素e，L的长度加的长度加1。(11)删除操作：删除操作：ListDelete(&L,i,&e)初始条件：线性表初始条件：线性表L已存在，且非空，已存在，且非空，1=i=ListLength(L)。操作结果：删除操作结果：删除L的第的第i个元素个元素,并且用并且用e返回其值，返回其值，L的长度减的长度减1。ADT List(12)遍历操作：遍历操作：ListTraverse(L,visit()初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：依次对操作结果：依次对L的

9、每个数据元素调用函数的每个数据元素调用函数visit()。一旦。一旦visit（）失败，则操作失败。（）失败，则操作失败。关于关于“基本操作基本操作”的说明的说明基本操作名基本操作名(参数表参数表) 初始条件：初始条件： 操作结果：操作结果：每个每个基本操作基本操作的定义格式为：的定义格式为： 初始化线性表初始化线性表：InitList(&L)操作结果：构造一个空的线性表操作结果：构造一个空的线性表L 。(5)求线性表的长度：求线性表的长度：ListLength(L)初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回线性表操作结果：返回线性表L中的数据元素的个数。中的数据

10、元素的个数。基本操作名基本操作名(参数表参数表) 初始条件：初始条件： 操作结果：操作结果：每个每个基本操作基本操作的定义格式为：的定义格式为：参数表中参数表中有两种参数：有两种参数：赋值参数赋值参数:只为操作提供输入值；只为操作提供输入值；引用参数引用参数:以以&打头，除可提供输入值，还将返回操作结果。打头，除可提供输入值，还将返回操作结果。(6) 取表元素：取表元素：GetElem(L,i,&e)初始条件：表初始条件：表L存在且存在且1=i=ListLength(L)。操作结果：用操作结果：用e返回线性表返回线性表L中的第个元素的值。中的第个元素的值。“初始条件初始条件”描

11、述了操作执行之前数据结构和参数应满足的描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。条件，若不满足，则操作失败，并返回相应出错信息。“操作结果操作结果”说明了操作正常完成之后，数据结构的变化说明了操作正常完成之后，数据结构的变化状态和应返回的结果。状态和应返回的结果。若初始条件为空，则省略！若初始条件为空，则省略！基本操作基本操作的定义格式为：的定义格式为：基本操作名基本操作名(参数表参数表) 初始条件：初始条件： 操作结果：操作结果：利用上述定义的线性表类型线性表类型 可以实现其它更复杂的操作例例 2-2例例 2-1线性表类型的线性表类型的应用举例应

12、用举例假设:有两个集合集合 A 和和 B 分别用两个线性表线性表 LA 和和 LB 表示（已知条件），即：线性表中的数据元素即为集合中的成员。 要求：一个新的集合要求：一个新的集合AAB。例例 2-1（理解）（理解） 将存在于线性表存在于线性表LB 中中而不存在于不存在于线性表线性表 LA 中中的数据元素插入到线插入到线性表性表 LA 中中去，得到一个扩大后的LA。上述问题可演绎为上述问题可演绎为要求对线性表作如下操作：要求对线性表作如下操作：已知：已知：LA和和LB是线性表，是线性表，类型为类型为List基本操作有基本操作有12种种1依次从线性表依次从线性表 LB 中中取取一个数据元素一个数

13、据元素;2按照按照LB中取的值在中取的值在 LA 中中查找查找是否存在是否存在相等的元素相等的元素; 3若不存在，则将该元素若不存在，则将该元素插入插入LA中中（插入（插入LA表尾即可）表尾即可），LA长度长度+1 。GetElem(Lb, i ,e) /i=1ListLength(LB) LocateElem(La, e, equal( ) ListInsert(La, 表长表长+1, e) /表长表长=ListLength(LA)操作步骤：4. 重复步骤重复步骤13，直到取完，直到取完LB所有元素所有元素 / 取取Lb中第中第i个数据元素赋给个数据元素赋给e if ( ) / La中不存在

14、和中不存在和 e 相同的数据元素，则将相同的数据元素，则将e插入插入La表尾表尾 for (i=1; i= Lb_len; i+) La_len = ListLength(La); Lb_len = ListLength(Lb); / 求线性表的长度求线性表的长度void union(List &La, List Lb) /算法算法2.1-类类C语言语言GetElem(Lb, i, e); ! LocateElem(La, e, equal( ) ListInsert(La, +La_len, e);例例 2-2已知：已知：线性表线性表LALA和和LBLB中的数据中的数据元素按值元素按

15、值非递减有序非递减有序排列。排列。现要求：现要求：将将LALA和和LBLB归并为一个归并为一个新的线性表新的线性表LCLC，且，且LCLC中的数据元素中的数据元素仍按值仍按值非递减有序非递减有序排列。排列。(Ordered List)例如例如：LA=3,5,8,11LB=2,6,8,9,11,15,20则归并后则归并后：LC= 策略？策略？2,3,5,6,8,8,9,11,11,15,201初始化初始化 LC 为空表；为空表；操作步骤：操作步骤：2分别从分别从 LA和和LB中中取得当前元素取得当前元素 ai 和和 bj；3若若 aibj，则将，则将 ai 插入插入到到 LC 表尾表尾(i 加加

16、1)，否则，将否则，将bj 插入插入到到 LC 表尾表尾( j 加加1 ) ；i, j 分别为分别为LA和和LB元元素的当前素的当前位序位序值。值。画图画图4重复重复 2. 和和 3. 两步两步，直至，直至 LA或或LB 中元素中元素 被取完为止；被取完为止；5将将 LB表或表或 LA表中剩余元素复制插入到表中剩余元素复制插入到 LC 表中。表中。操作步骤：操作步骤：InitList(Lc)1初始化初始化 LC 为空表；为空表；2分别从分别从 LA和和LB中中取得当前元素取得当前元素 ai 和和 bj；GetElem(La, i, ai); GetElem(Lb, j, bj);ListIns

17、ert(Lc, 表长表长+1, ai); i+;ListInsert(Lc, 表长表长+1, bj); j+;3若若 aibj，则将，则将 ai 插入插入到到 LC 表尾表尾(i 加加1)，否则，将否则，将bj 插入插入到到 LC 表尾表尾( j 加加1 ) ；void MergeList(List La, List Lb, List &Lc) /本算法将非递减的有序表本算法将非递减的有序表 La 和和 Lb 归并为归并为 Lcwhile (i = La_len) & (j = Lb_len) GetElem(La, i, ai); GetElem(Lb, j, bj); if

18、 (ai = bj) / 将将 ai 插入到插入到 Lc 中中 ListInsert(Lc, +k, ai); +i; else / 将将 bj 插入到插入到 Lc 中中 ListInsert(Lc, +k, bj); +j; /La和和Lb均不空均不空InitList(Lc); / 构造空的线性表构造空的线性表 Lci = j = 1; k = 0; /初始化各个三个表的位序（指针）初始化各个三个表的位序（指针）La_len = ListLength(La);Lb_len = ListLength(Lb); / MergeList while (i = La_len) / 当当La不空时不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入插入 La 表中剩余元素表中剩余元素 while (j = Lb_len) / 当当Lb不空时不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入插入 Lb 表中剩余元素表中剩余元素课本中给出的算法不能直接运行！课本中给出的算法不能直接运行！补充说明：补充说明：1、没有、没有main函数函数2、使用、使用“类类C”语言描述，