C语言:向排好序的数组中插入数据

时间:2022-07-31 11:40:40

题目:数组中已按从小到大顺序存有10个整数,键盘输入一个整数插入到数组中,插入后的数据还是按顺序排列的。

实例解析:

解法1:

要向排好序的数据中插入一个数据x,必须首先确定x应该插入到数组的何处,然后再行插入。

要确定x应插入到何处,需要将x依次与数组中的每个元素进行比较,若x小于某元素,则该元素的位置便是x应该插入的位置。这个过程可用下面代码实现。

for(i = 0; i <= 9; i++)

   if(x < a[i])

     break; 

循环结束后,i的值便是x插入后的序号,即a[i]应当存储x。

但是,此时还不能将x存入a[i],因为这样做就把a[i]原值覆盖了。正确的做法是,先把a[i]后移,然后再存入x。但是,如果a[i]后移到a[i+1],就把a[i+1]覆盖了,如何解决?

可以从数组最后一个数据开始向后移动,即先把最后一个后移,再把倒数第二个数据后移……

可用下面代码实现:

k = i;      //用k记录下i的值,以便后面循环再用i作循环变量

for(i = 9; i >= k; i--)

a[i+1] = a[i]; 

完成这一步后,此时空出来一个位置,便可以把x插入到a[k]了:

a[k] = x;

下面是完整的程序代码:

#include <stdio.h>

int main(int argc,const char *argv[])

{int a[11];

        int i,k,x;

        printf("请您输入一个数组中的10个数字:\n");

        for(i=0;i<=9;i++)

            scanf("%d",&a[i]);

        printf("请您输入一个要插入的数字:\n");

        scanf("%d",&x);

        for(i=0;i<=9;i++){

            if(x<a[i])   //找到第一个比x大的数据

 

                break;

        }

        k=i;        //跳出来记住位置

            for(i=9;i>=k;i--){        /*自第k个数据之后的所有数据后移*/

            a[i+1]=a[i];

            

        }a[k]=x;                      //将x插入一定要在for循环外面,在里面会把后面的数据覆盖

        for(i=0;i<=10;i++){

            printf("%d ",a[i]);

        }

    return 0;

}

解法2:

将数组的元素从最后一个开始依次与x比较,若数组元素大于x,则后移,直到遇到一个不大于x的元素或所有元素都比较完了为止。

for(i = 9; i >= 0 && a[i] > x; i--)

   a[i + 1] = a[i];

当循环结束时,存在两种情况:

(1)遇到一个元素,使得a[i]不大于x,此时,x应插入到a[i+1]。

(2)所有元素都比较完了,使得x<0退出循环,x应插入到a[0],亦即a[i+1]。

两种情况都可以用a[i+1] = x; 来完成插入。

解法二的主要代码为:

for(i = 9; i >= 0 && a[i] > x; i--)

   a[i+1] = a[i];

a[i+1] = x;