2：线性表.pptVIP

第二章 线性表 本章要点： 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 线性表实现方法的比较 2.1 线性表的类型定义 2.1.1 线性表的概念 1.定义：线性表时由n(n=0)个性质相同的数据元素组成的有限序列。通常记为(a1, a2,…ai-1, ai, ai+1,…an); 其中： n为表长，n=0时，为空表。 ai是一个数据元素，也称为结点。 当1in时，ai的直接前驱是ai-1，a1无直接前驱；ai的直接后继是ai+1， an无直接后继 ai 是第i个数据元素，称i为ai 在线性表中的位置，也就是该数据元素在表中的序号。 元素性质相同，且不能出现缺项 例： (A,B,C,….Z) 例： 学生基本情况登记表 线性结构特点：在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继 2.1.2 线性表的抽象数据 类型 抽象数据类型的定义为：P18 List = (D,R,P) 其中：D = {ai | ai∈D0,i=1,2,…n,n≥0} R = {N}, N = { ai-1 , ai | ai-1 , ai ∈D0 , i = 2,3,…n} D0 为某个数据对象 P：线性表的基本操作 线形表的抽象数据定义 ADT List{ ??数据对象：D={ai|ai∈ElemSet,i=1,2,……,n,n≥0} ??数据关系：R1={ai-1,ai|ai-1,ai∈D,i=2,……,n} ??基本操作： InitList(L) ??操作结果：构造一个空的线性表L。 DestroyList(L) ??初始条件：线性表L已存在。 ?操作结果：销毁线性表L。 ClearList(L) ??初始条件：线性表L已存在。 ??操作结果：将L重置为空表。 ListEmpty(L) ??初始条件：线性表L已存在。 ??操作结果：若L为空表，则返回TRUE,否则返回FALSE。 ListLength(L) ??初始条件：线性表L已存在。 ??操作结果：返回L中数据元素个数。 GetElem(L,i,e) ??初始条件：线性表L已存在,1≤i≤ListLength(L)。 ??操作结果：用e返回L中第i数据个元素的值。 LocateElem(L,e,compare()) ??初始条件：线性表L已存在,compare( )是数据元素判定函数。 ??操作结果：返回L中第1个与e满足关系compare( )的数据元素的位序。若这样的数据元素不存在，则返回值为0。 PriorElem(L,cur_e,pre_e) ??初始条件：线性表L已存在。 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 NextElem(L,cur_e,next_e) ??初始条件：线性表L已存在。 ??操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。 ListInsert(L,i,e) ??初始条件：线性表L已存在,1≤i≤ListLength(L)+1。 ??操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。 ListDelete(L,i,e) ??初始条件：线性表L已存在且非空,1≤i≤ListLength(L)。 ??操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 ListTraverse(L,visit()) 初始条件：线性表L已存在。 操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。 }ADT List 2.1.3 线性表的例子 例2.2 根据实例给出线性表归并的算法 已知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列 如：LA=(1,5,7,15) LB=(3,6,8,9,13,17) 则 LC=(1,3,5,6,7,8,9,13,17) 方法：LC是空表，将LA和LB中元素逐个插入到LC。 void mergelist(list la，list lb，list lc) {//已知线性表 LA 和 LB 中的数据元素按值非递减排列。 //归并 LA 和 LB 得到新的线性表