数据结构例程——合并有序表

本文针对数据结构基础系列网络课程(2)：线性表中第15课时有序表。

问题：有两个有序表LA和LB，将它们合并成一个有序表LC。要求不破坏原有表LA和LB 算法思想：

解法1：用顺序表实现(支持的算法库，及list.h文件，请点击链接…)

#include "list.h" void UnionList(SqList *LA,SqList *LB,SqList *&LC) { int i=0,j=0,k=0; //i、j、k分别作为LA、LB、LC的下标 LC=(SqList *)malloc(sizeof(SqList)); LC->length=0; while (i<LA->length && j<LB->length) { if (LA->data[i]<LB->data[j]) { LC->data[k]=LA->data[i]; i++; k++; } else //LA->data[i]>LB->data[j] { LC->data[k]=LB->data[j]; j++; k++; } } while (i<LA->length) //LA尚未扫描完,将其余元素插入LC中 { LC->data[k]=LA->data[i]; i++; k++; } while (j<LB->length) //LB尚未扫描完,将其余元素插入LC中 { LC->data[k]=LB->data[j]; j++; k++; } LC->length=k; } int main() { SqList *L1,*L2,*L3; ElemType a[]= {1,3,5}; ElemType b[]= {2,4,8,10}; CreateList(L1,a,3); printf("L1:"); DispList(L1); CreateList(L2,b,4); printf("L2:"); DispList(L2); printf("归并\n"); UnionList(L1,L2,L3); printf("L3:"); DispList(L3); DestroyList(L1); DestroyList(L2); DestroyList(L3); }

解法2：用单链表实现(支持的算法库，及linklist.h文件，请点击链接…)

#include <stdio.h> #include <malloc.h> #include "linklist.h" void UnionList1(LinkList *LA,LinkList *LB,LinkList *&LC) { LinkList *pa=LA->next,*pb=LB->next,*pc,*s; LC=(LinkList *)malloc(sizeof(LinkList)); //创建LC的头结点 pc=LC; //pc始终指向LC的最后一个结点 while (pa!=NULL && pb!=NULL) { if (pa->data<pb->data) { s=(LinkList *)malloc(sizeof(LinkList));//复制*pa结点 s->data=pa->data; pc->next=s;pc=s; //采用尾插法将*s插入到LC的最后 pa=pa->next; } else { s=(LinkList *)malloc(sizeof(LinkList));//复制*pb结点 s->data=pb->data; pc->next=s;pc=s; //采用尾插法将*s插入到LC的最后 pb=pb->next; } } while (pa!=NULL) { s=(LinkList *)malloc(sizeof(LinkList)); //复制*pa结点 s->data=pa->data; pc->next=s;pc=s; //采用尾插法将*s插入到LC的最后 pa=pa->next; } while (pb!=NULL) { s=(LinkList *)malloc(sizeof(LinkList)); //复制*pa结点 s->data=pb->data; pc->next=s;pc=s; //采用尾插法将*s插入到LC的最后 pb=pb->next; } pc->next=NULL; } int main() { LinkList *L1,*L2,*L3; ElemType a[]={1,3,5}; ElemType b[]={2,4,8,10}; CreateListR(L1,a,3); printf("L1:");DispList(L1); CreateListR(L2,b,4); printf("L2:");DispList(L2); printf("归并\n"); UnionList1(L1,L2,L3); printf("L3:");DispList(L3); DestroyList(L1); DestroyList(L2); DestroyList(L3); return 0; }