数据结构教程 第2章 线性表ppt课件.ppt

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

1、第二章线性表线性表顺序表单链表线性链表的其他变形单链表的应用：多项式及其运算（不做要求）静态链表本章的基本内容是：线性表：简称表，是n（n≥0）个具有相同类型的数据元素的有限序列。线性表的长度：线性表中数据元素的个数。空表：长度等于零的线性表，记为：L=()。非空表记为：L＝（a1,a2,…,ai-1,ai,…,an)2.1线性表2.1.1线性表的概念其中，ai（1≤i≤n）称为数据元素，称为结点或表项；下角标i表示该元素在线性表中的位置或序号。a1a3a4ana2线性表的图形表示线性表（a1,a2,…,ai-1,ai,…,an)的图形表示如下：2.1线性表a1a3a4ana2线性表的特性1.

2、有限性：线性表中数据元素的个数是有穷的。2.相同性：线性表中数据元素的类型是同一的。3.顺序性：线性表中相邻的数据元素ai-1和ai之间存在序偶关系(ai-1,ai)，即ai-1是ai的前驱，ai是ai-1的后继；a1无前驱，an无后继，其它每个元素有且仅有一个前驱和一个后继。2.1线性表线性表的抽象数据类型定义（见P44）ADTLinearListisObjects:n个原子表项的一个有限序列。数据类型为T。Function:creat()intlength()intsearch(T&x)intLocate(inti)T*getData(inti)voidsetData(inti,T&x)b

3、oolInsert(inti,T&x)boolRemove(inti,T&x)boolIsEmpty()boolIsFull()voidCopyList(LinearList&L)voidsort()endLinearList2.1线性表进一步说明:（1）线性表的基本操作根据实际应用而定；（2）复杂的操作可以通过基本操作的组合来实现；templateClassLinearLIst{Public:LinearList();~LinearList();virtualintSize()const=0;virtualintLength()const=0;virtualintSea

4、rch(T&x)const=0;virtualintLocate(inti)const=0;virtualT*getData(inti)const=0;virtualvoidsetData(inti,T&x)const=0;virtualboolInsert(inti,T&x)const=0;virtualboolRemove(inti,T&x)const=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualvoidsort()const=0;virtualboolinput()const=0;virtualboolo

5、utput()const=0;virtualboolLinearListoperator=(LinearList&L)const=0;}2.1.2线性表类定义2.1线性表2.2顺序表2.2.1顺序表的定义和特点例：（34,23,67,43）342367434存储要点用一段地址连续的存储单元依次存储线性表中的数据元素定义：把线性表中的所有表项按照其逻辑顺序依次存储到从计算机存储中指定存储位置开始的一块连续的存储空间中。特点：（1）在顺序表中，各个表项的逻辑顺序与其存放的物理顺序一致。（2）对顺序表中所有表项，既可以进行顺序访问，也可以进行随机访问。2.2顺序表2.2.1顺序表的定义和

6、特点例：（34,23,67,43）34236743存储空间的起始位置4用什么属性来描述顺序表？顺序表的容量（最大长度）顺序表的当前长度2.2顺序表2.2.1顺序表的定义和特点例：（34,23,67,43）342367434如何实现顺序表的内存分配？顺序表一维数组2.2顺序表2.2.1顺序表的定义和特点如何求得任意元素的存储地址？0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)2.2顺序表2.2.1顺序表的定义和特点0…i-2i-1…n-1Max-1a1…ai-1ai…an空闲长度

7、Loc(ai)=Loc(a1)+(i-1)×c随机存取：在O(1)时间内存取数据元素一般情况下，(a1，a2，…,ai-1，ai,…,an)的顺序存储：cLoc(ai)Loc(a1)2.2顺序表2.2.1顺序表的定义和特点顺序表类的声明（见P46）constintMaxSize=100;template//模板类classSeqList:publicLinearList{pr