数据结构与算法3分析.ppt

;3.1 栈及其抽象数据类型; 设栈S=(e1，e2，…，en)，则e1称为栈底元素，en为栈顶元素，图3-1是栈的示意图。 栈中元素是以e1，e2，…，en的顺序进栈，而出栈的顺序却是en,…,e2,e1。也就是说栈是按照“先进后出”(FILO，First In Last Out）或“后进先出”(LIFO，Last In First Out）的原则组织数据的。所以，栈也被称为后进先出LIFO、先进后出FILO线性表或下推表。 ;;;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ;3.2 栈的表示及实现 ; 把栈组织成一个单链表，即采用链接结构来表示栈，这样的数据结构称为链接栈。图3-3 链接栈示意图 栈的链式存储结构一般是通过单链表来实现的。在单链表中，每一个结点表示栈中的一个元素。由于栈是在链表头部进行插入和删除操作，故链接栈不需要再设置表头结点。栈顶指针top就是链接栈的头指针，它可以唯一地确定一个栈。 假设元素e1,e2,...,en依次进栈，则图3-3是该链接栈的示意图。 ; 由于链接栈具有动态分配元素结点的特点，所以，在内存足够大的情况下，可以认为链接栈中最大元素的个数没有限制。因此在下面的单向链接栈类模板描述中去掉了判断栈满的操作IsFull。其他基本操作与前面的顺序栈基本操作的含义完全相同。下面将链接栈存储结点的类模板命名为LinkNode，将单向链接栈的类模板命名为LinkStack。 ; 在对链接栈的基本操作中，使用较多的是进栈和出栈操作。进栈Push就是向链接栈的栈顶插入一个元素结点，先将待进栈结点的指针域指向原来的栈顶结点，然后将栈顶指针top修指向该结点，使进栈元素结点成为新的栈顶结点。出栈Pop就是从链接栈的栈顶删除一个元素结点，先将栈顶元素取出放到x中，然后使栈顶指针top指向原栈顶结点的后继结点，然后物理上删除该结点。当top为空时，链接栈为空。删除链接栈时使用析构函数~LinkStack来完成，~LinkStack的工作是将所有元素出栈。 ;3.3 队列及其抽象数据类型; 排队是日常生活中最常见的现象，在车站买票、在银行办理业务等许多场合都需要排队。排队的特点是新来的??要站在在队尾，而队首的人先离开。这种“先来先服务”的办事方式就可以抽象成队列这种数据结构。 队列是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。队列的插入操作也成为入队，允许入队的一端称为队尾（rear）；队列的删除操作也称为出队，允许出队的一端称为队头（front）。不含元素的队列称为空队列。因此，队列又称为“先进先出”（FIFO，First In First Out）或“后进后出”（LILO，Last In Last Out）线性表。 ;3.3 队列及其抽象数据类型;;3.3 队列及其抽象数据类型;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;3.4 队列的表示及实现;【例3-2】在屏幕上显示杨辉三角。杨辉三角的特点是第n行有n个数，除了第一个数和最后一个数是1外，其他数是上一行中位其左右的两个数之和。如图3-7所示的是6行杨辉三角的情况。图3-7 杨辉三角 分析：根据第i行和第i+1行的变换规律，可以用循环队列来完成杨辉三角的显示任务。具体方法将第1行的1入队，然后循环进行如下操作：在输出第i行时，计算第i+1行的数据并将他们依次入队。为了便于计算，将队列的最大容量设置为n+2，在相邻的两行元素之间加一标识‘0’来区别不同行的队列元素。通过不断地入队和出队，来完成杨辉三角的输出。下面基于LinearStack类模板生成数据类型为int类的模板类对象，直接使用类中的相应成员函数解决这个问题。;队列的链式存储结构是仅在表头删除结点和在表尾插入结点的单链表，也为链接队列。因为需要在表头进行删除操作和在表尾进行插入操作，所以在链接队列中，需要增加指向队头和队尾的两个指针front和rear。这样，一个链接队列就由一个头指针front和一个尾指针rear唯一地确定了。 图3-8是存储了n个元素的链接队列的示意图。;3.5 应用实例;3.5 应用实例;【例3-3】计算机的编译程序需要检查一个表达式中括号是否匹配问题。如在C++语言中，表达式中允许使用两种括号：圆括号和方括号。设计一种对C++语言的表达式中的括号是否匹配进行检验的算法。 求解思路：括号匹配的处理过程与栈的特点相吻合，可以用栈来实现。具体算法是：从左