1465 数据结构：有序链表的合并

1465 数据结构：有序链表的合并

数据结构：有序链表的合并 Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte Description 线性表a（有n个元素）和线性表b（有m个元素）的元素均为整数，并且均按从小到大排列。现将线性表a和b中的元素合并为一个新的的线性表c，c中的元素仍然按照从小到大排列。其中：0 typedef int ElemType; typedef struct LNode {  ElemType data; struct LNode *next; }LNode,*LinkList; void CreateList_L(LinkList &L,int n) //建立带头结点的n个元素的单链表L，请参考P31 { …………………… …………………… } void MergeList(LinkList &LA,LinkList &LB,LinkList &LC) //归并有序单链表LA和LB得到新的单链表LC，请参考P36 { ……………………………… ……………………………… } void Display_L(LinkList L) //显示链表L中的数据 {   LinkList p=L->next; cout<data; p=p->next; while (p) { cout<<" "<< p->data; p=p->next; } cout<>n; CreateList_L(La,n); cin>>m; CreateList_L(Lb,m); MergeList(La,Lb,Lc); Display_L(Lc); return 0; } Input 只有一个测试案例。 输入包括2行，第1行为n和n个整数，第2行为m和m个整数。 Output 线性表c中的元素。注意：整数之间有1个空格，最后一个整数后面没有空格。 Sample Input 3 1 4 5 4 2 6 7 8 Sample Output 1 2 4 5 6 7 8

AC代码：

#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASSIBLE -1#define OVERFLOW -2using namespace std;typedef int Status;typedef int ElemType;typedef int *Triplet;ElemType *T,*p,*q,ai,bj;typedef struct{ ElemType *elem; int length; int listsize; }SqList;typedef int Status;Status InitList_Sq(SqList &L) { L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK;}Status GetElem (SqList L , int i,ElemType &e) {if(i<1||i>L.length+1) return ERROR; e=L.elem[i-1]; return OK;} Status ListInsert_Sq(SqList &L,int i,ElemType e ){ if (i<1||i>L.length+1) return ERROR; if (L.length>=L.listsize) { T=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); if (!T) exit(OVERFLOW); L.elem=T; L.listsize+=LISTINCREMENT; } q=&(L.elem[i-1]); for (p=&(L.elem[L.length]); p>=q; p--)*(p+1)=*p; *q=e; ++L.length; return OK;} Status MergeList(SqList La, SqList Lb,SqList &Lc){ int i=1,j=1,k=0,La_len,Lb_len,t=1; InitList_Sq(Lc); La_len=La.length; Lb_len=Lb.length; while((i<=La_len)&&(j<=Lb_len)){ GetElem(La,i,ai); GetElem(Lb,j,bj); if(ai<=bj){ ListInsert_Sq(Lc,++k,ai);++i; } else{ ListInsert_Sq(Lc,++k,bj); ++j; } } while(i<=La_len){ GetElem(La,i++,ai); ListInsert_Sq(Lc,++k,ai); } while(j<=Lb_len){ GetElem(Lb,j++,bj); ListInsert_Sq(Lc,++k,bj); } }int main(){ SqList La,Lb,Lc; ElemType elem,elem1; int i,j=0,k=0; int n,m; cin>>n; InitList_Sq(La); InitList_Sq(Lb); InitList_Sq(Lc); La.length=n; for (i=1;i<=n;i++) cin>>La.elem[i-1]; cin>>m; Lb.length=m; for (i=1;i<=m;i++) cin>>Lb.elem[i-1]; Lc.length=m+n; MergeList(La,Lb,Lc); for(i=1;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。