Question

【C语言】插入法 向有序数组插入新元素 求大神帮忙改程序

用户先输入一个n，接着输入一个有序排列好（由小到大）的n个整数（我们人为规定没有重复的数据），最后输入一个新数，然后将新数插入进去，形成新的n+1个数的有序数列

输入
n
a_1 a_2 a_3......a_n
k
输出
a_1 a_2 a_3..k....a_n

#include<stdio.h>
int main()
{
int a[1000];
int k;
int i;
int j;
int n;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&k);
for(i=0;i<n;i++)
{
if(k<a[0])
{
for(j=n-1;j>0;j--)
{
a[j]=a[j-1];
}
a[0]=k;
}
if(k>a[i]&&k<a[i+1])
{
for(j=n-1;j>i+1;j--)
{
a[j+1]=a[j];
}
a[i+1]=k;
}
if(k>a[n-1])
{
a[n]=k;
}
}
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}

return0;
}

【输出的最后会有一串奇怪的数，这是为什么？】

Answer 1

你好，我看了下你的基本思想应该是，对K值做了3中假设，1.假设比数组中最小的数a[0]小；2.假设 K处于该数组的中间；3.比该数组最大的值还大。 但是你的错误是出现在第一种,即,k值比a[0]小的情况下，那么我没需要将整个数组后移，那么数组最后一个元素的值a[n-1]就应该变成a[n],可是楼主，你把最后一个值定义成了a[n-1-1]，并将其赋值给a[n-1];这样 你就会丢弃一个a[n-1]的值，数组的长度也就变了，但是 你呢 ！又按照增长后的数组长度去输出打印，最后一个值肯定是随机值，就是你说的奇怪值。所以建议做一下修改
：
if(k<a[0])
{
for(j=n;j>0;j--)
{
a[j]=a[j-1];
}
a[0]=k;
}

追问

大神说的对，我是新手会多多学习。但是我改了以后，输出的数少了一个，加入插在第三个，现在第四个被覆盖掉了。于是我
在这种情况下：if(k>a[i]&&k<a[i+1])
将 a[j+1]=a[j];【改成a[j]=a[j-1];】

结果最后一个数又没了==。这是数组长度问题？请问该怎么改？

追答

童鞋，看你的这段代码：
if(k>a[i]&&ki+1;j--)
{
a[j+1]=a[j]; //这边爱是的情况是将a[i+2]的值搬运到a[i+3]之后，当j=i+1是就退出了；但是这是，a[i+2]的值还是原来的,a[i+1]的值还没被搬运出来，就下面就用k覆盖了。所以错了，应改成j>=i+1;你好好思考
}
a[i+1]=k;
}

Answer 2

 if(k<a[0])//拿到外面来不需要放到for循环里
 {
     for(j=n;j>0;j--)
    {
         a[j]=a[j-1];
     }
    a[0]=k;
 }
 else if(k>a[n-1])  
{
     a[n]=k;
}
 else{
    for(i=0;i<n-1;i++)//这里到n-1
    {
       if(k>a[i]&&k<a[i+1])
       {       
             for(j=n-1;j>i;j--)//这里到i
            {
                a[j+1]=a[j];
            }
            a[i+1]=k;
            break;//已找到位置 可以跳出for循环
        }
     }
 }
 最后输出到i<n+1即可

追问

谢谢，但是不对，插入的那个数输出时没有，而且结尾也有“4032”这种数，求解！

追答

我测试正常啊 把你的数据拿来我试试

Answer 3

for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
修改为
for(i=0;i<n+1;i++)
{
scanf("%d",&a[i]);
}
可以避免下文中许多地方：a[n]越界，就可以正常通过了
最后个return0;

改为return 0;加空格

追问

还是不行==。请赐教！