[数据结构与算法]数据结构--链表--静态链表（c语言）

静态链表的原理

? 静态链表是用数组来存储链表，用数组来代替指针，是为了给没有指针的高级语言设计的弈中实现单链表能力的方法。那么，该怎么用数组去存储链表元素的数据以及指针呢。

? 首先我们让数组元素存储两个数据，一个是要存储的data，一个是指向下一个元素的游标cur。数组的每一个下标都对应一个data和cur，这里的cur相当于链表中的next指针，用于指向下一个元素。

静态链表的实现

添加和删除元素的描述

? 首先，定义一下数组的元素和数组，这里将数组存储的数据类型设成了整型。

typedef int ElemType; 
typedef struct{
    ElemType data;
    int cur;
}Component,StaticLinkList[MAXSIZE];

注意一下：这里的StaticLinkList相当于一种数据类型为该结构体，长度为MAXSIZE的数组类型，之后我们可以通过StaticLinkList space去声明一个类型为Component，长度为MAXSIZE的数组。

? 静态链表由两个部分组成，一个是备用链表，一个是存储链表。顾名思义，备份链表存储的是还没有存储数据的链表，存储链表是已经存储了数据的链表。数组的头尾元素不存储数据，相当于备用链表和存储链表的头节点。数组的第一个元素的cur存储的是备份链表的第一个元素的下标，数组的最后一个元素的cur存储的是存储链表的第一个元素的下标，存储链表最后一个元素的cur存储的是0。

? 当我们去添加一个元素的时候，我们会先像链表一样去malloc一个节点。具体步骤就是先找到数组的第一个元素，通过它的cur值找到备份链表的第一个元素，并将数组的第一个元素的cur指向备份链表的第二个元素（也就是备份链表第一个元素的下一个）。找到了备份链表的第一个元素后，我们需要给这个元素的data赋值，然后将它插入存储链表中。假如，我们要将它插入第i个位置。那么，我们需要找到第i - 1个元素，并将该元素插入第i - 1个元素后面。插入的时候，我们需要将要插入的元素的cur值指向第i个元素，然后将第i - 1个元素的cur值指向该元素。（和链表插入一样）

? 当我们去删除一个元素时，我们也会像链表一样去Free掉该节点，实际上也就是将该节点头插法插入备份链表。具体步骤时先找到数组的第一个元素，通过它的cur值找到备份链表的第一个元素，然后将要删除的节点的cur值指向备份链表的第一个元素，再将数组的第一个元素的cur值指向该节点的下标。然后就是删除了，加入我们要删除第i个元素，我们就会去找到第i - 1个元素，然后将第i - 1个元素的cur值指向第i + 1个元素的下标，然后Free掉第i个节点。

? 当添加元素和删除元素都了解之后，静态链表就大概都了解了吧。

定义静态链表

#define MAXSIZE 100 /*定义数组最大长度*/
typedef int ElemType; /*将元素类型设为整型*/
typedef enum{
    OK = 1,WRONG = 0,ERROR = -1
}Status;
typedef struct{
    ElemType data;
    int cur;
}Component,StaticLinkList[MAXSIZE];

?

初始化静态链表

Status InitList(StaticLinkList space){
    for(int i = 0;i < MAXSIZE;i++){
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;/*最后一位的游标设为0，相当于头节点*/
    return OK;
}

Malloc和Free函数的模拟

int Malloc(StaticLinkList space){
    int i = space[0].cur;
    if(i != MAXSIZE - 1){/*存满了的情况*/
        space[0].cur = space[i].cur;
        return i;
    }
    return WRONG;
}

void Free(StaticLinkList space, int index){/*删除节点，相当于头插法插入备用链表*/
    space[index].cur = space[0].cur;
    space[0].cur = index;
}

插入元素

Status Insert(StaticLinkList space, int index, ElemType e){/*在第index元素的位置上插入元素e，index的取值范围是1到Length+1*/
    if(index < 0 || index > Length(space) + 1){
        return ERROR;
    }
    int i = Malloc(space);
    if(i){
        space[i].data = e;
        int j = MAXSIZE - 1;
        for(int m = 1;m <= index - 1;m++){/*找到第index-1位置的元素*/
            j = space[j].cur;
        }
        space[i].cur = space[j].cur;
        space[j].cur = i;
        return OK;
    }
    return ERROR;
}

删除元素

Status Delete(StaticLinkList space, int index){/*删除第index位置上的元素，index的取值范围是1到Length*/
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index - 1;i++){/*找到第index-1位置的元素*/
        j = space[j].cur;
    }
    int temp = space[j].cur;
    space[j].cur = space[temp].cur;
    Free(space, temp);
    return OK;
}

链表长度和遍历

int Length(StaticLinkList space){
    int len = 0;
    int i = space[MAXSIZE - 1].cur;
    while(i > 0){
        i = space[i].cur;
        len++;
    }
    return len;
}
void traverse(StaticLinkList space){
    int i = space[MAXSIZE - 1].cur;
    while(i){
        printf("%d", space[i].data);
        i = space[i].cur;
    }
    printf("\n");
}

查找元素和修改元素

ElemType Search(StaticLinkList space, int index){
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index;i++){
        j = space[j].cur;
    }
    return space[j].data;
}
Status Modify(StaticLinkList space, int index, ElemType e){
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index;i++){
        j = space[j].cur;
    }
    space[j].data = e;
    return OK;
}

完整代码演示

#include<stdio.h>
#define MAXSIZE 100 /*定义数组最大长度*/
typedef int ElemType; /*将元素类型设为整型*/
typedef enum{
    OK = 1,WRONG = 0,ERROR = -1
}Status;
typedef struct{
    ElemType data;
    int cur;
}Component,StaticLinkList[MAXSIZE];

Status InitList(StaticLinkList space){
    for(int i = 0;i < MAXSIZE;i++){
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;/*最后一位的游标设为0，相当于头节点*/
    return OK;
}

int Malloc(StaticLinkList space){
    int i = space[0].cur;
    if(i != MAXSIZE - 1){/*存满了的情况*/
        space[0].cur = space[i].cur;
        return i;
    }
    return WRONG;
}

void Free(StaticLinkList space, int index){/*删除节点，相当于头插法插入备用链表*/
    space[index].cur = space[0].cur;
    space[0].cur = index;
}

int Length(StaticLinkList space){
    int len = 0;
    int i = space[MAXSIZE - 1].cur;
    while(i > 0){
        i = space[i].cur;
        len++;
    }
    return len;
}

Status Insert(StaticLinkList space, int index, ElemType e){/*在第index元素的位置上插入元素e，index的取值范围是1到Length+1*/
    if(index < 0 || index > Length(space) + 1){
        return ERROR;
    }
    int i = Malloc(space);
    if(i){
        space[i].data = e;
        int j = MAXSIZE - 1;
        for(int m = 1;m <= index - 1;m++){/*找到第index-1位置的元素*/
            j = space[j].cur;
        }
        space[i].cur = space[j].cur;
        space[j].cur = i;
        return OK;
    }
    return ERROR;
}

Status Delete(StaticLinkList space, int index){/*删除第index位置上的元素，index的取值范围是1到Length*/
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index - 1;i++){/*找到第index-1位置的元素*/
        j = space[j].cur;
    }
    int temp = space[j].cur;
    space[j].cur = space[temp].cur;
    Free(space, temp);
    return OK;
}

void traverse(StaticLinkList space){
    int i = space[MAXSIZE - 1].cur;
    while(i){
        printf("%d", space[i].data);
        i = space[i].cur;
    }
    printf("\n");
}

ElemType Search(StaticLinkList space, int index){
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index;i++){
        j = space[j].cur;
    }
    return space[j].data;
}

Status Modify(StaticLinkList space, int index, ElemType e){
    if(index < 0 || index > Length(space)){
        return ERROR;
    }
    int j = MAXSIZE - 1;
    for(int i = 1;i <= index;i++){
        j = space[j].cur;
    }
    space[j].data = e;
    return OK;
}

int main(){
    StaticLinkList test;
    InitList(test);
    Insert(test, 0, 1);
    Insert(test, 0, 2);
    Insert(test, 0, 3);
    Insert(test, 0, 4);
    Insert(test, 0, 5);
    Insert(test, 0, 6);
    traverse(test);
    Delete(test, 3);
    traverse(test);
    Modify(test, 1, 9);
    traverse(test);
    printf("%d",Search(test, 2));
}/*主函数里的插入，删除，修改等函数都是由返回值的，需要根据返回值判断是否插入或删除成功。*/

运行结果: