《数据结构——C语言描述》习题及答案 耿国华 2

6. 要求循环队列不损失一个空间全部都能得到利用, 设置一个标志域tag , 以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 [提示]：

初始状态：front==0, rear==0, tag==0 队空条件：front==rear, tag==0 队满条件：front==rear, tag==1

其它状态：front !=rear, tag==0（或1、2）

入队操作： …

…（入队）

if (front==rear) tag=1；（或直接tag=1）

出队操作： …

a

…（出队） tag=0；

[问题]：如何明确区分队空、队满、非空非满三种情况？

7. 简述以下算法的功能（其中栈和队列的元素类型均为int）：

（1）void proc_1(Stack S)

{ int i, n, A[255]; n=0;

while(!EmptyStack(S))

{n++; Pop(&S, &A[n]);}

for(i=1; i<=n; i++) Push(&S, A[i]); }

将栈S逆序。

（2）void proc_2(Stack S, int e)

a

{ Stack T; int d; InitStack(&T);

while(!EmptyStack(S))

{ Pop(&S, &d);

if (d!=e) Push( &T, d); }

while(!EmptyStack(T))

{ Pop(&T, &d); Push( &S, d); } }

删除栈S中所有等于e的元素。 （3）void proc_3(Queue *Q)

{ Stack S; int d; InitStack(&S);

while(!EmptyQueue(*Q))

{

a

DeleteQueue(Q, &d); Push( &S, d);

}

while(!EmptyStack(S))

{ Pop(&S, &d); EnterQueue(Q，d) } }

将队列Q逆序。

实习题

1． 回文判断。称正读与反读都相同的字符序列为“回文”序列。

试写一个算法，判断依次读入的一个以@为结束符的字母序列，是否为形如‘序列1 &序列2’模式的字符序列。其中序列1和序列2 中都不含字符‘&’，且序列2

a