DS02-线性表.ppt

《DS02-线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第2章线性表线性表的顺序存储线性表的链式存储线性表两种不同存储结构的比较线性表的应用具体介绍一种数据结构时，总是从下述三个方面展开：逻辑结构：是从逻辑关系上描述数据，可看作上从具体问题中抽象出来的数据模型，与计算机存储无关。存储结构：是逻辑结构在存储器中的实现（数据及其关系运算的映像）。数据操作：是定义在数据逻辑结构上的一组运算。每种数据结构都有一个运算集合。书中给出的数据类型的描述，实际上是一种数据结构在某一存储结构下的实现。2.1线性表的基本概念线性结构的基本特征是：①有而且只有一个“第一元素”；②有而且只有一个

2、“最后元素”；③除第一元素之外，其他元素都有唯一的直接前趋；④除最后元素之外，其他元素都有唯一的直接后继。线性表是一种常用的简单的数据结构，它属于线性结构的范畴。线性表（LinearList）是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中，数据元素的个数n称为线性表的长度。当n＝0时称为空表。字母表（A,B,C,…,Z）的表长是26，起始结点是A，没有直接前趋，A的唯一的直接后继是B；终端结点Z没有直接后继，Z的唯一的直接前趋是Y；而对于B,C,

3、D,…,Y中的任意一个字母，都有一个唯一的直接前趋和一个唯一的直接后继。例2.326个大写英文字母表线性表的基本操作initList(L)：初始化操作，置L为空线性表。ClearList(L)：清除线性表的内容，将L置为空线性表ListLength(L)：求表长(表中元素个数)ins(L，i，Item)：插入数据Del(L，i)：删除数据GetNext(L，Item，p):获取下一个结点线性表的基本操作GetNode(L，i)：获取表L中位置i的结点值Loc(L，Item)：定位(按值查找)GetPrior(L，It

4、em，p)：获取值为Item的结点的前趋结点这是一个算法，在此是用C语言编写的一个函数…………2.2线性表的顺序存储线性表的顺序存储方式，就是利用一段连续的内存地址来存储线性表的数据元素。在C语言中，用一个数组来实现。线性表的这种机内表示称作线性表的顺序存储结构或顺序映象。同时，我们把这种顺序存储结构的线性表称为顺序表。对线性表A(a1，a2，…ai-1，ai，ai+1，…an)a1a2…ai-1aiai+1…antypedefstruct{charname[20];/*姓名*/charno[10];/*学号*/fl

5、oatscore;/*成绩*/}STUDENT；STUDENTs[20];则s就是一个以STUDENT类型为数据元素的线性表。例2.4一个顺序存储结构的线性表的例子线性表L中，若每个元素占用m个存储单元，则第i+1个数据元素的存储位置LOC(i+1)和第i个数据元素的存储位置LOC(i)之间满足如下关系：LOC(i+1)=LOC(i)+m线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为：LOC(i)=LOC(1)+(i-1)*m其中LOC(1)是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或

6、基地址。顺序表的基本操作顺序表的C语言描述typedefintdatatype;/*定义表元素类型*/#definemaxsize1024;/*线性表的最大长度*/typedefstruct{datatypeelem[maxsize];/*存放表结点的数组*/intlength;/*表长*/}sequenli顺序表的基本操作顺序表的初始化算法2.1构造一个空的顺序表voidInitList(sequenlist*L){L->length=0;}删除一个线性表要删除一个已经存在的线性表，只需要把该线性表设置为空表，也就

7、是把表长置为0。算法2.2删除一个线性表voidDestroyList(sequenlist*L){L->length=0;}本算法时间复杂度为O（1）。顺序表的基本操作定位(按值查找)：要查找一个值，只需要从头到尾的遍历线性表，如果找到，则返回找到的位置，否则继续，如果一直到最后一个位置都没有找到，则返回-1。本算法中，n是线性表的长度；可能找到值为Item的元素，也可能找不到Item，这时候，算法的比较次数为O(n)。因此，总结起来，本算法的时间复杂度为O(n)。顺序表的基本操作intLoc(sequenlist

8、L，datatypeitem){inti,j;j=L.length;/*表的长度*/if(j==0)returnFALSE;for(i=1;i<=j;i++){if(L.elem[i]==item)returni;}printf(“找不到该值！”);return0;}算法2.3定位（按值Item查找）插入数据要在线性表中第i个位置插入一个数据元