二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(12)

栈和队列比较

都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。

简化的栈和队列结构

在算法中使用栈和队列时可以采用简化的形式。

表 错误！文档中没有指定样式的文字。.4 简化的栈和队列结构

栈和队列的应用

w) 表达式求值

参见课本P53。

x) 括号匹配

例：检查表达式中的括号是否正确匹配。如{ ( ) [ ] }正确，( [ ) ] }则错误。 分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。

思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。

// 检查输入的表达式中括号是否匹配

bool MatchBrackets ()

{

const int MAXSIZE = 1024; // 栈的最大容量

char s [MAXSIZE]; // 简化的栈结构

int top; // 栈顶

// 栈初始化

top = 0;

// 检查括号是否匹配

ch = getchar();

while ( ch!=EOF ) {

switch ( ch ) {

case ‘(‘, ‘[’, ‘{’:

s [top++] = ch; // 所有左括号入栈

break;

case ‘)’:

if ( top==0 or s [--top]!=’(’ ) return false; // 栈空或右括号与栈顶左括号失配

case ‘]’:

if ( top==0 or s [--top]!=’[’ ) return false;

case ‘}’:

if ( top==0 or s [--top]!=’{’ ) return false;

}

ch = getchar(); // 取下一个字符

}

if ( top==0 ) return true; // 正好匹配

else return false; // 栈中尚有未匹配的左括号

}

y) 递归程序的非递归化

将递归程序转化为非递归程序时常使用栈来实现。

z) 作业排队

如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。

aa) 按层次遍历二叉树

void LevelOrder ( BinTree bt, VisitFunc visit )

{

const int MAXSIZE = 1024; // 队列容量(足够大即可)

BinTree q [MAXSIZE]; // 简化的队列结构

int front, rear; // 队头、队尾

if ( ! bt ) return ;

// 初始化队列，根结点入队列

front = rear = 0;

q [rear] = bt;

rear = (rear+1)%MAXSIZE;

// 队列不空，则取出队头访问并将其左右孩子入队列

while ( front!=rear ) {

p = q [front];

front = (front+1)%MAXSIZE;

if ( p ) {

visit ( p->data ); // 访问结点

q [rear] = p->lchild;

rear = (rear+1)%MAXSIZE;

q [rear] = p->rchild;

rear = (rear+1)%MAXSIZE;

}

}

}

第四章串

基础知识和算法

概念

串，空串，空格串，串的长度；子串，子串在主串中的位置，主串；串相等。 串的基本操作 表 错误！文档中没有指定样式的文字。.5 串的基本操作

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-12.html