数据结构第四章链栈和链队列.

合肥工业大学计算机与信息学院1算法与数据结构（第四章链栈和链队列）合肥工业大学计算机与信息学院2第四章链栈和链队列第四章链栈和链队列4.1引言4.2链栈4.3链队列合肥工业大学计算机与信息学院3第四章链栈和链队列4.1引言前面已介绍的顺序栈、顺序队列的有关特性回顾与分析：运算实现：算法实现简单。存储特性：静态规模，编译前确定。问题：程序的通用性和空间利用率之间的矛盾！期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，这就涉及到动态变量。动态变量：在程序运行过程中产生和释放的变量。与之相反的是静态变量，静态变量：在程序运行过程中一直存在的变量。在一般程序设计语言（如C、C++）中，静态变量是出现在说明语句中的变量，而动态变量则由于是在运行过程中产生，因而不会事先说明。如何实现动态变量？通过指针来实现：指针变量的说明，动态变量产生和释放。合肥工业大学计算机与信息学院44.1引言下面依次介绍指针变量动态变量的说明，动态变量操作、产生和释放。（1）指针变量说明例：变量说明语句intm,n,*p，*q;说明了4个变量，其中：m和n说明为int型，p,q为指向int型变量的指针，其所指示的变量名称分别为*p，*q。（动态变量）指针和其所指示的变量之间的关系如下图所示。1020p*pq*q指针和目标变量的关系：所谓指针指向一个变量，就是存放着目标变量的地址的值。合肥工业大学计算机与信息学院54.1引言（2）动态变量的操作基本操作：和其他类型的变量类似，可以对动态变量赋值、引用。特别要注意区分：指针赋值和动态变量赋值操作的关系和效果。例如语句*p=*q;和p=q;的效果存在明显的差异：假设初始时*p=10；*q=20；如图所示。1020p*pq*q*p=*q的效果201020p*pq*qp=q的效果区别：一个是整型变量的赋值，一个是指针型变量的赋值。*p合肥工业大学计算机与信息学院64.1引言（3）动态变量产生动态变量需要在执行申请变量操作后才能产生，否则无效。申请变量的操作如下：（对前面给出的变量说明）p=newint;------产生一个int类型变量，并将该变量的地址放到指针变量p中。（4）动态变量的释放释放变量：将动态变量的存储空间还给系统，以便重新分配使用。释放变量的操作：deletep;-----释放指针p所指示的变量（即*p）的存储空间（因而使*p无效，除非重新赋值或申请）合肥工业大学计算机与信息学院74.1引言例：阅读下面程序，写出运行结果。voidmain(){int*p,*q;p=newint;q=newint;*p=10;*q=20;cout*p*qendl;*p=*q;*p=30;*q=40;cout*p*qendl;p=q;*p=40;*q=50;cout*p*qendl;deletep;}输出结果是？合肥工业大学计算机与信息学院84.2链栈4.2.1链表链表：将表中元素用链地址连接起来构成的表。例如，下图就是一个链表的示意图，其中：由若干称为结点的“单元”连接而成。每个结点由两部分组成：存放元素值的字段存放下一个结点的地址的字段。另外，有一个指向表头的指针（头指针）head，指示起点。最后一个结点（也称为尾结点）的后继指针为空值，表示其后续没有结点了。结点尾结点a1a2a3an……∧head头指针合肥工业大学计算机与信息学院94.2链栈链表存储结构的实现如何实现链表的存储结构？对此，可有两类方法，其一是用数组来实现，其二是用动态链表。1.用数组来存储表中元素------静态链表就是用数组元素存储表中元素的值，以及后续元素的地址。（因而需要说明为构造类型）例如，右图是一个存储了部分英语字母的链表。这类表由于数组的规模事先确定，因而称为静态链表。静态链表的不足：难以兼顾到通用性和存储空间的利用率。E6D0A3B4C1G-1F50123456下标datanexthead=2∧合肥工业大学计算机与信息学院104.2链栈2.采用动态变量来实现——动态链表其中每个结点用一个结构来描述，包括两个字段，存放元素值的字段data存放下一个结点的指针如右图所示。设结点类型为node，则类型描述如下：typedefstructLinkNode{elementtypedata;//元素字段structLinkNode*next;//指针字段}node;不特别说明的情况下，链栈就是采用动态链表来存储。datanextnode类型合肥工业大学计算机与信息学院114.2链栈4.2.2链栈结构及描述可以用链表来存储栈：表头存储栈顶元素;设一个栈顶指针。如图所示。结构的描述：数据成员：除了计数分量count外，还需要给出栈顶指针top.函数成员：原有的函数full（）可以不用（为什么？）。由于链表采用的是动态结构，即使在栈变量的作用域外，动态变量也不会自行释放。因此，需要设一个析构函数，以便在栈变量无效时自行释放链表的存储空间。antopa1a2a3∧……合肥工业大学计算机与信息学院124.2链栈由此得类stack的描述如下：classstack{public://函数成员stack();~stack();boolempty()const;boolfull()const;error_codeget_top(elementtype&x)const;error_codepush(constelementtypex);error_codepop();private://数据成员intcount;node*top;//栈顶指针};新增的析构函数原有的函数合肥工业大学计算机与信息学院134.2链栈4.2.3链栈运算的实现初始化运算的实现：stack::stack（）{count=0;top=NULL;}判断空的实现：boolstack::empty(){returncount==0;}//等价于：returntop==NULL;判断满的实现：boolstack::full(){returnfalse;}//本函数无实际意义合肥工业大学计算机与信息学院144.2链栈取栈顶元素的实现：error_codestack::get_top(elementtype&x)const{if(empty())returnunderflow;x=top-data;returnsuccess;}析构函数的实现：主要任务是释放链表中各结点的存储空间，有两种方法，一种方法是：直接释放各结点的存储空间。另一种方法是：调用后面要描述的出栈算法：逐个将元素出栈，直到为空为止。（下面采用这种方法来实现）stack::~stack(){while(!empty())pop();}合肥工业大学计算机与信息学院154.2链栈入栈运算的实现入栈就是将待插入元素装入一个结点后，连接到链表的表头上。因此，操作包括：产生结点；装入元素的值到结点中；连接结点到表头----注意连接操作的顺序。修改其他信息。操作过程如下图所示。算法如下：error_codestack::push(constelementtypex){s=newnode;s-data=x;//产生结点；装入元素的值到结点中；s-next=top;top=s;//连接结点到表头count++;//计数returnsuccess;//返回成功操作标志}a1a2a3an∧……xstop①②③合肥工业大学计算机与信息学院164.2链栈出栈运算的实现出栈操作就是删除表头结点，并释放其元素空间。另外要修改相关的信息。注意删除操作的次序。error_codestack::pop(){if(empty())returnunderflow;u=top;top=top-next;deleteu;count--;returnsuccess;}a1a2a3an^……top③释放该结点u①②合肥工业大学计算机与信息学院4.2链栈例：设计算法将单链表L就地逆置。求解思路：依次将原来链栈中的结点分离，并插入到初值为空的另一个链栈中。voidstack::reverse(){node*p=NULL;node*u;node*L=top;while(L!=NULL){u=L;L=L-next;//结点分离u-next=p;p=u;//入栈}top=p;//原表头指针指示新表的表头}17合肥工业大学计算机与信息学院184.3链队列4.3.1链队列存储结构将队头指针标记为front，队尾指针记为rear.另外，为了使入队操作在队列为空和不空时的操作保持一致，特别设置一个不存放元素值的附加结点（称为头结点）。a1a2a3an^……rear/////frontfront合肥工业大学计算机与信息学院194.3链队列由上述讨论可得到链队列类queue的描述如下：其中：数据成员部分除了计数变量count外，增设了头尾指针。函数成员中增设了析构函数。另外，判断满的函数可以不用。classqueue{public://函数成员queue();~queue();boolempty()const;boolfull()const;error_codeget_front(elmenttype&x)const;error_codeappend(constelementtypex);error_codeserve();private://数据成员intcount;node*front,*rear;};新增的析构函数原有的函数合肥工业大学计算机与信息学院204.3链队列4.3.2链队列的运算实现如前所述，链队列的结构为带头结点的链表，如下图所示。运算实现：初始化的实现：分析：首先要清楚，空队列的结构形式：元素个数为0，但要有头结点----事先没有，需要产生出来。如图所示。算法如下。queue::queue（）{front=newnode;//产生由头指针front指示的头结点rear=front;//尾指针也指向头结点front-next=NULL;//头结点（此时也是尾结点）后继指针设置为空count=0;}^frontrearfronta1a2an^a3……rear合肥工业大学计算机与信息学院214.3链队列判断空的运算的实现boolstack::empty(){returncount=0;};//等价于returnfront==rear;或returnfront-next=NULL；判断满的运算的实现boolstack::full(){returnFALSE;}//本函数无实际意义取队头元素运算的实现error_codequeue::get_front(elementtype&x)const{if(empty())returnunderflow;x=front-next-data;returnsuccess;}合肥工业大学计算机与信息学院224.3链队列入队运算的实现分析：对链队列的入队操作应当包括如下操作：产生结点，装入待插入元素；将新结点连接到表尾；调整尾指针；计数。如下图所示。算法如下：error_codequeue::append(constelementtypex){s=newnode;s-data=x;s-next=NULL;rear-next=s;rear=s;count++;returnsuccess;}fronta1a2an^a3……rears①②x③^④⑤合肥工业大学计算机与信息学院234.3链队列出队运算的实现分析：在队列不空的情况下，出队运算就是删除表头结点，即删除由指针？所指向的结点。（同时要释放该结点）另外要注意的一个极端情况的处理：删除的是最后的一个结点。error_codequeue::serve(){if(empty())returnunderflow;u=front-next;;front-next=u-next;deleteu;count--;if(front-next==NULL)