chap13_线性表.ppt

Chap 13 线性表 线性结构的特点 在数据元素的非空有限集中， （1）存在唯一的一个被称做“第一个”的数据元素； （2）存在唯一的一个被称做“最后一个”的数据元素； （3）除第一个之外，集合中的每个数据元素均只有一个前驱； （4）除最后一个之外，集合中每个数据元素均只有一个后继。 线性表的定义 线性表(Linear List) ：由n(n≧)个数据元素(结点)a1，a2， …an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，…an) 线性表是最常用且最简单的一种数据结构。 线性表是n个数据元素的有限序列。 数据元素可以是一个数、一个符号、也可以是一幅图、一页书或更复杂的信息。 数据元素也可由若干个数据项组成。这时常把数据元素称为记录。含有大量记录的线性表又称文件。 姓 名 学 号 性 别 年龄 健康情况 王小林 790631 男 18 健康 陈 红 790632 女 20 一般 刘建平 790633 男 21 健康 张立立 790634 男 17 神经衰弱 …….. …….. ……. ……. ……. 线性表中的数据元素类型多种多样，但同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系 ai是ai+1的直接前驱元素，ai+1是ai的直接后继元素。 线性表中元素的个数n定义为线性表的长度，为0时称为空表。在非空表中的每个数据元素都有一个确定的位置。ai是第i个元素，把i称为数据元素ai在线性中的位序。 线性表类型定义 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)DestroyList(L)ClearList(L)ListEmpty(L)ListLength(L)GetElem(L,i,e)LocateElem(L,e,compare())PriorElem(L,cur_e,pre_e)NextElem(L,cur_e,next_e) ListInsert(L,i,e)ListDelete(L,i,e)ListTraverse(L,visit()) union(List La,List Lb) }ADT List 算法2.1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B。 void Union(List La, List Lb) { // 算法2.1 // 将所有在线性表Lb中但不在La中的数据元素插入到La中 int La_len,Lb_len,i ;//教材略去本行声明 ElemType e; //教材略去本行声明 La_len = ListLength(La); // 求线性表的长度 Lb_len = ListLength(Lb); for (i=1; i=Lb_len; i++) { GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal)) // La中不存在和e相同的数据元素 ListInsert(La, ++La_len, e); // 插入 } } // union 算法2.2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 void MergeList(List La, List Lb, List Lc) { // 算法2.2 // 已知线性表La和Lb中的元素按值非递减排列。 // 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。 int La_len, Lb_len; ElemType ai, bj; int i=1, j=1, k=0; InitList(Lc); La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i = La_len) (j = Lb_len)) { // La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj)