数据结构与算法-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工作室小甲鱼