初识线性表和抽象数据类型数据结构与算法学习笔记

初识线性表和抽象数据类型

线性表
抽象数据类型

数据类型
抽象
抽象数据类型
抽象数据类型的标准格式
线性表的抽象数据类型定义

线性表线性表是什么,简单来说线性表就如同生活中的排队一样,具有线一样性质的数据结构.线性表有0个(当数据元素为0时,称该线性表为空表)或者多个数据元素组成

线性表有以下几个特点
- 线性表是一个序列,即各数据元素之间有一定的前后关系
- 若线性表不为空表,则第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱或者后继
- 线性表中数据元素是有限的,因为无论计算计多强大,发展到多先进的程度,计算机能够处理的数据永远不可能是无限的

前驱和后继(数学语言描述)
若将线性表记为a1.a2,…ai-1,ai,ai+1,…,an,则表中ai-1领先于ai,ai领先于ai+1,则称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素

可以看出，区别于很多计算机高级语言，线性表的序列是从1开始的，也因此，我们将线性表的元素个数n定义为线性表的长度。
【初识线性表和抽象数据类型】

文章图片

上面这个图中可以看出总经理下分了别的职位，而总监下又分了别的职位，从线性表的特点：若线性表不为空表,则第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱或者后继，由于该图中一个数据元素有多个后继，所以我们可以判断该表不是线性表。
抽象数据类型数据类型 数据类型[^1]指一组性质相同的值得集合以及定义在此集合上的一些操作的总称

在C语言中，数据类型按照取值的不同，可以分为
- 原子类型：不可再分解的基本类型，比如注1中的几种类型
- 结构类型：若干个类型组合而成，可以再分解的，比如整形数组（若干个整型数据组成）、结构体…

[^1]比如编程语言中的整形,浮点型,字符型
抽象什么是抽象?抽象就是抽取出事物具有的普遍性的本质,它要求抽出问题的特征而忽略非本质的细节(对具体事务的一个概括),抽象是一种思考问题的方式,它隐藏了繁杂的细节。
比如，脏活累活交给男人来干，男人就是抽象，它不具体指是哪一个人。
抽象数据类型

对已有的数据类型进行抽象，就有了抽象数据类型(Abstract Data Type,ADT)，指一个数学模型及定义在该模型上的一组操作。

抽象数据类型的定义仅仅取决于它的一组逻辑特性,与其在计算机内部如何表示无关,例如1+1=2,在不同CPU的处理可能不一样，由于其数学特性相同，所以在计算机编程者眼中，它们相同。
“抽象”意义在于数学类型上的数学抽象特性。抽象数据类型不仅指已经定义并实现的数据类型，还可以是计算机变成这自己定义的数据类型，例如以后要学习的线性表。
抽象数据类型的标准格式

ADT（抽象数据类型名） Data 数据元素之间逻辑关系的定义 Operation 操作 endADT

线性表的抽象数据类型定义

ADT线性表(List) Data 线性表数据对象集合为{a~1~.a~2~,...a~i-1~,a~i~,a~i+1~,...,a~n~} 并且每个元素类型均为DataType，除a~1~外，每个元素有且只有一个直接前驱元素，除a~n~外，每个元素有且只有一个直接后继元素元素之间关系：一一对应 Operation InitList(*L); //初始化,建立一个空的线性表L ListEmpty(L); //判断L是否为空表,为空,返回true,否则返回false ClearList(*L); //清空线性表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); //返回线性表的元素个数 endADT

有了上面的定义,我们就可以方便的实现一些操作,例如下面的求两表并集(A=A∪B):

/*要实现两表并集,只需要遍历一表每一个元素,而后判断另一表是否有该元素,若有,忽略,没有插入*/ List *unionL(List *La,List Lb) { int lengtha=ListLength(*La); //获得La的长度 int lengthb=Listlength(Lb); //获得Lb的长度 ElemType *e; //接收表Lb的值 /*表Lb为空表,直接返回表La*/ if(lengthb==0) { return La; } else { for(int i=1; i<=lengthb; i++)//遍历Lb { GetElem(Lb,i,*e); //将Lb第i个元素赋值给e if(!(locateElem(*La,e)))//判断La中是否有e,若没有在表a末尾插入e { ListInsert(*La,(lengtha+1)++,*e); } } } return La; }

可见，定义了一个抽象数据类型，将其封装之后，我们将能够更方便快捷的解决一些实际问题