线性表 - 静态链表

/** 静态链表是用数组描述的链表，也叫游标表示法。是为了解决没有指针的语言
 *  数组的第一个和最后一个元素作为特殊元素处理，不存数据
 *  第一个元素：存放备用链表第一个节点的下标
 *  最后一个元素：则存放第一个有数据元素的下标，相当于单链表的头结点的作用
 */

/** 优缺点
 * 优：在插入和删除操作时，只需要修改游标，不需要移动元素
 *     从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点
 *
 * 缺：1.连续存储分配的表长度难以解决的问题没有解决
 *    2.失去了顺序存储结构随机存储的特性
 */

下面查看静态链表的几种状态

初始状态 顺序插入数据后 在乙和丁之间插入丙 删除数据后的状态

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 100
typedef int Status;
typedef int  ElemType;
typedef struct node {
    ElemType data;
    int cur;
} Component,StaticLinkList[MAXSIZE];

/** 初始化的时候 为了确保是空链表 将第一个数据的下标职位0， 在求链表长度的时候有用*/
Status InitStaticList(StaticLinkList space) {
    int i = 0;
    for (i = 0; i < MAXSIZE-1; i++) {
        space[i].cur = I+1;
    }
    space[MAXSIZE-1].cur = 0;
    return OK;
}

//取出空闲结点的第一个来使用， 并将第一个空闲结点的下一个的结点作为备用链表的第一个位置存储
int Malloc_Index(StaticLinkList space) {
    int i = space[0].cur;
    if (i) {
        space[0].cur = space[i].cur;
    }
    return I;
}


Status Insert_element(StaticLinkList space, int i,ElemType e) {
    if (i > MAXSIZE-1 || space[0].cur > MAXSIZE-1) {
        return ERROR;
    }
    
    int k = MAXSIZE-1;
    int  tempIndex = Malloc_Index(space);
    space[tempIndex].data = e;
    
    if (tempIndex) {
        for (int j = 1; j <= i-1; j++) {
            k = space[k].cur;
        }
        space[tempIndex].cur = space[k].cur; //此处类似于头插法，将下标0 永远放在最后一个结点的next上
        space[k].cur = tempIndex;
        return OK;
    }
    return ERROR;
}


/** 将原来空闲的第一个结点作为要删除结点的next也就是成了空闲的第二个结点, 然后将要删除的节点作为第一个空闲结点*/
void Free_Node(StaticLinkList space, int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;
}


/** 这个求长度有意思，是怎么变成0的呢？因为初始化空链表的时候 将空链表的下标置为了0 */
int ListLength(StaticLinkList list) {
    int j = 0;
    int i = list[MAXSIZE-1].cur;
    while (i) {
        i = list[i].cur;
        j++;
    }
    return j;
}


/** 需要两个下标，一个指向当前结点，一个指向当前的前一个结点*/
Status Delete_element2(StaticLinkList space, int i, ElemType e) {

    if (i > MAXSIZE-1 || ListLength(space) < i) {
        return ERROR;
    }

    int k = MAXSIZE-1;
    int previous = space[k].cur;
    for (int j = 1; j < i; j++) {
        previous = k;
        k = space[k].cur;
    }
    space[previous].cur = space[k].cur;
    Free_Node(space, k);
    return OK;
}



Status Delete_element(StaticLinkList space, int i, ElemType e) {
    
    if (i > MAXSIZE-1 || ListLength(space) < i) {
        return ERROR;
    }
    
    int k1,k2;
    k1 = MAXSIZE-1;
    //k1代表将要删除结点的上一个结点的下标
    for (int j = 1; j <= i-1; j++) {
        k1 = space[k1].cur;
    }
    
    k2 = space[k1].cur;
    space[k1].cur = space[k2].cur;
    Free_Node(space, k2);
    return OK;
}


void Iterate_StaticList(StaticLinkList space) {

    int minIndex = space[MAXSIZE-1].cur;
    int k = minIndex;
    int maxLength = ListLength(space);
    for (int i = 0; i < maxLength; i++) {
        printf("++++++current data： %d，%d\n",space[k].data,k);
        k = space[k].cur;
    }
}

#pragma mark - 使用
void k_StaticNode(void) {
    
    StaticLinkList list;
    InitStaticList(list);
    
    //顺序插入元素
    for (int i = 1; i < 10; i++) {
        Insert_element(list, i, i);
    }
    
    Iterate_StaticList(list);
    
    //在指定位置插入元素
    printf("\n\n");
    Insert_element(list, 5, 14);
    Insert_element(list, 9, 12);
    Iterate_StaticList(list);
    
    //在指定位置删除元素
    printf("\n\n");
    Delete_element(list, 6, 0);
    Iterate_StaticList(list);
}