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

痛定思痛。 2022-06-11 09:23 103阅读 0赞

###     ###

法一：一个一个比较，整理这个题的目的在于，归并时，若空间不够，则重新开辟空间，学会使用realloc函数，

法二：全部放到一起，然后重新排序。

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

Time Limit: 100MS Memory Limit: 880KB

[Submit][] [Statistic][] [Discuss][]

#### 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

代码：

view source print ? 
           
            001 #include <stdio.h> 002 #include <stdlib.h> 003 #define LIST_INIT_SIZE 10000 004 #define LISTINCREMENT 100 005 typedef int element; 006 typedef struct 007 { 008 element *elem; 009 int length; 010 int listsize; 011 }SqList; 012 int InitList(SqList *L) 013 { 014 L->elem = (element *)malloc(LIST_INIT_SIZE*sizeof(element)); 015 if(!L->elem) 016 return 0; 017 L->length = 0; 018 L->listsize = LIST_INIT_SIZE; 019 return 1; 020 } 021 int Create(SqList *L,int n) 022 { 023 while(L->listsize-L->length<n) 024 { 025 L->elem = (element *)realloc(L->elem,(LISTINCREMENT+L->listsize)*sizeof(element)); 026 if(!L->elem) 027 return 0; 028 else 029 L->listsize = L->listsize + LISTINCREMENT; 030 } 031 int i; 032 for(i = 0;i<=n-1;i++) 033 scanf("%d",&L->elem[i]); 034 L->length+=n; 035 return 1; 036 } 037 int sun(SqList *L) 038 { 039 if(L->listsize<=L->listsize) 040 { 041 L->elem = (element *)realloc(L->elem,(LISTINCREMENT+L->listsize)*sizeof(element)); 042 if(!L->elem) 043 return 0; 044 else 045 L->listsize = L->listsize + LISTINCREMENT；//合并函数时，加元素，若不够，重新开空间。学会使用realloc函数 046 } 047 L->length++; 048 return 1; 049 050 051 } 052 int Merge(SqList *L,SqList *S,SqList *H) 053 { 054 int i=0,j=0,k=0; 055 056 while(i<L->length&&j<S->length) 057 { 058 if(L->elem[i]>S->elem[j]) 059 { 060 H->elem[k] = S->elem[j]; 061 k++;j++; 062 sun(H); 063 } 064 if(L->elem[i]<=S->elem[j]) 065 { 066 H->elem[k] = L->elem[i]; 067 k++;i++; 068 sun(H); 069 } 070 071 } 072 if(i ==L->length) 073 { 074 while(j<S->length) 075 { 076 H->elem[k] = S->elem[j]; 077 k++;j++; 078 sun(H); 079 } 080 } 081 if(j == S->length) 082 { 083 while(i<L->length) 084 { 085 086 H->elem[k] = L->elem[i]; 087 k++;i++; 088 sun(H); 089 } 090 } 091 return 1; 092 093 } 094 void Display(SqList *H) 095 { 096 int i = 0; 097 for(i =0;i<=H->length-2;i++) 098 { 099 printf("%d ",H->elem[i]); 100 } 101 printf("%d\n",H->elem[H->length-1]); 102 } 103 int main() 104 { 105 int m,n; 106 scanf("%d%d",&m,&n); 107 SqList S,H,L; 108 InitList(&S); 109 Create(&S,m); 110 InitList(&L); 111 Create(&L,n); 112 InitList(&H); 113 Merge(&S,&L,&H); 114 Display(&H); 115 return 0; 116 } 117 118

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/submitsolution/pid/3329.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Solution/status/pid/3329.html
[Discuss]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Discuss/discusslist/pid/3329.html