链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。

单向链表.jpg

模拟链表

结构体模拟链表

先用一个结构体来表示链表的结点类型

struct node{
    int data;
    struct node *next;
};

那么循环输入几个数存入链表中就可以这样写

    head = NULL; // 头指针的初始为空
    for (i = 0; i <= n; i++) {
        
        scanf("%d",&a);
        // 动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
        p = (struct node*)malloc(sizeof(struct node));
        // 将数据存储到当前结点的data域中
        p->data = a;
        // 设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
        p->next = NULL;
        if (head == NULL) {
            // 如果这是第一个创建的结点，则将头指针指向这个结点
            head = p;
        }else{
            // 不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
            q ->next = p;
        }
        p = q;  // 指针q也指向当前结点
    }

那么在这个链表中间插入一个数的话又该如何操作呢？首先用一个临时指针t从链表的头部开始遍历，等到指针t的下一个结点的值比插入的数大的时候，就将插入的数插入到中间即可。

    t= head;    // 从链表头部开始遍历
    while (t != NULL) {// 没有到达链表尾部的时候循环
        // 如果当前结点是最后一个结点或者下一个结点的值大于待插入数的时候插入
        if (t ->next == NULL || t ->next ->data >a) {
            // 动态申请一个空间，用来存放新增的结点
            p = (struct node*)malloc(sizeof(struct node));
            
            p->data = a;
            // 新增结点的后继指针指向当前结点的后继指针所指向的结点
            p->next = t->next;
            // 当前结点的后继指针指向新增结点
            t->next = p;
            break;
            
        }
        t = t->next;
    }

数组模拟单向链表

链表中的每一个结点只有两个部分。我们可以用一个数组data来存储序列中的每一个数。那么每一个数的右边我们就需要再用一个数组right来存放序列中每一个数。

数组模拟单向链表.png

现在需要在8前面插入一个6，只需要将6直接存放在数组data的末尾data[10] = 6。接下来只需要将right[3]改为10，表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4，表示新序列中10号元素右边的元素存放在data[4]中。

插入一个数.png

现在我们可以通过right数组就可以从头到尾遍历整个序列了。下面是完整代码：

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

    getchar();
    getchar();
    
    return 0;
}

void arrayMethod(){
    
    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;
        }
    }
    
    // 直接在data数组末尾添加一个数
    len++;
    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];
    }
}

输入：