devbox
程序质量控制师
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

两个有序表的合并（三种方法）_顺序表的合并

作者：程序质量控制师 | 2024-02-06 13:38:14

赞

踩

顺序表的合并

设有两个递增排列的有序表，要求合并后仍按递增（非递减）有序排列

目录

一、顺序表

1.1 初始化顺序表

1.2 创建顺序表

1.3 合并两个有序表

1.4 完整代码

二、单链表

2.1 不带头结点的单链表

2.1.1 初始化不带头结点的单链表

2.1.2 创建不带头结点的单链表

2.1.3 合并两个有序表

2.2 带头结点的单链表

2.2.1 初始化带头结点的单链表

2.2.2 创建带头结点的单链表

2.2.3 合并两个有序表

2.3 完整代码

三、运行结果

附：系列文章

一、顺序表

利用顺序存储结构合并有序表， 需要依次从两个有序表中取出一个元素进行比较，将较小的元素放入第三个表中，最后输出第三个表，就是合并后的有序表了

1.1 初始化顺序表

  1. int Init_List(PList L){
  2.     L->data=(int *)malloc(sizeof(int)*SIZE);   //初始化动态分配内存
  3.     L->len=0;      //初始化表长为空
  4.     L->size=SIZE;
  5.     return 1;
  6. }

1.2 创建顺序表

  1. int Creat_List(PList L){
  2. 	int e,i=0;
  3. 	while(scanf("%d",&e)==1){
  4. 		if(L->len>=L->size){     //当前顺序表超长时要重新分配空间
  5. 			L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
  6. 			L->size+=INCREAM;
  7. 		}
  8. 		L->data[i++]=e;
  9. 		L->len++;
  10. 	}
  11. 	return 1;
  12. }

1.3 合并两个有序表

  1. int Connect_List(PList L1,PList L2,PList L3){
  2. 	int i=0,j=0,k=0;
  3. 	if(L1->len+L2->len>L3->size){    //合并有序表要先判断两者长度和是否大于第三个表
  4. 		L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
  5. 		L3->size+=INCREAM;
  6. 	}
  7. 	while(i<L1->len&&j<L2->len){     //循环判断
  8. 		if(L1->data[i]==L2->data[j]){
  9. 		    j++;	
  10. 		}else if(L1->data[i]<L2->data[j]){    //将较小元素放入第三个顺序表
  11. 			L3->data[k++]=L1->data[i++];
  12. 		}else{
  13. 			L3->data[k++]=L2->data[j++];
  14. 		}
  15. 	}
  16. 	while(i<L1->len){              //将另一个未空的顺序表剩余元素放入第三个顺序表
  17. 		L3->data[k++]=L1->data[i++];    
  18. 	}
  19. 	while(j<L2->len){
  20. 		L3->data[k++]=L2->data[j++];
  21. 	}
  22. 	L3->len=k;     //最后别忘了第三个顺序表的长度
  23. 	return 1;
  24. }

1.4 完整代码

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #define SIZE 10
  4. #define INCREAM 10
  5. typedef struct List{
  6. 	int *data;
  7. 	int len;
  8. 	int size;
  9. }List,*PList;
  10. int Init_List(PList L){
  11.     L->data=(int *)malloc(sizeof(int)*SIZE);
  12.     L->len=0;
  13.     L->size=SIZE;
  14.     return 1;
  15. }
  16. int Creat_List(PList L){
  17. 	int e,i=0;
  18. 	while(scanf("%d",&e)==1){
  19. 		if(L->len>=L->size){
  20. 			L->data=(int *)realloc(L->data,(L->size+INCREAM)*sizeof(int));
  21. 			L->size+=INCREAM;
  22. 		}
  23. 		L->data[i++]=e;
  24. 		L->len++;
  25. 	}
  26. 	return 1;
  27. }
  28. int Print_List(PList L){
  29. 	int i;
  30. 	for(i=0;i<L->len;i++){
  31. 		printf("%d ",L->data[i]);
  32. 	}
  33. 	printf("\n");
  34. 	return 1;
  35. }
  36. int Connect_List(PList L1,PList L2,PList L3){
  37. 	int i=0,j=0,k=0;
  38. 	if(L1->len+L2->len>L3->size){
  39. 		L3->data=(int *)realloc(L3->data,(L3->size+INCREAM)*sizeof(int));
  40. 		L3->size+=INCREAM;
  41. 	}
  42. 	while(i<L1->len&&j<L2->len){
  43. 		if(L1->data[i]==L2->data[j]){
  44. 		    j++;	
  45. 		}else if(L1->data[i]<L2->data[j]){
  46. 			L3->data[k++]=L1->data[i++];
  47. 		}else{
  48. 			L3->data[k++]=L2->data[j++];
  49. 		}
  50. 	}
  51. 	while(i<L1->len){
  52. 		L3->data[k++]=L1->data[i++];
  53. 	}
  54. 	while(j<L2->len){
  55. 		L3->data[k++]=L2->data[j++];
  56. 	}
  57. 	L3->len=k;
  58. 	return 1;
  59. }
  60. int main(){
  61. 	List L1,L2,L3;
  62. 	Init_List(&L1);
  63. 	Init_List(&L2);
  64. 	Init_List(&L3);
  65. 	Creat_List(&L1);
  66. 	getchar();
  67. 	Creat_List(&L2);
  68. 	Connect_List(&L1,&L2,&L3);
  69. 	Print_List(&L3);
  70. 	return 0;
  71. }

二、单链表

用单链表合并两个有序表，我们有两种方法，一种是带头结点的单链表，另一个是不带头结点的单链表

2.1 不带头结点的单链表

运用不带头结点单链表时，我们需要先找到两个有序表中首元素较小的有序表，然后将它给第三个表，作为第三个表的首元素，在执行接下来的判断

2.1.1 初始化不带头结点的单链表

  1. PNode Init1_Node(){
  2. 	PNode head;
  3. 	head=NULL;     //初始置头结点为空
  4. 	return head;
  5. }

2.1.2 创建不带头结点的单链表

  1. int Creat1_Node(PNode *head){
  2. 	int e;
  3. 	PNode Last;
  4. 	while(scanf("%d",&e)==1){
  5. 		PNode Pnew=(PNode)malloc(sizeof(Node));
  6. 		Pnew->data=e;
  7. 		Pnew->next=NULL;
  8. 		if(*head==NULL){    //判断头结点是否为空
  9. 			*head=Pnew;        //不带头结点单链表的创建具体见我的专栏
  10. 			Last=Pnew;     
  11. 		}else{
  12. 			Last->next=Pnew;
  13. 			Last=Pnew;
  14. 		}
  15. 	}
  16. 	return 1;
  17. }

2.1.3 合并两个有序表

  1. PNode Connect1_Node(PNode p,PNode q){
  2. 	PNode r;
  3. 	if(p->data<q->data){     //首先要找到首元素较小的，使r的首元素为这个较小元素
  4. 		r=p;                                     
  5. 		p=p->next;
  6. 	}else if(p->data<q->data){
  7. 		r=q;
  8. 		q=q->next;
  9. 	}else{
  10. 		r=p;
  11. 		p=p->next;
  12. 		q=q->next;
  13. 	}
  14. 	while(p&&q){           //然后一直循环，直到其中一个单链表为空
  15. 		if(p->data<q->data){       //将较小的元素插入r后面
  16. 			r->next=p;
  17. 			r=p;
  18. 			p=p->next;
  19. 		}else if(p->data>q->data){   
  20. 			r->next=q;
  21. 			r=q;
  22. 			q=q->next;
  23. 		}else{          //当两者相等时，我们直接跳过即可
  24. 			q=q->next;
  25. 		}
  26. 	}
  27. 	if(p) r->next=p;    //最后将另一个还有元素的单链表连接到r后面
  28. 	if(q) r->next=q;
  29. 	return r;
  30. }

2.2 带头结点的单链表

运用带头结点的单链表合并有序表，我们直接进行判断，将较小的元素插入第三个表的表尾

2.2.1 初始化带头结点的单链表

  1. PNode Init2_Node(){
  2. 	PNode head=(PNode)malloc(sizeof(Node));    //初始化一个头结点
  3. 	head->next=NULL;
  4. 	return head;
  5. }

2.2.2 创建带头结点的单链表

  1. int Creat2_Node(PNode head){
  2. 	PNode p=head;
  3. 	int e;
  4. 	while(scanf("%d",&e)==1){ 
  5. 		PNode Pnew=(PNode)malloc(sizeof(Node));    //具体见专栏 
  6. 		Pnew->data=e;
  7. 		p->next=Pnew;
  8. 		p=Pnew; 
  9. 	}
  10. 	p->next=NULL;
  11. 	return 1;
  12. }

2.2.3 合并两个有序表

  1. int Connect2_Node(PNode head1,PNode head2){
  2. 	PNode head3,p,q,r;
  3. 	p=head1->next;
  4. 	q=head2->next;
  5. 	r=Init2_Node();
  6. 	while(p&&q){          //思路其实和顺序表，不带头结点单链表的思路一样，就是这里
  7. 		if(p->data<q->data){      //不用管两个链表中哪个首元素较小，因为
  8. 			r->next=p;            //我们的头结点没有值
  9. 			r=p;  
  10. 			p=p->next;             //其他和不带头结点单链表方法一样
  11. 		}else if(p->data>q->data){
  12. 			r->next=q;
  13. 			r=q;
  14. 			q=q->next;
  15. 		}else{
  16. 			q=q->next;
  17. 		}
  18. 	}
  19. 	if(p) r->next=p;
  20. 	if(q) r->next=q;
  21. 	return 1;
  22. }

2.3 完整代码

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. typedef struct Node{
  4. 	int data;
  5. 	struct Node *next;
  6. }Node,*PNode;
  7. PNode Init1_Node(){
  8. 	PNode head;
  9. 	head=NULL;
  10. 	return head;
  11. }
  12. PNode Init2_Node(){
  13. 	PNode head=(PNode)malloc(sizeof(Node));
  14. 	head->next=NULL;
  15. 	return head;
  16. }
  17. int Creat1_Node(PNode *head){
  18. 	int e;
  19. 	PNode Last;
  20. 	while(scanf("%d",&e)==1){
  21. 		PNode Pnew=(PNode)malloc(sizeof(Node));
  22. 		Pnew->data=e;
  23. 		Pnew->next=NULL;
  24. 		if(*head==NULL){
  25. 			*head=Pnew;
  26. 			Last=Pnew;
  27. 		}else{
  28. 			Last->next=Pnew;
  29. 			Last=Pnew;
  30. 		}
  31. 	}
  32. 	return 1;
  33. }
  34. int Creat2_Node(PNode head){
  35. 	PNode p=head;
  36. 	int e;
  37. 	while(scanf("%d",&e)==1){
  38. 		PNode Pnew=(PNode)malloc(sizeof(Node));
  39. 		Pnew->data=e;
  40. 		p->next=Pnew;
  41. 		p=Pnew; 
  42. 	}
  43. 	p->next=NULL;
  44. 	return 1;
  45. }
  46. int Print1_Node(PNode head){
  47. 	while(head){
  48. 		printf("%d ",head->data);
  49. 		head=head->next;
  50. 	}
  51. 	printf("\n");
  52. }
  53. int Print2_Node(PNode head){
  54. 	PNode p=head->next;
  55. 	while(p){
  56. 		printf("%d ",p->data);
  57. 		p=p->next;
  58. 	}
  59. 	printf("\n");
  60. 	return 1;
  61. }
  62. PNode Connect1_Node(PNode p,PNode q){
  63. 	PNode r;
  64. 	if(p->data<q->data){
  65. 		r=p;
  66. 		p=p->next;
  67. 	}else if(p->data<q->data){
  68. 		r=q;
  69. 		q=q->next;
  70. 	}else{
  71. 		r=p;
  72. 		p=p->next;
  73. 		q=q->next;
  74. 	}
  75. 	while(p&&q){
  76. 		if(p->data<q->data){
  77. 			r->next=p;
  78. 			r=p;
  79. 			p=p->next;
  80. 		}else if(p->data>q->data){
  81. 			r->next=q;
  82. 			r=q;
  83. 			q=q->next;
  84. 		}else{
  85. 			q=q->next;
  86. 		}
  87. 	}
  88. 	if(p) r->next=p;
  89. 	if(q) r->next=q;
  90. 	return r;
  91. }
  92. int Connect2_Node(PNode head1,PNode head2){
  93. 	PNode head3,p,q,r;
  94. 	p=head1->next;
  95. 	q=head2->next;
  96. 	r=Init2_Node();
  97. 	while(p&&q){
  98. 		if(p->data<q->data){
  99. 			r->next=p;
  100. 			r=p;
  101. 			p=p->next;
  102. 		}else if(p->data>q->data){
  103. 			r->next=q;
  104. 			r=q;
  105. 			q=q->next;
  106. 		}else{
  107. 			q=q->next;
  108. 		}
  109. 	}
  110. 	if(p) r->next=p;
  111. 	if(q) r->next=q;
  112. 	return 1;
  113. }
  114. int main(){
  115. 	PNode p,q;
  116. 	p=Init2_Node();
  117. 	Creat2_Node(p);
  118. 	getchar();
  119. 	q=Init2_Node();
  120. 	Creat2_Node(q);
  121. 	Connect2_Node(p,q);
  122. 	Print2_Node(p);
  123. 	return 0;
  124. }

三、运行结果

附：系列文章

序号文章目录直达链接
1顺序表的十个基本操作（全）https://want595.blog.csdn.net/article/details/127139051
2单链表的十三个基本操作（全）https://want595.blog.csdn.net/article/details/127139598
3四种创建单链表的方法https://want595.blog.csdn.net/article/details/127017405
4删除重复元素（顺序表、单链表）https://want595.blog.csdn.net/article/details/127023468
5两个有序表的合并（三种方法）https://want595.blog.csdn.net/article/details/127104602
6一元多项式相加问题（两种方法）https://want595.blog.csdn.net/article/details/127131351
7约瑟夫环问题（三种方法）https://want595.blog.csdn.net/article/details/127019472
8顺序栈与链栈https://want595.blog.csdn.net/article/details/127035609
9顺序循环队列与链队列https://want595.blog.csdn.net/article/details/127040115
10后缀表达式的转换（栈的运用）https://want595.blog.csdn.net/article/details/127088466
11简单表达式的计算（两种方法）https://want595.blog.csdn.net/article/details/127121720
12next数组（详细求法）https://want595.blog.csdn.net/article/details/127217629
13BF算法（具体应用）https://want595.blog.csdn.net/article/details/127138894
14串的模式匹配相关问题（BF算法、KMP算法）https://want595.blog.csdn.net/article/details/127182721
15二叉树的遍历（七种方法）https://want595.blog.csdn.net/article/details/127472445
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/程序质量控制师/article/detail/62958
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号