数据结构与算法-C语言7-链式存储结构之静态链表

数据结构与算法-目录

前言

   C语言具有指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加方便灵活。 后来的面向对象语言，如Java、C#等，虽不使用指针，但因为启用了对象引用机制，从某种角度上也间接实现了指针的某些作用。
   早期的编程语言如Basic、Fortran等，不像C语言拥有指针功能，但是又希望能够实现单链表，于是在数组的基础上创建了单链表，称为静态链表。
   首先我们用数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下表都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素后继在数组中的下表，我们把cur叫做游标。

我们把这种用数组描述的链表叫静态链表，这种描述方法还有起名叫做游标实现法。

1、静态链表模块介绍

1.1、基本结构

//线性表的静态链表存储结构
#define MAXSIZE 1000//假设链表的最大长度1000
typedef struct
{
    ElemType data;
    int cur;//游标(Cursor),为0时表示无指向
}Component,StaticLinkList[MAXSIZE];

为了我们方便插入数据，我们通常会把数组建立得大一些，以便有一些空闲空间可以方便插入不至于溢出。
结构体数组中，space[0]作为备用链表的头指针，space[1]作为链表的头指针。

另外我们对数组的第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的cur就存放备用链表的第一个结点的下表;而数组的最后一个元素的cur则存放第一个有数值的元素的下表，相当于单链表中的头结点作用，当整个链表为空时，则为0²。

1.2、初始化

//将一维数组space中个分量链成一备用链表
//space[0].cur为头指针，"0"表示空指针
Status InitList(StaticLinkList space)
{
    int i;
    for(i = 0;i < MAXSIZE - 1;i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;//目前静态链表为空
    return OK;
}

1.3、分配内存

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，不需要时释放。

我们前面说过，在动态链表中，结点的申请和释放分别借用malloc()和free()两个函数来实现。在静态链表中，操作的是数组，不存在像动态链表一样的申请和释放问题，所以我们需要自己实现这两个函数。

为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的以及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可从备用链表上取得第一个结点作为待插入的新结点。

//若备用空间链表为空，则返回分配的结点下表，否则返回0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//当前数组的第一个元素的Cur存的值
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//由于要拿出一个分量来使用
                        //所以我们,就得把它的下一个分量用作备用
    }
    return i;
}

1.4、回收内存

//将下表为k的空闲结点回收到备用链表
void Free_SSL(StaticLinkList space,int k)
{
   space[k] = space[0].cur;//把原来第一位指向的下标赋给新第一位
   space[0].cur = k;//要删除的分量赋给第一个元素cur
}

1.5、插入元素

//在L中第i个元素之前插入新的数据元素e
Status ListInsert(StaticLinkList L, int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;//注意k首先是最后一个元素的下表
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(L);//获得空闲分量的下标
    if(j)
    {
        L(j).data = e;//将数据赋值给此分量的下表
        for(l = 1;l <= i - 1;l++)//相当于循环链表，找到第i-1位
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;//新的第i个元素元素指向原本第i个元素
        L[k].cur = j;//第i - 1个元素指向新的第i个元素
        return OK;
    }
    return ERROR;
}

就这样，我们实现了在数组中，实现不移动元素，却插入了数据的操作。

1.6、删除元素

删除元素时，需要释放结点的函数free()，回收内存。

//删除在L中第i个数据元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j , k;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for(j = 1;j < = i - 1;j++)//相当于遍历链表
    {
        k = L[k].cur;
    }
    j = L[k].cur;//把要删除的数组下标赋值给j
    Free_SLL(L,j);//调用删除函数
    return OK;
}

1.7、遍历

//初始条件:静态链表L已存在。操作结果:返回L中数据元素个数
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

2、实例

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

typedef int ElemType;
typedef int DataType;

//---------线性表的静态单链表存储结构--------
#define MAXSIZE 100
typedef struct
{
    ElemType data;
    int cur;
}SLinkList[MAXSIZE];

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

//分配备用链表的一个结点,返回下标
//若为0，则说明备用链表用完
int Malloc_SL(SLinkList space)
{
    int i = space[0].cur;
    if (space[0].cur)                 //判断备用链表是否非空
        space[0].cur = space[i].cur; //备用链表头指针指向第二个空结点
    return i;                        //返回第一个空结点
}

void SListInit(SLinkList space)
{
    int i;
    for (i = 0; i < MAXSIZE; i++)
        space[i].cur = i + 1;         //将所有结点链入备用链表

    space[0].cur = space[1].cur;    //备用链表头指针链像第二个结点
    space[1].cur = 0;               //第一个结点作为链表的头结点
}

//获取链表的长度
int SListLength(SLinkList space)
{
    int len = 0;
    int i = space[1].cur;           //用头指针第一个结点的下标
    while (i)
    {
        ++len;
        i = space[i].cur;
    }
    return len;
}

//在链表的第i个位置插入元素e
void SlistInsert(SLinkList space, int i, ElemType e)
{
    if (i < 1 || i > SListLength(space) + 1) //超出范围
        return;

    int k = 1, j;
    for (j = 0; j <i - 1; j++)         //使k指示要删除的结点的前一个结点
        k = space[k].cur;

    int v = Malloc_SL(space);
    if (v)                           //如果有空间
    {
        space[v].data = e;
        space[v].cur = space[k].cur;
        space[k].cur = v;           //链入链表
    }
}

//删除第i个位置的元素
void SListDelete(SLinkList space, int i)
{
    if (i < 1 || i > SListLength(space))  //超出范围退出
        return;
    int k = 1, j;
    for (j = 0; j <i - 1; j++)         //使k指示要删除的结点的前一个结点
        k = space[k].cur;

    int temp = space[k].cur;
    space[k].cur = space[temp].cur;
    Free_SL(space, temp);
}

void SListTraverse(SLinkList space)
{
    int i = space[1].cur;
    while (i)
    {
        printf("%d\n", space[i].data);
        i = space[i].cur;
    }
}
int main()
{
    SLinkList space;
    SListInit(space);   //初始化
    int i;
    for (i = 1; i <= 10; i++)
        SlistInsert(space, 1, i);
    SListDelete(space, 10);

    SListTraverse(space);
    getchar();
    return 0;
}

执行结果：

10
9
8
7
6
5
4
3
2

3.静态链表优缺点

优点：

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

缺点：

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

特别感谢：

axiqia的专栏
鱼C工作室小甲鱼