22、在有序数组中插入一个数值，数组仍然有序——数组

插入数据，有序数组仍然有序

方法一：

在一个数组中完成的操作

代码实现：

/*
	2017年6月19日16:31:52
	功能：向有序的数组中插入一个数据，但是数据仍然有序
*/
#include<stdio.h> 
#define N 5

void sort(int a[],int num)
{
 	int i,j,temp1,temp2;
	
 	int end = a[N-2];								//a[N-2]是原数组的最大一个数据

	if(num >= end)									//如果插入的数据比原数组中的最大数据还大则插入到数组最后面
  		a[N-1] = num;
 	else											//否则就是在数组的第一位置或者中间位置插入
 	{
 	    for(i = 0; i < N-1; i++)
   		 if(a[i] > num)								//判断插入数值与数组中的元素的大小						
   		{
   			 temp1 = a[i];							//先保存当前位置的值
    		a[i] = num;								//插入数值
   			 for(j = i+1; j < N; j++)				//此处的for循环是对数据进行移位操作
    			{									//以下三行将插入位置之后的数依次向后移动
     				temp2 = a[j];
    				a[j] = temp1;
     				temp1 = temp2;
        		}
  			 break;									//找到合适的位置后就终止外层循环
   		}
	 }
}

int main()
{
 	int a[N]={5,8,10,20};
 	int i=0;
 	int num;

 	printf("原数组的表示形式：");
 	for(i=0;a[i]!='\0';i++)							//a[i]!='\0'注意此形式的写法
 		printf("%d\t",a[i]);

 	printf("\n输入要插入的数：");
 	scanf("%d",&num);

 	sort(a,num);

 	printf("新数组的表示形式：");
 	for(i=0;i<N;i++)
		printf("%d\t",a[i]);

 	printf("\n");

 	return 0;
} 



/*
	总结：
	在VC++6.0中的显示结果：
	----------------------------------------------------------------
	原数组的表示形式：5     8       10      20
	输入要插入的数：15
	新数组的表示形式：5     8       10      15      20
	----------------------------------------------------------------
	此方法是在一个数组中完成的移动操作
*/

　　

方法二：

在新的数组中存储，并且完成操作

代码实现：

/*
	2017年6月19日15:03:14
	功能：在有序的数组中插入一个数据之后，数组仍然是有序的
*/
#include"stdio.h"
#define N 10
#define M 9
int main()
{
	int a[M] = {2,3,4,5,6,7,8,9,9};
	int b[N]; 
	int i, j, num;
	printf("please input a number: ");
	scanf("%d",&num);
	if(num < a[0])							//找出插入的数据在数组中的下标位置
	{
		j = 0;
	}
	else if(num > a[M-1])
	{
		j = M;
	}
	else
	{
		for(i = 0; i < M; i++)
		{
			if( num == a[i])
			{
				j = i;
			}
			if( num > a[i]&& num < a[i+1])
			{
				j = i + 1;
			}	
		}
	}
	for( i = 0; i < N;i++)
	{
		if(i < j)
		{
			b[i] = a[i];
		}
		if(i == j)
		{
			b[i] = num;
		}
		if(i > j)
		{
			b[i] = a[i-1];
		}			
	}
	printf("The new array is ：");
	printf("\n" );
	for(i = 0; i < N; i++)
	{
		printf("%d\t",b[i]);
		
	}
	printf("\n" );
	return 0;
}
/*
	总结：
	在VC++6.0中显示的结果为：
	————————————————————————————————————————
	please input a number: 1
	The new array is ：
	1       2       3       4       5       6       7       8       9       9

	please input a number: 4
	The new array is ：
	2       3       4       4       5       6       7       8       9       9
	————————————————————————————————————————
	采用一个新的数组进行存储
*/