合并两个顺序表（将两个数组中的数值按由小到大的顺序放到第三个数组中）数据结构

• 原理：排序就是两段代码相互比较，当a中的第 1个小于b中的第1个，就让c中的第1个等于a中的第1个。然后a中的第2个与b中的第1个比较，若是b中的第1个比a中的第2个小，就让c中的第2个等于b中的第一个。再之后就是a中的第2个与b中的第2个相比较，让小的排在前面，依此类推。直到a或b中的一个结束，也就是无值可比的时候，另一方就不用再比较大小（a或b序列无法和自己本身比较大小）直接往c中放就行了。
• 核心算法:

void sort_merge(link *a,link *b,link *c)//排序，合并函数
{
	int i=1,j=1,k=1;

	if(a->last+b->last>maxsize)
		printf("顺序表c太短:\n");
	else
	{
		while(i<=a->last&&j<=b->last)//a和b同时满足未到末尾的条件
		{
			if(a->data[i]<=b->data[j])//a值小于b值得情况下
			{
				c->data[k]=a->data[i];
				i++;
				k++;
			}
			else
			{
				c->data[k]=b->data[j];
				j++;
				k++;
			}
		}//while循环结束

		while(i<=a->last)//b序列已到末尾
		{
				c->data[k]=a->data[i];
				i++;
				k++;
		}

		while(j<=b->last)//a序列已到末尾
		{
			c->data[k]=b->data[j];
				j++;
				k++;	
		}
		c->last=k-1;
	}
	shuchu(c);//调用输出函数输出c
}

• 下面有两段代码，核心代码是一样的，第二段代码是改良之后的版本,当然了，每一段都是完整的程序。

  1.第一段代码只是a或b中的一方未到末尾时，c序列中的值是由小到大排 序。

• 第二段代码确保输出结果全是由小到大排序。

第一段如下：

//将两个数组中的数按由小到大的顺序放到第三个数组中
#include"stdio.h"
#define maxsize 100
typedef struct 
{
	int data[maxsize];
	int last;//长度
}link;

void shuchu(link *a)//打印函数
{
	int i;
	printf("序列如下:\n");
	for(i=1;i<=a->last;i++)//打印，直到末尾
	{
		printf("%d\t",a->data[i]);
	}
	printf("\n");
}

void sort_merge(link *a,link *b,link *c)//排序，合并函数
{
	int i=1,j=1,k=1;

	if(a->last+b->last>maxsize)
		printf("顺序表c太短:\n");
	else
	{
		while(i<=a->last&&j<=b->last)//a和b同时满足未到末尾的条件
		{
			if(a->data[i]<=b->data[j])//a值小于b值得情况下
			{
				c->data[k]=a->data[i];
				i++;
				k++;
			}
			else
			{
				c->data[k]=b->data[j];
				j++;
				k++;
			}
		}//while循环结束

		while(i<=a->last)//b序列已到末尾
		{
				c->data[k]=a->data[i];
				i++;
				k++;
		}

		while(j<=b->last)//a序列已到末尾
		{
			c->data[k]=b->data[j];
				j++;
				k++;	
		}

		c->last=k-1;

	}
	shuchu(c);//调用输出函数输出c
}

void shuru(link *a,link *b,link *c,int q,int p)//输入函数
{
	int i,j,x;
	a->last=0;//初始化
	b->last=0;
	c->last=0;

	printf("请输入a表中的各值:\t");//向a中写值
	for(i=1;i<=q;i++)
	{
		scanf("%d",&x);
		a->data[i]=x;
		a->last++;
	}
	printf("a");
	shuchu(a);//打印刚输入的a序列

	printf("请输入b表中的各值:\t");
	for(j=1;j<=p;j++)
	{
		scanf("%d",&x);
		b->data[j]=x;
		b->last++;
	}
	printf("b");
	shuchu(b);//打印刚输入的b序列
		
	printf("c");
	sort_merge(a,b,c);//排序，合并函数

}

void main()//主函数
{
	link a,b,c;//三个表
	int q,p;//a,b表的长度
	printf("请输入a表的长度:\t");
	scanf("%d",&q);
	printf("请输入b表的长度:\t");
	scanf("%d",&p);
	shuru(&a,&b,&c,q,p);
}

• 出现上图这样的结果不是算法错了，算法是没有问题的。是因为a中的所有值都比b中的第1个值要小，所以a中的值都排在前面。
  

• 由以上的结果可知，第一段中所谓的排序并不是很准确。所以经过改良的第二段代码很准确。但是核心算法是一样的，是没问题的。

第二段如下：
相比第一段，只是在输入之后，多加了一个冒泡排序。

#include"stdio.h"
#define maxsize 100
typedef struct 
{
	int data[maxsize];
	int last;//长度
}link;

void shuchu(link *a)//打印函数
{
	int i;
	printf("序列如下:\n");
	for(i=1;i<=a->last;i++)//打印，直到末尾
	{
		printf("%d\t",a->data[i]);
	}
	printf("\n");
}

void sort_merge(link *a,link *b,link *c)//排序，合并函数
{
	int i=1,j=1,k=1;

	if(a->last+b->last>maxsize)
		printf("顺序表c太短:\n");
	else
	{
		while(i<=a->last&&j<=b->last)//a和b同时满足未到末尾的条件
		{
			if(a->data[i]<=b->data[j])//a值小于b值得情况下
			{
				c->data[k]=a->data[i];
				i++;
				k++;
			}
			else
			{
				c->data[k]=b->data[j];
				j++;
				k++;
			}
		}//while循环结束

		while(i<=a->last)//b序列已到末尾
		{
				c->data[k]=a->data[i];
				i++;
				k++;
		}

		while(j<=b->last)//a序列已到末尾
		{
			c->data[k]=b->data[j];
				j++;
				k++;	
		}

		c->last=k-1;

	}
	shuchu(c);//调用输出函数输出c
}

void shuru(link *a,link *b,link *c,int q,int p)//输入函数
{
	int i,j,x;
	a->last=0;//初始化
	b->last=0;
	c->last=0;

	printf("请输入a表中的各值:\t");//向a中写值
	for(i=1;i<=q;i++)
	{
		scanf("%d",&x);
		a->data[i]=x;
		a->last++;
	}
	shuchu(a);//打印刚输入的a序列

	for(i=q;i>1;i--)//冒泡排序，确保a序列中的值为由小到大。
	{
		for(j=1;j<i;j++)
		{
			if(a->data[j]>a->data[j+1])
			{
				x=a->data[j];
				a->data[j]=a->data[j+1];
				a->data[j+1]=x;
			}
		}
	}
	shuchu(a);//打印刚输入的a序列

	printf("请输入b表中的各值:\t");
	for(j=1;j<=p;j++)
	{
		scanf("%d",&x);
		b->data[j]=x;
		b->last++;
	}
	printf("a");
	shuchu(b);//打印刚输入的b序列
	
	for(i=p;i>1;i--)//冒泡排序，确保b序列中的值为由小到大。
	{
		for(j=1;j<i;j++)
		{
			if(b->data[j]>b->data[j+1])
			{
				x=b->data[j];
				b->data[j]=b->data[j+1];
				b->data[j+1]=x;
			}
		}
	}
	shuchu(b);//打印刚输入的b序列

	sort_merge(a,b,c);//排序，合并函数

}

void main()//主函数
{
	link a,b,c;//三个表
	int q,p;//a,b表的长度
	printf("请输入a表的长度:\t");
	scanf("%d",&q);
	printf("请输入b表的长度:\t");
	scanf("%d",&p);
	shuru(&a,&b,&c,q,p);
}

运行如下:

加了冒泡排序之后，出来的结果就很漂亮了。