数据结构静态链表和动态链表_什么是静态链表

数据结构静态链表和动态链表_什么是静态链表静态链表:分配一整片连续的内存空间,各个结点集中安置,逻辑结构上相邻的数据元素,存储在指定的一块内存空间中,数据元素只允许在这块内存空间中随机存放,这样的存储结构生成的链表称为静态链表

静态链表的定义:

静态链表:分配一整片连续的内存空间,各个结点集中安置,逻辑结构上相邻的数据元素,存储在指定的一块内存空间中,数据元素只允许在这块内存空间中随机存放,这样的存储结构生成的链表称为静态链表。也就是说静态链表是用数组来实现链式存储结构,静态链表实际上就是一个结构体数组
在这里插入图片描述

举例:通过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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注