静态链表的定义:
静态链表:分配一整片连续的内存空间,各个结点集中安置,逻辑结构上相邻的数据元素,存储在指定的一块内存空间中,数据元素只允许在这块内存空间中随机存放,这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构,静态链表实际上就是一个结构体数组
举例:通过a[1]中存放的游标变量3可找到存放的数据元素5的后继元素为3,再通过a[3]中存放的游标变量2可找到存放数据元素3的后继数据为2,以此类推,直到某元素的游标变量为0即可停止(注:a[0]为头结点不存储数据元素)
备用链表:
在链表中,我们不可能恰好将所有的位置都使用,那么就会出现空闲的位置,用来连接这些空闲位置的链表,我们就将其称之为备用链表,他的作用为:回收数组中目前没有适用的空间。
那么此时就相当于有两个链表,实现不同的功能,一个用来连接数据,另一个用来连接数组中的空闲空间。
一般情况下,备用链表的表头位于数组下标为0(a[0])的位置,而数据链表的表头位于数据下标为1(a[1])的位置。
如上图所示:备用链表的连接顺序依次是:a[0],a[2],a[4]数据链表的连接顺序依次是a[1],a[3],a[5]
静态链表添加数据的实现过程:
以存储{1,2,3}为例,分析过程如下:
数据未存储前,数据链表当前是不存在的,所有的游标都存在于备用链表中,如下所示:
下面我们要进行的工作是将1存储进去,此时既然要存储数据,因此必须产生数据链表,那么如何产生数据链表呢?方法:备用链表摘除结点,以便存储新数据,而最简便的方法就是摘除a[0]的后继节点,即为下标为1(a[1])的位置。
将1存放进去:
将2存放进去:
将3存放进去:
定义静态链表:
方法一:
#define Maxsize 10//定义静态链表的最大长度
struct Node//定义静态链表结构类型
{
ElemType data;
int next;//游标:为下一个数据元素的数组下标,类似于指针
};
void testSLinkList()
{
struct Node a[Maxsize];//数组a作为静态链表
}
方法二:
#define Maxsize 10
struct Node
{
ElemType data;
int next;
};
typedef struct Node SLinkList[Maxsize];//这里相当于SLinkList可用来定义为一个数组,数组长度为Maxsize,类型为Node
void teastLinkLIst()
{
SLinkList a;//等价于struct Node a[Maxsize]
}
验证其两种方式是否正确:
#include<stdio.h>
#define Maxsize 10
struct Node
{
int data;
int next;
};
typedef struct
{
int data;
int next;
}SLinkList[Maxsize];
void testSLinkList()
{
struct Node x;
printf("sizeX=%d\n", sizeof(x));
struct Node a[Maxsize];//定义了一个数组a,其数组长度为Maxsize,类型为struct Node
printf
今天的文章数据结构静态链表和动态链表_什么是静态链表分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/70599.html