数据结构与算法之静态链表（游标实现法）

介绍：为了让数组模拟单链表，数组元素都是由两个数据域组成，data,cur。也就是说，数组的每个下标都对应一个data和cur。数据域data,用来存放数据元素，也就是通常我们要处理的数据；而游标cur相当于单链表中的next指针，存放该元素后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表，这种描述方法还叫做游标实现法。

原理说明：用于模拟链表的数组的第一个元素与最后一个元素作为特殊元素处理，数据域（data）不存放数据，第一个元素的索引域（cur）存放的是第一个备用元素的下标，最后一个元素的索引域存放的是第一个含有实际数据的数组元素的下标。

静态链表（游标实现法）
#include<stdio.h>

#define MAXSIZE 1000

typedef struct{

    int data;
    int cur;

}Component,StaticLinkList[MAXSIZE];

void InitList(StaticLinkList space)//静态链表初始化(space此时表示含有MAXSIZE个元素的数组)
{
    int i;

    for(i=0;i<MAXSIZE-1;i++)
    {
        space[i].cur = i+1;
    }

    space[MAXSIZE-1].cur = 0;//此时表示链表为空
}

//为静态链表“分配内存”，模拟malloc函数
int Malloc_SLL(StaticLinkList space)
{
    
    int i = space[0].cur;//space[0].cur用于存放模拟静态链表的数组剩余的元素中的第一个元素的下标。

    if(i)//如果i等于0表示链表已满。
    {
        //因为space[i]马上要被使用了，故在使用前把其下一个元素下标赋给静态链表的特殊结点。
        space[0].cur =  space[i].cur;
    }

    return i;
}

//为静态链表“释放内存”，模拟free函数
void Free_SSL(StaticLinkList space,int k)
{
    space[k].cur = space[0].cur;
    space[0].cur = k;
}

//计算静态链表的实际长度
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE-1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

//往静态链表中插入元素
bool ListInsert(StaticLinkList L,int i,int e)
{
    int j,k,l;

    k = MAXSIZE-1;

    if(i<1||i>ListLength(L)+1)
    {
        return false;
    }

    j = Malloc_SLL(L);

    if(j)
    {
        L[j].data = e;

        for(l=1;l<=i-1;l++)
        {
            k = L[k].cur;
        }

        L[j].cur = L[k].cur;

        L[k].cur = j;

        return true;
    }

    return false;
}

//清空静态链表（目标：在逻辑上把静态表恢复到初始状态逻辑）
void ClearList(StaticLinkList space)
{
    int i,j,k;

    i = space[MAXSIZE-1].cur;//链表第一个有效结点的下标（特殊位置1）
    space[MAXSIZE-1].cur = 0;//首先将静态链表在形式上置为空

    k = space[0].cur;//备用链表第一个结点的下标（特殊位置2）
    space[0].cur = i;//将链表的第一个有效结点连到备用链表的表头

    //用于获取最后一个有效结点的下标
    while(i)
    {
        j = i;
        i = space[i].cur;
    }

    space[j].cur = k;//备用链表的第一个结点链接到链表的尾部（特殊位置3）
}

//销毁静态链表（同清空操作一致）
void DestoryList(StaticLinkList space)
{
    int i,j,k;

    i = space[MAXSIZE-1].cur;//链表第一个有效结点的下标
    space[MAXSIZE-1].cur = 0;//将链表在形式上置为空

    k = space[0].cur;//备用链表第一个结点的下标
    space[0].cur = i;//将链表的第一个有效结点连到备用链表的表头

    //用于获取最后一个有效结点的下标
    while(i)
    {
        j = i;
        i = space[i].cur;
    }

    space[j].cur = k;//备用链表的第一个结点链接到链表的尾部
}

//判断链表是否为空
bool ListEmpty(StaticLinkList space)
{
    if(space[MAXSIZE-1].cur==0)
        return true;
    else
        return false;
}

//获取静态链表中指定位置（位序，而不是下标）的元素
bool GetElem(StaticLinkList L,int i,int *e)
{
    int k,j;

    if(i<1||i>ListLength(L))
        return false;

    k = L[MAXSIZE-1].cur;//k此时为第一个有效结点的下标
    for(j=1;j<=i-1;j++)
    {
        k = L[k].cur;
    }
    *e = L[k].data;
    return true;
}

//获取指定元素在静态链表中的位置(不是位序,是数组下标)
int LocateElem(StaticLinkList L,int aim)
{
    int k=L[MAXSIZE-1].cur;
    
    //下面返回的是位序
    //int j=0,i;
    //for(i=1;i<ListLength(L);i++)
    //{ 
    //  k = L[k].cur;
    //  j++;
    //  if(L[k].data==aim)
    //      return j;
    //}
    //return -1;

    //返回位置(下标)
    while(k&&L[k].data!=aim)
    {
        k = L[k].cur;
    }
    return k;//如果值为0，则表示查找失败。
}

//获取静态链表指定元素的前驱
bool PriorElem(StaticLinkList L,int aim,int *pre_e)
{
    int k = L[MAXSIZE-1].cur;
    int j;

    while(k&&L[k].data!=aim)
    {
        j = k;
        k = L[k].cur;
    }
    
    if(k)//这一步很重要
    {
        *pre_e = L[j].data;

        return true;
    }

    return false;
    
}

//获取静态链表指定元素后继
bool NextElem(StaticLinkList L,int aim,int *next_e)
{

    //方法1
    int k = L[MAXSIZE-1].cur;
    int j=0;
    
    while(k&&L[k].data!=aim)
    {
        k = L[k].cur;
        j = L[k].cur;
    }
    if(k&&j)
    {
        *next_e = L[j].data;

        return true;
    }

    //方法2
    /*
    int j;
    int i = LocateElem(L,aim);//链表为空或者目标元素未查到，统统返回0
    if(i)
    {
        //如果i为静态链表最后一个有效元素的下标，则此时该下标所对应的元素不存在后继，j等于0.
        j = L[i].cur;

        if(j)
        {
            *next_e = L[j].data;
            return true;
        }
    }*/
    
    return false;
}

//删除静态链表指定位置的元素
bool ListDelete(StaticLinkList L,int i)
{
    int j,k=MAXSIZE-1;

    if(i<1||i>ListLength(L))
    {
        return false;
    }

    for(j=1;j<=i-1;j++){

        k = L[k].cur;
    }

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

    return true;
}

//遍历静态链表
void ListTraverse(StaticLinkList L)
{
    int k = L[MAXSIZE-1].cur;
    
    while(k)
    {
        printf("%d ",L[k].data);
        k = L[k].cur;
    }

    printf("\n");
}

int main()
{
    int i;
    int e,e0;
    StaticLinkList L;
    
    //静态链表初始化
    InitList(L);

    //向静态链表中插入数据
    for(i=1;i<10;i++)
    {
        if(!ListInsert(L,i,i+1))
        {
            printf("数据插入失败\n");
            return 0;
        }
    }

    //遍历静态链表
    printf("遍历静态链表元素如下：");
    ListTraverse(L);

    //判断链表是否为空
    /*
    if(ListEmpty(L))
    {
        printf("静态链表为空\n");
    }else
    {
        printf("静态链表不为空\n");
    }
    //清空链表
    ClearList(L);
    if(ListEmpty(L))
    {
        printf("静态链表为空\n");
    }*/
    
    //获取静态链表指定位置元素
    if(GetElem(L,2,&e))
    {
        printf("位序2上的元素为：%d\n",e);

    }else
    {
        printf("获取指定位置元素失败\n");
    }

    //获取指定元素的下标
    printf("值为9的元素在静态链表中的下标为：%d\n",LocateElem(L,9));//注意用来表示静态链表的数组是从下标1开始存储有效元素的。

    //获取指定元素的前驱
    if(PriorElem(L,8,&e0))
    {
        printf("静态链表中值为8的元素的前驱值为：%d\n",e0);
    }else
    {
        printf("你所指定的元素不存在前驱\n");
    }
    
    //获取指定元素的后继
    if(NextElem(L,8,&e0))
    {
        printf("静态链表中值为8的元素的后继值为：%d\n",e0);
    }else
    {
        printf("你所指定的元素不存在后继\n");
    }
    
    //获取指定位置
    if(GetElem(L,3,&e))
    {
        printf("静态链表位置3上的元素值为：%d\n",e);
    }
    else
    {
        printf("你所指定的位置不存在\n");
    }

    //删除静态链表指定位置元素
    if(ListDelete(L,4))
    {
        printf("执行删除操作后，静态链表中的元素如下：");
        ListTraverse(L);
    }
    else
    {
        printf("删除操作失败\n");
    }
    return 0;
}