热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

数据结构静态链表特别篇

本教程来自本人博客越行勤‘sBlog,欢迎大家访问域名https:yingwiki.top文章目录静态链表算法解析题目初步理解代码InitSpace_SLMalloc

本教程来自 本人博客 越行勤‘s Blog ,欢迎大家访问
域名 https://yingwiki.top



文章目录

    • 静态链表
      • 算法解析
        • 题目
          • 初步理解
        • 代码
          • InitSpace _SL
          • Malloc_SL
          • Free_SL
          • difference
      • 静态链表代码


静态链表

我在《 数据结构 第二章 :双链表,循环链表,静态链表以及对比总结》,初步认识了静态链表。

第一次去理解代码,其实有一点点费力。但是也不是那么复杂,主要抓住下面这一点

静态链表:分配一整个连续内存空间每个节点,每个节点集中安置;静态链表中没有用指针,但是数组的索引值 Index充当了指针的作用。

静态链表就是为那行没有指针的编程语言二存在的,存储数据用的是连续的空间,但是逻辑上连续的空间,在物理上无需连续,还是抓住了链表的特点。

typedef struct
{ElemType data;int cur;//其实可以把它看着指针,指针也不少一个数吗?
}SLinkList[MaxSize];

cur: 就是下一个结点的数组下标,其实可以把它看着指针,指针也不少一个数吗?


算法解析

第一次实现静态链表,我面对的一个问题就是 如何寻找到没有使用的数据结点,我给出的解决方案是:


  • cur = 0,表示结尾
  • cur =MaxSize ,表示没有使用该段空间

所以需要开辟一个没有存储数据(插入结点等操作需要开辟空间)的结点就需要使用循环扫描出cur== MaxSize 的结点(没有使用的结点)。

有没有不需要循环的方法呢?当然是有的,我们来看看书上的一个例子。


题目

实现集合运算 (A−B)U(B−U)(A-B)U(B-U)(AB)U(BU) 来讨论静态链表的算法。


初步理解

为了更好的理解,我想提讲述出它的具体原理

在静态链表中 存着两个链表


  1. 链表1(备用链表). 头节点 为 SLinkList[0],存储着没有数据的结点
  2. 链表2(数据链表). 头结点为 SLinkList[1] (也可以不是 SLinkList[1] ,只要是空闲结点就可以了),存储着有数据的结点,

当然它是如何他是如何存储两个链表在一个数组中呢?

回想我们单链表是如何找到链表的呢? 找到头结点

那很简单,我们也只需要规定, L[0]为备用链表的头结点,L[1]为存储数据的头结点

开辟一个存储数据的结点:从备用链表中取出–>一个结点到数据链表中

删除回收一个存储数据的结点:从将被删除的结点–>插入到备用链表中

是不是很有启发性呢,经典的空间换取时间,当然我们这样多花费了1个空间(备用链表的头结点),就避免了时间复杂度为O(n)的大循环。


代码


InitSpace _SL

函数功能:初始化链表,由于此时没有存储数据,其实就是创建 备用链表

void InitSpace _SL(SLinkList &space)
{for(i&#61;0;i<MaxSize-1;i&#43;&#43;) //数组下标从0开始&#xff0c;只需要循环到 MaxSize-2space[i].cur&#61;i&#43;1;space[MaxSize - 1]&#61;&#61;0;//0表示NULL ,space[MaxSize - 1]也就是 备用链表的尾结点
}

结果

如上图&#xff0c;每个cur指向下一个结点。


Malloc_SL

函数功能&#xff1a;从备用链表中取出&#xff08;拿出来并在备用链表中删除&#xff09;一个可以存储数据的新结点&#xff0c;返回其的数组下标&#xff08;地址&#xff09;&#xff0c;返回0表示分配空间失败

int Malloc_SL(SLinkList &space)
{i&#61;space[0].cur;//备用链表的第一个结点取出if(space[0].cur)//如果 space[0].cur&#61;&#61;0 说明备用链表被使用完了&#xff0c;分配空间失败space[0].cur&#61;space[i].cur;//将取出的结点从备用链表中删除return i;
}

Free_SL

函数功能&#xff1a; 将被删除的结点k,连接到备用链表的头结点之后&#xff08;回收K结点&#xff09;

Free_SL(SLinkList &space ,int k)
{space[k].cur&#61;space[0].cur;sapce[0].cur&#61;k;
}

简单示意图

画的太丑了


difference

函数作用&#xff1a;依次此输入 A,B的元素&#xff0c;计算(A−B)U(B−U)(A-B)U(B-U)(AB)U(BU)&#xff0c; &#xff0c;计算结果到space ,S返回数据链表的头结点。

此函数使用许多功能&#xff0c;插入元素&#xff0c;删除元素等功能都在这里有体现
(A-B)U(B-U)

当然你要理解 (A−B)U(B−U)(A-B)U(B-U)(AB)U(BU)

void difference(SLinkList &space,int &S)
{InitSpace_SL(space); //初始化静态链表&#xff08;创建备用链表&#xff09;S&#61;Malloc_SL(space); //生成数据链的头结点r&#61;S; //r为当前A集合链表的表尾scanf(m,n); //输入数据链表的大小 m :A n: B//生成链表A,并填入数据 for(j&#61;1;j<&#61;m;&#43;&#43;j){i&#61;Malloc_SL(space);Scanf(space[i].data);//输入数据 space[r].cur&#61;i; //插入数据到数据链表r&#61;i; //r为当前A集合链表的表尾}space[r].cur&#61;0; //数据链尾结点为NULL(0)for(j&#61;1;j<&#61;n;j&#43;&#43;){scanf(b);p&#61;S; //p存储着要删除结点前驱结点k&#61;space[S].cur; //k指向集合A元素的下一个结点//遍历A集合 数据b是否也在A中&#xff08;是否重复&#xff09;while(k!&#61;space[r].cur&&space[k].data!&#61;b) // k!&#61;space[r].cur 到达存储A集合链表的表尾 space[k].data!&#61;b b不在元素 A{p&#61;k;//p存储着要删除结点前驱结点k&#61;space[k].cur;//遍历下一个结点}if(k&#61;&#61;Space[r].cur)//数据b没有重复&#xff0c;加入数据b//数据b插入到 r结点之后{i&#61;Malloc_SL(space);space[i].data&#61;b; space[i].cur&#61;space[r].cur;space[r].cur&#61;i; }else//数据B重复了{space[p].cur&#61;space[k].cur; //此时K删除点if(r&#61;&#61;k) //如果删除的是r结点&#xff0c;需要改r的指向r&#61;p;}}
}

看不明白&#xff0c;多阅读几遍&#xff0c;就明白了。

假设A集合为 {c,b,e,g,f,d} B为 {a,b,n,f}

那样运行结构为运行结果


静态链表代码

上述算法&#xff0c;创建链表&#xff0c;插入数据都是整合在difference() 中的。根据上述算法的基本思路&#xff0c;可以实现一下静态链表的基本操作。可以对比我在《 数据结构 第二章 :双链表&#xff0c;循环链表&#xff0c;静态链表以及对比总结》,中实现的静态链表&#xff0c;插入数据平均时间复杂度不在是O(n)&#xff0c;经典的空间换时间

对于链表&#xff0c;无非就三种操作&#xff0c;遍历元素&#xff0c;插入元素&#xff0c;删除元素&#xff0c;

在我实现的方法中&#xff0c;规定


  1. 链表1&#xff08;备用链表&#xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点
  2. 链表2&#xff08;数据链表&#xff09;. 头结点为 SLinkList[1],存储着有数据的结点&#xff0c;

代码

#include/**
关于如何判断 节点是否被使用其实有两种实现方法
1. 专门设置一个数值例如 cur&#61;-1 表示改节点没有被使用当然这个时有一定的缺点的&#xff0c;在插入元素的时候也需要去遍历一个元素去找那个节点没有被使用。2. 在静态链表中 存着两个链表
链表1&#xff08;备用链表&#xff09;. 头节点 为 SLinkList[0],存储着没有数据的结点
链表2&#xff08;数据链表&#xff09;. 头结点为 SLinkList[1],存储着有数据的结点&#xff0c; 插入元素&#xff0c;需要从备用链表中取一个元素---到数据链表&#xff0c;
删除一个结点&#xff0c;需要从数据链表中被删除结点---链接到备用链表这样&#xff0c;我们多花费一个空间就可以减少 不少的时间复杂度
**/
#define MaxSize 100
typedef struct
{char data;int cur;
}SLinkList[MaxSize];bool Init_SLinkList(SLinkList& L); //初始化链表
bool Insert_SLinkList(SLinkList& L, int i, char e); //按位插入元素
int Locate_SLinkList(SLinkList L, char e); //返回元素e的索引,返回0则不存在
bool GetElem_SLinkList(SLinkList L, int i, char& e);// 按索引查找元素
bool Delte_SLinkList(SLinkList& L, int i, char& e);//删除 第i个元素&#xff0c;删除数据返回到eint MallocNode(SLinkList& L);//寻找到一个可用 结点 ,返回0&#xff0c;表示空间用完
bool GetNode_SLinkList(SLinkList L, int i, int& k); //获取第i个结点Node的地址k
bool InsertNext_SLinkList(SLinkList& L, char e, int k);//在任意k结点之后插入元素
bool DeleteNode_SLinkList(SLinkList& L, int k); //删除指定结点,k为删除结点的地址void test()
{SLinkList L;Init_SLinkList(L);char e;//插入数据测试for (int i&#61;1; i < 10; i&#43;&#43;){InsertNext_SLinkList(L, &#39;a&#39;&#43;i-1, i);}printf("插入数据完成^_^\n \n");int i&#61;L[1].cur;int j&#61;1;while (i){printf("第%3d个数据为 %3c cur为%3d\n", j, L[i].data,L[i].cur );i &#61; L[i].cur;j&#43;&#43;;}//获取修改数据测试GetElem_SLinkList(L, 4, e);printf("第 4个数据为 %3c\n\n", e);Insert_SLinkList(L, 3, &#39;z&#39;);printf("在第3个数据插入 z 完成\n");GetElem_SLinkList(L, 3, e);printf("第 3个数据为 %3c\n\n", e);GetElem_SLinkList(L, 4, e);printf("第 4个数据为 %3c\n\n", e);printf("z是第%3d个元素\n", Locate_SLinkList(L, &#39;z&#39;));//删除数据测试printf("删除第 3个元素\n");Delte_SLinkList(L, 3, e);i &#61; L[1].cur;j &#61; 1;while (i){printf("第%3d个数据为 %3c cur为%3d\n", j, L[i].data, L[i].cur);i &#61; L[i].cur;j&#43;&#43;;}getchar();
}
int main()
{test();return 0;
}/*
初始化静态链表&#xff0c;其实就在创建备用链表
*/

bool Init_SLinkList(SLinkList& L)
{//备用连的头结点 L[0]&#xff0c;创建备用链表for (int i &#61; 2; i < MaxSize - 1; i&#43;&#43;) //遍历到MaxSize -2即可L[i].cur &#61; i&#43;1;//第一个结点从2开始L[0].cur &#61; 2;//备用链表表尾L[MaxSize-1].cur &#61; 0;//创建数据链表的头结点 L[1]L[1].cur &#61; 0;return true;
}
/*
返回一个备用链表里的地址
0表示链表已满
*/

int MallocNode(SLinkList& L)
{int i &#61; L[0].cur;//从备用链表取出的结点if (L[0].cur)//如果备用链表没有满L[0].cur &#61; L[i].cur;//该结点从备用链表中删除return i;
}bool DeleteNode_SLinkList(SLinkList& L, int k)
{//将k结点和后面一个结点交换数据int p &#61; L[k].cur;L[k].data &#61; L[p].data;L[k].cur&#61; L[p].cur;//删除结点pL[p].cur &#61; L[0].cur; L[0].cur &#61; p;return true;
}bool GetNode_SLinkList(SLinkList L, int i, int& k)
{if (i<1 || i>MaxSize - 2)return false;int p &#61; L[1].cur;int j &#61; 1;//计数器//遍历数据链表while (p && j < i){p &#61; L[p].cur;j&#43;&#43;;}if (!p && j > i)//i<0或者第i个数据不存在return false;k &#61; p;return true;
}bool InsertNext_SLinkList(SLinkList& L, char e, int k)
{if (k<1 || k >&#61; MaxSize) //结点不存在return false;int p &#61; MallocNode(L);if (!p)//如果分配失败return false;L[p].data &#61; e;L[p].cur &#61; L[k].cur;L[k].cur &#61; p;return false;
}bool Insert_SLinkList(SLinkList& L, int i, char e)
{int k;if (!GetNode_SLinkList(L, i-1, k))return false;return InsertNext_SLinkList(L, e, k);
}int Locate_SLinkList(SLinkList L, char e)
{int k &#61; L[1].cur;int i &#61; 1;while (k && L[k].data !&#61; e){k &#61; L[k].cur;i&#43;&#43;;}if (k &#61;&#61; 0)//如果e不存在i &#61; 0;return i;
}bool GetElem_SLinkList(SLinkList L, int i, char& e)
{int k;if (!GetNode_SLinkList(L, i, k))return false;e &#61; L[k].data;return false;
}
bool Delte_SLinkList(SLinkList& L, int i, char& e)
{int k;if (!GetNode_SLinkList(L, i,k ))return false;e &#61; L[k].data;DeleteNode_SLinkList(L, k);return false;
}

结果


推荐阅读
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • 本文详细介绍了如何在Linux系统上安装和配置Smokeping,以实现对网络链路质量的实时监控。通过详细的步骤和必要的依赖包安装,确保用户能够顺利完成部署并优化其网络性能监控。 ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 本文详细记录了在基于Debian的Deepin 20操作系统上安装MySQL 5.7的具体步骤,包括软件包的选择、依赖项的处理及远程访问权限的配置。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 技术分享:从动态网站提取站点密钥的解决方案
    本文探讨了如何从动态网站中提取站点密钥,特别是针对验证码(reCAPTCHA)的处理方法。通过结合Selenium和requests库,提供了详细的代码示例和优化建议。 ... [详细]
  • 火星商店问题:线段树分治与持久化Trie树的应用
    本题涉及编号为1至n的火星商店,每个商店有一个永久商品价值v。操作包括每天在指定商店增加一个新商品,以及查询某段时间内某些商店中所有商品(含永久商品)与给定密码值的最大异或结果。通过线段树分治和持久化Trie树来高效解决此问题。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
  • 本文详细介绍了 Dockerfile 的编写方法及其在网络配置中的应用,涵盖基础指令、镜像构建与发布流程,并深入探讨了 Docker 的默认网络、容器互联及自定义网络的实现。 ... [详细]
  • 自学编程与计算机专业背景者的差异分析
    本文探讨了自学编程者和计算机专业毕业生在技能、知识结构及职业发展上的不同之处,结合实际案例分析两者的优势与劣势。 ... [详细]
author-avatar
好kc好先生之家
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有