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

不念不忘少年蓝@ 2022-07-11 13:15 165阅读 0赞

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

  1. 5 3
  2. 1 3 5 6 9
  3. 2 4 10

Example Output

  1. 1 2 3 4 5 6 9 10
  2. #include<stdio.h>
  3. #define MAXSIZE 20006
  4. typedef int ElementType ;
  5. typedef struct node
  6. {
  7. ElementType data[MAXSIZE] ;
  8. int length;
  9. }sq;
  10. void create (sq * l, int n)
  11. {
  12. int i;
  13. for(i=0;i<n;i++)
  14. {
  15. scanf("%d",&l->data[i]);
  16. }
  17. l->length=n-1;
  18. }
  19. void merger(sq * l, sq * s, sq * p)
  20. {
  21. int u=0 ,v=0 ,k=0 ;
  22. while((u<=l->length) && (v<=s->length))
  23. {
  24. if(l->data[u] < s->data[v])
  25. {
  26. p->data[k++]=l->data[u++] ;
  27. }
  28. else
  29. {
  30. p->data[k++]=s->data[v++];
  31. }
  32. }
  33. while(u <= l->length)
  34. {
  35. p->data[k++]=l->data[u++];
  36. }
  37. while(v <= s->length)
  38. {
  39. p->data[k++]=s->data[v++];
  40. }
  41. p->length=l->length+s->length+1;
  42. }
  43. void show (sq * p)
  44. {
  45. int i;
  46. for(i=0;i<=p->length;i++)
  47. {
  48. if(i!=p->length)
  49. printf("%d ",p->data[i]);
  50. else
  51. printf("%d\n",p->data[i]);
  52. }
  53. }
  54. int main()
  55. {
  56. int n,m;
  57. sq l, s, p;
  58. scanf("%d%d",&n,&m);
  59. create(&l,n);
  60. create(&s,m);
  61. merger(&l,&s,&p);
  62. show(&p);
  63. return 0;
  64. }

发表评论

表情:
评论列表 (有 0 条评论,165人围观)

还没有评论,来说两句吧...

相关阅读