资源描述：
《线性表的类型定义、顺序表示和实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现线性表是一种最简单的线性结构。什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：在数据元素的非空有限集中，①存在惟一的一个被称做"第一个"的数据元素；②存在惟一的一个被称做"最后一个"的数据元素；③除第一个之外，集合中的每个数据元素均只有一个前驱；④除最后一个之外，集合中的每个数据元素均只有一个后继。这里的"有序"仅指在数据元素之间存在一个"领先"或"落后"的次序关系，而非指数据元素"值"的大小可比性。比较典型的线性结构：线性表、栈、队列、串等。2.1线性表的类
2、型定义2.1.1线性表的定义线性表(linear_list)是n个数据元素的有限序列，记作（a1,a2,…,ai,…,an）。线性表的数学模型（形式定义）：含有n个数据元素的线性表是一个数据结构LinearList=（A,R）其中：A={ai
3、ai∈ElemType,1≤i≤n,n≥0}R={r}r=｛
4、1≤i≤n-1}说明：①线性表的数据元素可以是各种类型（整、实、记录类型等）typedefintElemType;typedefcharElemType;等；②同一线性表中的数据元素必须具有相同的特性，属同一类型；③关系r是一个有序偶对的集合，即对于非空的线性表（a
5、1,a2,…,ai-1,ai,ai+1,…,an），ai-1领先于ai，表示了数据元素之间的相邻关系，称ai-1是ai的直接前驱，ai是ai-1的直接后继；④序列中数据元素的个数n定义为线性表的表长，n=0时的线性表被称为空表；⑤称i为数据元素在线性表中的位序。2.1.2线性表的抽象数据类型ADTLinearList{Data:一个线性表L定义为L=(a1,a2,…,an)，当L=（）时定义为一个空表。Operation:boolinitList(&L);//初始化线性表L，即把它设置为一个空表voidclearList(&L);//将L重置为空表intgetSize(L);//返回L
6、中数据元素的个数boolisEmpty(L);//判断L是否为空，若空则返回true，否则返回falsevoidtraverList(L,visit());//遍历线性表L，依次对L的每个数据元素调用函数visit()ElemType&getElem(L,pos);//返回线性表第pos个数据元素的值intlocateElem(&L,e,compare());//返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回0boolinsertElem(&L,e,pos);//在L的pos位置插入e，线性表L长度加1booldeleteElem(&L,p
7、os);//删除L的第pos个数据元素boolcreateList(&L,n,visit());//创建有n个元素的线性表}2.1.3操作举例例：假设利用两个线性表La和Lb分别表示两个集合A和B，求一个新的集合A=A∪B。算法：①取得Lb中的1个元素；②在La中查找这个元素；③若不存在：插入La中；若存在，取Lb中下一个元素，重复①、②、③，直到取完Lb的每个元素。voidunionList(SqList&la,SqListlb){intlbSize=getSize(lb);ElemTypee;for(inti=1;i<=lbSize;++i){e=getElem(lb,i);if(
8、!locateElem(la,e,equal))insertElem(la,e,la.size+1);}}intequal(ElemTypee1,ElemTypee2){if(e1.id==e2.id)return1;return0;}算法的时间复杂度为O(La.size×Lb.size)。2.2线性表的顺序表示和实现2.2.1线性表的顺序表示线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表。
9、表示为：A=(a1，a2，…，ai，ai+1，…，an)第i个元素的地址假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(ai)：loc(ai)=loc(a1)+(i-1)×k其中loc(a1)称为基地址。线性表的顺序存储结构示意图顺序存储结构可以借助于高级程序设计语言中的一维数组来表示。用C++语言描述的顺序表类型如下所示： sqlist.h#include
