数据结构学习第一弹 静态链表

前言

之前学习的那些各种链表都是由指针实现的，而其中的每个节点都是通过有malloc和free来分配和释放存储空间的，所以这种链表被称为动态链表。那么既然有动态链表，那肯定也有静态链表，因为对于一些高级语言来说，十分尴尬的是并没有指针，所以就有一种采用游标来模拟单链表的方式

静态链表

前面说到了，用一个叫做游标的东西来模拟指针，从而达到链表的效果，那么具体是怎样实现的呢。其实游标也就是数组元素的下标，他的作用是指向后继元素的下标，而对于单链表的描述，采用的是用数组来存储，由于内存是一开始就分配好的，属于静态存储分配，所以称为静态链表。

静态链表的定义

用于描述静态链表的数组中的每个数组元素有两个域构成：data域用于存放数据元素，cur域(即游标)存放该数据元素的后系元素所在的下标。

#define MAXSIZE 100
typedef int ElemType;       //数据类型
typedef struct
{
    ElemType data;          //数据域
    int cur;                //游标
}Node,SLinkList[MAXSIZE];

静态链表的基本操作

静态链表的基本原理

首先，我们初始化静态链表的时候，把每个下标的游标都指向下一个数组元素的下标，然后数组的最后一个元素(即下标为(MAXSIZE-1)的元素)的游标指向下标为零的元素。
对于下标为0和下标为MAXSIZE-1的元素我们要特殊处理，即不为它们的data存储数据,通常呢，我们把没有使用到的数组元素称为备用链表(即备胎)。
在这里数组的第一个元素的作用是存放备用链表的第一个元素的数组下标，而数组的最后一个元素是用来指向数组的第一个元素，相当于单链表中头指针的作用。

有如下几种基本操作

• InitList(SLinkList l):初始化静态链表
• InsertList(SLinkList l,int i,ElemType e)：在链表的第i个位置插入元素
• DeleteList(SLinkList l,int i,ElemType *e):删除第i个元素
• Malloc_SLL(SLinkList l):获得空闲分量的下标
• Free_SLL(SLinkList l)：将空间回收
• GetListLength(SLinkList l):获得链表的长度
• GetElem(SLinkList l,int i,ElemType *e)：获取第i个元素
• PrintList(SLinkList l)：打印链表元素

#define Error 0
#define OK 1
typedef int Status;
//初始化静态链表
Status InitList(SLinkList l)
{
    for(int i=0;i<MAXSIZE-1;i++)    //初始化链表的游标使其全部链接起来
        l[i].cur = i+1;
    l[MAXSIZE-1].cur = 0;           //初始化最后一个结点为0
    return OK;
}
//分配空闲结点
int Malloc_SLL(SLinkList l)
{
    //总是取头节点之后的第一个空闲结点做分配
    int i = l[0].cur;               
    if(l[0].cur)
    {
        //同时空闲链表非空，头节点调整
        l[0].cur = l[i].cur;    
    }
    return i;   //返回申请到的空闲结点的数组下标
}
void Free_SLL(SLinkList l,int i)
{
    //将k结点收回
    l[i].cur = l[0].cur;    //总是将收回的结点放置在头结点之后
    l[0].cur = i;
}
Status GetElem(SLinkList l,int i,ElemType *e)
{
    int j = 1,k = l[MAXSIZE-1].cur;
    //查找位置不合法
    if(i<1 || i>GetListLength(l)+1)
        return Error;
    while(k && j<i)         //找到第i个位置
    {
        j++;
        k = l[k].cur;
    }
    *e = l[k].data;
    return OK;
}
Status InsertList(SLinkList l,int i,ElemType e)
{
    //插入位置不合法
    if(i<1 || i>GetListLength(l)+1)
        return Error;
    int k = MAXSIZE-1;
    //找到第i-1个位置
    for(int j = 0;j<i-1;j++)
        k = l[k].cur;
    int v = Malloc_SLL(l);  //分配一个结点v
    if(v)
    {
        l[v].data = e;
        l[v].cur = l[k].cur;
        l[k].cur = v;
    }
    return OK;
}
Status DeleteList(SLinkList l,int i,ElemType *e)
{
    if(i<1 || i>GetListLength(l)+1)
        return Error;
    int k = MAXSIZE - 1;
    for(int j = 0;j<i-1;j++)
        k = l[k].cur;
    int temp = l[i].cur;
    *e = l[i].data;
    l[k].cur = l[temp].cur;
    Free_SLL(l,temp);           //将结点释放至空闲链表位置

}
int GetListLength(SLinkList l)
{
    itn len = 0;
    int k = l[MAXSIZE-1].cur;
    while(k)
    {
        len++;
        k = l[k].cur;
    }
    return len;
}
Status PrintList(SLinkList l)
{
    int k = l[MAXSIZE-1].cur;
    while(k)
    {
        printf("%d ",l[k].cur);
        k = l[k].cur;
    }
    printf("\n");
    return OK;
}

静态链表的优缺点

优点:
在插入删除操作时，只需要修改游标，不需要移动元素，从而改进了在线性存储结构中的插入和删除操作需要移动大量数据元素的缺点。
缺点:

• 没有解决连续存储分配带来的表长难以确定的问题
• 失去了顺序存储结构随机存储的特性