合工大数据结构04链栈链队列.ppt

《合工大数据结构04链栈链队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1数据结构(第四章链栈和链队列)DataStructures张晶计算机与信息学院2021/10/72第四章链栈和链队列第四章链栈和链队列4.1引言4.2链栈4.3链队列3第四章链栈和链队列4.1引言前面已介绍的顺序栈、顺序队列的有关特性回顾与分析：运算实现：简单，时间复杂度好。存储特性：静态规模，编译前确定。问题：程序的通用性和空间利用率之间的矛盾！期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，这就涉及到动态变量。动态变量：在程序运行过程中产生和释放的变量。与之相反的是静态变量，静态变量：在程序运行过程中一直存

2、在的变量。在一般程序设计语言（如C、C++）中，静态变量是出现在说明语句中的变量，而动态变量则由于是在运行过程中产生，因而不会事先说明。如何实现动态变量？通过指针来实现：指针变量的说明，动态变量产生和释放。44.1引言下面依次介绍指针变量动态变量的说明，动态变量操作、产生和释放。（1）指针变量说明例：变量说明语句intm,n,*p，*q;说明了4个变量，其中：m和n说明为int型，p,q为指向int型变量的指针，其所指示的变量名称分别为*p，*q。（动态变量）指针和其所指示的变量之间的关系如下图所示。1020p*pq*q指针

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

4、的操作如下：（对前面给出的变量说明）p=newint;------产生一个int类型变量，并将该变量的地址放到指针变量p中。（4）动态变量的释放释放变量：将动态变量的存储空间还给系统，以便重新分配使用。释放变量的操作：deletep;-----释放指针p所指示的变量（即*p）的存储空间（因而使*p无效，除非重新赋值或申请）74.1引言例：阅读下面程序，写出运行结果。intmain(){int*p,*q;p=newint;q=newint;*p=10;*q=20;cout<<*p<<*q<

5、out<<*p<<*q<

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

7、nexthead=2∧104.2链栈2.采用动态变量来实现——动态链表其中每个结点用一个结构来描述，包括两个字段，存放元素值的字段data存放下一个结点的指针如右图所示。设结点类型为node，则类型描述如下：structnode{elementtypedata;//元素字段node*next;//指针字段};不特别说明的情况下，链栈就是采用动态链表来存储，就是链栈。datanextnode类型114.2链栈4.2.2链栈结构及描述可以用链表来存储栈：表头存储栈顶元素;设一个栈顶指针。如图所示。结构的描述：数据成员：除了计数分

8、量count外，还需要给出栈顶指针top.函数成员：原有的函数full（）可以不用（为什么？）。由于链表采用的是动态结构，即使在栈变量的作用域外，动态变量也不会自行释放。因此，需要设一个析构函数，以便在栈变量无效时自行释放链表的存储空间。antopa1a2a3∧……124.2链栈由此得类s