模拟链表

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

链表中的每一个结点只有两个部分。我们可以用一个数组 data 来存储每序列中的每一个
数。那每一个数右边的数是谁，这一点该怎么解决呢？上一节中是使用指针来解决的，这里
我们只需再用一个数组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中），如下。

用数组模拟链表的方法实现：

#include <stdio.h>

int main(){
    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;
    //初始化数组right

    for(i=1;i<=n;i++){
        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;
    }