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

《数据结构与算法分析第4章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第4章线性表、栈和队列数据结构：相互有关联的数据元素的集合。反映数据的值和数据的位置逻辑结构：反映数据元素之间逻辑关系。存储结构(物理结构)：数据的逻辑结构在计算机存储空间的存放形式。4.1线性表由称为元素(element)的数据项组成的一种有限且有序的序列。记为：术语：空表、长度、表头、表尾、有序线性表、无序线性表线性表ADT抽

2、象数据类型是指数据结构作为一个软件组件的实现。通过ADT掌握数据结构的实现和操作。线性表ADT设计的思想：当前位置。一个栅栏和两个分离部分。如：<20,23

3、12,15>注：当前位置的元素（当前元素）为栅栏右边的第1个元素，或右边部分的第1个元素。线性表的C++抽象类声明templateclassList{public:virtualvoidclear()=0;//回收元素的存储空间virtualboolinsert(constElem&)=0;//当前位置插入新元素vir

4、tualboolappend(constElem&)=0;//表尾插入新元素virtualboolremove(Elem&)=0;//删除当前元素virtualvoidsetStart()=0;//将栅栏置于表头前virtualvoidsetEnd()=0;//将栅栏置于表尾后virtualvoidprev()=0;//将栅栏向前（左）移动一个元素virtualvoidnext()=0;//将栅栏向后（右）移动一个元素virtualintleftLength()const=0;//返回左边部分的

5、元素个数virtualintrightLength()const=0;//返回左边部分的元素个数virtualboolsetPos(intpos)=0;//返回栅栏在表中的位置virtualboolgetValue(Elem&)const=0;//返回当前元素的值virtualvoidprint()const=0;//输出线性表中元素序列｝；线性表的ADT举例1.线性表:<12

6、32,15>MyList.insert(99);结果:<12

7、99,32,15>2.线性表循环获得每个元素的值:for

8、(MyList.setStart();MyList.getValue(it);MyList.next())DoSomething(it);3.在线性表中查找元素值k，找到返回True，未找到返回False。boolfind(List&L,intK){intit;for(L.setStart();L.getValue(it);L.next())if(K==it)returntrue;//Founditreturnfalse;//Notfound}4.1.1顺序表的实现线性表的两种实现方法

9、–顺序表(又称顺序存储结构的线性，array-basedlist,sequentiallist)和链表(又称链式存储结构的线性表，Linkedlist)顺序存储结构（向量式的存储结构，顺序分配）的基本特点：(1)线性表中所有元素所占的存储空间是连续的。(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放。逻辑上相邻的两个元素在存储空间中是相邻的。利用元素存储的位置关系反映元素之间的逻辑关系。通常用一个一维数组来表示线性表的顺序存储空间。可以通过简单计算得到任意元素的存储地址：ADR(ai)=

10、ADR(a1)+(i-1)*k其中，k为每一个元素占的字节数，i为元素在线性表中的序号。？setPos函数和getValue函数的执行时间代价是？顺序表的插入操作时间代价Θ(n)//在当前位置（栅栏右边第1个元素处）插入一个新元素templateboolAList::insert(constElem&item){if(listSize==maxSize)returnfalse;//存储空间已满//从线性表尾到插入处，每个元素向右移动一个存储单元for(inti=

11、listSize;i>fence;i--)listArray[i]=listArray[i-1];listArray[fence]=item;//插入新元素listSize++;//Incrementlistsizereturntrue;}讨论：在实际应用中，顺序表有何优点和缺点，适宜用于何种情况，不适宜用于何种情况？优点缺点结构简单2.运算方便插入和删除需移动大量数据元素，时间代价大。容量不易扩充。存储空间分配困难：（1）静态分配：存储空间利用效率低。（2）动态分配：每次重新分配需移动大量数据