数据结构——桟和队列概要.ppt

　 ⑷ 链队列的撤消 void Destroy_LinkQueue(LinkQueue Q ) /* 将链队列Q的队首元素出队 */ { while (Q.front!=NULL) { Q.rear=Q.front-next; /* 令尾指针指向队列的第一个结点 */ free(Q.front); /* 每次释放一个结点 */ /* 第一次是头结点，以后是元素结点 */ Q.front=Q.rear; } } * 1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？ 2 循环队列的优点是什么?如何判断它的空和满? 3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？ 4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？ 5 利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SqStack S) ，并说明S为何不作为指针参数的算法? * 6 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。试为此双向栈设计初始化InitStack(S) ，入栈Push(S,i,x)，出栈Pop(S,i,x)算法，其中i为0或1 ，用以表示栈号。 7 设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 a, b, c, d入队 a, b, c出队 i , j , k , l , m入队 d, i出队 n, o, p, q, r入队 * 8 假设Q[0,6]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 d, e, b, g, h入队 d, e出队 i , j , k , l , m入队 b,g,h 出队 n, o, p, q, r入队 * * * 由于栈具有的“后进先出”的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。 数制转换 括号匹配问题 栈与递归调用的实现 * 十进制整数N向其它进制数d(二、八、十六)的转换是计算机实现计算的基本问题。 转换法则：该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d 其中：div为整除运算,mod为求余运算 例如 (1348)10= (2504)8，其运算过程如下： n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 * 采用静态顺序栈方式实现 void conversion(int n , int d) /*将十进制整数n转换为d(2或8)进制数*/ { int k, *e ; Init_Stack(S); while (n0) { k=n%d ; push(S , k) ; n=n/d ; } /* 求出所有的余数，进栈 */ while (S.top!=0) /* 栈不空时出栈，输出 */ { pop(S, e) ; printf(“%d” , *e) ; } } * 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配? 匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。 算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。 * 算法描述 #define TRUE 0 #define FLASE -1 SqStack S ; Init_Stack(S) ; /*堆栈初始化*/ in