一、问题描述

有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32.现需要往这串数中插入6使其得到的新序列仍符合从小到大的排列。

 

二、问题分析

我们可以用一个数组data来存储每个序列中的每一个数，再用一个数组right来存放序列中每一个数右边的数是谁。

              1            2              3           4            5              6           7             8            9              10

data        

                                                              

             1            2              3           4            5              6           7             8            9              10

right 

 

 

上图的两个数组中，第一个整型数组data是用来存放序列中具体数字的，另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中位置的。

比如right[1]的值为2，就表示当前序列中1号元素右边的元素存放在data[2]中；如果是0，比如right[9]的值为0，就表示当前序列中9号元素的右边没有元素。

现在需要在8前面插入一个6，只需将6直接存放在数组data的末尾即data[10]=6。接下来只需要将right[3]改为10，表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4，表示新序列中10号元素右边的元素存放在data[4]中。这样我们通过right数组就可以从头到尾遍历整个序列了（序列的每个元素的值存放在对应的数组data中），如下：

              1            2              3           4            5              6           7             8            9              10

data 

 

              1            2              3           4            5              6           7             8            9              10

right 

 

三、代码实现

int data[101],right[101];    int i,n,t,len;    scanf("%d",&n);  //输入已有的数    for(i=1;i<=n;i++)        scanf("%d",&data[i]);    len=n;    for(i=1;i<=n;i++)  //初始化数组right    {        if(i!=n)            right[i]=i+1;        else            right[i]=0;    }     len++;  //直接在数组data的末尾增加一个数     scanf("%d",&data[len]);      /*从链表的头部开始遍历*/    t=1;    while(t!=0)    {        if(data[right[t]]>data[len])  //如果当前结点下一个结点的值大于待插入数，将数输入到中间        {            right[len]=right[t];  //新插入数的下一个结点标号等于当前结点的下一个结点标号            right[t]=len;  //当前结点的下一个结点编号就是新插入数的编号            break;  //插入完成跳出循环         }         t=right[t];    }     /*输出链表中所有的数*/     t=1;    while(t!=0)    {        printf("%d ",data[t]);        t=right[t];        }    return 0;