作用于顺序表的算法.ppt

作用于顺序表的算法 上次课，我们介绍了顺序表的原理及实现方法，还构造了一个顺序表。本次课，我们将在上次课的基础上，来讨论基于顺序表的一些算法。在应用中来加深对顺序表的理解。 1、有序顺序表的合并。 对应于26页算法2.7。 已知顺序表LA、LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的顺序表LC，且LC中的数据元素仍按值非递减有序排列。 下面是顺序表归并算法的具体实现 void MergeList_Sq(SqList LA,SqList LB,SqList LC) {///LA、LB中元素原来按非递减顺序存储 /////要求合并后的LC也按照非递减序存储 int i,j,k; i=j=k=1; //下面生成线性表LC LC.length=LA.length+LB.length; LC.listsize=LA.length+LB.length+1; LC.elem=(ElemType*)malloc((LC.listsize)*sizeof(ElemType)); while(i=LA.length j=LB.length) {//当LA、LB同时不为空时，进行下面操作 ElemType pa=LA.elem[i];//取LA的第i个元素 ElemType pb=LB.elem[j];//取LB的第j个元素 if(pa=pb) {//如果pa=pb LC.elem[k]=pa;//pa插入LC尾部 k++;i++;//LC、LA下标后移 } else { LC.elem[k]=pb; k++;j++; } } while(i=LA.length) {//如果LA中还有元素，则所有元素全部插入LC尾部 ElemType pa=LA.elem[i]; LC.elem[k]=pa; k++;i++; } while(j=LB.length) {//如果LB中还有元素，则所有元素全部插入LC尾部 ElemType pb=LB.elem[j]; LC.elem[k]=pb; k++;j++; } } 另一种方法 void MergeList111_Sq(SqList LA,SqList LB,SqList LC) {///LA、LB中元素原来按非递减顺序存储 /////要求合并后的LC也按照非递减序存储 int i,j,k; i=j=1; InitList_Sq(LC);//此处和上面算法中不同。 while(i=LA.length j=LB.length) { ElemType pa=LA.elem[i]; ElemType pb=LB.elem[j]; if(pa=pb) { ListInsert_Sq(LC,LC.length+1,pa); i++; } else { ListInsert_Sq(LC,LC.length+1,pb); j++; } } while(i=LA.length) { ElemType pa=LA.elem[i]; ListInsert_Sq(LC,LC.length+1,pa); k++;i++; } while(j=LB.length) { ElemType pb=LB.elem[j]; ListInsert_Sq(LC,LC.length+1,pb); j++; } } 2、求集合的并集 对应于20页算法2.1的实现。 假定利用两个顺序表LA和LB分别表示两个集合A和B，现在要求一个新的集合A=A∪B。集合中不允许元素重复。 下面是顺序表求并集算法的具体实现 void union1(SqList LA,SqList LB) {//求集合LA、LB两个集合的并集，不允许有重复元素 int i,j; for(j=1;j=LB.length;j++) { ElemType e=LB.elem[j]; if(LocateElem_Sq(LA,e,equal)==0)//LA中不存在 { ListInsert_Sq(LA,LA.length+1,e); } } } 测试数据： int main(int argc, char* argv[]) { SqList LA,LB; InitList_Sq(LA); InitList_Sq(LB); int a[4]={3,5,8,11}; int b[7]={2,6,8,9,11,15,20}; for(int i=0;i4;i++) ListIn