合工大计算机专业相关课件数据结构

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

DataStructures胡学钢张晶计算机与信息学院2009年9月1第四章链栈和链队列

第四章链栈和链队列

4.1引言

4.2链栈

4.3链队列

2第四章链栈和链队列4.1引言

前面已介绍的顺序栈、顺序队列的有关特性回顾与分析：

运算实现：简单，时间复杂度好。

存储特性：静态规模，编译前确定。

问题：程序的通用性和空间利用率之间的矛盾！

期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，这就涉及到动态变量。

动态变量：在程序运行过程中产生和释放的变量。与之相反的是静态变量，

静态变量：在程序运行过程中一直存在的变量。在一般程序设计语言（如C、C++）中，静态变量是出现在说明语句中的变量，而动态变量则由于是在运行过程中产生，因而不会事先说明。

如何实现动态变量？通过指针来实现：指针变量的说明，动态变量产生和释放。34.1引言下面依次介绍指针变量动态变量的说明，动态变量操作、产生和释放。（1）指针变量说明

例：变量说明语句intm,n,*p，*q;说明了4个变量，其中：m和n说明为int型，p,q为指向int型变量的指针，其所指示的变量名称分别为*p，*q。（动态变量）指针和其所指示的变量之间的关系如下图所示。1020p*pq*q指针和目标变量的关系：所谓指针指向一个变量，就是存放着目标变量的地址的值。44.1引言（2）动态变量的操作

基本操作：和其他类型的变量类似，可以对动态变量赋值、引用。特别要注意区分：指针赋值和动态变量赋值操作的关系和效果。例如语句*p=*q;和p=q;的效果存在明显的差异：假设初始时*p=10；*q=20；如图所示。1020p*pq*q*p=*q的效果201020p*pq*qp=q的效果区别：一个是整型变量的赋值，一个是指针型变量的赋值。*p54.1引言（3）动态变量产生动态变量需要在执行申请变量操作后才能产生，否则无效。申请变量的操作如下：（对前面给出的变量说明）

p=newint;

------产生一个int类型变量，并将该变量的地址放到指针变量p中。（4）动态变量的释放释放变量：将动态变量的存储空间还给系统，以便重新分配使用。释放变量的操作：

deletep;-----释放指针p所指示的变量（即*p）的存储空间（因而使*p无效，除非重新赋值或申请）64.1引言例：阅读下面程序，写出运行结果。intmain(){int*p,*q;p=newint;q=newint;*p=10;*q=20;cout<<*p<<*q<<endl;*p=*q;*q=30;cout<<*p<<*q<<endl;p=q;*p=40;*q=50;cout<<*p<<*q<<endl;deletep;}输出结果是？74.2链栈4.2.1链表为了避免前述的顺序存储方式在的问题规模事先难以确定的问题，可以将表中元素用链地址连接起来构成一个表。由此而得到链表。链表：将表中元素用链地址连接起来构成的表。例如，下图就是一个链表的示意图，其中：由若干称为结点的“单元”连接而成。每个结点由两部分组成：存放元素值的字段存放下一个结点的地址的字段。另外，有一个指向表头的指针（头指针）head，指示起点。最后一个结点（也称为尾结点）的后继指针为空值，表示其后续没有结点了。结点尾结点a1a2a3an……∧

head头指针84.2链栈链表存储结构的实现如何实现链表的存储结构？

对此，可有两类方法，其一是用数组来实现，其二是用动态链表。1.用数组来存储表中元素------静态链表就是用数组元素存储表中元素的值，以及后续元素的地址。（因而需要说明为构造类型）例如，右图是一个存储了部分英语字母的链表。这类表由于数组的规模事先确定，因而称为静态链表。静态链表的不足：难以兼顾到通用性和存储空间的利用率。E6D0A3B4C1G-1F50123456下标datanexthead=2∧94.2链栈2.采用动态变量来实现——动态链表

其中每个结点用一个结构来描述，包括两个字段，存放元素值的字段data存放下一个结点的指针如右图所示。设结点类型为node，则类型描述如下：

typedefstruct{elementtypedata;//元素字段node*next;//指针字段}node;

不特别说明的情况下，链栈就是采用动态链表来存储，就是链栈。

datanextnode类型104.2链栈4.2.2链栈结构及描述可以用链表来存储栈：表头存储栈顶元素;设一个栈顶指针。如图所示。结构的描述：数据成员：除了计数分量count外，还需要给出栈顶指针top.函数成员：原有的函数full（）可以不用（为什么？）。由于链表采用的是动态结构，即使在栈变量的作用域外，动态变量也不会自行释放。因此，需要设一个析构函数，以便在栈变量无效时自行释放链表的存储空间。antopa1a2a3∧

……114.2链栈由此得类stack的描述如下：classstack{public://函数成员stack();~stack();Boolempty()const;Boolfull()const;error_codeget_top(elementtype&x)const;error_codepush(constelementtyoex);error_codepop();private://数据成员intcount;node*top;//栈顶指针};新增的析构函数原有的函数124.2链栈4.2.3链栈运算的实现初始化运算的实现：stack::stack（）{count=0;top=NULL;}判断空的实现：Boolstack::empty(){returncount==0;}//等价于：returntop==NULL;判断满的实现：Boolstack::full(){returnFALSE;}//本函数无实际意义134.2链栈取栈顶元素的实现：error_codestack::get_top(elementtype&x)const{if(empty())returnunderflow;x=top->data;returnsuccess;}析构函数的实现：主要任务是释放链表中各结点的存储空间，有两种方法，一种方法是：直接释放各结点的存储空间。另一种方法是：调用后面要描述的出栈算法：逐个将元素出栈，直到为空为止。（下面采用这种方法来实现）error_codestack::~stack(){while(!empty())pop();}144.2链栈入栈运算的实现入栈就是将待插入元素装入一个结点后，连接到链表的表头上。因此，操作包括：产生结点；装入元素的值到结点中；连接结点到表头----注意连接操作的顺序。修改其他信息。操作过程如下图所示。算法如下：error_codestack::push(constelementtypex){s=newnode;s->data=x;//产生结点；装入元素的值到结点中；s->next=top;top=s;//连接结点到表头count++;//计数returnsuccess;//返回成功操作标志}a1a2a3an∧……xstop①②③154.2链栈出栈运算的实现出栈操作就是删除表头结点，并使放其元素空间。另外要修改相关的信息。注意删除操作的次序。error_codestack::pop(){if(empty())returnunderflow;u=top;top=top->next;deleteu;count--;returnsuccess;}a1a2a3an^……top③释放该结点u①②164.3链队列4.3.1链队列存储结构

分析：在用如图所示链表存储队列时，如何确定其对应关系？即队头、队尾元素的位置-------不同结构影响运算的性能。首先，队头位置的确定。如果将表头作为队尾，显然不便（？）因此，应将表头设置为队头，因而将表头指针标记为front.

其次，为了使入队操作更快捷，需要设置尾指针（为什么？），不妨设为rear.如图所示。另外，为了使入队操作在队列为空和不空时的操作保持一致，特别设置一个不存放元素值的附加结点（称为头结点）。如图所示。不做强调的情况下，后面的链队列均为此结构。fronta1a2a3an^……rear/////frontfront174.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;

};新增的析构函数原有的函数184.3链队列4.3.2链队列的运算实现如前所述，链队列的结构为带头结点的链表，如下图所示。运算实现：初始化的实现：分析：首先要清楚，空队列的结构形式：元素个数为0，但要有头结点----事先没有，需要产生出来。如图所示。算法如下。queue::queue（）{front=newnode;//产生由头指针front指示的头结点rear=front;//尾指针也指向头结点front->next=NULL;//头结点（此时也是尾结点）后继指针设置为空count=0;}

^frontrearfronta1a2an^a3……rear194.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;}204.3链队列入队运算的实现分析：对链队列的入队操作应当包括如下操作：产生结点，装入待插入元素；将新结点连接到表尾；调整尾指针；计数。如下图所示。算法如下：error_codequeue::append(constelementtypex){s=newnode;s->data=x;s->next=NULL;rear->next=s;rear=s;count++;returnsuccess;}fronta1a2an^a3……rears①

②x③^④⑤214.3链队列出队运算的实现分析：在队列不空的情况下，出队运算就是删除表头结点，即删除由指针

？

所指向的结点