数据结构教学幻灯片讲义.pptVIP

第二章 线性表; 2.1线性表的类型定义; 3.抽象类型线性表的定义： ADT List { 数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n=0} 数据关系：R1={ai-1,aiai-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数据个元素LocatElem(L,e,compare( )) 初始条件：线性表L已存在，compare（）是数据元素的判定 函数 操作结果：返回L中第1个与e满足关系compar（）数据元素的位序。若这样的数据元素不存在，则返回值为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 两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=A∪B 算法思想：将存在于LB中而不存在于LA??的元素插入到LA中.方法为:依次取LB中每一个元素,依值在LA中查找，若不存在则插入 ;算法思想：设LC为空表，然后将LA或LB中的元素逐个插入到LC中,为将LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB中某个元素，若设i当前所指元素为a，j当前所指的元素为b，则当前插入到LC中的元素c为小的元素值 ;Void MergeList(List La, List Lb,List Lc){ //归并La和Lb得到新的线性表Lc，Lc的数据元素也按值非递减排列 InitList(Lc); //初始化LC表 i=j=1; k=0; La_len=ListLength(La); //求LA表长 Lb_len=Listlength(Lb); //求LB表长 while((i=La_len)(j=Lb_len)) {//LA和LB非空 GetElem(La,i,ai); GetElem(Lb,j,bj); ; if (ai=bj) {ListInsert(Lc,++k,ai); ++i;} else {ListInsert(Lc,++k,bj); ++j;} } While(i=La_len){ GetElem(La,i++,ai); ListInsert(Lc,++k,ai); }