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

1、1算法与数据结构算法与数据结构（第四章第四章 链栈和链队列链栈和链队列）2第四章第四章 链栈和链队列链栈和链队列 第四章 链栈和链队列 4.1 引言 4.2 链栈 4.3 链队列 3第四章 链栈和链队列 o 4.1 引言引言 前面已介绍的前面已介绍的顺序栈、顺序队列顺序栈、顺序队列的有关特性回顾与分析：的有关特性回顾与分析： 运算实现运算实现：算法实现简单。：算法实现简单。 存储特性存储特性：静态规模，编译前确定。：静态规模，编译前确定。 问题问题：程序的通用性和空间利用率之间的矛盾！：程序的通用性和空间利用率之间的矛盾！ 期望期望：在实际运行过程中，根据实际问题的需要临时确定存：在实际运行过

2、程中，根据实际问题的需要临时确定存储空间，这就涉及到动态变量。储空间，这就涉及到动态变量。 动态变量动态变量：在程序运行过程中产生和释放的变量。：在程序运行过程中产生和释放的变量。 与之相反的是静态变量，与之相反的是静态变量， 静态变量静态变量：在程序运行过程中一直存在的变量。：在程序运行过程中一直存在的变量。 在一般程序设计语言（如在一般程序设计语言（如C、C+）中，）中， 静态变量是出现在说明语句中的变量，静态变量是出现在说明语句中的变量， 而动态变量则由于是在运行过程中产生，因而不会事先说明。而动态变量则由于是在运行过程中产生，因而不会事先说明。 如何实现动态变量如何实现动态变量？ 通过

3、指针来实现：指针变量的说明，动态变量产生和释放通过指针来实现：指针变量的说明，动态变量产生和释放 。 44.1 引言引言下面依次介绍指针变量动态变量的说明，动态变量操作、下面依次介绍指针变量动态变量的说明，动态变量操作、产生和释放产生和释放 。（1）指针变量说明）指针变量说明 例：变量说明语句例：变量说明语句 int m, n, *p，*q; 说明了说明了4个变量，其中：个变量，其中： m和和n说明为说明为int型，型， p,q为指向为指向int型变量的指针，其所指示的变量名称分别型变量的指针，其所指示的变量名称分别为为*p，*q。（。（动态变量动态变量） 指针和其所指示的变量之间的关系如下图

4、所示。指针和其所指示的变量之间的关系如下图所示。p*pq*q指针和目标变量的关系指针和目标变量的关系：所谓所谓指针指向一个变量指针指向一个变量，就是存，就是存放着目标变量的地址的值放着目标变量的地址的值。54.1 引言引言（2）动态变量的操作）动态变量的操作 基本操作基本操作：和其他类型的变量类似，可以对动态变量赋值、引用。：和其他类型的变量类似，可以对动态变量赋值、引用。 特别要特别要注意区分注意区分：指针赋值和动态变量赋值操作的关系和效果。：指针赋值和动态变量赋值操作的关系和效果。例如例如 语句语句 *p = *q; 和和 p = q; 的效果存在明显的的效果存在明显的差异差异： 假设初始

5、时假设初始时*p=10； *q=20； 如图所示。如图所示。p*pq*q*p = *q的效果效果p*pq*q p = q的效果的效果区别区别：一个是：一个是整型变量整型变量的赋值，的赋值， 一个是一个是指针型变量指针型变量的赋值。的赋值。64.1 引言引言（3）动态变量产生动态变量产生 动态变量需要在执行申请变量操作后才能产生，否则无效。动态变量需要在执行申请变量操作后才能产生，否则无效。 申请变量的操作如下：申请变量的操作如下：（对前面给出的变量说明）对前面给出的变量说明） p=new int; -产生一个产生一个int类型变量，并将该变量的地址放到指针变量类型变量，并将该变量的地址放到指针

6、变量p中。中。（4）动态变量的释放动态变量的释放 释放变量：将动态变量的存储空间还给系统，以便重新分配使用。释放变量：将动态变量的存储空间还给系统，以便重新分配使用。 释放变量的操作：释放变量的操作： delete p; -释放指针释放指针p所指示的变量（即所指示的变量（即*p）的存储空间）的存储空间 （因而使（因而使*p无效，除非重新赋值或申请）无效，除非重新赋值或申请）74.1 引言引言o 例：阅读下面程序，写出运行结果。例：阅读下面程序，写出运行结果。 void main() int *p,*q; p=new int; q=new int; *p=10; *q=20; cout*p*qe

7、ndl; *p=*q; *p=30; *q=40; cout*p*qendl; p=q; *p=40; *q=50; cout*p*q data; return success; o析构函数的实现：析构函数的实现：n主要任务是释放链表中各结点的存储空间，有两种方法，主要任务是释放链表中各结点的存储空间，有两种方法，o一种方法是：直接释放各结点的存储空间。一种方法是：直接释放各结点的存储空间。o另一种方法是：调用后面要描述的出栈算法：逐个将元素出栈，另一种方法是：调用后面要描述的出栈算法：逐个将元素出栈，直到为空为止。（下面采用这种方法来实现）直到为空为止。（下面采用这种方法来实现）stack:

8、stack( ) while ( !empty() ) pop( ); 154.2 链栈o入栈运算的实现入栈运算的实现 入栈就是将待插入元素装入一个结点后，连接到链表的表头上。入栈就是将待插入元素装入一个结点后，连接到链表的表头上。因此，操作包括：产生结点；装入元素的值到结点中；因此，操作包括：产生结点；装入元素的值到结点中；连接结点到表头连接结点到表头-注意连接操作的顺序。修改其他信息。注意连接操作的顺序。修改其他信息。操作过程如下图所示。操作过程如下图所示。算法如下：算法如下：error_code stack:push(const elementtype x ) s = new node;

9、 s - data = x; /产生结点；装入元素的值到结点中；产生结点；装入元素的值到结点中； s - next = top; top = s; / 连接结点到表头连接结点到表头 count +; / 计数计数 return success; / 返回成功操作标志返回成功操作标志a1a2a3an xstop164.2 链栈o出栈运算的实现出栈运算的实现 出栈操作就是删除表头结点，并释放其元素空间。出栈操作就是删除表头结点，并释放其元素空间。另外要修改相关的信息。注意删除操作的次序。另外要修改相关的信息。注意删除操作的次序。error_code stack:pop( )if ( empty()

10、 ) return underflow; u = top; top=top-next; delete u; count -; return success;a1a2a3an topu4.2 链栈o 例：设计算法将单链表L就地逆置。求解思路：求解思路：依次将原来链栈中的结点分离，并插入到初值为空的另一依次将原来链栈中的结点分离，并插入到初值为空的另一个链栈中。个链栈中。void stack:reverse() node *p=NULL; node *u; node *L=top; while(L!=NULL) u=L; L=L-next; /结点分离结点分离 u-next=p; p=u; /入栈

11、入栈 top=p; /原表头指针指示新表的表头原表头指针指示新表的表头17184.3 链队列4.3.1链队列存储结构链队列存储结构将队头指针标记为将队头指针标记为front，队尾指针记为，队尾指针记为rear.另外，为了使入队操作在另外，为了使入队操作在队列为空队列为空和和不空时不空时的操作保持一致，的操作保持一致， 特别特别设置设置一个不存放元素值的附加结点（称为一个不存放元素值的附加结点（称为头结点头结点）。）。 rearfrontfront194.3 链队列o由上述讨论可得到链队列类由上述讨论可得到链队列类queue的描述的描述如下：如下：其中：其中：n数据成员部分除了计数变量数据成员部

12、分除了计数变量count外，增设了头尾指针。外，增设了头尾指针。n函数成员中增设了析构函数。另外，判断满的函数可以不用。函数成员中增设了析构函数。另外，判断满的函数可以不用。 class queue public: / 函数成员函数成员 queue(); queue(); bool empty()const; bool full()const; error_code get_front(elmenttype &x)const; error_code append(const elementtype x); error_code serve(); private: / 数据成员数据成员

13、int count; node * front, * rear; ;204.3 链队列4.3.2 链队列的运算实现链队列的运算实现如前所述，链队列的结构为带头结点的链表，如下图所示。如前所述，链队列的结构为带头结点的链表，如下图所示。运算实现：运算实现：o初始化的实现：初始化的实现：分析：首先要清楚，空队列的结构形式：元素个数为分析：首先要清楚，空队列的结构形式：元素个数为0，但要有头结点，但要有头结点-事先没有，需要产生出来。如图所示。算法如下。事先没有，需要产生出来。如图所示。算法如下。queue:queue（）（） front = new node; / 产生由头指针产生由头指针fron

14、t指示的头结点指示的头结点 rear = front; / 尾指针尾指针 也指向头结点也指向头结点front - next = NULL; / 头结点（此时也是尾结点）后继指针设置为空头结点（此时也是尾结点）后继指针设置为空count = 0; frontrearfronta1a2an a3 rear214.3 链队列o 判断空的运算的实现判断空的运算的实现 bool stack:empty( ) return count = 0; ; /等价于等价于 return front = rear; 或或 return front - next = NULL；o 判断满的运算的实现判断满的运算的实现

15、 bool stack:full() return FALSE; /本函数无实际意义本函数无实际意义o 取队头元素运算的实现取队头元素运算的实现error_code queue:get_front(elementtype &x)const if ( empty() ) return underflow; x = front - next - data; return success;224.3 链队列o入队运算的实现入队运算的实现分析：对链队列的入队操作应当包括如下操作：分析：对链队列的入队操作应当包括如下操作： 产生结点，装入待插入元素；产生结点，装入待插入元素； 将新结点连接到表尾

16、；调整尾指针；计数。如下图所示。将新结点连接到表尾；调整尾指针；计数。如下图所示。算法如下：算法如下：error_code queue:append(const elementtype x ) s = new node; s - data = x; s - next = NULL; rear - next = s; rear = s; count +; return success;fronta1a2an a3 rears x 234.3 链队列n 出队运算的实现出队运算的实现分析：在队列不空的情况下，出队运算就是删除表头结点，分析：在队列不空的情况下，出队运算就是删除表头结点，即删除由指针即

17、删除由指针 ？ 所指向的结点。（同时要释放该结点）所指向的结点。（同时要释放该结点） 另外要注意的一个极端情况的处理：删除的是最后的一个结点。另外要注意的一个极端情况的处理：删除的是最后的一个结点。error_code queue:serve()if ( empty() ) return underflow; u = front - next;front - next = u - next;delete u;count -;if ( front - next = NULL ) rear = front;return success;、ufronta1a2an rearu a1 frontrearufront -