中山网站建设华联在线,网站建设标准简约,赶集网发布信息免费,网站维护html模板第二部分、线性表详解#xff1a;数据结构线性表10分钟入门 线性表#xff0c;数据结构中最简单的一种存储结构#xff0c;专门用于存储逻辑关系为一对一的数据。
线性表#xff0c;基于数据在实际物理空间中的存储状态#xff0c;又可细分为顺序表#xff…第二部分、线性表详解数据结构线性表10分钟入门 线性表数据结构中最简单的一种存储结构专门用于存储逻辑关系为一对一的数据。
线性表基于数据在实际物理空间中的存储状态又可细分为顺序表顺序存储结构和链表链式存储结构。
本章还会讲解顺序表和链表的结合体——静态链表不仅如此还会涉及循环链表、双向链表、双向循环链表等链式存储结构。
一、什么是线性表线性存储结构
通过前面的学习我们知道具有“一对一”逻辑关系的数据最佳的存储方式是使用线性表。那么什么是线性表呢 线性表全名为线性存储结构。使用线性表存储数据的方式可以这样理解即“把所有数据用一根线儿串起来再存储到物理空间中”。 图 1 一对一逻辑关系的数据 如图 1 所示这是一组具有“一对一”关系的数据我们接下来采用线性表将其储存到物理空间中。 首先用“一根线儿”把它们按照顺序“串”起来如图 2 所示 图 2 数据的线性结构 图 2 中左侧是“串”起来的数据右侧是空闲的物理空间。把这“一串儿”数据放置到物理空间我们可以选择以下两种方式如图 3 所示。 图 3 两种线性存储结构 图 3a) 是多数人想到的存储方式而图 3b) 却少有人想到。我们知道数据存储的成功与否取决于是否能将数据完整地复原成它本来的样子。如果把图 3a) 和图 3b) 线的一头扯起你会发现数据的位置依旧没有发生改变和图 1 一样。因此可以认定这两种存储方式都是正确的。将具有“一对一”关系的数据“线性”地存储到物理空间中这种存储结构就称为线性存储结构简称线性表。使用线性表存储的数据如同向数组中存储数据那样要求数据类型必须一致也就是说线性表存储的数据要么全部都是整形要么全部都是字符串。一半是整形另一半是字符串的一组数据无法使用线性表存储。 1、顺序存储结构和链式存储结构 图 3 中我们可以看出线性表存储数据可细分为以下 2 种 如图 3a) 所示将数据依次存储在连续的整块物理空间中这种存储结构称为顺序存储结构简称顺序表如图 3b) 所示数据分散的存储在物理空间中通过一根线保存着它们之间的逻辑关系这种存储结构称为链式存储结构简称链表 也就是说线性表存储结构可细分为顺序存储结构和链式存储结构。 2、前驱和后继 数据结构中一组数据中的每个个体被称为“数据元素”简称“元素”。例如图 1 显示的这组数据其中 1、2、3、4 和 5 都是这组数据中的一个元素。 另外对于具有“一对一”逻辑关系的数据我们一直在用“某一元素的左侧前边或右侧后边”这样不专业的词其实线性表中有更准确的术语 某一元素的左侧相邻元素称为“直接前驱”位于此元素左侧的所有元素都统称为“前驱元素”某一元素的右侧相邻元素称为“直接后继”位于此元素右侧的所有元素都统称为“后继元素” 以图 1 数据中的元素 3 来说它的直接前驱是 2 此元素的前驱元素有 2 个分别是 1 和 2同理此元素的直接后继是 4 后继元素也有 2 个分别是 4 和 5。如图 4 所示 图 4 前驱和后继 二、顺序表顺序存储结构及初始化详解
顺序表全名顺序存储结构是线性表的一种。通过《一、什么是线性表》一节的学习我们知道线性表用于存储逻辑关系为“一对一”的数据顺序表自然也不例外。 不仅如此顺序表对数据的物理存储结构也有要求。顺序表存储数据时会提前申请一整块足够大小的物理空间然后将数据依次存储起来存储时做到数据元素之间不留一丝缝隙。 例如使用顺序表存储集合 {1,2,3,4,5}数据最终的存储状态如图 1 所示 图 1 顺序存储结构示意图
由此我们可以得出将“具有 一对一 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。 通过观察图 1 中数据的存储状态我们可以发现顺序表存储数据同数组非常接近。其实顺序表存储数据使用的就是数组。
1、顺序表的初始化
使用顺序表存储数据之前除了要申请足够大小的物理空间之外为了方便后期使用表中的数据顺序表还需要实时记录以下 2 项数据
顺序表申请的存储容量顺序表的长度也就是表中存储数据元素的个数 提示正常状态下顺序表申请的存储容量要大于顺序表的长度。 因此我们需要自定义顺序表C 语言实现代码如下 typedef struct Table{ int * head;//声明了一个名为head的长度不确定的数组也叫“动态数组” int length;//记录当前顺序表的长度 int size;//记录顺序表分配的存储容量 }table; 注意head 是我们声明的一个未初始化的动态数组不要只把它看做是普通的指针。 接下来开始学习顺序表的初始化也就是初步建立一个顺序表。建立顺序表需要做如下工作
给 head 动态数据申请足够大小的物理空间给 size 和 length 赋初值
因此C 语言实现代码如下 #define Size 5 //对Size进行宏定义表示顺序表申请空间的大小 table initTable(){ table t; t.head(int*)malloc(Size*sizeof(int));//构造一个空的顺序表动态申请存储空间 if (!t.head) //如果申请失败作出提示并直接退出程序 { printf(初始化失败); exit(0); } t.length0;//空表的长度初始化为0 t.sizeSize;//空表的初始存储空间为Size return t; } 我们看到整个顺序表初始化的过程被封装到了一个函数中此函数返回值是一个已经初始化完成的顺序表。这样做的好处是增加了代码的可用性也更加美观。与此同时顺序表初始化过程中要注意对物理空间的申请进行判断对申请失败的情况进行处理这里只进行了“输出提示信息和强制退出”的操作可以根据你自己的需要对代码中的 if 语句进行改进。 通过在主函数中调用 initTable 语句就可以成功创建一个空的顺序表与此同时我们还可以试着向顺序表中添加一些元素C 语言实现代码如下 #include stdio.h #include stdlib.h #define Size 5 typedef struct Table{ int * head; int length; int size; }table; table initTable(){ table t; t.head(int*)malloc(Size*sizeof(int)); if (!t.head) { printf(初始化失败); exit(0); } t.length0; t.sizeSize; return t; } //输出顺序表中元素的函数 void displayTable(table t){ for (int i0;it.length;i) { printf(%d ,t.head[i]); } printf(\n); } int main(){ table tinitTable(); //向顺序表中添加元素 for (int i1; iSize; i) { t.head[i-1]i; t.length; } printf(顺序表中存储的元素分别是\n); displayTable(t); return 0; } 程序运行结果如下 顺序表中存储的元素分别是 1 2 3 4 5 可以看到顺序表初始化成功。
