━━堆栈、队列结构、二叉树.ppt

C+程序设计,第7章(3) 堆栈、队列结构、二叉树,主要内容,堆栈结构顺序栈、链栈 顺序栈类的设计采用面向对象程序设计 顺序栈类的应用举例 链栈类的设计采用面向对象程序设计 链栈类的应用举例 队列结构顺序队列、链队列 顺序循环队列类的设计采用面向对象程序设计 顺序循环队列类的应用举例 链队列类的设计采用面向对象程序设计 链队列类的应用举例 树型结构二叉树 树型结构基于二叉树的常用遍历算法,堆栈结构顺序栈、链栈,堆栈的逻辑结构是限制插入和删除操作仅能在一端进行的线性结构。 栈顶与栈底：指线性表的两端。 能进行插入和删除的一端称栈顶（top）；而另一端称栈底（bottom）。 在栈顶插入新元素称进栈（压入）；删除元素称出栈（弹出）。 特殊线性表：是后进先出（LIFO：Last In First Out）结构的线性表。 进栈时：最先进栈的在最下面，最后进栈的在最上面。 出栈时：最后进栈的最先出栈，最先进栈的最后出栈。 堆栈的物理结构有连续、非连续存储两种结构，但逻辑功能基本相同。 连续存储方式：顺序栈。 非连续存储方式：链栈。 堆栈结构的应用堆栈是最常用、最重要的数据结构之一。 【例】 局部变量是存放在栈中。 表达式的优先级处理可由栈来实现。 函数调用时参数的传递、函数值的返回也是由栈来实现。,堆栈结构顺序栈、链栈,顺序栈的物理结构连续存储 可以随机访问顺序栈中的元素。 需要先开一定量的内存空间，使用时有可能溢出。 顺序栈的操作执行简单，速度快。 链栈的物理结构非连续存储 只能顺序访问链栈中的元素。 随用随开内存空间，使用时不可能溢出。 链栈的操作执行复杂（不断地动态分配），速度慢。,顺序栈类的设计采用面向对象程序设计,顺序栈类模板 StackSeq 的设计： 私有成员数据： int top ; /栈顶指针（对于顺序栈，栈顶位置就是栈顶元素的下标） T *elements ; /栈空间首地址（对于顺序栈，栈空间是T类型的数组，开在动态存储区） int max ; /栈空间中最多容纳的元素个数（对顺序栈，就是栈空间数组的长度）,顺序栈类的设计采用面向对象程序设计, 公有成员函数： StackSeq ( int = 20 ) ; /构造函数（参数省略时，默认栈空间中最多容纳20个元素） StackSeq ( ) ; /析构函数（释放动态存储区的栈空间） void push ( T d ) ; /压栈（将d元素压入栈中，本操作 top 将改变） T pop ( ) ; /出栈（弹出栈顶元素并返回，本操作 top 将改变） T get ( int k ) ; /读取并返回栈内第k号元素（元素编号为第0top号，本操作 top 不变） int length ( ) ; /求出栈内元素的个数 void print ( ) ; /输出栈内所有元素（将第0top号的元素依次输出，本操作 top 不变） void empty ( ) ; /清空栈（使栈内无任何元素，即空栈） bool isEmpty ( ) ; /判断栈是否为空 bool isFull ( ) ; /判断栈是否已满,【例】（顺序栈类模板 StackSeq 的定义，以 “stackseq.h” 为文件名保存。） #include template class StackSeq /顺序栈类模板 StackSeq 的声明 int top ; /栈顶指针（对于顺序栈，栈顶位置就是栈顶元素的下标） T *elements ; /栈空间首地址（对于顺序栈，栈空间是T类型的数组，开在动态存储区） int max ; /栈空间中最多容纳的元素个数（对于顺序栈，就是栈空间数组的长度） public: StackSeq ( int = 20 ) ; /构造函数（参数省略时，默认栈空间中最多容纳20个元素） StackSeq ( ) ; /析构函数（释放动态存储区的栈空间） void push ( T d ) ; /压栈（将d元素压入栈中，本操作 top 将改变） T pop ( ) ; /出栈（弹出栈顶元素并返回，本操作 top 将改变） T get ( int k ) ; /读取并返回栈内第k号元素（元素编号为第0top号，本操作 top 不变） int length ( ) ; /求出栈内元素的个数 void print ( ) ; /输出栈内所有元素（将第0top号的元素依次输出，本操作 top 不变） void empty ( ) ; /清空栈（使栈内无任何元素，即空栈） bool isEmpty ( ) ; /判断栈是否为空 bool isFull ( ) ; /判断栈是否已满 ;,/构造函数 template StackSeq : StackSeq ( int n ) top = -1 ; /栈顶 top 为 -1 时，表示空栈 elements = new T n ; /在堆区建立栈空间（T类型数组，首地址存放在elements中） max = n ; /栈空间中最多容纳的元素个数（也就是栈空间数组的长度） assert ( elements != 0 ) ; /分配不成功，则结束程序 /析构函数 template StackSeq : StackSeq ( ) delete elements ; /释放动态存储区的栈空间 /压栈 template void StackSeq : push ( T d ) assert ( ! isFull( ) ) ; /栈满，则结束程序 elements +top = d ; /栈顶指针先加1，元素d再进栈 /出栈 template T StackSeq : pop ( ) assert ( ! isEmpty( ) ) ; /栈空，则结束程序 return elements top- ; /返回栈顶元素，然后栈顶指针减1,/读取并返回栈内第 k 号元素（栈内元素编号为第 0 top 号） template T StackSeq : get ( int k ) assert ( k=0 ,顺序栈类的应用举例,【例】（在文件 s1.txt 中，有若干学生成绩资料。要求：以Student类作为顺序栈元素的数据类，对顺序栈类模板 StackSeq 中的各成员函数进行测试。学生类 Student 的声明 ，前面例子中已出现，并以 “student.h” 为文件名保存。 ） #include #include #include “stackseq.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_SS( 10 ) ; /定义学生栈s_SS Student s ; cout s ,在s1.txt 中，学生资料： 61001 方飞飞 96 61002 巩浩文 72 61003 程可国 69 61004 麦宏岩 33 61005 文一奇 97 61006 王碧方 99,cout “s_SS栈内元素个数=” s_SS.length( ) endl ; cout “s_SS栈内元素有：n” ; s_SS.print( ) ; cout “s_SS栈内0号元素是：n” s_SS.get( 0 ) ; cout “s_SS栈内3号元素是：n” s_SS.get( 3 ) ; cout “s_SS栈内元素个数=” s_SS.length( ) endl ; cout “依次全部出栈 n” ; while ( !s_SS.isEmpty( ) ) cout s_SS.pop( ) ; cout “s_SS栈内元素个数=” s_SS.length( ) endl ; cout s_SS.pop( ) ; ,【例】（使用顺序栈类模板 StackSeq ，建立整数栈i_SS、字符栈c_SS，随机产生6个范围在09之间的整数、6个范围在AZ之间的字母，依次进各栈，再出各栈。） #include #include #include “stackseq.h” void main ( ) StackSeq i_SS( 6 ) ; StackSeq c_SS( 8 ) ; cout “依次进栈 n” ; cout “整数栈：t字符栈：n” ; for ( int i=0; i6; i+ ) i_SS.push( rand()%10 ) ; c_SS.push( rand()%26+65 ) ; cout i_SS.get( i ) “tt” c_SS.get( i ) endl ; ,if ( i_SS.isFull( ) ) cout “整数栈已满!n” ; else cout“整数栈未满，可再压入” 6-i_SS.length() “个!n”; if ( c_SS.isFull() ) cout “字符栈已满!n” ; else cout“字符栈未满，可再压入” 8-c_SS.length() “个!n”; cout “依次出栈 n” ; cout “整数栈：t字符栈：n” ; for ( i=0; i6; i+ ) cout i_SS.pop( ) “tt” c_SS.pop( ) endl ; if ( i_SS.isEmpty( ) ) cout “整数栈已空!n” ; if ( c_SS.isEmpty( ) ) cout “字符栈已空!n” ; ,【例】（栈结构应用于表达式优先级的实现。若有 + - * / 运算符和等号=组成的算术表达式，只有两个优先级( 先 */ 后 +- )。设： A+B*C-D/E=； 实现运算符的优先级。） 【算法】定义两个栈：操作数栈 n_S，运算符栈 c_S。从左往右扫描算术表达式，遇到操作数，则压入n_S栈；遇到运算符，则与c_S栈栈顶运算符比较优先级，若新运算符优先级高，或此时c_S栈空，则压入c_S栈；否则将c_S栈栈顶运算符出栈，与n_S栈出栈的两个操作数进行运算，结果压入n_S栈，再将新运算符压入c_S栈。继续扫描，直至遇到号，扫描结束。两栈的元素继续按前面规则出栈运算。,链栈类的设计采用面向对象程序设计,结点类模板 Node 的声明：前面例子中已出现，并以 “node.h” 为文件名保存。 结点类模板 Node 的成员： 私有成员数据： 数据域： T data ; /T类型的变量data 链域： Node *next ; /next为指向下一个结点的指针 公有成员函数： Node ( ) ; /表头结点的构造 Node ( T d ) ; /普通结点的构造 void set ( T d ) ; /将当前结点的数据域置为d T get ( ) ; /获取并返回当前结点的数据域 void show ( ) ; /输出当前结点的数据域 友元函数、友元类： friend class ListLink ; /友元类，链表类可以访问结点类的私有、保护成员 friend class StackLink ; /友元类，链栈类可以访问结点类的私有、保护成员 friend class QueueLink ; /友元类，链队列类可以访问结点类的私有、保护成员,链栈类的设计采用面向对象程序设计,链栈类模板 StackLink 的设计： 私有成员数据： Node * top ; 公有成员函数： StackLink ( ) ; /构造函数（空栈） StackLink ( ) ; /析构函数（释放栈内各结点的动态空间） void push ( T d ) ; /压栈（将d元素压入栈中，本操作 top 将改变） T pop ( ) ; /出栈（弹出栈顶元素并返回，本操作 top 将改变） T getTop ( ) ; /读取并返回栈顶元素（本操作 top 不变） int length ( ) ; /求出栈内元素的个数 void print ( ) ; /输出栈内所有元素（本操作 top 不变） void empty ( ) ; /清空栈（使栈内无任何元素，即空栈） bool isEmpty ( ) ; /判断栈是否为空,【例】（链栈类模板 StackLink 的定义，以 “stacklink.h” 为文件名保存。） #include template class StackLink /链栈类模板 StackLink 的声明 Node * top ; /指向栈顶结点的指针 public: StackLink ( ) top = NULL ; /构造函数（空栈） StackLink ( ) empty( ) ; /析构函数（释放栈内各结点的动态空间） void push ( T d ) ; /压栈（将d元素压入栈中，本操作 top 将改变） T pop ( ) ; /出栈（弹出栈顶元素并返回，本操作 top 将改变） T getTop ( ) /读取并返回栈顶元素（本操作 top 不变） assert ( ! isEmpty( ) ) ; return top-data ; int length ( ) ; /求出栈内元素的个数 void print ( ) ; /输出栈内所有元素（本操作 top 不变） void empty ( ) ; /清空栈（使栈内无任何元素，即空栈） bool isEmpty ( ) return top = NULL ; /判断栈是否为空 ;,/压栈（将d元素压入栈中，本操作 top 将改变） template void StackLink : push ( T d ) Node *pnew = new Node ( d ) ; pnew-next = top ; top = pnew ; /出栈（弹出栈顶元素并返回，本操作 top 将改变） template T StackLink : pop ( ) assert ( ! isEmpty( ) ) ; /栈空，则结束程序 Node *temp = top ; top = top-next ; T da = temp-data ; delete temp ; return da ; ,/求出栈内元素的个数 template int StackLink : length ( ) Node *temp = top ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /输出栈内所有元素（本操作 top 不变） template void StackLink : print ( ) Node *temp = top ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空栈（使栈内无任何元素，即空栈） template void StackLink : empty ( ) Node * temp ; while ( top != NULL ) temp = top ; top = top-next ; delete temp ; ,链栈类的应用举例,【例】（在文件 s1.txt 中，有若干学生成绩资料。要求：以Student类作为链栈结点的数据类，对链栈类模板 StackLink 中的各成员函数进行测试。学生类 Student 的声明 ，前面例子中已出现，并以 “student.h” 为文件名保存。 ） #include #include #include “node.h” #include “stacklink.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_SL ; /定义学生栈s_SL Student s ; cout s ) s_SL.push( s ) ; inf.close( ) ;,在s1.txt 中，学生资料： 61001 方飞飞 96 61002 巩浩文 72 61003 程可国 69 61004 麦宏岩 33 61005 文一奇 97 61006 王碧方 99,cout “s_SL栈内元素个数=” s_SL.length( ) endl ; cout “s_SL栈内元素有：n” ; s_SL.print( ) ; cout “s_SL栈顶元素是：n” s_SL.getTop( ) ; cout “s_SL栈内元素个数=” s_SL.length( ) endl ; cout “依次全部出栈 n” ; while ( !s_SL.isEmpty( ) ) cout s_SL.pop( ) ; cout “s_SL栈内元素个数=” s_SL.length( ) endl ; cout s_SL.pop( ) ; ,队列结构顺序队列、链队列,队列的逻辑结构是限制插入和删除操作分别在两端进行的线性结构。 队头与队尾：指线性表的两端。 能进行插入的一端称队尾（rear）；能进行删除的一端称队头（front）。 在队尾加入新元素称进队；在队头删除元素称出队。 特殊线性表：是先进先出（ FIFO： First In First Out）结构的线性表。 进队时：随队尾加入元素，队尾指针（rear）不断向后移。 出队时：随队头元素的出队，队头指针（front）也不断向后移。 即：进队与出队都是队尾和队头指针的位置在变。 队列的物理结构有连续、非连续存储两种结构，但逻辑功能基本相同。 连续存储方式：顺序队列。 非连续存储方式：链队列。 队列结构的应用队列是最常用、最重要的数据结构之一。 【例】在Windows操作系统中，使用了很多消息等待队列，以实现先来的先服务。,顺序队列的物理结构连续存储 可以随机访问顺序队列中的元素。 需要先开一定量的内存空间，使用时有可能溢出。 顺序队列的操作执行简单，速度快。 链队列的物理结构非连续存储 只能顺序访问链队列中的元素。 随用随开内存空间，使用时不可能溢出。 链队列的操作执行复杂（不断地动态分配），速度慢。,队列结构顺序队列、链队列,顺序循环队列类的设计采用面向对象程序设计,对顺序队列的分析： 空队时，队头指针front（下标）和队尾指针rear（下标）重叠在一起，都为-1。进队时随着队尾加入元素，队尾指针（rear）不断加 1 移动；出队时随着队头元素的出队，队头指针（front）也不断加 1 移动。进队和出队都是队尾和队头指针的位置在变（若要位置不变，移动元素工作量太大） ，最后造成分配给队列的存储空间前端不能再被利用，而后端逐渐产生溢出。,顺序循环队列类的设计采用面向对象程序设计,顺序循环队列：将顺序队列做成一个逻辑上的循环队列；而这样做会使得：空队时rear = front，满队时 rear = front；为了区分空队与满队，在队列中少放一个元素，即队列中只剩下一个空位置时就算满队，以此作为标志来区分空队与满队。,顺序循环队列类的设计采用面向对象程序设计,顺序循环队列类模板 QueueSeq 的设计： 私有成员数据： int rear, front ; /队尾、队头指针（对于顺序队列，就是队尾、队头位置的下标） T *elements ; /队列空间的首地址（队列空间是T类型的数组，开在动态存储区） int max ; /队列空间最多可容纳的元素个数+1（也就是队列空间数组的长度） 公有成员函数： QueueSeq ( int = 20 ) ; /构造函数（参数省略时，队列空间默认最多容纳19个元素） QueueSeq ( ) ; /析构函数（释放动态存储区的队列空间） void enter ( T d ) ; /新元素d从队尾进队（rear 改变） T leave ( ) ; /队头元素出队（front 改变，返回出队的元素） T get ( int k ) ; /读取并返回队列中的第k号元素（队头元素编号为1。 front 不变） int length ( ) ; /求出队列中元素的个数 void print ( ) ; /输出队列中的所有元素（从队头元素开始输出。front 不变） void empty ( ) ; /清空队列（使队列中无任何元素，即空队） bool isEmpty ( ) ; /判断队列是否为空 bool isFull ( ) ; /判断队列是否已满,【例】（顺序循环队列类模板QueueSeq的声明，以 “queueseq.h” 为文件名保存。） #include template class QueueSeq /顺序循环队列类模板 QueueSeq 的声明 int rear, front ; /队尾、队头指针（对于顺序队列，就是队尾、队头位置的下标） T *elements ; /队列空间的首指针（队列空间是T类型的数组，开在动态存储区） int max ; /队列空间最多可容纳的元素个数+1（也就是队列空间数组的长度） public: QueueSeq ( int = 20 ) ; /构造函数（参数省略时，队列空间默认最多容纳19个元素） QueueSeq ( ) ; /析构函数（释放动态存储区的队列空间） void enter ( T d ) ; /新元素d从队尾进队（rear 改变） T leave ( ) ; /队头元素出队（front 改变，返回出队的元素） T get ( int k ) ; /读取并返回队列中的第k号元素（队头元素编号为1号。 front 不变） int length ( ) ; /求出队列中元素的个数 void print ( ) ; /输出队列中的所有元素（从队头元素开始输出。front 不变） void empty ( ) ; /清空队列（使队列中无任何元素，即空队） bool isEmpty ( ) ; /判断队列是否为空 bool isFull ( ) ; /判断队列是否已满 ;,/构造函数（参数省略时，队列空间默认最多容纳19个元素） template QueueSeq : QueueSeq ( int n ) rear = front = 0 ; /队尾rear等于队头front ，表示空栈，初始值都为0 elements = new T n ; /在堆区建立队列空间（是T类型数组，首地址保存在elements中） max = n ; /队列空间最多容纳元素个数+1（对于顺序队列，就是队列空间数组的长度） assert ( elements != 0 ) ; /分配不成功，则结束程序 /析构函数（释放动态存储区的队列空间） template QueueSeq : QueueSeq ( ) delete elements ; /释放动态存储区的队列空间 /新元素d从队尾进队（rear 改变） template void QueueSeq : enter ( T d ) assert ( ! isFull() ) ; /队列满，则结束程序 rear = ( rear+1 ) % max ; elements rear = d ; /队尾指针先加1，元素再进队 /队头元素出队（front 改变，返回出队的元素） template T QueueSeq : leave ( ) assert ( ! isEmpty() ) ; /队列空，则结束程序 front = ( front+1 ) % max ; return elements front ; /队头指针先加1，队头元素离队,/读取并返回队列中的第k号元素（队头元素编号为1。 front 不变） template T QueueSeq : get ( int k ) assert ( k=1 ,【例】（在文件s1.txt中，有若干学生成绩资料。要求：以Student类作为顺序队列元素的数据类，对顺序循环队列类模板 QueueSeq 中的各成员函数进行测试。学生类 Student 的声明 ，前面例子中已出现，并以 “student.h” 为文件名保存。 ） #include #include #include “queueseq.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_QS( 10 ) ; /定义学生队列s_QS Student s ; int i = 0 ; cout s ,在s1.txt 中，学生资料： 61001 方飞飞 96 61002 巩浩文 72 61003 程可国 69 61004 麦宏岩 33 61005 文一奇 97 61006 王碧方 99,顺序循环队列类的应用举例,cout “s_QS队列中元素个数=” s_QS.length( ) endl ; cout “s_QS队列中2号元素是：n” s_QS.get( 2 ) ; cout “s_QS队列中5号元素是：n” s_QS.get( 5 ) ; cout “s_QS队列中元素个数=” s_QS.length( ) endl ; cout “现在前3位依次出队：n” ; for ( i=1; ( i=3 ,链队列类的设计采用面向对象程序设计,结点类模板 Node 的声明：前面例子中已出现，并以 “node.h” 为文件名保存。 结点类模板 Node 的成员： 私有成员数据： 数据域： T data ; /T类型的变量data 链域： Node *next ; /next为指向下一个结点的指针 公有成员函数： Node ( ) ; /表头结点的构造 Node ( T d ) ; /普通结点的构造 void set ( T d ) ; /将当前结点的数据域置为d T get ( ) ; /获取并返回当前结点的数据域 void show ( ) ; /输出当前结点的数据域 友元函数、友元类： friend class ListLink ; /友元类，链表类可以访问结点类的私有、保护成员 friend class StackLink ; /友元类，链栈类可以访问结点类的私有、保护成员 friend class QueueLink ; /友元类，链队列类可以访问结点类的私有、保护成员,链队列类的设计采用面向对象程序设计,链队列类模板 QueueLink 的设计： 私有成员数据： Node *rear , *front ; /指向队尾结点、队头结点的指针 公有成员函数： QueueLink ( ) ; /构造函数（空队列） QueueLink ( ) ; /析构函数（释放队列中各结点的动态空间） void enter ( T d ) ; /进队（将d元素加入到队尾，本操作 rear 将改变） T leave ( ) ; /出队（队头元素离队，并返回其值，本操作 front 将改变） T getFront ( ) ; /读取并返回队头元素（本操作 front 不变） int length ( ) ; /求出队列中元素的个数 void print ( ) ; /输出队列中所有元素（本操作 front 、rear 不变） void empty ( ) ; /清空队列（使队列中无任何元素，即空队列） bool isEmpty ( ) ; /判断队列是否为空,【例】（链队列类模板 QueueLink 的定义，以 “queuelink.h” 为文件名保存。） #include template class QueueLink /链队列类模板 QueueLink 的声明 Node * rear , *front ; /指向队尾结点、队头结点的指针 public: QueueLink ( ) rear = front = NULL ; /构造函数（空队列） QueueLink ( ) empty( ) ; /析构函数（释放队列中各结点的动态空间） void enter ( T d ) ; /进队（将d元素加入到队尾，本操作 rear 将改变） T leave ( ) ; /出队（队头元素离队，并返回其值，本操作 front 将改变） T getFront ( ) /读取并返回队头元素（本操作 front 不变） assert ( ! isEmpty( ) ) ; return front-data ; int length ( ) ; /求出队列中元素的个数 void print ( ) ; /输出队列中所有元素（本操作 front 、rear 不变） void empty ( ) ; /清空队列（使队列中无任何元素，即空队列） bool isEmpty ( ) return front = NULL ; /判断队列是否为空 ;,/进队（将d元素加入到队尾，本操作 rear 将改变） template void QueueLink : enter ( T d ) Node *pnew = new Node ( d ) ; if ( front = NULL ) front = rear = pnew ; else rear-next = pnew ; rear = pnew ; /出队（队头元素离队，并返回其值，本操作 front 将改变） template T QueueLink : leave ( ) assert ( ! isEmpty( ) ) ; /队列空，则结束程序 Node *temp = front ; front = front-next ; T da = temp-data ; delete temp ; return da ; ,/求出队列中元素的个数 template int QueueLink : length ( ) Node *temp = front ; int count = 0 ; while ( temp != NULL ) count+ ; temp = temp-next ; return count ; /输出队列中所有元素（本操作 front 、rear 不变） template void QueueLink : print ( ) Node *temp = front ; while ( temp != NULL ) cout data ; temp = temp-next ; /清空队列（使队列中无任何元素，即空队列） template void QueueLink : empty ( ) Node * temp ; while ( front != NULL ) temp = front ; front = front -next ; delete temp ; ,链队列类的应用举例,【例】（在文件 s1.txt 中，有若干学生成绩资料。要求：以Student类作为链队列结点的数据类，对链队列类模板 QueueLink 中的各成员函数进行测试。学生类Student的声明 ，前面例子中已出现，并以 “student.h” 为文件名保存。 ） #include #include #include “node.h” #include “queuelink.h” #include “student.h” void main ( ) ifstream inf ( “s1.txt” , ios:in | ios:nocreate ) ; if ( ! inf ) cout s_QL ; /定义学生队列s_QL Student s ; cout s ) s_QL.enter( s )