数据结构_栈和队列.pptVIP

3.1.1 栈（stack） 栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，允许插入和删除的一端称为栈顶(top)(表尾)，表头—栈底(bottom)，不含元素的空表称空栈 特点：后进先出（LIFO）或先进后出（FILO） 基本操作： InitStack(S) 操作结果：构造一个空栈S。 DestroyStack(S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 ClearStack(S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回S的元素个数，即栈的长度。 GetTop(S, e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(S, e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素 Pop(S, e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 StackTraverse(S, visit( ) ) 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit( )。一旦visit()失败，则操作失效。 栈的存储结构 顺序栈 实现：一维数组s[M] 算法为： 　void conversion( ){ //对于输入的任意一个非负十进制整数，输出与其等 值的八进制数。 Initstack(S); scanf (“%d”,N); while (N){ Push(S, N % 8); N=N / 8; } while (!StackEmpty(S)){ Pop(S,e); printf(“%d”,e); } }//conversion Tower of Hanoi问题 问题描述：有A,B,C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上 //3.9 void ditui(int j){ if(j1){ printf(j); ditui(j-1); }} //可看课后答案　　3.10 解：void test(int sum){Stack s; int x,y;InitStack(s);do{ scanf(x); Push(s,x); }while(x!=0);sum=0;printf(sum); while(!StackEmpty(s)){y=sum;Pop(s,x);y+=x;printf(y); } DestoryStack(s);} 设计算法判断一个算术表达式的圆括号是否正确配对 #include string.h#include stack.hint PairBracket( char *S){//检查表达式中括号是否配对 int i;SeqStack T; //定义一个栈 InitStack (T); for (i=0; istrlen(S) ; i++) {if ( S[i]==( ) Push(T, S[i]); //遇(时进栈if ( S[i]==) ) Pop(T); //遇)时出栈} return (!EmptyStack(T)); // 由栈空否返回正确配对与否} 3.4　队列 队列定义 队列(Queue）是一种先进先出 (First In First Out, 缩写为FIFO ) 的线性表。它只允许在表的一端进行插入，而在另一端删除元素。 　 在队列中，允许插入的一端叫做队尾(rear），允许删除的一端则称为队头(front）。 　假设队列为 q = (a1,a2,… , an), 那么 a1 就是队头元素，an 则是队尾元素。 队列的示意图为： 基本操作：