数据结构与算法课件第4章

数据结构与算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陈星

第4章线性表、栈和队列数据结构：相互有关联的数据元素的集合。反映

数据的值和数据的位置逻辑结构：反映数据元素之间逻辑关系。存储结构(物理结构)：数据的逻辑结构在计算机存储空间的存放形式。4.1线性表由称为元素(element)的数据项组成的一种有限且有序的序列。记为：<a0,a1,…,an-1>

术语：空表、长度、表头、表尾、有序线性表、无序线性表线性和非线性:线性linear，指量与量之间按比例、成直线的关系，在数学上可以理解为一阶导数为常数的函数；非线性non-linear则指不按比例、不成直线的关系，一阶导数不为常数。线性结构是一个数据元素的有序集合,它有四个基本特征：集合中必存在唯一的一个"第一个元素"；集合中必存在唯一的一个"最后的元素"；除最后元素之外，其它数据元素均有唯一的"后继"；除第一元素之外，其它数据元素均有唯一的"前驱"。

线性表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为元素在线性表中的序号。思考:顺序表中插入和删除一个元素的过程和时间代价?顺序表的插入操作时间代价Θ(n)//在当前位置（栅栏右边第1个元素处）插入一个新元素template<classElem>boolAList<Elem>::insert(constElem&item){if(listSize==maxSize)returnfalse;//存储空间已满//从线性表尾到插入处，每个元素向右移动一个存储单元for(inti=listSize;i>fence;i--)listArray[i]=listArray[i-1];listArray[fence]=item;//插入新元素listSize++;//Incrementlistsizereturntrue;}讨论：在实际应用中，顺序表有何优点和缺点，适宜用于何种情况，不适宜用于何种情况？优点缺点结构简单2.运算方便3.存储空间利用效率高插入和删除需移动大量数据元素，时间代价大。容量不易扩充。存储空间分配困难：（1）静态分配：存储空间利用效率低。（2）动态分配：每次重新分配需移动大量数据元素。结论：只适合小线性表、长度和数据元素不变化的线性表。算法编程课堂练习

对一个长度为n顺序表（用一维数组V表示顺序表的存储空间），要求将元素x和它后一个单元的元素交换，可用的中间变量为T。

写出相应的算法程序。ProcedureEXCHANE(V,n,x)IF(n<2)thenreturnfalse;//无法完成交换操作，返回i=1Dowhile(V(i)≠xandi<n)//搜索线性表元素x i=i+1enddoIf(i>=n)thenreturnfalse;//无法完成交换操作，返回T=V(i)//交换x和其后单元的元素V(i)=V(i+1)V(i+1)=TReturn第3章3.11题答案3.11(a)

(b)

因此

得

4.1.2链表

每一个数据结点对应一个存储单元，占据一小块存储空间，称为存储结点，简称结点。每个存储结点由两部分组成：1)数据域（element域）：存放数据元素值。2）指针域（next域）：存放指针（数据元素在线性表中的逻辑位置）。通常指向该结点的下一个结点。

特点：（1）物理上无序：存储空间可以不连续，各数据点的存储顺序与数据元素间的逻辑关系可以不一致。（2）逻辑上有序：指针域确定数据元素之间的逻辑关系。（3）用头指针HEAD指向第一个数据元素，用最后一个结点的指针域为空（0或NULL）表示线性链表的结束。

链表的实现示例单元地址Element域Next域12382201317441195121063097142810592271015011120Head链表的插入三个重要指针：head、tail、fence变量leftcnt和rightcnt分别保存左右两部分的长度。//在栅栏位置处插入一个新元素template<classElem>boolLList<Elem>::insert(constElem&item){fence->next=newLink<Elem>(item,fence->next);if(tail==fence)tail=fence->next;rightcnt++;returntrue;}问题：当链表为空，没有元素可供head，tail和fence来指向，当链表左边部分为空时，fence不能指向任何元素。解决方法：增加表头结点。算法编程练习

一个链表长度为n，头指针为head，用两个同样大小的一维数组V(1:m)和Next(1:m)分别保存该链表各结点的数据域值和指针域值。请编程实现:在链表中元素值为x的结点之前插入一个新元素。新元素值为b，数组下标为p。

提示：不但要考虑一般情况下操作，还要考虑特殊情况下的操作。ProcedureInsert(V,next,x,b,p) V(p)=b//如果链表为空if(head==NULL)return;//在第一个结点前插入

if(V(head)==x){next(p)=head;head=p;return}//寻找值为x结点的前一个结点,该结点地址保存在q中

q=head

while((next(q)!=NULL)&&(((V(next(q))!=x))q=next(q)if(next(q)==NULL)returnfalse;//没有找到x//将结点p插入到结点q之后next(p)=next(q);next(q)=pReturn算法编程练习

一个链表长度为n，头指针为head，用两个同样大小的一维数组V(1:m)和Next(1:m)分别保存该链表各结点的数据域值和指针域值。请编程实现:在链表中元素值为x的结点之后插入一个新元素。新元素值为b，数组下标为p。ProcedureInsert(V,next,x,b,p) V(p)=b//如果链表为空if(head==NULL)return;//寻找值为x结点,该结点地址保存在q中

q=head;

while((next(q)!=NULL)&&(((V(q)!=x))q=next(q);if((next(q)==NULL)&&(V(q)!=x))returnfalse;//没有找到xif((next(q)==NULL)&&(V(q)==x))//x在链表尾next(q)=p,next(p)=NULL;//将结点p插入到结点q之后next(p)=next(q);next(q)=pReturn链表的删除操作可利用空间表链表插入和删除操作取得空结点和回收删除的结点对存储空间合理的存储分配和回收机制语言编译器的效率不高可利用空间表(freelist)插入一个新结点到链表前,首先从可利用空间表中取走一个结点。删除一个链表上的结点后，要将删除的结点放到可利用空间表的首端。4.1.4元素的表示

1.顺序表和链表中的元素是存储数据元素的一份拷贝(副本)还是存储指向数据元素的指针?

建议:数据元素大而且重复多,存储数据元素指针.2.是否要求线性表中元素类型相同?

根据应用选择元素类型是固定还是不同.3.当线性表被删除或调用Clear函数(回收)时,如何处理表中对象占用的内存?

注意:如果表中元素是对象的指针,就可能删除指向对象的指针,从而使对象占用的内存变成不可访问的(悬挂引用).?4.1.5双链表单链表只允许从一个结点访问它的后继结点特点（与单链表比）：优点：可从任何一个结点出发，访问其它所有结点。缺点：占用更多空间。双链表:每个结点有两个指针域，左指针指向其前件结点；右指针指向其后件结点。双链表的插入操作

双链表的删除操作

编程练习

一个双链表长度为n，头指针为head，用三个同样大小的一维数组V(1:m)、LNext(1:m)和RNext(1:m)分别保存该链表各结点的数据域值和左、右指针域值。请用C语言编程实现:

1.在链表中元素值为x的结点之后插入一个新元素。新元素值为b，数组下标为p。

2.删除链中元素值为x的结点。注：假设此双链表中值为x的结点最多只有一个。4.2字典ADT

描述用于一个简单数据库的接口，称为字典。字典将定义为一个ADT，它提供在数据库存储、查找和删除记录的功能。常用操作：记录检索(find)：通过比较关键码，返回匹配的记录。插入记录(insert)：插入新记录。删除记录(remove)：删除指定关键码的记录。删除任意记录(removeAny)：删除任意一条（如最后一条）记录。可实现字典的数据结构：

4.3栈

栈：一种特殊的线性表。其插入与删除只在一端进行。符合“先进后出，后进先出”的原则，允许插入和删除的一端称为栈顶，不允许插入和删除的一端称为栈底。通常用栈项指针top来指向栈项，用栈底指针bottom来指向栈底。元素的插入称为压入或入栈，元素的删除称为弹出或退栈。

4.3.1顺序栈程序设计中，用一维数组作为栈的顺序存储空间。为使用方便，通常栈顶指针指向栈空间的高地址一端。栈顶指针指向栈中第一个空闲位置。栈的基本运算：1、入栈运算2、退栈运算3、读栈项元素。4.3.2链式栈采用链式存储结构的栈。通常用来收集计算机存储空间中所有空闲的存储结点，即可利用空间表。4.3.3顺序栈与链式栈的比较1.基本操作时间代价的比较基本操作时间代价入栈运算退栈运算读栈项元素顺序栈链式栈2.存储空间利用的比较讨论！4.3.4递归的实现栈的最广泛应用：子程序调用时将有关子程序的必要信息压入到一个栈中子程序调用结束后，再将信息从栈中弹出。采用栈，递归调用（不是全部）可以用迭代来代替。4.4队列队列：符合“先进先出，后进后出”的原则，在一端进行插入，在另一端进行删除的线性表。如消息映射队列。例：排队，自动流水线上装配部件。计算机操作系统利用队列管理多个用户程序：消息队列。允许插入的一端称为队尾，用尾指针（rear）指向；允许删除的一端称为队首，用头指针(front)指向。队尾插入元素称为入队操作，队首删除元素称为出队操作。4.4.1顺序队列顺序队列实现上的困难：1.要求队列中n个元素都存储在数组的前n个单元中。（1）0号单元存储队尾元素。删除元素的时间代价：Θ（1）插入新元素的时间代价：Θ（n）（1）0号单元存储队首元素。插入新元素的时间代价：Θ（1）删除元素的时间代价：Θ（n）2.不要求队列中n个元素都必须存储在数组的前n个单元中。删除元素的时间代价：Θ（1）插入新元素的时间代价：Θ（1）但如果队列不断地插入和删除元素后，整个队列向数组中编号较高的位置移动。解决方法：循环队列思考：一维数组中如何实现循环队列。？循环队列中如何区分队列空和队列满例1：队列中只有一个元素，位于单元m。front=m，rear＝m。删除该元素，front=front+1=m+1=rear+1队列空时，rear比front小1。例2：循环队列如右示，只有一个空闲单元m。此时：front=m+1,rear=m-1若插入一个新元素，则rear=rear+1=m即队列满时，rear比front小1。解决办法：1、设置标志区别队列空或满。2、以尾指针追上头指针作为队列满的条件。3、记录元素的数量。4.4.2链式队列4.4.3顺序队列和链式队列的比较表达式计算21+3*52/(4+18)-3^2/4=?要求：从左到右只需一次扫描表达式。自动区分运算符和运算数。自动根据运算符的优先级确定计算顺序。

表达式计算21+3*52/(4+18)-3^2/4;运算符和优先级：低＋－

×/高^特殊：()

？如何判断山峰利用栈实现表达式计算21+3*52/(4+18)-3^2/4;规则：在表达式最后加一个结束符；将结束符;看作最低优先级。设置两个栈：运算符栈，暂存表达式处理过程中的运算符。运算数栈，暂存表达式处理过程中的运算数。首先将结束符;直接压入运算符栈