张乃孝全套配套课件算法与数据结构 第2章 线性表.ppt

《张乃孝全套配套课件算法与数据结构 第2章 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章  线性表本章讨论的线性表和随后几章要讨论的串、栈与队列都属于线性结构。它们的共同之处，是结点中有并且仅有一个开始结点和一个终端结点。它们分别属于几种不同抽象数据类型的实现，它们之间的区别，主要是操作的不同。2.1基本概念与抽象数据类型2.1.1基本概念线性表（简称为表）是零个或多个元素的有穷序列。L=（k0，k1,…，kn-1）线性表的逻辑结构：L=其中K={k0，k1,…，kn-1}，R={

2、0≤i≤n-2}，i称为元素ki的索引或下标。表中的元素又称表目。某院系的学生名册学号姓名性

3、别年龄院名称系名称……09001001张丰男17生命科学学院生物技术学系09001002刘小红女18生命科学学院生物技术学系09001003李静女18生命科学学院细胞及遗传学系09001004王建平男18生命科学学院细胞及遗传学系…………………表中所含元素的个数称为表的长度。长度为零的表称为空表。k0称为第一个元素，kn-1称为最后一个元素，ki（0≤i≤n-2）是ki+1的前驱，ki+1是ki的后继。2.1.2抽象数据类型假设用List表示一个线性表类型，用DataType来表示其元素的类型，元素的下标用positio

4、n类型的量表示，则可以说明如下:Listlist;DataTypex;positionp;线性表的抽象数据类型ADTListisoperationsListcreateNullList(void)创建并且返回一个空线性表。intinsertPre(Listlist,positionp,DataTypex)在list中p位置前插入值为x的元素，并返回插入成功与否的标志。intinsertPost(Listlist,positionp,DataTypex)在list中p位置后插入值为x的元素，并返回插入成功与否的标志。i

5、ntdeleteV(Listlist,DataTypex)在list中删除一个值为x的元素，并返回插入成功与否的标志。intdeleteP(Listlist,positionp)在list中删除位置为p的元素，并返回插入成功与否的标志。Positionlocate(Listlist,DataTypex)在list中查找值为x的元素的位置。intisNull(Listlist)判别list是否为空线性表。endADTList2.2顺序表示线性表最简单的存储方法是采用顺序方式，称作线性表的顺序表示，通常可称此时的线性表为顺序

6、表具体做法是：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。线性表的顺序存储结构是一种可以随机存取的存储结构。2.2.1存储结构假设每个元素占用c个存储单元，则下标为i+1的元素的存储位置与下标为i的元素的存储位置之间，满足下列关系：loc(ki+1)=loc(ki)+c通常把顺序表中k0的存储位置loc(k0)，称为线性表的首地址或基地址，下标为i的元素ki的存储位置为：loc(ki)=loc(k0)+i*cC语言的描述structSeqList{intMAXNUM；/*顺序表中最大元素的个数*/intn;/

7、*存放线性表中元素的个n≤MAXNUM*/DataType*element;/*element[0],element[1]，…，element[n-1]存放线性表中的元素*/}；typedefstructSeqList*PSeqList;线性表的顺序表示：类型和界面定义。如果palist是一个指向SeqList类型的指针变量，则：palist->MAXNUM：顺序表中最大元素的个数；palist->n：顺序表中实际元素的个数；palist->element[0]，…，palist->element[palist->n-1

8、]：顺序表中的各个元素。2.2.2运算的实现1.创建一个空顺序表PSeqListcreateNullList_seq(intm)首先需要调用函数malloc(sizeof(structSeqList))，得到一个structSeqList的空间，然后再按参数m的大小调用malloc(sizeof(DataType)*m)，得到为顺序表分配的一个由参数m指定大小的数组空间，并将顺序表的MAXNUM字段置为m，n字段置为0。程序实现2.判断线性表是否为空intisNullList_seq(PSeqListpalist)判断p

9、alist的n字段是否为0即可程序实现3.在顺序表中求某元素的下标intlocate_seq(PSeqListpalist,DataTypex)将顺序表中的元素依次与x进行比较，若某次比较相等，则返回此元素的下标，运算结束；否则继续比较，直到所有的元素都与x比较过，这时说明顺序表中不存在值为ｘ的元素，返回一个特殊的值