顺序表应用5：有序顺序表归并

顺序表应用5：有序顺序表归并

Time Limit: 100MS  Memory Limit: 800KB Submit  Statistic

Problem Description

已知顺序表A与B是两个有序的顺序表，其中存放的数据元素皆为普通整型，将A与B表归并为C表，要求C表包含了A、B表里所有元素，并且C表仍然保持有序。

Input

 输入分为三行： 第一行输入m、n（1<=m,n<=10000）的值，即为表A、B的元素个数； 第二行输入m个有序的整数，即为表A的每一个元素； 第三行输入n个有序的整数，即为表B的每一个元素；

Output

 输出为一行，即将表A、B合并为表C后，依次输出表C所存放的元素。

Example Input

5 3 1 3 5 6 9 2 4 10

Example Output

1 2 3 4 5 6 9 10

#include <stdio.h> #include <iostream> #include <stdlib.h> #include <malloc.h> #define LISTINCREASMENT 100                 /*每次分配元素的个数*/ #define  LISTSIZE 10                           /*顺序存储的最大个数*/ #define  OVERFLOW -1 #define  OK 1 int n,m; using namespace std; typedef int ElemType; typedef struct                                   /*顺序表元素的的定义*/ {     ElemType * elem;     int length;     int listsize; } Sqlist; int SqInitial(Sqlist &L)                           /*初始化线性表*/ {     L.elem=(ElemType *) malloc (LISTSIZE*sizeof(ElemType));     if (! L.elem)  exit(OVERFLOW); //存储分配失败     L.length=0;     L.listsize=LISTSIZE;     return OK; } int ListInsert(Sqlist &L,int i,ElemType e)            /*插入元素*/ {     if(i<1|| i > L.length+1) exit(-1);     if(L.length>=L.listsize)     {         ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREASMENT)                                             *sizeof(ElemType));         if(!newbase)   return  OVERFLOW;// 当前存储空间已满L.elem=newbase;         L.listsize+=LISTINCREASMENT;         /*表的容量不足分配内存*/     }     ElemType *  q=&(L.elem[i-1]);     ElemType *  p;     for(p=&(L.elem[L.length-1]); p>=q; --p)         *(p+1)=*p;     *q=e;     ++L.length;     return OK; } void display(Sqlist &L) {     int i;     for(i=0;i<L.length-1;i++)     {         cout<<L.elem[i]<<" ";     }      cout<<L.elem[i]<<endl; } void Merge(Sqlist &L,Sqlist &L1,Sqlist &L2) {     int i=0,j=0,t=0,f;     while(i<n && j<m)     {    t++;         if(L.elem[i]<L1.elem[j])         {             ListInsert(L2,t,L.elem[i]);             i++;         }         else         {             ListInsert(L2,t,L1.elem[j]);             j++;         }     }    // cout<<"提前输出"<<endl;    // display(L2);     while(i<n)     {            t++;            ListInsert(L2,t,L.elem[i]);            i++;     }     while(j<m)     {         t++;         ListInsert(L2,t,L1.elem[j]);         j++;     }    // cout<<"i=="<<i<<" j=="<<j<<endl; } int main() {     Sqlist L,L1,L2;     int t =1 ,d;     cin>>n>>m;     SqInitial(L);     SqInitial(L1);     SqInitial(L2);     //printf("构建长度为len的顺序表。\n");     for(t=1; t<=n; t++)                         /*构建长度为n的顺序表*/     {         //printf("Please input the %dth list elem:",t);         scanf("%d",&d);         ListInsert(L,t,d);     }     for(t=1; t<=m; t++)                         /*构建长度为n的顺序表*/     {                 scanf("%d",&d);         ListInsert(L1,t,d);     }     Merge(L,L1,L2);     display(L2);return 0; }

转载于:https://www.cnblogs.com/CCCrunner/p/6444614.html

相关资源：JAVA上百实例源码以及开源项目