1.3 静态链表

静态链表，也是线性存储结构的一种，它兼顾了顺序表和链表的优点于一身，可以看做是顺序表和链表的升级版。

使用静态链表存储数据，数据全部存储在数组中（和顺序表一样），但存储位置是随机的，数据之间"一对一"的逻辑关系通过一个整形变量（称为"游标"，和指针功能类似）维持（和链表类似）。

静态链表中，除了数据本身通过游标组成的链表外，还需要有一条连接各个空闲位置的链表，称为备用链表。

备用链表的作用是回收数组中未使用或之前使用过（目前未使用）的存储空间，留待后期使用。也就是说，静态链表使用数组申请的物理空间中，存有两个链表，一条连接数据，另一条连接数组中未使用的空间。

通常，备用链表的表头位于数组下标为 0（a[0]） 的位置，而数据链表的表头位于数组下标为 1（a[1]）的位置。

静态链表中设置备用链表的好处是，可以清楚地知道数组中是否有空闲位置，以便数据链表添加新数据时使用。比如，若静态链表中数组下标为 0 的位置上存有数据，则证明数组已满。

静态链表的实现及基本操作

#include "stdafx.h"
#define SIZE 6

typedef struct {
    char data;
    int cursor;
}component;

//将结构体数组中所有分量链接到备用链表中
void reserveArr(component *array);
//初始化静态链表
int initArr(component *array);
//输出函数
void displayArr(component * array, int body);
//从备用链表上摘下空闲节点的函数
int mallocArr(component * array);

//初始化备用链表
void reserveArr(component *array) {
    for (int i = 0; i < SIZE; i++) {
        array[i].cursor = i + 1;
    }
    array[SIZE - 1].cursor = 0;
}

//从备用链表获取空间
int mallocArr(component *array) {
    int i = array[0].cursor; //获取第一个空闲节点的位置
    if (array[0].cursor) {
        array[0].cursor = array[i].cursor; //第一个空闲节点后移
    }
    return i;
}

//备用链表回收空间
void freeArr(component *array, int add) {
    array[add].cursor = array[0].cursor;
    array[0].cursor = add;
}

// 向静态链表赋值
int initArr(component *array) {
    reserveArr(array);
    int headPointer = mallocArr(array);
    int tailPointer = headPointer;
    for (int i = 1; i < 4; i++) {
        int j = mallocArr(array);
        array[tailPointer].cursor = j;
        array[j].data = 'a' + i - 1;
        tailPointer = j;
    }
    array[tailPointer].cursor = 0;
    return headPointer;
}

void displayArr(component * array, int pointer) {
    int tempPointer = pointer;
    while (array[tempPointer].cursor){
        printf("%c, %d \n", array[tempPointer].data, array[tempPointer].cursor);
        tempPointer = array[tempPointer].cursor;
    }
    printf("%c, %d \n", array[tempPointer].data, array[tempPointer].cursor);

}


//增
void insertArr(component * array, int headPointer, int add, char data) {
    int tempPointer = headPointer;
    for (int i = 1; i < add; i++) {
        tempPointer = array[tempPointer].cursor;
    }
    int insert = mallocArr(array);
    array[insert].cursor = array[tempPointer].cursor; 
    array[insert].data = data;
    array[tempPointer].cursor = insert;
}


//删
void deleteArr(component *array, int pointer, char a) {
    int tempPointer = pointer; 
    while (array[tempPointer].cursor) {
        tempPointer = array[tempPointer].cursor;
        if (tempPointer == 0) {
            printf("could not find this element in the chain\n");
            return;
        }
    }
    int del = tempPointer;
    tempPointer = pointer;
    while (array[tempPointer].cursor != del) {
        tempPointer = array[tempPointer].cursor;
    }
    array[tempPointer].cursor = array[del].cursor;
    freeArr(array, del);
}

//查
int selectElem(component *array, int pointer, char elem) {
    int tempPointer = pointer;
    while (array[tempPointer].cursor != 0) {
        if (array[tempPointer].data == elem) {
            return tempPointer;
        }
        tempPointer = array[tempPointer].cursor;
    }
    return -1;
}

//改
void amendElem(component * array, int pointer, char oldElem, char newElem) {
    int add = selectElem(array, pointer, oldElem);
    if (add == -1) {
        printf("could not find this element in the chain\n");
        return;
    }
    array[add].data = newElem;
}


int main() {
    component array[SIZE];
    int pointer = initArr(array);
    printf("静态链表：\n");
    displayArr(array, pointer);

    printf("在第3的位置上插入结点‘e’:\n");
    insertArr(array, pointer, 3, 'e');
    displayArr(array, pointer);

    printf("删除数据域为‘a’的结点:\n");
    deleteArr(array, pointer, 'a');
    displayArr(array, pointer);

    printf("查找数据域为‘e’的结点的位置:\n");
    int selectAdd = selectElem(array, pointer, 'e');
    printf("%d\n", selectAdd);

    printf("将结点数据域为‘e’改为‘h’:\n");
    amendElem(array, pointer, 'e', 'h');
    displayArr(array, pointer);

    return 0;
}