数据结构DS02-线性表

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

1、第2章线性表线性表的顺序存储线性表的链式存储线性表两种不同存储结构的比较线性表的应用2.1线性表的基本概念线性结构的基本特征是：①有而且只有一个“第一元素”；②有而且只有一个“最后元素”；③除第一元素之外，其他元素都有唯一的直接前趋；④除最后元素之外，其他元素都有唯一的直接后继。线性表是一种常用的简单的数据结构，它属于线性结构的范畴。线性表（LinearList）是具有相同数据类型的n(n≥0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中，数据元素的个数n称为线

2、性表的长度。当n＝0时称为空表。例2.326个大写英文字母表（A,B,C,…,Z）的表长是26，起始结点A没有直接前趋，A的唯一的直接后继是B；终端结点Z没有直接后继，Z的唯一的直接前趋是Y；而对于B,C,D,…,Y中的任意一个字母，都有一个唯一的直接前趋和一个唯一的直接后继。线性表的基本操作initList(L)：初始化操作，构造一个空线性表LClearList(L)：清除线性表L的内容，将L置为空表ListLength(L)：求表长(表中元素个数)ins(L，i，Item)：插入数据Del(L，i)

3、：删除数据线性表的基本操作（续）GetNode(L，i)：获取表L中位置i的结点值Loc(L，Item)：定位(按值查找)GetPrior(L，Item，p)：获取值为Item的结点的前趋结点GetNext(L，Item，p):获取值为Item的结点的后继结点2.2线性表的顺序存储线性表的顺序存储方式，就是利用一段连续的内存地址来存储线性表的数据元素。在C语言中，是用一个数组来实现的。线性表的这种机内表示称作线性表的顺序存储结构或顺序映象。同时，我们把这种顺序存储结构的线性表称为顺序表。对线性表A(a1

4、，a2，…ai-1，ai，ai+1，…an)a1a2…ai-1aiai+1…an其顺序存储结构可表示如下:例2.4一个顺序存储结构的线性表（顺序表）的例子。typedefstruct{charname[20];/*姓名*/charno[10];/*学号*/floatscore;/*成绩*/}STUDENT；STUDENTs[20];则s就是一个以STUDENT类型为数据元素的线性表。线性表L中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足如下关系：LOC(

5、ai+1)=LOC(ai)+m线性表L的第i个元素的存储位置和第一个元素的存储位置的关系为：LOC(ai)=LOC(a1)+(i-1)*m其中LOC(a1)是线性表的第一个数据元素的存储位置，通常称为线性表的起始位置或基地址。顺序表的基本操作顺序表的C语言描述typedefintdatatype;/*定义表元素类型*/#definemaxsize1024/*线性表的最大长度*/typedefstruct{datatypeelem[maxsize];/*存放表结点的数组*/intlength;/*表长*/

6、}sequenlist;顺序表的基本操作顺序表的初始化算法2.1构造一个空的顺序表voidInitList(sequenlist*L){L->length=0;}顺序表的基本操作清除一个线性表的内容要清除一个已经存在的线性表的内容，只需要把该线性表设置为空表，也就是把表长置为0。算法2.2清除一个线性表的内容voidClearList(sequenlist*L){L->length=0;}本算法时间复杂度为O（1）。顺序表的基本操作定位(按值查找)：要查找一个值，只需要从头到尾的遍历线性表，如果找到，则

7、返回找到的位置，否则继续，如果一直到最后一个位置都没有找到，则返回0。本算法中，可能找到Item，这时候，平均比较次数为O(n/2)，其中，n是线性表的长度；也可能找不到Item，这时候，算法的比较次数为O(n)。因此，总结起来，本算法的时间复杂度为O(n)。算法2.3定位（按值查找）intLoc(sequenlistL，datatypeItem){inti,j;j=L.length;/*表的长度*/if(j==0)returnFALSE;for(i=1;i<=j;i++){if(L.data[i]==

8、Item)returni;}printf(“找不到该值！”);return0;}找到了值为item的结点顺序表的基本操作插入数据要在线性表中第i个位置插入一个数据元素，需要考虑以下因素：i是否在1和L.length之间，如果在，则先将原来最后一个数据元素直到第i个数据元素依次向后移动一个位置，再将Item插到第i个位置，然后线性表长度加上1，返回TRUE；如果不在1和L.length之间，则说明插入位置不合适，返回FALSE。如图2.2所示