数据结构：静态链表

static-link-list.c

//
// Created by 方朋 on 16/12/20.
//


#include <stdio.h>
#include "global.h"

// 数组要尽量建大点,这里假设链表最大长度1000
#define MAXSIZE 1000

/*
 * 静态链表
 * 用数组模拟指针, 数组元素为结构体, 包含data和cur成员。
 * data表示数据, cur相对于 p->next 指针,只不过这里用下标表示。
 */
typedef struct {
    ElemType data;
    int cur;    // 游标, 为0时表示无指向
} Component, StaticLinkList[MAXSIZE];


/*
 * ===========描述=============
 * 对数组的第一个和最后一个元素做特殊元素处理,不存数据。
 * 把未使用的数组元素称为『备用链表』, 数组第一个元素(arr[0])的cur存放备用链表的第一个结点下标。
 * 把已使用的数组元素称为『已用链表』, 数组最后一个元素(arr[MAXSIZE - 1])的cur存放已用链表的第一个结点下标。相对于头结点
 * 当整个链表为空时,则为0
 * =============================
 */

/* 初始化 */
Status InitList(StaticLinkList space)
{
    for (int i = 0; i < MAXSIZE - 1; ++i) {
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;
    return OK;
}

/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
    int len = 0;
    int data_cur = L[MAXSIZE - 1].cur;  // 获取已用链表第一个元素下标
    while (data_cur) {
        data_cur = L[data_cur].cur;
        len++;
    }
    return len;
}

/*
 * 获取空闲分量
 * 若备用链表为非空, 返回分配的结点下标, 否则返回0
 */
int Malloc_SLL(StaticLinkList L)
{
    int free_cur = L[0].cur;
    if (free_cur)
        L[0].cur = L[free_cur].cur;     // 找到第一个空闲值K ,并将L[0].cur下标改成K的cur下标指向
    return free_cur;
}
/*
 * 在第i个元素之前插入新数据e
 */

Status ListInsert(StaticLinkList L, int i, ElemType e)
{
    int data_cur = MAXSIZE - 1;     /* 注意data_cur首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1) return ERROR;

    int free_cur = Malloc_SLL(L);       /* 获得空闲分量的下标 */

    if (free_cur) {
        L[free_cur].data = e;           /* 将数据赋值给此分量的data */
        for (int j = 1; j < i; ++j) {   /* 通过forloop 找到第i个元素之前的位置 */
            data_cur = L[data_cur].cur;
        }
        L[free_cur].cur = L[data_cur].cur;  /* 把第i个元素之前的cur赋值给新元素的cur */
        L[data_cur].cur = free_cur;
        return OK;
    }
    return ERROR;
}

Status ListTraverse(StaticLinkList L)
{
    int data_cur = L[MAXSIZE - 1].cur;
    while (data_cur)
    {
        printf("%c ", L[data_cur].data);
        data_cur = L[data_cur].cur;
    }
    printf("\n");
    return OK;
}

/*  将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticLinkList L, int k)
{
    L[k].cur = L[0].cur;
    L[0].cur = k;
}

/*  删除在L中第i个数据元素   */
Status ListDelete(StaticLinkList L, int i)
{
    int j, k;
    if (i < 1 || i > ListLength(L))
        return ERROR;

    k = MAXSIZE - 1;
    for (j = 1; j < i; j++)
        k = L[k].cur;

    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j);
    return OK;
}


int main(int argc, char **argv)
{
    StaticLinkList L;
    Status i;
    i = InitList(L);
    printf("初始化L后：L.length=%d\n", ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("\n在L的表头依次插入FEDBA后：\nL.data=");
    ListTraverse(L);
    printf("初始化L后：L.length=%d\n", ListLength(L));

    i=ListInsert(L,3,'C');
    printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
    ListTraverse(L);

    i=ListDelete(L,1);
    printf("\n在L的删除“A”后：\nL.data=");
    ListTraverse(L);

    printf("\n");
}