热门标签 | 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;
}

结果


推荐阅读
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 尽管使用TensorFlow和PyTorch等成熟框架可以显著降低实现递归神经网络(RNN)的门槛,但对于初学者来说,理解其底层原理至关重要。本文将引导您使用NumPy从头构建一个用于自然语言处理(NLP)的RNN模型。 ... [详细]
  • 深入理解Java泛型:JDK 5的新特性
    本文详细介绍了Java泛型的概念及其在JDK 5中的应用,通过具体代码示例解释了泛型的引入、作用和优势。同时,探讨了泛型类、泛型方法和泛型接口的实现,并深入讲解了通配符的使用。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文详细记录了在基于Debian的Deepin 20操作系统上安装MySQL 5.7的具体步骤,包括软件包的选择、依赖项的处理及远程访问权限的配置。 ... [详细]
  • 数据库内核开发入门 | 搭建研发环境的初步指南
    本课程将带你从零开始,逐步掌握数据库内核开发的基础知识和实践技能,重点介绍如何搭建OceanBase的开发环境。 ... [详细]
  • 使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表
    本文介绍了一段通用代码示例,该代码不仅能够操作 Azure Active Directory (AAD),还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级:AAD 和 Subscription。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本文探讨了如何在编程中正确处理包含空数组的 JSON 对象,提供了详细的代码示例和解决方案。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细介绍如何使用arm-eabi-gdb调试Android平台上的C/C++程序。通过具体步骤和实用技巧,帮助开发者更高效地进行调试工作。 ... [详细]
  • 本文介绍了Java并发库中的阻塞队列(BlockingQueue)及其典型应用场景。通过具体实例,展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递,并结合线程池和原子类优化性能。 ... [详细]
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社区 版权所有