教案 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 void purge(List &La,List Lb){ ∥已知线性表Lb中的数据元素依值非递减有序排列，现构造线性表La, ∥使La中只包含Lb中所有值不相同的数据元素 InitList (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(ListEmpty(La)!equal(en,e)) ListInsert(La,+La len,,e;∥La中不存在和e相同的数据元素，则插入之 en=e; }l∥for }∥purge 时间复杂度：O(ListLength(Lb)(前提Lb为有序表)（视GetElem和在表尾的插入操作 为单位时间) 2、算法设计：已知集合B,要求删除B中值相同的多余数据元素。 2、例2-2 已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新 的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。 【设计思路】 输入：线性表La、线性表Lb(均按值非递减有序排列 输出：Lc(按值非递减有序排列→merge(La,Lb,&Lc) 处理方法：，La和Lb均按值非递减有序排列 ∴.设置两个位置指示器i和j,分别指向La和Lb中的某个元素，初始均指向第1个。 比较i和j所指向的元素ai和bj,选取值小的插入到Lc的尾部，并使相应的位置指示器 向后移。 【算法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 <=bi){ ListInsert(Lc,++k,ai);++i; }else ListInsert(Lc,++k,bj);++j;} while(i<=La len){ GetElem(La,i++,ai); ListInsert(Lc,++k,ai); 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第3页程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 3 页 第 3 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 void purge(List &La, List Lb) { // 已知线性表 Lb 中的数据元素依值非递减有序排列，现构造线性表 La， // 使 La 中只包含 Lb 中所有值不相同的数据元素 InitList（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( ListEmpty(La) || !equal(en，e) ) { ListInsert(La, ++La_len, e); // La 中不存在和 e 相同的数据元素，则插入之 en = e; } } // for } // purge 时间复杂度：O(ListLength(Lb)) (前提 Lb 为有序表) (视 GetElem 和在表尾的插入操作 为单位时间) 2、算法设计：已知集合 B，要求删除 B 中值相同的多余数据元素。 2、例 2-2 已知线性表 La 和 Lb 中的数据元素按值非递减有序排列，要求将 La 和 Lb 归并成一个新 的线性表 Lc，且 Lc 中的数据元素仍按值非递减有序排列。 【设计思路】 输入：线性表 La、线性表 Lb(均按值非递减有序排列) 输出：Lc(按值非递减有序排列) ➔merge(La, Lb, &Lc) 处理方法：∵La 和 Lb 均按值非递减有序排列 ∴设置两个位置指示器 i 和 j，分别指向 La 和 Lb 中的某个元素，初始均指向第 1 个。 比较 i 和 j 所指向的元素 ai 和 bj，选取值小的插入到 Lc 的尾部，并使相应的位置指示器 向后移。 【算法 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; } } while (i <= La_len) { GetElem(La, i++, ai); ListInsert(Lc, ++k, ai); }