数据结构-特殊线性表讲义.ppt

本章目录;3.1 栈;栈 ( Stack )的定义;a1;栈的操作特性：后进先出; ADT Stack { 数据对象： D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系： R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n } 约定an 端为栈顶，a1 端为栈底。 ;初始化栈;InitStack(S);Push (S，e);Pop(S);GetTop (S);StackEmpty (S);定义： template class T class SqStack { private： T *base； //栈底指针 int top； //栈顶 int stacksize； //栈容量 public： }；;SqStack (int m)； //构建函数 ~SqStack ( )； //析构函数 void Push (T x)； //入栈 T Pop ( )； //出栈 T GetTop ( )； //获取栈顶元素 int StackEmpty ( )； //测栈空 void ClearStack ( )； //清空栈 void StackTop ( )； //返回栈顶指针 void StackTranverse ( )；//显示栈中元素;top base;创建顺序栈;顺序栈入栈算法;顺序栈出栈算法;取栈顶元素算法;链栈的结点定义;链栈;链栈入栈算法;链栈出栈;顺序栈和链栈的比较;栈顶;栈的应用举例; 算法基于原理： N = (N div d)×d + N mod d ;10_8 数制转换类算法;表达式求值 ;中缀表达式手工求值;运算符优先级定义;中缀表达式计算机求值步骤;中缀表达式计算机求值步骤;中缀表达式计算;中缀表达式计算;中缀表达式计算;中缀表达式计算;OP + S1 + S2;中缀表达式?后缀表达式;中缀表达式转换为后缀表达式;先找运算符，再找操作数;后缀表达式计算;例3：递归;调用过程;3.2 队列;队列的逻辑结构; ADT Queue { 数据对象： D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0} 数据关系： R1＝{ a i-1,ai | ai-1, ai ∈D, i=2,...,n} 约定其中a1 端为队列头， an 端为队列尾;初始化队列;EnQueue(Q, e);a1;链队列——链式映象;rear front;假溢出;;队列初始化： 队头指针进1: 队尾指针进1: 队空条件： 队满条件：;循环队列的类定义;循环队列成员函数定义;循环队列创建;循环队列入队算法;;*;a1;链队的结点定义;链队类的定义;链队成员函数定义;链队初始化算法;链队入队算法; 链队出队算法;队列应用举例;舞伴问题 ;舞伴问题的解;资源分配问题 ;小 结;习题;习题;习题;6.计算后缀表达式：4 5 * 3 2 + - 的值。 7.假设以数组se[m]存放循环队列的元素，同时设变量rear和front分别作为队首、队尾指针，且队首指针指向队首前一个位置，写出这样设计的循环队列入队、出队的算法。;Status algo1( Stack S) { int i, n, A[255] ; n = 0 ; while ( ! StackEmpty(S) ) { n + + ; Pop( S, A[i] ) ; } for ( i=1; i=n; i + + ) Push ( S, A[i] ); };9. 简述以下算法的功能（栈和队列的元素类型均为 int）。;The End