212线性表的基本操作 该算法运行完后,线性 【例2-2】利用两个线性表 表Lb被销毁!如果要 B,现要求一个新的集合A=/求Lb保持原先的值, 【具体算法】运行后Lb仍保持原先的值 void union ( List &La, List &Lb) La_|en= ListLength(La);∥求线性表La的长度 Lb|en= ListLength(Lb);∥求线性表Lb的长度 for(i=1;i<= Lb len;++)∥b表中的元素尚未处理完 GetElem(Lb,i,&e);∥从Lb中取出第个元素,并将其值赋给e if(! LocateElem(La,e))La中不存在值为e的数据元素 Listlnsert(La,++ La len,e);∥将该元素e插入到La中最后一个元素 后
第 11 页 2.1.2 线性表的基本操作 【例2-2 】利用两个线性表La和Lb分别表示两个集合A和 B，现要求一个新的集合A=A∪B。 【具体算法 】 void union (List &La, List &Lb) { La_len = ListLength (La); //求线性表La的长度 while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完 { ListDelete (Lb, 1, &e); //从Lb中删除第一个元素，并将其值赋给e if (!LocateElem(La, e)) //La中不存在值为e的数据元素 ListInsert (La, ++La_len, e); //将该元素e插入到La中最后一个元素 后 } DestroyList (Lb); //销毁线性表Lb } 该算法运行完后，线性 表Lb被销毁！如果要 求Lb保持原先的值， 算法又如何写？？？ 【具体算法 】___运行后Lb仍保持原先的值 void union (List &La, List &Lb) { La_len = ListLength (La); //求线性表La的长度 Lb_len = ListLength (Lb); //求线性表Lb的长度 for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完 { GetElem (Lb, i, &e); //从Lb中取出第i个元素，并将其值赋给e if (!LocateElem(La, e)) //La中不存在值为e的数据元素 ListInsert (La, ++La_len, e); //将该元素e插入到La中最后一个元素 后 } }
212线性表的基本操作 【例2-3】已知一个非纯集合B(即集合B中可能有相同元素),试 构造一个纯集合A,使A中只包含B中所有值各不相同的成员。 【分析】假设仍以线性表表示集合,则此问题和例2-2类似,即构造 线性表La,使其只包含线性表Lb中所有值不相同的数据元素。所不 同之处是,操作实施之前,线性表La不存在,则操作的第一步首先 应该构造一个空的线性表,之后的操作步骤和例22相同。 【具体步骤】 (1)构造一个空的线性表La; (2)从线性表Lb中取得一个数据元素; (3)依该数据元素的值在线性表La中进行查访; (4)若线性表La中不存在和其值相同的数据元素,则从Lb中删 除的这个数据元素插入到线性表La中。 (5)重复(2)至(4)的操作直至Lb为空表为止
第 12 页 2.1.2 线性表的基本操作 【例2-3 】已知一个非纯集合Ｂ（即集合B中可能有相同元素），试 构造一个纯集合A，使Ａ中只包含B中所有值各不相同的成员。 【分析 】假设仍以线性表表示集合，则此问题和例2-2类似，即构造 线性表La，使其只包含线性表Lb中所有值不相同的数据元素。所不 同之处是，操作实施之前，线性表La不存在，则操作的第一步首先 应该构造一个空的线性表，之后的操作步骤和例2-2相同。 【具体步骤 】 （1）构造一个空的线性表La； （2）从线性表Lb中取得一个数据元素； （3）依该数据元素的值在线性表La中进行查访； （4）若线性表La中不存在和其值相同的数据元素，则从Lb中删 除的这个数据元素插入到线性表La中。 （5）重复（2）至（4）的操作直至Lb为空表为止
212线性表的基本操作 该算法运行完后,线性 【例2-3】已知一个非纯集合B 构造一个纯集合A,使A中只包 表Lb同样被销毁!如 P果要求Lb保持原先的 【具体算法】运行后Lb仍保持原先的值 void purge list &La, List &Lb) netList(La);La_len=0;∥创建一个空的线性表La Lb|en= ListLength(Lb);∥求线性表Lb的长度 for(i=1;i<= Lb len;++)∥b表中的元素尚未处理完 GetElem (Lb, i,&e); ∥从Lb中取出第个元素,并将其值赋给e if(! Locate elem(La,e)∥La中不存在值为e的数据元素 Listlnsert(La,++ La len,e);∥将该元素e插入到La中最后一个元素 后
第 13 页 2.1.2 线性表的基本操作 【例2-3 】已知一个非纯集合Ｂ（即集合B中可能有相同元素），试 构造一个纯集合A，使Ａ中只包含B中所有值各不相同的成员。 【具体算法 】 void purge (List &La, List &Lb) { InitList (La); La_len = 0 //创建一个空的线性表La while ( !ListEmpty(Lb) ) //Lb表中的元素尚未处理完 { ListDelete (Lb, 1, &e); //从Lb中删除第一个元素，并将其值赋给e if (!LocateElem(La, e)) //La中不存在值为e的数据元素 ListInsert (La, ++La_len, e); //将该元素e插入到La中最后一个元素 后 } DestroyList (Lb); //销毁线性表Lb } 该算法运行完后，线性 表Lb同样被销毁！如 果要求Lb保持原先的 值，算法又如何写？？？ 【具体算法 】___运行后Lb仍保持原先的值 void purge (List &La, List &Lb) { InitList (La); La_len = 0; //创建一个空的线性表La Lb_len = ListLength (Lb); //求线性表Lb的长度 for (i = 1; i <= Lb_len; i++) //Lb表中的元素尚未处理完 { GetElem (Lb, i, &e); //从Lb中取出第i个元素，并将其值赋给e if (!LocateElem(La, e)) //La中不存在值为e的数据元素 ListInsert (La, ++La_len, e); //将该元素e插入到La中最后一个元素 后 } }
212线性表的基本操作 【例24】判别两个集合A和B是否相等。 分析】两个集合相等,指的是这两个集合中包含的成员相同。当以线性表表示 集合时,则要求分别表示这两个集合的线性表La和Lb,不仅长度相同,所含数据 元素也必须一一对应。值得注意的是,两个“相同”的数据元素在各自的线性表 中的“位序”不一定相同。因此,如果在一个线性表中找不到和另一个线性表的 某个数据元素相同的数据元素,则立即可以得出“两个集合不等”的结论;反之, 只有当判别出“其中一个线性表只包含和另一个线性表相同的全体成员”时,才 得出“两个集合相等”的结论。 方法一】使用辅助结构Lc (1)若线性表La和线性表Lb的长度不等,则返回两集合不等 2)构造一个线性表Lc (3)将线性表La中的数据元素复制到线性表Lc中,使得Lc与La相同; (4)对Lb中的每个数据元素,在Lc中进行查询; (5)若Lc中存在与该数据元素相同的数据元素,则从Lc中删除该元素; (6)重复(4)和(5)步,直到Lb中的数据元素都遍历完为止; (7)如果Lc为空,则返回两集合相等,否则,返回两集合不等
第 14 页 2.1.2 线性表的基本操作 【例2-4 】判别两个集合A和B是否相等。 【分析 】两个集合相等，指的是这两个集合中包含的成员相同。当以线性表表示 集合时，则要求分别表示这两个集合的线性表La和Lb，不仅长度相同，所含数据 元素也必须一一对应。值得注意的是，两个“相同”的数据元素在各自的线性表 中的“位序”不一定相同。因此，如果在一个线性表中找不到和另一个线性表的 某个数据元素相同的数据元素，则立即可以得出“两个集合不等”的结论；反之， 只有当判别出“其中一个线性表只包含和另一个线性表相同的全体成员”时，才 得出“两个集合相等”的结论。 【方法一 】____使用辅助结构Lc （1）若线性表La和线性表Lb的长度不等，则返回两集合不等； （2）构造一个线性表Lc； （3）将线性表La中的数据元素复制到线性表Lc中，使得Lc与La相同； （4）对Lb中的每个数据元素，在Lc中进行查询； （5）若Lc中存在与该数据元素相同的数据元素，则从Lc中删除该元素； （6）重复（4）和（5）步，直到Lb中的数据元素都遍历完为止； （7）如果Lc为空，则返回两集合相等，否则，返回两集合不等
212线性表的基本操作 【例24】判别两个集合A和算法中构造的线性表Lc是 辅助结构,它的引入是为 【具体算法】方法一 了在程应赫行计和由不破坏 bool isequal (list la, l ict 的 f(Listlenath如果不使用辅助结 ListLength( Lb return(FAL 构Lc,那算法又 etL如何设计呢??? .C, i, e); Lb_len= ListLength for (k= 1; k<=La len; k++ round & ListEmpty(Lc)) return (TRUE; GetElem La, k, e); else ListInsert (&LC, k,e return (FALSE; Destroy List(&Lc) foundE true
第 15 页 2.1.2 线性表的基本操作 【例2-4 】判别两个集合A和B是否相等。 【具体算法 】____方法一 bool isequal (List La, List Lb) { if ( ListLength(La) != ListLength(Lb) ) return (FALSE); InitList (&Lc); La_len = ListLength (La); Lb_len = ListLength (Lb); for (k = 1; k <= La_len; k++) { GetElem (La, k, e); ListInsert (&Lc, k, e); } found = TRUE; for (k = 1; k <= Lb_len, found; k++) { GetElem (Lb, k, e); i = LocateElem (Lc, e); if (i == 0) found = FALSE; else ListDelete (&Lc, i, e); } if (found && ListEmpty(Lc)) return (TRUE); else return (FALSE); DestroyList (&Lc); } 算法中构造的线性表Lc是 一辅助结构，它的引入是为 了在程序执行过程中不破坏 原始数据La，因此算法的 如果不使用辅助结 最后应销毁Lc！ 构Lc，那算法又 如何设计呢？？？