数据结构与算法分析第4章 (2).ppt

数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第4章线性表、栈和队列线性表ADT
抽象数据类型是指数据结构作为一个软件组件的实现。
通过ADT掌握数据结构的实现和操作。

线性表ADT设计的思想：
当前位置。
一个栅栏和两个分离部分。
如：<20,23|12,15>
注：当前位置的元素（当前元素）为栅栏右边的第1个元素，或右边部分的第1个元素。线性表的C++抽象类声明
template<classElem>classList{
public:
virtualvoidclear()=0;//回收元素的存储空间
virtualboolinsert(constElem&)=0;//当前位置插入新元素
virtualboolappend(constElem&)=0;//表尾插入新元素
virtualboolremove(Elem&)=0;//删除当前元素
virtualvoidsetStart()=0;//将栅栏置于表头前
virtualvoidsetEnd()=0;//将栅栏置于表尾后
virtualvoidprev()=0;//将栅栏向前（左）移动一个元素
virtualvoidnext()=0;//将栅栏向后（右）移动一个元素
virtualintleftLength()const=0;//返回左边部分的元素个数
virtualintrightLength()const=0;//返回左边部分的元素个数
virtualboolsetPos(intpos)=0;//返回栅栏在表中的位置
virtualboolgetValue(Elem&)const=0;//返回当前元素的值
virtualvoidprint()const=0;//输出线性表中元素序列
｝；线性表的ADT举例
1.线性表:<12|32,15>
MyList.insert(99);
结果:<12|99,32,15>
2.线性表循环获得每个元素的值:
for(MyList.setStart();MyList.getValue(it);MyList.next())
DoSomething(it);
3.在线性表中查找元素值k，找到返回True，未找到返回False。
boolfind(List<int>&L,intK){
intit;
for(L.setStart();L.getValue(it);L.next())
if(K==it)returntrue;//Foundit
returnfalse;//Notfound
}4.1.1顺序表的实现
线性表的两种实现方法–顺序表(又称顺序存储结构的线性，array-
basedlist,sequentiallist)和链表(又称链式存储结构的线性表，Linkedlist)
顺序存储结构（向量式的存储结构，顺序分配）的基本特点：
(1)线性表中所有元素所占的存储空间是连续的。
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放。
逻辑上相邻的两个元素在存储空间中是相邻的。利用元素存储的位置关系反映元素之间的逻辑关系。
通常用一个一维数组来表示线性表的顺序存储空间。
可以通过简单计算得到任意元素的存储地址：
ADR(ai)=ADR(a1)+(i-1)*k
其中，k为每一个元素占的字节数，i为元素在线性表中的序号。
？setPos函数和getValue函数的执行时间代价是？顺序表的插入操作优点算法编程课堂练习ProcedureEXCHANE(V,n,x)
IF(n<2)thenreturnfalse;//无法完成交换操作，返回
i=1
Dowhile(V(i)≠xandi<n)//搜索线性表元素x
i=i+1
enddo
If(i>=n)thenreturnfalse;//无法完成交换操作，返回
T=V(i)//交换x和其后单元的元素
V(i)=V(i+1)
V(i+1)=T
Return
4.1.2链表

每一个数据结点对应一个存储单元，占据一小块存储空间，称为存储结点，简称结点。
每个存储结点由两部分组成：1)数据域（element域）：存放数据元素值。2）指针域（next域）：存放指针（数据元素在线性表中的逻辑位置）。通常指向该结点的下一个结点。
特点：（1）物理上无序：存储空间可以不连续，各数据点的存储顺序与数据元素间的逻辑关系可以不一致。
（2）逻辑上有序：指针域确定数据元素之间的逻辑关系。
（3）用头指针HEAD指向第一个数据元素，用最后一个结点的指针域为空（0或NULL）表示线性链表的结束。
链表的实现示例单元地址链表的插入//在栅栏位置处插入一个新元素
template<classElem>
boolLLis