静态链表的构建

🕗 发布于 2024-12-13 15:16 链表算法 数据结构

前言：

静态链表的概述：

静态链表是一种在数组中模拟链表结构的数据结构，它通过数组的索引来模拟指针，实现节点之间的链接，就不需要使用指针了。
每个节点由两部分组成：数据域和游标。数据域用于储存数据，而游标则指向数组中下一个节点的在数组中的索引。
静态链表优点是它不需要像动态链表那样频繁地进行内存分配和释放，节省了内存管理的开销。
静态链表的定义是基于数组的，其中数组的第一个和最后一个元素通常作为特殊元素处理，不储存数据。在含有头节点的静态链表中，数组的第1个节点(索引1)被用作头节点，头节点的cur指向链表的第一个数据节点，cur为第一个节点所在的数组索引，如果链表为空，则头节点的cur为0
数组的第0个节点的cur存放的是还可存储数据的节点的索引
静态链表的逻辑不太好理解，还是过道题印象印象深刻些

接下来用一道题来详细描述，原题链接：https://www.dotcpp.com/oj/problem1677.html

输入格式

静态链表的存储空间始终只有11个节点，起始为空表。insert a e代表在第a个姓氏前插入姓氏e；delete a代表删除第a个姓氏；search e代表查找姓氏e的位置；show代表输出静态链表存储空间的状态。输入保证操作都合法。

输出格式

只遇到search和show时才输出。当遇到search时输出姓氏e在space中的位置；当遇到show时输出这11个结点的状态。姓氏占8个字符而数字占2个字符，姓氏左对齐。每个指令输出后面跟着含有20个星号的行。

样例输入：

show
insert 1 ZHAO
show
insert 2 QIAN
show
insert 3 SUN
show
insert 4 LI
insert 5 ZHOU
insert 6 WU
insert 7 ZHENG
insert 8 WANG
show
insert 1 ZHANG
show
search LI
show

样例输出：

         2
         0
         3
         4
         5
         6
         7
         8
         9
        10
         0
********************
         3
         2
ZHAO     0
         4
         5
         6
         7
         8
         9
        10
         0
********************
         4
         2
ZHAO     3
QIAN     0
         5
         6
         7
         8
         9
        10
         0
********************
         5
         2
ZHAO     3
QIAN     4
SUN      0
         6
         7
         8
         9
        10
         0
********************
        10
         2
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
         0
********************
         0
        10
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
ZHANG    2
********************
 5
********************
         0
        10
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
ZHANG    2
********************

解题思路：

在构建静态链表前要定义两个结构体，一个用于表示静态链表中的节点，一个管理静态链表的整体信息，包括链表的起始位置。当前长度和最大容量。

#define MAXSIZE 11        //静态链表的长度
typedef char ElemType[8]; //元素类型，
 
typedef struct{       //静态链表中的节点
    ElemType data;    //节点中的数据
    int cur;          //下一个节点的下标(相当于指针，下一节点地址)
}NodeType;
 
NodeType space[MAXSIZE];  //用来存储节点的数据，相当于一般链表中的内容
 
typedef struct{        //管理静态链表的整体信息
    int elem;          //静态链表存储空间基址(起始元素的下标)
    int length;        //静态链表中的元素数目
    int listSize;      //静态链表可容纳元素数目
}SLinkList;

初始化静态链表，先模拟系统分配链表内存，再构造头节点

void InitSpace_SL()    //初始化静态链表元素
{
    memset(space, 0, sizeof(space)); // 初始化数组空间
    for(int i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1; // 每个节点的cur指向下一个节点
    space[MAXSIZE - 1].cur = 0; // 最后一个节点的cur指向0，表示链表结束
}
 
void InitHeadNode_SL(SLinkList& S)//初始化静态链表头节点
{
    S.elem=1;//静态链表的基址指向第一个节点
    S.length=0;  //初始长度为0
    S.listSize=MAXSIZE-2;  //可容纳元素数目
    space[0].cur = 2; // 空闲链表的头指针指向第2个节点，也就是从索引2开始后面可分配空间
    space[1].cur = 0; // 头结点的cur为0，表示链表为空
}

输出节点状态

void PrintSpace_SL()
{
    for(int i=0;i<MAXSIZE;i++)
    {
        //cout<<setw(8)<<setfill(' ')<<space[i].data;
        printf("%-8s",space[i].data);
        printf("%2d\n",space[i].cur);
    }
}

在第a个节点前插入元素，插入后还要更新可分配节点，

int Malloc_SL()
{
    int i = space[0].cur; // 获取第一个空闲节点的位置
    if(space[0].cur)
        space[0].cur = space[i].cur; // 更新空闲链表的头指针
    return i; // 返回分配的节点位置，返回0时说明链表已满
}
 
void Free_SL(int k)
{
    space[k].cur = space[0].cur; // 将节点k插入到空闲链表的头部
    space[0].cur = k;
}
void Insert_SL(SLinkList& S,int number, ElemType s)//插入节点
{
    int newNode = Malloc_SL(); // 分配一个新节点
    if (!newNode)
    {
        cout << "链表已满" << endl;
        return;
    }
 
    // 将新节点的数据赋值为要插入的数据
    strcpy(space[newNode].data, s);
 
    // 找到要插入位置的前一个节点
    int i = S.elem; // 从头结点开始
    for (int j = 1; j < number; j++)
    {
        i = space[i].cur; // 移动到下一个节点
        if (i == 0)
        {
            cout << "插入位置无效" << endl;
            Free_SL(newNode); // 释放新分配的节点
            return;
        }
    }
 
    // 插入新节点
    space[newNode].cur = space[i].cur; // 新节点的cur指向原节点的下一个节点
    space[i].cur = newNode; // 原节点的cur指向新节点
    S.length++;//链表长度增加
}

查找元素位置

int LocateElem_SL(SLinkList& S,ElemType e)
{
    //在静态单链线性表中查找第一个值为e的元素
    int i;
    i=S.elem;// 从头结点开始
    while(i&&strcmp(space[i].data,e))
    {
        i=space[i].cur;
    }
    return i;
}

删除第a个节点

void delete_SL(SLinkList& S, int number)//删除
{
    if (number < 1 || number > S.length)
    {
        cout << "删除位置无效" << endl;
        return;
    }
 
    int i = S.elem; // 从头结点开始
    for (int j = 1; j < number; j++)
    {
        i = space[i].cur; // 移动到下一个节点
    }
 
    int delNode = space[i].cur; // 要删除的节点
    space[i].cur = space[delNode].cur; // 跳过要删除的节点
    Free_SL(delNode); // 释放节点
    S.length--; // 链表长度减少
}

完整代码：

#include<iostream>
#include<algorithm>
#include<cstring> // 添加memset函数的头文件
#include<iomanip>
using namespace std;
 
#define MAXSIZE 11        //静态链表的长度
typedef char ElemType[8]; //元素类型，
 
typedef struct{
    ElemType data;    //节点中的数据
    int cur;          //下一个节点的下标
}NodeType;
 
NodeType space[MAXSIZE];  //用来存储节点的数据，相当于一般链表中的内容
 
typedef struct{
    int elem;          //静态链表存储空间基址(起始元素的下标)
    int length;        //静态链表中的元素数目
    int listSize;      //静态链表可容纳元素数目
}SLinkList;
 
void InitSpace_SL()    //初始化静态链表元素
{
    memset(space, 0, sizeof(space)); // 初始化数组空间
    for(int i = 0; i < MAXSIZE - 1; i++)
        space[i].cur = i + 1; // 每个节点的cur指向下一个节点
    space[MAXSIZE - 1].cur = 0; // 最后一个节点的cur指向0，表示链表结束
}
 
void InitHeadNode_SL(SLinkList& S)//完成初始化静态链表的头节点
{
    S.elem=1;//静态链表的基址指向第一个节点
    S.length=0;  //初始长度为0
    S.listSize=MAXSIZE-2;
    space[0].cur = 2; // 空闲链表的头指针指向第2个节点
    space[1].cur = 0; // 头结点的cur为0，表示链表为空
}
 
 
int Malloc_SL()
{
    int i = space[0].cur; // 获取第一个空闲节点的位置
    if(space[0].cur)
        space[0].cur = space[i].cur; // 更新空闲链表的头指针
    return i; // 返回分配的节点位置
}
 
void Free_SL(int k)
{
    space[k].cur = space[0].cur; // 将节点k插入到空闲链表的头部
    space[0].cur = k;
}
 
void PrintSpace_SL()
{
    for(int i=0;i<MAXSIZE;i++)
    {
        //cout<<setw(8)<<setfill(' ')<<space[i].data;
        printf("%-8s",space[i].data);
        printf("%2d\n",space[i].cur);
    }
}
 
int LocateElem_SL(SLinkList& S,ElemType e)
{
    //在静态单链线性表中查找第一个值为e的元素
    int i;
    i=S.elem;
    while(i&&strcmp(space[i].data,e))
    {
        i=space[i].cur;
    }
    return i;
}
 
void Insert_SL(SLinkList& S,int number, ElemType s)
{
    int newNode = Malloc_SL(); // 分配一个新节点
    if (!newNode)
    {
        cout << "链表已满" << endl;
        return;
    }
 
    // 将新节点的数据赋值为要插入的数据
    strcpy(space[newNode].data, s);
 
    // 找到要插入位置的前一个节点
    int i = S.elem; // 从头结点开始
    for (int j = 1; j < number; j++)
    {
        i = space[i].cur; // 移动到下一个节点
        if (i == 0)
        {
            cout << "插入位置无效" << endl;
            Free_SL(newNode); // 释放新分配的节点
            return;
        }
    }
 
    // 插入新节点
    space[newNode].cur = space[i].cur; // 新节点的cur指向原节点的下一个节点
    space[i].cur = newNode; // 原节点的cur指向新节点
    S.length++;//链表长度增加
}
 
void print()
{
    cout<<"********************"<<endl;
}
 
void delete_SL(SLinkList& S, int number)
{
    if (number < 1 || number > S.length)
    {
        cout << "删除位置无效" << endl;
        return;
    }
 
    int i = S.elem; // 从头结点开始
    for (int j = 1; j < number; j++)
    {
        i = space[i].cur; // 移动到下一个节点
    }
 
    int delNode = space[i].cur; // 要删除的节点
    space[i].cur = space[delNode].cur; // 跳过要删除的节点
    Free_SL(delNode); // 释放节点
    S.length--; // 链表长度减少
}
 
 
void solve(SLinkList& S,string s)//处理题目的输入逻辑
{
    if(s=="show")
    {
        PrintSpace_SL();
        print();
    }
    else if(s=="insert")
    {
        int number=0;
        ElemType s1;
        cin>>number>>s1;
        Insert_SL(S,number,s1);
    }
    else if(s=="search")
    {
        ElemType s1;
        cin>>s1;
        int result=LocateElem_SL(S,s1);
        printf("%2d\n",result);
        print();
    }
    else if(s=="delete")
    {
        int number;
        cin>>number;
        delete_SL(S,number);
    }
}
 
int main()
{
    SLinkList S;
    InitSpace_SL();
    InitHeadNode_SL(S);
    string s;
    while(cin>>s)
    {
        solve(S,s);
    }
    return 0;
}

原文地址：https://blog.csdn.net/fengbizhe/article/details/144430712

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：React框架：解锁现代化Web开发的新维度
下一篇：CSS系列（3）-- 定位与文档流详解

.NET(C#) 如何配置用户首选项及保存用户设置
.NET(C#) 如何配置用户首选项及保存用户设置
阅读更多2024-12-14
【最新】北大数字普惠金融指数数据集-省市县（2011-2023年）
郭峰,王靖一,王芳,孔涛,张勋,程志云.测度中国数字普惠金融发展:指数编制与空间特征[J].经济学(季刊),2020,19(04):1401-1418.时间跨度：省级和城市级指数时间跨度为2011-2
阅读更多2024-12-14
GESP202412 四级【Recamán】题解（AC）
a11ak−1−kkakak−1−kak−1k小杨想知道 Recamán 数列的前n项从小到大排序后的结果。手动计算非常困难，小杨希望你能帮他解决这个问题。
阅读更多2024-12-14
IDEA遇到EasyConnect中的网络资源无法访问的问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/wanshanyu_/article/de
阅读更多2024-12-14
双目摄像头标定方法
此时已经完成标定，左下角为反投影误差，右边为外参可视化。将双目左右目拍的图像上传（左右目最好不少于20张）此时回到主页面，即可看到成功导出。把这些误差大的删除即可。
阅读更多2024-12-14
Servlet、omcat服务器架构与工作原理
Servlet是运行在服务器端的Java程序，它的主要职责之一是接收并处理来自客户端（如浏览器）的HTTP请求。当客户端发送一个请求到服务器时，Servlet可以解析请求中的信息，例如请求的URL路径
阅读更多2024-12-14
Vue生命周期钩子函数：深入解析与实践
作为高级Vue前端开发人员，对Vue组件的生命周期钩子函数有着深刻的理解是至关重要的。生命周期钩子函数是指在Vue组件的创建、更新、销毁等过程中，Vue自动调用的一系列方法。通过这些钩子函数，我们可以
阅读更多2024-12-14
安卓开发--使用android studio发布APP
app发布
阅读更多2024-12-14
数据结构与算法学习笔记----拓扑排序
@ author: 明月清了个风。
阅读更多2024-12-14
python 将数据保存到现有的Excel文件的新工作表
out_file = ‘query.xlsx’df1 = pd.DataFrame(out_data)若直接写入：df1.to_excel(out_file, index=False, sheet_n
阅读更多2024-12-14