3.静态链表

//
//  main.c
//  03-静态链表
//
//  Copyright © 2017年 Mr.Young. All rights reserved.
//

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

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

#define MAXSIZE     100 //链表的最大长度

typedef int Status;
typedef int BOOL;
typedef int ElemType;

typedef struct {
    ElemType data;
    int cur;
}component, SLinkList[100];

/**
 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，“0”表示空指针
 */
void InitSpace_SL(SLinkList *space) {
    for (int i = 0; i < MAXSIZE-1 ; i++)
        (*space)[i].cur = i+1;
    (*space)[MAXSIZE-1].cur = 0;
    (*space)[MAXSIZE-2].cur = 0; // 备用链表最后一个元素置为空
}

/**
 若备用空间链表非空，则返回分配的结点下标，否则返回0
 */
int Malloc_SL(SLinkList *space) {
    int i = (*space)[0].cur;
    if ((*space)[0].cur) // 静态链表不为空
        (*space)[0].cur = (*space)[i].cur;
    return i;
}

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

/**
 销毁静态链表L，L不再存在
 */
Status DestroySLinkList(SLinkList *L) {
    int i = (*L)[MAXSIZE-1].cur; // 获取链表中第一个结点的下标
    while ((*L)[i].cur) {
        i = (*L)[i].cur;
    } // 循环得到最后一个结点的下标
    (*L)[i].cur = (*L)[0].cur;
    (*L)[0].cur = (*L)[MAXSIZE-1].cur;
    (*L)[MAXSIZE-1].cur = 0; // 将静态链表的头结点设为空
    return OK;
}

/**
 将值为s的结点插入在第一个结点之前
 */
Status InsFirst(SLinkList *L, int s) {
    int i = (*L)[MAXSIZE-1].cur; // 获取链表中第一个结点的下标
    int m = Malloc_SL(L); // 分配一个下标为m的新结点
    (*L)[MAXSIZE-1].cur = m;
    (*L)[m].cur = i;
    (*L)[m].data = s;
    return OK;
}

/**
 已知h指向线性链表的头结点，删除链表中的第一个结点并以q返回
 */
Status DelFirst(SLinkList *L, ElemType *e) {
    int i = (*L)[MAXSIZE-1].cur; // 获取第一个结点的下标
    *e = (*L)[i].data;
    (*L)[MAXSIZE-1].cur = (*L)[i].cur;
    Free_SL(L, i);
    return OK;
}

/**
 删除静态链表L中的尾结点并以e返回
 */
Status Remove(SLinkList *L, ElemType *e) {
    int i = (*L)[MAXSIZE-1].cur; // 获取第一个结点的下标
    if (!(*L)[i].cur) { // 如果静态链表中只有一个结点
        (*L)[MAXSIZE-1].cur=(*L)[i].cur;
        Free_SL(L, i);
    }
    int j = (*L)[i].cur;
    while ((*L)[j].cur) {
        i = (*L)[i].cur;
        j = (*L)[i].cur;
    }
    *e = (*L)[j].data;
    Free_SL(L, j);
    (*L)[i].cur = 0;
    return OK;
}

/**
 若线性链表L为空表，则返回TRUE，否则返回FALSE
 */
BOOL ListEmpty(SLinkList L) {
    return L[MAXSIZE-1].cur==0;
}

/**
 返回线性链表L中元素的个数
 */
int ListLength(SLinkList L) {
    int i = L[MAXSIZE-1].cur; // 获取第一个结点的下标
    int len = 0;
    while (i) {
        len++;
        i = L[i].cur;
    }
    return len;
}

/**
 返回静态链表中位序为i的数据元素的值
 */
ElemType GetCurElem(SLinkList L, int k) {
    if (k<1 || k>ListLength(L)) {
        printf("访问的位置不合法!\n");
        exit(OVERFLOW);
    }
    int i = L[MAXSIZE-1].cur; // 获取第一个结点的下标
    int j = 1;
    while (j!=k && i) {
        i = L[i].cur;
        j++;
    }
    return L[i].data;
}

/**
 返回静态链表中第一个与e相等的结点位序
 */
int LocatePos(SLinkList L, ElemType e) {
    int i = L[MAXSIZE-1].cur; // 获取第一个结点的下标
    int j = 0;
    while (i) {
        ++j;
        if (L[i].data==e)
            return j;
        i=L[i].cur;
    }
    return 0;
}

/**
 已知cur_e为静态链表L中的一个结点的数据，并用pri_e保存该结点的直接前驱的数据，若无前驱，则返回ERROR
 */
Status PriorElem(SLinkList L, ElemType cur_e, ElemType *pri_e) {
    int i = L[MAXSIZE-1].cur; // 获取第一个结点的下标
    if (L[i].data==cur_e) {
        printf("该结点没有前驱结点!\n");
        return ERROR;
    }
    int j;
    while (i) {
        j = L[i].cur; // j指向i的下一个结点
        if (j && L[j].data == cur_e) {
            *pri_e = L[i].data;
            return OK;
        }
        i = j;
    }
    return ERROR;
}

/**
 已知cur_e为静态链表L中的一个结点的数据，并用next_e保存该结点的直接后继的数据，若无前驱，则返回ERROR
 */
Status NextElem(SLinkList L, ElemType cur_e, ElemType *next_e) {
    int i = L[MAXSIZE-1].cur; // 获取第一个结点的下标
    int j;
    while (i) {
        j = L[i].cur;
        if (j && L[i].data==cur_e) {
            *next_e = L[j].data;
            return OK;
        }
        i = j;
    }
    printf("该结点没有后继结点!\n");
    return ERROR;
}

/**
 在静态链表L中的第k个位置之前插入数据为e的结点
 */
Status ListInsert(SLinkList *L, int k, ElemType e) {
    if (k<1 || k>ListLength(*L)+1) {
        printf("插入的位置不合法!\n");
        return ERROR;
    }
    if (k==1) {
        InsFirst(L, e);
        return OK;
    }
    int i = (*L)[MAXSIZE-1].cur;
    int j = 1;
    while (i && j<k-1) {
        ++j;
        i = (*L)[i].cur;
    }
    int m = (*L)[i].cur; // m指向第k个结点
    int new = Malloc_SL(L); // 从静态表中找出一个空闲结点下标
    (*L)[new].cur = m;
    (*L)[new].data = e;
    (*L)[i].cur = new;
    return OK;
}

/**
 在静态链表L中，删除第k个结点，并用e保存第k个位置的值
 */
Status ListDelete(SLinkList *L, int k, ElemType *e) {
    if (k<1 || k>ListLength(*L)) {
        printf("删除的位置不合法!\n");
        return ERROR;
    }
    int i = (*L)[MAXSIZE-1].cur; // 获取第一个结点的下标
    int j = 1;
    while (i && j <k-1) { // 找到第k-1个结点位置
        j++;
        i = (*L)[i].cur;
    }
    int m = (*L)[i].cur; // 第k个结点的下标
    (*L)[i].cur = (*L)[m].cur;
    *e = (*L)[m].data;
    Free_SL(L, m);
    return OK;
}

/**
 遍历静态链表L
 */
void ListTraverse(SLinkList L) {
    int i = L[MAXSIZE-1].cur; // 获取静态链表第一个结点的下标
    int j = 0;
    while (i) {
        j++;
        printf("第%d个结点的值为：%d\n", j, L[i].data);
        i = L[i].cur;
    }
}

int main(int argc, const char * argv[]) {
    
    SLinkList *L = (SLinkList *)malloc(sizeof(SLinkList));
//    SLinkList *L = (SLinkList *)malloc(sizeof(component)*MAXSIZE);
    InitSpace_SL(L);
//    for (int i = 0; i < MAXSIZE; i++) {
//        printf("%d\n", (*L)[i].cur);
//    }
    printf("length = %d\n", ListLength(*L));
    InsFirst(L, 1);
    InsFirst(L, 2);
    InsFirst(L, 3);
    ListInsert(L, 1, 10);
    ListInsert(L, 5, 5);
    ListTraverse(*L);
    ElemType remove;
    Remove(L, &remove);
    printf("remove last is %d\n", remove);
    printf("length = %d\n", ListLength(*L));
    
    DestroySLinkList(L);
    free(L);
    return 0;
}