博客

静态链表

1. 静态链表


静态链表实际上就是用数组的方式代替指针来描述单链表，当然，其插入，删除等操作会比较的复杂，但其思想是比较巧妙且值得学习的。

静态链表的存储结构

/* 线性表的静态链表存储结构 */
typedef struct 
{
    ElemType data;
    int cur;  /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];

将以一维数组为基础的表添加上游标

Status InitList(StaticLinkList space) 
{
 int i;
 for (i=0; i<MAXSIZE-1; i++)  
  space[i].cur = i+1;
 space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
 return OK;
}

如图：

在新建的空表中，游标总是与数组元素的下标差1，需要特别了解的是，数组的第一个元素的游标总是标向表中的第一个空闲位置，数组的最后一个元素与单链表的头指针类似，总标向表中的第一个数据（在链表中，第一个数据往往是很重要的，找到了第一个数据，就可以根据游标或线索依次找到其他数据）

静态链表的插入操作


首先需要类似于malloc的函数来开辟空间插入

int Malloc_SSL(StaticLinkList space) 
{ 
 int i = space[0].cur;             /* 当前数组第一个元素的cur存的值 */
                                   /* 就是要返回的第一个备用空闲的下标 */
 if (space[0]. cur)         
     space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
                                         /* 所以我们就得把它的下一个 */
                                         /* 分量用来做备用 */
 return i;
}

插入操作：

Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
  L[j].data = e;   /* 将数据赋值给此分量的data */
  for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
     k = L[k].cur;           
  L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
  L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
  return OK;   
    }   
    return ERROR;   
}

图解（我们以插入两个数据为例）：

1.由Malloc_SSL函数找到第一个空闲空间位置然后插入数据

j=Malloc_SSL(L);
L[j].data=e;

2.改变游标，将新插入的数据的游标改为0

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

3.当插入第二个元素时：

向静态链表中插入一串数据，推荐用头插法（始终在1号位插入）

    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');

静态链表的删除操作


首先需要实现类似free函数的自定义函数

void Free_SSL(StaticLinkList space, int k) 
{  
    space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}

删除操作：

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 - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return OK;   
}

特别提醒：在整个删除操作中，其实并没有删除数组中指定要删除的数，Free_SSL函数的作用是将要删除的数据位更换为第一空闲位

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

这两行代码，第一行，是找到要删除数据所处的位置，然后将要删除数据的前一个数据的游标后移