四、数据结构：线性表-静态链表

1、静态链表是一个存储了很多节点的数组，每一个节点包括两部分：数据和下一个节点的数组下标。

一条静态链表包括一个数据表和一个备用表。数据表就是存放数据，备用表就是这块内存中空余的内存。

如上图，每一个节点的内容如下

typedef struct{
    char data;
    int next;
}staticLink;

在图中就相当于一个staticLink类型的数组：staticLink array[8] 。

（1）前面绿色的数字就是这个数组的下标。

（2）红色的节点就是存了数据的内存，前面的字母是数据，后面的数字标识下一个数据在内存中的位置（位置就是数组下标）。

（3）蓝色的节点表示空闲的内存，前面是空的等待存入数据，后面的数字标识下一个空内存在数组中的位置。

（4）在链表中的第一个节点数不存数据的，array[0].next永远存着首个空内存的位置，比如上图中array[0].next = 2。

（5）p是这个链表中第一个数据的位置，在做增删查改时永远不要去改变p的值，而是声明一个tmp = p.

（6）最后一个数据、最后一个空内存的next都是0 ，标识链表的结束。如上的array[8]和array[7]

 

下面是初始化静态链表及其增删查改操作，有点绕，但认真理解写一遍，运行一遍还是可以理解的。

#include <stdio.h>
#define MAXSIZE  7

typedef struct{
    int data;
    int next;
}staticLink;

void createLink(staticLink *array){
    for(int i = 0;i<MAXSIZE;i++){
        array[i].next = i+1;
        array[i].data = -1;
    }
    array[MAXSIZE-1].next = 0;

}
int getNote(staticLink *array){
    int i = array[0].next;
    //printf("getnod = %d\n",i);
    if(array[0].next){
        array[0].next = array[i].next;
    }
    return i;
}

int initStaticLink(staticLink *array){
    createLink(array);
    //int position = getNote(array);
    int p = getNote(array);
    int tmp = p;
    for (int i = 0;i<4;i++){
        int j = getNote(array);
        array[tmp].data = i+1;
        array[tmp].next = j;
        tmp = j;
    }

    array[tmp].next = 0;

    return p;
}

void display(staticLink *array,int p){
    int tmp = p;
    while(array[tmp].next != 0){
    for(int i = 0;i<position;i++){
        tmp = array[tmp].next;
    }
    int new = getNote(array);
    array[new].data = data;
    array[new].next = array[tmp].next;
    array[tmp].next = new;
    printf("insert %d,%d\n",new,array[new].next);
}

int drop(staticLink *array,int p,int position){
    int tmp = p;
    for(int i = 0;i<position-2;i++){
        tmp = array[tmp].next;
    }
    int drop = array[tmp].next;
    if(tmp == p || array[drop].next == 0){
        printf("no position\n");
        return p;
    }
    array[tmp].next = array[drop].next;

    array[drop].data = -1;
    array[drop].next = array[0].next;
    array[0].next = drop;
    return p;
}

int select(staticLink *array,int p,int data){
    int tmp = p;
    int position = 0;
    while(array[tmp].next){
        if(array[tmp].data == data){
            position = tmp;
            printf("founded it position = %d\n",position);
            break;
        }
        tmp = array[tmp].next;
    }
    return position;
}

int update(staticLink *array,int p,int position,int data){
    int tmp = p;
    for (int i = 0;i<position-1;i++){
        tmp = array[tmp].next;
    }
    if(tmp == p || array[tmp].next == 0){
        printf("not exit\n");
        return p;
    }
    array[tmp].data = data;
    return p;
}
int main(){
    staticLink array[MAXSIZE];
    int p = initStaticLink(array);
    display(array,p);
    p = update(array,p,3,9);
    display(array,p);
    return 0;
}

void insert(staticLink *array,int p,int position,int data){
    int tmp = p;
    for(int i = 0;i<position;i++){
        tmp = array[tmp].next;
    }
    int new = getNote(array);
    array[new].data = data;
    array[new].next = array[tmp].next;
    array[tmp].next = new;
    printf("insert %d,%d\n",new,array[new].next);
}

int drop(staticLink *array,int p,int position){
    int tmp = p;
    for(int i = 0;i<position-2;i++){
        tmp = array[tmp].next;
    }
    int drop = array[tmp].next;
    if(tmp == p || array[drop].next == 0){
        printf("no position\n");
        return p;
    }
    array[tmp].next = array[drop].next;

    array[drop].data = -1;
    array[drop].next = array[0].next;
    array[0].next = drop;
    return p;
}

int select(staticLink *array,int p,int data){
    int tmp = p;
    int position = 0;
    while(array[tmp].next){
        if(array[tmp].data == data){
            position = tmp;
            printf("founded it position = %d\n",position);
            break;
        }
        tmp = array[tmp].next;
    }
    return position;
}

int update(staticLink *array,int p,int position,int data){
    int tmp = p;
    for (int i = 0;i<position-1;i++){
        tmp = array[tmp].next;
    }
    if(tmp == p || array[tmp].next == 0){
        printf("not exit\n");
        return p;
    }
    array[tmp].data = data;
    return p;
}
int main(){
    staticLink array[MAXSIZE];
    int p = initStaticLink(array);
    display(array,p);
    p = update(array,p,3,9);
    display(array,p);
    return 0;
}