2.1线性表的类型定义-ADT List 2.1线性表的类型定义-例2-1 ,ADT List定义 ,基于ADT List的算法设计 ·P19 ·例2-1复设利用两个战性表La利b分别表示两个集合A和B 基本操作 (即：戴性表中的敏据元素即为果合中的成黄】，观要求一 个新的集金A一AUB。 。初始化、筛毁 ,查询：个体、整体 物入：线性表La、线性表b 。动志变化：播入、时除 输出：变化了的La 争union(&La,Lb) 处理方法：扩大线性表La,将存在于线性表Lb中而不存在于 ·重点掌提以下三个基本操作 线性表La中的敏搭元素辑入到铁性表La中去。 。GetElem(L,i,&e) 8 步骤： ListInsert(&L,i,e) ~1,从线性表b中依次取得每个数据元素 ListDelete(&L,i,&e) LocateElem 2,依值在线性表La中进行查访 注意：接口的形式可以略有变化，如e=GetElem(L,) 不存在，则插入之 7 回 1的 73 回 2.1线性表的类型定义-例2-1 21线性表的类型定义削2.2 void union(List &La,List Lb){ ,基于ADT List的算法设计 /∥将所有在城性表b中不在La中的数元素入到a中 La_len ListLength(La); 。例2-2巴加旋性兼La布Lb中的数据元素妆值摔递减有序掉 e是变◆ Lb_Jen=ListLength(b:/求，性囊的长度 列，要求将La不Lb归并成一个新的战性表L,且Lc中的数据 调用时不 元素仍：值非递减有序神列。 加&符号 =i<=地e;it+) GetElem(b,同：/取Lb中第i个数W元肃减皓e 输入：线性表La、线性表b(均按值丰道减有序排列) if(LocateElem(La.e.eoual)) 输出：Lc(拨值非道减有序排列merge(La,Lb,&Lc) /La中不存在和e相同的元豪，则插入之 处理方法：：La和Lb均按值非通减有序排列 ListInsert(La,++La_len,e); ∴设置两个位置指示器和j,分别指肉L和Lb中的某个元 )/union 素，初始均指向第1个。LC初始化为空表。 比较和所指肉的元景a和bj,进取值小的插入到Lc的尾部， T(na,nb)=O(b*na),na、nb表示La表和Lb表的长度 并使相应的位置指示卷向后移。 算法：算法2.2P21 9/73 图 10y73 图 2.1线性表的类型定义-例2-2 2,1线性表的类型定义-例2-2 void MergeList(List La,List Lb,List &Lc){ a和Lb中的元素教值非 /归La和Lb得到断的，性表Lc,Lc的元素拔值非递减排列。 ListInsert(Lc,++k,ai); InitList(Lc); i=j=1;k=0: while (j<=Lb_len){ La_len ListLength(La); GetElem(Lb,j++,bj); Lb len ListLength(Lb): ListInsert(Lc,++k,bj); while ((i<=La_len)&&(j<=Lb_len)){ a和b均非空 }//MergeList GetElem(La,i,ai);GetElem(Lb,j,bj); if (ai<=bj){ ListInsert(Lc,++k,ai);++i; T(na,nb)=O(na+nb) ListInsert(Lc,++k,bj);++j; 1/ 图 12万 图7/73 2.1 线性表的类型定义-ADT List „ ADT List定义 „ P19 基本操作 „ 初始化、销毁 „ 查询：个体、整体 „ 动态变化：插入、删除 „ 重点掌握以下三个基本操作 „ GetElem(L, i ,&e) „ ListInsert(&L, i, e) „ ListDelete(&L, i, &e) 注意: 接口的形式可以略有变化,如 e = GetElem(L, i) 8/73 2.1 线性表的类型定义-例2-1 „ 基于ADT List的算法设计 „ 例2-1 假设利用两个线性表La和Lb分别表示两个集合A和B （即：线性表中的数据元素即为集合中的成员），现要求一 个新的集合A＝A∪B。 输入：线性表La、线性表Lb 输出：变化了的La Îunion(&La, Lb) 处理方法：扩大线性表La，将存在于线性表Lb中而不存在于 线性表La中的数据元素插入到线性表La中去。 步骤： 1．从线性表Lb中依次取得每个数据元素; 2．依值在线性表La中进行查访; 3．若不存在，则插入之。 算法：算法2.1 P20 ListLength GetElem LocateElem ListInsert 9/73 2.1 线性表的类型定义-例2-1 void union(List &La, List Lb) { // 将所有在线性表Lb中但不在La中的数据元素插入到La中 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 T(na, nb) =O(nb*na), na、nb表示La表和Lb表的长度 e是变参, 调用时不 加&符号 10/73 2.1 线性表的类型定义-例2-2 „ 基于ADT List的算法设计 „ 例2-2 已知线性表La和Lb中的数据元素按值非递减有序排 列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据 元素仍按值非递减有序排列。 输入：线性表La、线性表Lb(均按值非递减有序排列) 输出：Lc(按值非递减有序排列) Îmerge(La, Lb, &Lc) 处理方法：∵La和Lb均按值非递减有序排列 ∴设置两个位置指示器i和j，分别指向La和Lb中的某个元 素，初始均指向第1个。Lc初始化为空表。 比较i和j所指向的元素ai和bj，选取值小的插入到Lc的尾部， 并使相应的位置指示器向后移。 算法：算法2.2 P21 11/73 2.1 线性表的类型定义-例2-2 void MergeList(List La, List Lb, List &Lc) { // 已知线性表La和Lb中的元素按值非递减排列。 // 归并La和Lb得到新的线性表Lc，Lc的元素按值非递减排列。 InitList(Lc); i = j = 1; k = 0; 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); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; }else { ListInsert(Lc, ++k, bj); ++j; } } 12/73 2.1 线性表的类型定义-例2-2 while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); } while (j <= Lb_len) { GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj); } } // MergeList T(na, nb) =O(na+nb)