数据结构与算法(三) |
您所在的位置:网站首页 › 数据结构中线性结构中元素对应关系为哪些 › 数据结构与算法(三) |
目录 一、前情提要 二、静态链表的介绍 三、代码展示 一、前情提要上篇讲到了最基本的链式存储结构——单链表。但单链表的功能可能不能满足我们的需求,所以就衍生出了静态链表。本篇文章将会介绍其功能,并给出相关代码。后面还有双向链表和循环链表,本来想一起写的,但太长了,分三次吧。 二、静态链表的介绍Q1:啥叫静态链表? A:简单点说静态链表是用数组描述的链表。注意:和前面的线性存储不一样,这里是用数组模拟链表。 Q2:为啥会出现静态链表这种东西? A:这就得说说C语言的伟大了,因为它具有指针的能力,这样使得它可以非常容易的操作内存中的地址和数据。 但后来的面向对象语言,如:Java、C#等。它们是没有指针这个东西的。更别说一些早期的语言,如:Basic、Fortran等。由于没有指针,按照之前单链表的结构,指针域就没办法实现。所以衍生了静态链表这个产物。 Q3:那我们是如何用数组描述链表的呢? A:首先我们让数组的元素都是由两个数据域组成,称之为Date和Cur。也就是说数组的每一个下标都对应一个Date和Cur。 数据域Date,用来存放数据元素,也就是我们通常要处理的数据。 数据域Cur,相当于单链表中的Next指针,存放该元素的后继在数组中的下标,我们把Cur叫做游标。 这种实现方法也叫游标实现法。 为了方便插入数据,我们通常会把数组建立更大一些,以便有一些空闲空间插入时不至于溢出。说到这里它的优点和缺点都很明显了。、 优点&&缺点 优点:在插入和删除操作时只需要修改游标,不需要移动元素。从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。 缺点:(1)没有解决连续存储分配带来的表长难以确定的问题。 (2)失去了顺序(线性)存储结构随机存取的特性。 “失去了顺序存储结构随机存取的特性。”这句话听起来可能有点懵,我解释一下。因为顺序存储是由数组实现的,给我随机的数组下标我都可以将数据存进去,取出来。而现在变成了链表的形式,变成了链式存储,只能从头到尾进行查找,然后存取。 总的来说,静态链表就是为了给没有指针的高级语言实现单链表能力的一种方法。尽管大家以后不一定用的上,但这样的思考方式是非常巧妙的,应该理解其思想,以备不时之需。 它的功能和单链表也差不多,边分析边写代码吧。 静态链表创建+初始化操作 在静态链表中有个约定俗称的规定: 1.第一个和最后一个结点作为特殊元素处理,不存数据。 2.我们通常把未被使用的数组元素称之为备用链表,而数组第一个元素(即下标为0的元素)的Cur就存放备用链表的第一个结点的下标。 3. 数组最后一个元素的Cur则存放第一个有数值的元素(首元结点)的下标,相当于单链表中头结点的作用。当整个链表为空的时候,数组中最后一个元素的Cur为0。 4.如果一个结点下一位置的数据为空但这个结点数据不为空,则这个结点的Cur用0来表示。因为这个这是最后一个有数据的结点了,没有下一个有数据的结点了,所以Cur为0相当于指针中的NULL。 画图理解一下: #define MaxSize 1000 typedef struct { int Data; //两个数据域 int Cur; //一个是存储数据,另外一个就是游标(存储下一个元素的下标) }Component,StaticList[MaxSize];//Component是备用链表,StaticList是 静态链表。 void Init(StaticList Space) //静态链表初始化。主要有两点:1.将Cur游标存储下一个结点的下标 { //2.最后一个结点的Cur游标存储第一个有数值的元素的下标。 for(int i=0;i |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |