静态链表初识—参考《大话数据结构》+《王道数据结构》

简介: 静态链表初识—参考《大话数据结构》+《王道数据结构》

一、什么是静态链表

知识回顾: 众所周知,常见物理存储结构中,有链式结构、顺序结构、散列存储、索引存储。常见的逻辑结构,如下图。
初印象: 乍一听, "静态",不禁想起了顺序表的静态申请和动态申请。链表,那又是一种线性的逻辑结构,并且一般链表都是链式存储的结构。

在这里插入图片描述

面试被问: 前段时间面试一个前端的岗位,被问:C#和java这类语言没有指针,那么它们怎么实现链表的?其实就是静态链表实现的。
我的理解:一种用数组下标替代指针的单链表

二、 王道书上的描述

在这里插入图片描述

三、直接上手代码

①定义

每个结点由数据+游标组成,再定义一个由这些结点组成地一个数组。为了防止溢出,我们一般把数组建立地大一些。

#define Maxsize 1000
#define ElemType int
typedef struct Staticlist
{
   
   
    ElemType data;
    int cur;//游标
}Elem,StaticList[Maxsize];

②初始化

这里的初始化,实则是对游标的初始化。每个结点的游标记录着它下一个结点的位置。所以初始化中0下一个为1,1下一个为2....998下一个为999,999下一个为0。如下图
在这里插入图片描述

int InItList(StaticList space) 
{
   
   
    for (int i = 0; i < Maxsize-1; ++i)
    {
   
   
        space[i].cur = i+1;
    }
    space[Maxsize-1].cur = 0;
}

静态数组讲究的地方了:数组的第一个和最后一个元素不存数据,空着做特殊处理。数组被分为两部分,一部分是已经使用,一部分未被使用。我们称未被使用的数组称为备用数组,那么我们怎么知道那些是已使用那些是未使用呢?我们给他们定义一个分界线,并把分界线的下标存在第一元素space[0].cur里头。数组最后一个元素cur用来存放第一个插入元素的下标,相当于头结点。
概括下讲究的地方:
1)数组分成2部分:已使用+未使用
2)第一个位置cur:存分界点下标,(备用链表下标)
3)最后一个位置cur:存第一个插入元素的下标,相当于头结点
在这里插入图片描述

③插入操作

回顾: 动态链表的插入:1)申请新结点 2)连接新结点和老节点 。
思考: 我们的静态链表如何申请新结点,如何把新节点连接到已分配的数组中?
方法: 前面我们已经知道了,第一个元素是用来存放分界点的,所以自然而然我们找到space[0]并取出其中的cur,那么space[0].cur就是我们所需分配的新结点的下标。结合上图更易理解。
完善: 我们不仅仅需要知道后续要分配的空间,还需要更新下次申请的时候该找谁?正所谓:“子子孙孙无穷尽也”。故而我们得出以下函数:

int MallocStaticList(StaticList space)
{
   
   
    int i = space[0].cur;
    if (i != 0)//当第一个空间指向0的时候,就没有备用空间了
    {
   
   
        space[0].cur = space[i].cur;//下一个分配结点的下标,就是被分配结点的下一个cur
    }
    return i;
}

④插入操作

在顺序表中,我们在某位置插入一个值,往往需要把这个位置以后的元素,都挪动一位,然后把元素插入进这个空出来的位置。不过在静态链表中不需要,虽然静态链表的存储方式是顺序存储,但是它却具备了链表的优势。下面我们来实现插入操作:

在这里插入图片描述

int Insert_Elem(SaticList L,int i,int e)
{
   
   
    int k=MaxSize-1;//最后一个结点的下标
    if(i<1||i>MaxSize+1)//判断插入位置是否符合要求
    {
   
   
        return 0;
    }
    int j=MallocStaticList(L);//返回第一个备用区的下标
    if(j!=0)
    {
   
   
        L[j].data=e;//数据e给第一个备用区下标
        for(int n=1;n<=i-1;++i)//找到第i个元素之前的位置
        {
   
   
            k=L[k].cur;//注意k的值一直在发生改变,最后一个元素的cur是首元结点的下标
        }
        L[j].cur=L[k].cur;//让待插元素的cur变成i之前的那个元素的cur
        L[k].cur=j;//把这个从备用区拿到的下标,作为第i个元素的cur
    }
    else
    {
   
   
        return 0;
    }
}

⑤删除操作

和单链表一样,既然我们删除了某元素,那么我们就需要把这个元素的空间给free了,那么我们来写一个free函数。

在这里插入图片描述

void FreeStaticList(SaticList space,int k)
{
   
   
    space[k].cur=space[0].cur;//把第一个元素的cur值给要删除的元素
    spcae[0].cur=k;//然后把这个位置的下标,作为备用区的起点
}
int Delete_Elem(SaticList L,int i)
{
   
   
    if(i<1||i>MaxSize-1)
    {
   
   
        return 0;
    }
    int j,k=MaxSize-1;//还是得从最后那个元素开始找
    for( j=1;n<=i-1;++n)
    {
   
   
        k=L[k].cur//找到第i-1个元素
    }
    j=L[k].cur;//然第i-1个元素的cur,即第i个元素
    L[k].cur=L[j].cur;
    FreeStaticList(L,j);
}

改日那天我来总结总结这个代码的妙处,今天就先放它一马。

⑥、统计结点个数

int List_num(StaticList L)
{
   
   
    int cout=0;
    int i=L[MaxSize-1].cur;
    while(i)
    {
   
   
    i=L[i].cur;
    cout++;
    }
    return cout;
}

四、总结

这个静态链表相比普通链表,实质还是操作各自的指针域,普通链表的关键 “接口” 主要是:头指针 而这个静态链表的主要接口还是最后一个结点以及第一个结点

相关文章
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
22天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
22天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
22天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
22天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
计科一二班数据结构《实验十报告》参考答案
计科一二班数据结构《实验十报告》参考答案
15 0
计科一二班数据结构《实验十报告》参考答案

热门文章

最新文章

下一篇
无影云桌面