第五章计算机实验卡.doc

常见的线性表的基本运算：1. InitList（L） ??构造一个空的线性表L，即表的初始化。2. DestroyList(L)??销毁线性表。 3. ClearList(＆L)??将L重置为空表。4. ListEmpty(L)??若L为空表，则返回 TRUE，否则返回FALSE。5. ListLength（L） ??求线性表L中的结点个数，即求表长。6. GetElem(L，i，e)??用e返回L中第i数据个元素的值。这里要求1≤i≤ListLength（L）7. LocateElem(L，e，compare( ))??返回L中第1个与e满足关系compare( )的数据元素的位序。 不存在，则返回值为0。 8. ListInsert(L，i，e)??在L中第i个位置之前插入新的数据元素e，L的长度加1。 9. ListDelete(L，i，e)??删除L的第i个数据元素，并用e返回其值，L的长度减1。 组合基本运算，实现复杂运算：1. 假设利用两个线性表LA和LB分别表示两个集合A和B(即：线性表中的数据元素即为集合中的成员)，现要求一个新的集合A=AUB。????[思想]：这就要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素，并依值在线性表LA中进行查访，若不存在，则插入之。????[算法描述如下]：????vold 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)) ????????????ListInsert (La， ++La_len， e)； //La中不存在和e相同的数据元素，则插入 ??????}????} //union ????算法 2.1 2. 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。????[思想]：????从上述问题要求可知，LC中的数据元素或是LA中的数据元素，或是LB中的数据元素，则只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB中某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到LC中的元素min(a , b)；显然，指针i和j的初值均为1，在所指元素插入LC之后，在LA或LB中顺序后移。????[归并算法如算法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 = ListLehgth(Lb)； ??????while((i=La_len)(j=Lb_len)) //La和Lb均非空{ ????????GetElem(La，i，ai)； ????????GetElem(Lb，j，bj)；????????if (ai = bj) {Listlnsert(Lc，++k，ai )；++i；}????????else {Listlnsert(Lc， ++k， bj)； ++j； }????????} ??????while(i=La_len){ ????????GetElem(La，i++，ai)； ????????Listlnsert(Lc，++k，ai )；}??????while(j=Lb_len){ ????????GetElem(Lb，j++，bj)；????????Listlnsert(Lc，++k，bj)；}????} //?算法 2.2单链表上实现的运算： 1. 归并两个单链表的算法。 ????void MergeList_L (LinkList La， LinkList Lb，L