《数据结构A》第03章(唐家益).ppt

数据结构 第3章 堆栈和队列 3.1 堆栈 3.1.1 堆栈ADT 堆栈（或栈stack）是限定插入和删除运算只能在同一端进行的线性数据结构。 3.1.2 堆栈的顺序表示 一维数组s存储栈中元素， maxTop+1为最大允许容量， top指示栈顶， top==-1表示空栈, top==maxTop表示栈满。 S=(a0,a1,…,an-1) 3.1.3 堆栈的链接表示 3.2 队 列 3.2.1 队列ADT 一 队列的定义 队列是限定只能在其中一端插入元素，而在另一端删除元素的线性数据结构。（动态数据结构） 3.2.3 队列的链接表示 3.3 表达式计算 3.3.1 表 达 式 表达式习惯的书写形式是一个双目运算符 位于两个操作数之间，如a＋b，这类表达式称为中缀表达式。 除了双目运算符外，还有单目运算符，如I++和-a。条件运算符是C/C++语言中惟一的三目运算符。 3.3.2 计算后缀表达式的值 3.3.3 中缀表达式转换为后缀表达式 注意: 只考虑左结合的双目运算。 每个表达式以“＃”号作为其结束标记。 输入中缀表达式 由运算符、操作数、园括弧和‘＃’四种不同类型的项组成的序列 输出后缀表达式 3.4 递归 3.4.1 递归的概念 递归算法示例 例１　逆序输出正整数中各位 设有正整数n＝12345，输出54321。 设k位正整数为d1d2……dk，逆序输出 dkdk?1 …… d1，分成两步： (1)? 首先输出最后一位数dk； (2)? 然后输出正整数d1d2 …… dk?1的逆序形式。 3.4.2 递归的实现 子程序调用和系统栈 int fact (int n) { if (n==0) return 1; else { int temp=n*fact(n-1); return temp; } } N=fact(4); 递归函数的性能 优点：程序结构简洁而清晰，易于正确性证明和算法分析。 缺点：既费时又费空间。 尾递归 尾递归：如果一个递归函数的递归调用语句是递归函数的最后一句可执行语句，则称这样的递归为尾递归 。 递归的消除：尾递归函数可以容易地转换为迭代函数 。 void InfixToPostfix() { SeqStack char s(SIZE); char ch,y; s.Push(#); while (cinch, ch!=#) { if (isdigit(ch)||isalpha(ch)) coutch;//输出操作数 else if (ch=?=)) for(s.Top(y), s.Pop(); y!=(; s.Top(y), s.Pop()) couty; else { for (s.Top(y), s.Pop(); icp(ch)isp(y); s.Top(y), s.Pop()) couty ; s.Push(y); s.Push(ch); } } while (!s.IsEmpty()) { s.Top(y); s.Pop(); if (y!=#) couty; } coutendl; } 递归和递归定义 递归定义是一种直接或间接引用自身的定义方法。 一个合法的递归定义包括两部分：基础情况和递归部分。 基础情况以直接形式明确列举新事物的若干简单对象，递归部分给出由简单（或较简单）对象定义新对象的条件和方法。 斐波那契数列递归定义 斐波那契数列直接计算式 递归算法 一个递归算法是指直接或间接调用自身的算法 long Fib( long n） { if(n=1) return n; else return Fib(n-2)+Fib(n-1); } 递归数据结构 使用递归方式定义的数据结构常称为递归数据结构。 void PrintDigit(unsigned int n) { coutn%10; if(n=10) PrintDigit