关键词:
通过前面的学习知道,具有“一对一”逻辑关系的数据,最佳的存储方式是使用线性表。那么,什么是线性表呢?
图 2 数据的"线性"结构
图 3 两种线性存储结构
将具有“一对一”关系的数据“线性”地存储到物理空间中,这种存储结构就称为线性存储结构(简称线性表)。
使用线性表存储的数据,如同向数组中存储数据那样,要求数据类型必须一致,也就是说,线性表存储的数据,要么全不都是整形,要么全部都是字符串。一半是整形,另一半是字符串的一组数据无法使用线性表存储。
顺序存储结构和链式存储结构
图 3 中我们可以看出,线性表存储数据可细分为以下 2 种:也就是说,线性表存储结构可细分为顺序存储结构和链式存储结构。前驱和后继
数据结构中,一组数据中的每个个体被称为“数据元素”(简称“元素”)。例如,图 1 显示的这组数据,其中 1、2、3、4 和 5 都是这组数据钟的一个元素。另外,对于具有“一对一”逻辑关系的数据,我们一直在用“某一元素的左侧(前边)或右侧(后边)”这样不专业的词,其实线性表中有更准确的术语:
- 某一元素的左侧相邻元素称为“直接前驱”,位于此元素左侧的所有元素都统称为“前驱元素”;
- 某一元素的右侧相邻元素称为“直接后继”,位于此元素右侧的所有元素都统称为“后继元素”;
图 4 前驱和后继
不仅如此,顺序表对数据的物理存储结构也有要求。顺序表存储数据时,会提前申请一整块足够大小的物理空间,然后将数据依次存储起来,存储时做到数据元素之间不留一丝缝隙。
例如,使用顺序表存储集合
1,2,3,4,5
,数据最终的存储状态如图 1 所示:
图 1 顺序存储结构示意图
由此我们可以得出,将“具有 ‘一对一‘ 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。
通过观察图 1 中数据的存储状态,我们可以发现,顺序表存储数据同数组非常接近。其实,顺序表存储数据使用的就是数组。
顺序表的初始化
使用顺序表存储数据之前,除了要申请足够大小的物理空间之外,为了方便后期使用表中的数据,顺序表还需要实时记录以下 2 项数据:- 顺序表申请的存储容量;
- 顺序表的长度,也就是表中存储数据元素的个数;
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.length=0;//空表的长度初始化为0 t.size=Size;//空表的初始存储空间为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.length = 0;//空表长度初始化为0 t.size = Size;//空表可以存储元素个数 return t; //输出顺序表中元素函数 void display(table t) for (int i = 0; i < t.length;i++) printf("%d ",t.head[i]); printf("\\n"); int main() table t = initTable(); //向顺序表中添加元素 for (int i = 1; i <= Size;i++) t.head[i - 1] = i; t.length++; printf("顺序表中存储元素分别是:\\n"); display(t); return 0;
程序运行结果如下:
顺序表中存储的元素分别是:
1 2 3 4 5
顺序表插入元素
- 插入到顺序表的表头;
- 在表的中间位置插入元素;
- 尾随顺序表中已有元素,作为顺序表中的最后一个元素;
- 将要插入位置元素以及后续的元素整体向后移动一个位置;
- 将元素放到腾出来的位置上;
1,2,3,4,5
的第 3 个位置上插入元素 6,实现过程如下:
- 遍历至顺序表存储第 3 个数据元素的位置,如图 1 所示:
图 1 找到目标元素位置
- 将元素 3 以及后续元素 4 和 5 整体向后移动一个位置,如图 2 所示:
图 2 将插入位置腾出
- 将新元素 6 放入腾出的位置,如图 3 所示:
图 3 插入目标元素
//插入函数,其中,elem为插入的元素,add为插入到顺序表的位置 table addTable(table t,int elem,int add) //判断插入本身是否存在问题(如果插入元素位置比整张表的长度+1还大(如果相等,是尾随的情况),或者插入的位置本身不存在,程序作为提示并自动退出) if (add>t.length+1||add<1) printf("插入位置有问题"); return t; //做插入操作时,首先需要看顺序表是否有多余的存储空间提供给插入的元素,如果没有,需要申请 if (t.length==t.size) t.head=(int *)realloc(t.head, (t.size+1)*sizeof(int)); if (!t.head) printf("存储分配失败"); return t; t.size+=1; //插入操作,需要将从插入位置开始的后续元素,逐个后移 for (int i=t.length-1; i>=add-1; i--) t.head[i+1]=t.head[i]; //后移完成后,直接将所需插入元素,添加到顺序表的相应位置 t.head[add-1]=elem; //由于添加了元素,所以长度+1 t.length++; return t;
注意,动态数组额外申请更多物理空间使用的是 realloc 函数。并且,在实现后续元素整体后移的过程,目标位置其实是有数据的,还是 3,只是下一步新插入元素时会把旧元素直接覆盖。
顺序表删除元素
从顺序表中删除指定元素,实现起来非常简单,只需找到目标元素,并将其后续所有元素整体前移 1 个位置即可。后续元素整体前移一个位置,会直接将目标元素删除,可间接实现删除元素的目的。
1,2,3,4,5
中删除元素 3 的过程如图 4 所示:
图 4 顺序表删除元素的过程示意图
因此,顺序表删除元素的 C 语言实现代码为:
//删除指定元素 table deltable(table t,int del) //add表示顺序表中删除元素的位置 if (del>t.length|| del<1) printf("被删除的元素有误"); exit(0); //删除操作 for (int i = del; i < t.length;i++) t.head[i - 1] = t.head[i]; t.length--; return t;
顺序表查找元素
顺序表中查找目标元素,可以使用多种查找算法实现,比如说二分查找算法、插值查找算法等。
这里,我们选择顺序查找算法,具体实现代码为:
//查找函数,其中,elem表示要查找的数据元素的值 int selectTable(table t,int elem) for (int i=0; i<t.length; i++) if (t.head[i]==elem) return i+1; return -1;//如果查找失败,返回-1
顺序表更改元素
顺序表更改元素的实现过程是:
- 找到目标元素;
- 直接修改该元素的值;
顺序表更改元素的 C 语言实现代码为
//更改函数,其中,elem为要更改的元素,newElem为新的数据元素 table amendTable(table t,int elem,int newElem) int add=selectTable(t, elem); t.head[add-1]=newElem;//由于返回的是元素在顺序表中的位置,所以-1就是该元素在数组中的下标 return t;
以上是顺序表使用过程中最常用的基本操作,这里给出本节完整的实现代码:
#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.length = 0;//空表长度初始化为0 t.size = Size;//空表可以存储元素个数 return t; //插入函数,elem:插入的元素 add:插入到顺序表的位置 table addTable(table t, int elem,int add) /*1,判断插入本身是否存在问题 如果插入元素位置比整张表的长度+1还大,(如果相等,就是尾随的情况) 或者插入位置本身不存在程序作为提示,自动退出*/ if (add > t.length + 1 || add < 1) printf("插入位置有问题"); return t; /*做插入时,首先要看顺序表是否有多余的存储空间提供给插入的元素, 如果没有需要申请 */ if (t.length==t.size) t.head = (int*)realloc(t.head,(t.size+1)*sizeof(int)); if (!t.head) printf("存储分配失败"); exit(0); t.size += 1; //插入操作,需要从插入位置开始的后续元素,逐个后移 for (int i = t.length - 1; i >= add - 1;i--) t.head[i + 1] = t.head[i]; //后移完成后直接将所需元素,添加到顺序表相应的位置 t.head[add - 1] = elem; //由于添加了元素,所以长度+1 t.length++; return t; //删除指定元素 table deltable(table t,int del) //add表示顺序表中删除元素的位置 if (del>t.length|| del<1) printf("被删除的元素有误"); exit(0); //删除操作 for (int i = del; i < t.length;i++) t.head[i - 1] = t.head[i]; t.length--; return t; //查找元素,elem表示要找的数据元素的值 int findByElem(table t,int elem) for(int i=0;i < t.length;i++) if (t.head[i]==elem) return i + 1; return -1;//如果查找失败返回-1 //更改顺序表中某个元素 table updateTable(table t,int oldElem,int newElem) int n = findByElem(t,oldElem);//找出old元素所在位置 t.head[n - 1] = newElem;//由于返回的是元素在顺序表中的位置,所以-1就是元素在数组的下标 return t; //输出顺序表中元素函数 void display(table t) for (int i = 0; i < t.length;i++) printf("%d ",t.head[i]); printf("\\n"); int main() table t = initTable(); //向顺序表中添加元素 for (int i = 1; i <= Size;i++) t.head[i - 1] = i; t.length++; printf("原顺序表中存储元素顺序是:\\n"); display(t); table t1=addTable(t,8,2); printf("添加元素后是:\\n"); display(t1); t1=deltable(t1,2); printf("删除add位上的元素后:\\n"); display(t1); int n=findByElem(t1,4); printf("查找元素4的位置:%d \\n",n); t1 = updateTable(t1,1,9); printf("元素1修改为9后遍历:\\n"); display(t1); return 0;
程序运行结果为:
总结:
顺序表的短板
插入元素,时间复杂度 O(n)
小提示
数据结构之顺序表(代码片段)
...容SeqList.c文件内容前言讲完算法效率,就正式开始我们的数据结构 查看详情
线性表之单链表(代码片段)
在学完线性表之后,总结一下顺序表的优缺点优点无须为元素之间的逻辑结构增添额外的储存空间,自成一体。随机存取,十分方便。缺点空间利用率不高,容易造成“碎片”。插入删除操作需要移动大量的元素。当线性... 查看详情
线性表之顺序存储结构(顺序表)(代码片段)
目录1.线性表2.顺序存储结构(顺序表)2.1顺序表一般可以分为: 1.静态顺序表:使用定长数组存储元素 1.1静态顺序表:顺序表的大小是确定的,容量是固定的. 结论:静态顺序表不是很常量,了解就行.2.动态顺序表:... 查看详情
线性表之顺序表(代码片段)
线性表的结构体定义:#defineMaxSize100typedefstructintdata[MaxSize];intlength;Sqlist; 顺序表在内存中以数组形式保存,是一组连续的内存空间。顺序表基本算法:构造一个空的线性表://初始化线性表STATUSInitList(Sqlist&L)//置表长为0L.len... 查看详情
数据结构线性表之顺序表arraylist(代码片段)
...ArrayList。为什么我们称其为顺序表呢?原因顾名思义是该数据结构在逻辑上和物理结构上的存储顺序均是连续的。下面,我们就以一张图来说明什么是顺序表。 这个图代表逻辑上的9个元素,每一个位置均存储一个数据,数... 查看详情
数据结构线性表之实现单链表(代码片段)
数据结构线性表之实现单链表数据结构线性表之实现单链表相关文章单链表定义单链表相关操作数据结构线性表之实现单链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实现顺序表(三)数... 查看详情
线性表之栈(代码片段)
栈的定义: 一种只能在一端进行插入或删除操作的线性表被称为栈,其中允许删除或插入的一端为栈顶,另一端为栈底,栈底固定不变; 栈的特点:先进后出,例如弹夹,先装的子弹最后才能出; 按照存储结构可以... 查看详情
02线性表之顺序表(代码片段)
肚子饿了就要吃 ~ 嗝 ———路飞 目录1.本章重点2.线性表3.顺序表实现3.1顺序表的概念及结构4.静态顺序表5.动态顺序表 5.1“增”尾插:头插:5.2“删”尾删头删5.3随机“插入”5.4随机“删除”5.5内存销毁5.6“改”5... 查看详情
数据结构之线性表之顺序存储java实现(代码片段)
文章目录线性表的定义线性表的基本运算线性表的存储之顺序存储定义线性表添加元素查找元素删除元素打印线性表实现的完整代码测试一下线性表的定义线性表的逻辑特征:①有且仅有一个称为开始元素的a1,她没有前... 查看详情
数据结构线性表之实现单循环链表(代码片段)
数据结构线性表之实现单循环链表数据结构线性表之实现单循环链表相关文章单循环链表单循环链表定义数据结构线性表之实现单循环链表相关文章数据结构线性表之概念(一)数据结构线性表之抽象基类(二)数据结构线性表之实... 查看详情
03线性表之链表(代码片段)
肚子饿了就要吃 ~ 嗝 ———路飞 1.本章重点链表表示和实现(单链表+双链表)链表的常见OJ题顺序表和链表的区别和联系2.为什么需要链表引子:顺序表的问题及思考(1)动态顺序表特点:插入数据,... 查看详情
杨玲徐思《面向对象程序设计(java)》第十一周学习总结(代码片段)
...十一周学习总结第一部分:理论知识学习部分1、一般将数据结构分为两大类:线性数据结构和非线性数据结构。线性数据结构:线性表、栈、队列、串、数组和文件。非线性数据结构:树和图。2、线性表按其存储结构可分为顺... 查看详情
数据结构——线性表之顺序表篇(代码片段)
目录前言顺序表的介绍和简单实现关于顺序表顺序表的分类顺序表的初步组成功能函数的声明功能函数的实现初始化检查容量判断是否需要扩容头插头删 尾插尾删指定数据位置插入指定数据删除寻找数据并返回下标销毁顺序表... 查看详情
数据结构线性表循环链表之约瑟夫环(代码片段)
(一)前提41个人报数,1-3,当谁报数为3,谁就去嗝屁。现在获取他们嗝屁的顺序(二)实现结构顺序:3->1->5->2->4 (三)代码实现#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<time.h>#defineOK1#... 查看详情
线性表之链表(代码片段)
单链表也是一种链式存取的线性表,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,以next指针指向下一个节点而链接起来,相比于顺序表,链表有着快速增加,删除节点的优势,其节点... 查看详情
数据结构学习笔记二线性表之链表篇(双向链表)(代码片段)
链表根据带头不带头、单向或双向、循环非循环三个方面可组成成八种类型。这八种类型中仅有两种是我们常用的。第一种是单向不带头非循环链表,也就是单链表。单链表因为结构简单,但是实际操作比较复杂,所... 查看详情
线性表之顺序存储-顺序表(代码片段)
顺序表的操作[x]向有序顺序表插入一个元素[x]顺序表的冒泡排序[x]顺序表的删除操作[x]顺序表中元素的查找[x]顺序表的逆置[x]删除顺序表中的相同元素[x]向顺序表的指定位置插入元素[x]打印顺序表顺序表的存储结构#definemaxsize100/... 查看详情
数据结构与算法-线性表之循环链表(代码片段)
前言:前面几篇介绍了线性表的顺序和链式存储结构,其中链式存储结构为单向链表(即一个方向的有限长度、不循环的链表),对于单链表,由于每个节点只存储了向后的指针,到了尾部标识就停止了向后链的操作。也就是说... 查看详情