小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作 实战比特币脚本编程(1) JAVA WEB DAY 01_Tomcat & Servlet Java基础算法之堆排序(Heap Sort) synchronized批量重偏向与批量撤销 终于等到了!阿里P8历时九个月整理,Java面试宝典,核心知识点笔记在此 “数字心脏”动态解析消费密码,国家级消费市场大数据联合实验室在上海先行先试 全世界运行着大约230亿台物联网设备,安全问题如何解? 物联网产业园&thinkplus解决方案中心国学讲座如期而至 都是程序员,凭什么他能站在鄙视链的顶端? 猛男必看!去小红书做程序员是种什么体验 drozer提示[Errno 2] No such file or directory 【STM32】NB-iOT BC35-G模块 AT指令应用设计指导(附代码) 【北京迅为】i.MX6ULL终结者编译LED汇编程序 Linux系统读写网卡PHY寄存器工具 洛谷:P1226 【模板】快速幂||取余运算(分治,数学) 【2020顶会KDD】AutoST:面向时空预测的高效神经网络学习模型 C/C++实现并查集disjoint_set的模板(带路径压缩优化) 实现一个百万级推送服务,除了它,还有谁 “健康守护者”——STM32标准库和HAL库的比较 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 RTTR实现C++反射(1)集成rttr库 lotus node 远程运行 CCF历年4,5题收录 N卡 RTX3070/RTX3080/RTX3090挖矿算力推测 最高算力86MH 理论+实验:MySQL索引、事物与存储引擎 PostgreSQL JOIN 多表查询 TP框架实现Excel批量导入数据库数据 MySQL中的列转行 这次是真拯救了我,MySQL索引优化,explain讲得非常清楚了 Oracle快速入门(PLSQL编程) MySQL字符串拼接、截取 MySQL事务管理及存储引擎 《浪姐》万茜点赞宁静、郁可唯黑贴坐实?盗号者和程序员是背锅侠 程序员被公司辞退12天后,前领导要求回公司讲清代码,结果懵了 易语言大漠多线程foobar在游戏多窗口中时时显示输出信息 非科班,自学两年,复盘两个月,侥幸拿到头条、阿里offer 2020年全国数学建模大赛B题源代码以及模型的建立 (2) 2020年数学建模-校园供水系统智能管理 windows破解锁屏密码(亲测有效:再也不怕别人锁屏防你啦!) 清华大佬力荐的JVM学习路线+实战笔记+阿里真题,嚼碎吃透吊打面试官 打造多模块+高可用+高扩展Spring Cloud版分布式电商项目源码分享 Python爬虫入门教程 89-100 定个小目标,先用Python爬个一亿B站用户 五大分布式事务,你了解多少? 2020-09-12 九大核心专题,630页内容,熬夜23天吃透,我收割了3个大厂offer 防抖节流 防抖和节流 函数节流 debounce throttle 每天补充一点 一些零碎的小知识点 JavaScript作用域和作用域链知多少 01-jquery概述
您的位置:首页 >计算机基础 >

小甲鱼笔记:数据结构——线性表(一)线性表的顺序存储结构,线性表顺序存储结构的增,删,插入元素操作

一、线性表的定义

线性表(List):由零个或多个数据元素组成的有限序列。

TIPS: 1.线性表是一个序列,也就是说元素之间是有先来后到的。 2.若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他元素只有一个前驱和后继。3.线性表是有限的。

用数学语言定义: 若将线性表记为(a1,a2,…ai-1,ai,ai+1,…an)则ai-1领先于ai,ai领先于ai+1,称ai-1为ai的前驱元素,ai+1是ai的直接后继元素。 线性表 所以线性表元素的个数n(n>0)定义为线性表长度,当n=0成为空表。

二、抽象数据类型

定义:

一组性质相同的值的集合及定义在此集合上的一些操作总称。 例:很多编程语言的整型,浮点型,字符型这些即为数据类型。 在计算机中,内容并非无限大,若计算1+1=2整型数字的加减乘除,不需要开辟很大空间。 若计算1.23456+2.78946这样带小数的就需要比较大的空间存放,故要对数据类型进行分类,分出多种类型来适合各种不同的计算条件差异。

例如: C语言中数据类型分为两类: 原子类型:不可以再分解的基本类型,例如:整型,浮点型,字符型…

结构类型:由若干个类型组合而成,是可以再分解的,例如:整形数组是由若干个整形数据组成的

何为抽象:是指抽取出事物具有普遍性的本质,它要求抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象是一种思考问题的方式。

抽象数据类型

是指一个数学模型及定义在该模型上的一组操作,它的定义取决于它的一组逻辑特性,而与其他计算机内部如何表示和实现无关。

为了方便江杰对抽象数据类型进行规范描述,我们给出了描述抽象数据类型进行规范描述,我们给出了描述抽象数据类型的标准格式。
 ADT: 数据类型 DATA:数据元素之间的逻辑关系定义 OPERATION:操作

二、线性表的抽象数据类型

定义: ADT:线性表(List)

Data:线性表的数据对象集合为(a1,a2…an),每个元素的类型均为DataType。其中,除第一个元素a1外,每一个元素有且只有一个前驱元素,除了最后一个元素an外,每个元素有且只有一个后继元素。数据元素之间的关系是一对一的关系

Operation: InitList(*L):初始化操作,建立一个空的线性表L ListEmpty(L):判读线性表是否为空表,若线性表为空,返回true,否则返回false; ClearList(*L):将线性表清空。 GetElem(L,i,*e):将线性表L中第i个位置元素值返回给e; LocateElem(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在表中序号表示成功,否则,返回0表示失败。 ListInsert(*L,i,e):在线性表L中第i个元素位置插入新元素e; ListDelete(*L,I,*e):用删除线性表L中第i个位置元素,并用e返回其值。 ListLength(L):返回线性表L的元素个数。

对于不同的应用,线性表的基本操作是不同的,上述为基础Operation,对于实际问题中涉及的关于线性表的更多复杂操作,完全可以用这些基本操作的组合来实现。 例题: 若实现两个线性表A,B的并集操作,即要是的集合A=AUB; 分析: 只要遍历集合B中的每个元素,判断当前元素是否存在A中,若不存在,则插入A中;所以我们需要用到上述的基本Operation。 ListLength(L);GetElem(L,i,*e)LocateElem(L,e);ListInsert(*L,i,e);

伪代码实践:void UnionL(List *La,list Lb){int La_len,Lb_len,i;ElemType e;La_len = ListLength(*La);Lb_len = ListLength(Lb);for(int i = 1;i<La_len;i++){//遍历获得Lb中的所有元素GetElem(Lb,i,&e);//判断La中的中的元素是否与取出的e相同,若没有则插入元素if(!LocateElem(*La,e)){ListInsert(La,++La_len,e);}}}

三、线性表的顺序存储结构

引入: 线性表由两种物理存储结构:顺序存储结构链式存储结构。在此介绍顺序存储结构

顺序存储结构 是指用一段地址连续的存储单元依次存储线性表的数据元素。例如:数组。

物理上的存储方式就是在内存中找个初始地址,然后通过占位的形式,把一定内存空间给占掉,然后把相同数据类型的数据元素一次放在这块空地上。(可以理解为一个团体共50人,在看电影时,第一位领头人,去第一排第一个位置占座,剩余的49人依次跟在领头人的后面。)

线性表顺序存储的结构代码

 #define MAXSIZE 20typedef int ElemType; typedef struct{ElemType date[MAXSIZE];int length;//线性表当前长度}SqList;//对数组进行封装,增加了当前长度的变量
总结 顺序存储结构封装需要三个属性: ——存储空间的起始位置,数组data,它的存储位置就是线性表存储空间的存储位置 ——线性表的最大存储容量:数组的长度MaxSize. ——线性表的当前长度:length ——注意:数组的长度与线性表的当前长度需要进行区别:数组的长度时存放线性表的存储空间的总长度,一般初始化后长度不变(一些编程语言可以将数组长度变大,但一般情况下认为初始化长度不变)。而线性表的当前长度时线性表中的元素的个数,是会变化的。

四、地址计算方法

因为编程语言中我们的数组是从0开始进行遍历,但线性表一般从1开始遍历 假设ElemType占用的是c个存储单元(字节),那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是:(Loc表示获得存储位置的函数):Loc(ai+1) = Loc(ai)+c

所以对于第i个数据元素ai的存储位置可以由a1推算得出: Loc(ai) = Loc(a1)+(i - 1)* c;

在这里插入图片描述

通过公式,可以随时计算出线性表的任意位置的地址。不管是第一个还是最后一个都是相同的实践,它的存储实践性能为O(1),我们通常成为随机存储结构。

五、线性表顺序存储结构之获得元素操作

分析: 实现GetElem的具体操作,即将线性表L中的第i个位置元素值返回。只需要把数组第i-1下标的值返回即可。

代码实践

 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; //Status 是函数的类型,它的值是函数结果状态代码,如OK等。 //初始条件:顺序线性表L已存在,i<= i<=ListLength(L) //操作结果:用e返回L中第i个数据元素的值 Status GetElem(SqList L,int i,ElemType *e){if(L.length == 0 || i < 1 || i>L.length){return ERROR;}*e=L.data[ i - 1 ];return OK;}

注意这里的Status是一个整型,约定返回1代表OK,返回0代表ERROR。其时间复杂度为O(1)

六、线性表顺序存储结构之插入元素操作

分析 ——如果插入位置不合理,抛出异常 ——如果线性表长度大于等于数组长度,则抛出异常或动态增加数组容量。 ——从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置; ——将要插入元素填入位置i处; ——线性表长度+1

代码实践

Status ListInsert(SqList *L,int i,ElemType e){int k;if(L->length == MAXSIZE) //顺序线性表已经满了{return ERROR;}if(i < 1 || i > L->length+1)//i不在范围内时{return ERROR;}if(i <= L->length) //若插入数据位置不在表尾{//将要插入位置后数据元素向后移动一位for(k = L->length-1; k >= i -1;k--){L->data[k+1] = L->data[k];}}L->data[ i - 1] = e;//将新元素插入L->length++;return OK;}

注意:ListInsert(*L,i,e)插入元素操作的时间复杂度为O(n);第i个位置插入新元素e

七、线性表顺序存储结构之元素删除操作

分析 ——删除位置不合理,抛出异常 ——取出删除元素 ——从删除元素位置开始遍历。最后一个元素位置,分别将他们都向前移动一个 ——表长-1代码实践
 Status ListDelete(SqList *L,int i,ElemType *e){int k;if( L->length ==0){return ERROR;}if( i < 1 || i>L->length){return ERROR;}*e= L->data[i-1];if( i < L->length){for( k = i; k < L->length;k++){L->data[k-1] =L->data[k];}}L->length--;}

插入或删除的时间复杂度,最好的情况下为O(1),表示只需在尾部插入一个元素或者在尾部删除一个元素。最坏情况下,需要O(n)个时间复杂度,因为需要遍历循环线性表。两者进行平均可得时间复杂度O((n-1)/2)可以推出时间复杂度为O(n)

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。