第03章习题答案.pdf

1 第三章第三章 栈与队列栈与队列 严题集 严题集 3 1 如果进栈的元素序列为 如果进栈的元素序列为 1 2 3 4 5 6 能否的到 能否的到 4 3 5 6 1 2 和和 1 3 5 4 2 6 的出栈序列 并说明为什么不能得到或如何得到 的出栈序列 并说明为什么不能得到或如何得到 答 不能的到 4 3 5 6 1 2 原因 进栈 1 2 3 4 出栈 4 3 进栈 5 出栈 5 进栈 6 出栈 6 因为 1 在 2 的下面 依照出栈的顺序是后进先出 所以出栈顺序只能是 2 1 能得到 1 3 5 4 2 6 原因 进栈 1 出栈 1 进栈 2 3 出栈 3 进栈 4 5 出栈 5 4 出栈 2 进栈 6 出栈 6 严题集 严题集 3 3 写出下列程序段的输出结果 栈的元素类型写出下列程序段的输出结果 栈的元素类型 SElem Type 为为 char void main Stack S Char x y InitStack S X c y k Push S x Push S a Push S y Pop S x Push S t Push S x Pop S x Push S s while StackEmpty S Pop S y printf y printf x 答 输出为 stack 严题集 严题集 3 4 指出下述程序段的功能是什么 1 void Demo1 SeqStack S int i arr 64 n 0 while StackEmpty S arr n Pop S 如果栈不空 则出栈并将元素保存在数组 arr 中 for i 0 inext Q InitCiQueue void EnCiQueue CiQueue p data x p next Q next 直接把 p 加在 Q 的后面 Q next p Q p 修改尾指针 Status DeCiQueue CiQueue 队列已空 p Q next next x p data Q next next p next free p return OK DeCiQueue 方法二 方法二 typedef char DataType typedef struct node DataType data struct node next QueueNode typedef struct QueueNode rear LinkQueue 分析 1 置空队 在内存中申请一个结点 头结点 的空间 将 rear 指针指向它 该头结点的指针域也指 向它本身 2 判队空 从上表中可以看出空队的条件是 rear 指针指向的地址和 rear 指向的结点的指针指向的地 址相同 3 入队 首先申请一个结点 需要入队的结点 的内存空间 新入队结点的指针指向 rear 指向的结 点的指针所指向的地址 即头结点的地址 rear 指向的结点 即原队尾结点 的指针指向新入队结点 入 队后的尾结点 rear 指针指向新入队结点 4 出队 对于两个或两个以上结点的队列 将头结点的指针指向第二个结点 然后释放第一个结点的 内存空间 free 对于一个结点的队列 在进行了上述操作后 注意尾指针已经无所指 它指向的结点 已经被释放 所以要改变 rear 指针使其指向头结点 void InitQueue LinkQueue Q 置空队 Q rear QueueNode malloc sizeof QueueNode 申请头结点 将 rear 指针指向它 Q rear next Q rear 头结点的指针域也指向它本身 int QueueEmpty LinkQueue Q 判队空 return Q rear Q rear next void EnQueue LinkQueue Q DataType x 入队 QueueNode p QueueNode malloc sizeof QueueNode 申请新结点 p data x p next Q rear next 新结点的指针域指向头结点 Q rear next p 原尾结点的指针域指向新的尾结点 Q rear p 尾指针指向新的尾结点 DataType DeQueue LinkQueue Q 出队 5 DataType x QueueNode p p Q rear next next 将第一个结点的地址赋给 p Q rear next next p next 头结点的指针指向第二个结点或头结点本身 原队列只有一个结点 x p data 保存第一个结点的数据 if p Q rear 原队列中只有一个结点 Q rear p next 尾指针指向头结点 free p return x 严题集 严题集 3 31 回文是指正读反读均相同的字符序列 如回文是指正读反读均相同的字符序列 如 abba 和和 abdba 均是回文 但均是回文 但 good 不是 回文 试写一个算法判定给定的字符向量是否为回文 不是 回文 试写一个算法判定给定的字符向量是否为回文 方法一 同时使用栈和队列两种结构方法一 同时使用栈和队列两种结构 因为栈与队列出来的方向相反因为栈与队列出来的方向相反 int Palindrome Test 判别输入的字符串是否回文序列 是则返回 1 否则返回 0 SqStack S InitStack S LinkQueue Q InitQueue Q while c getchar Push S c 入栈 EnQueue Q c 入队列 while StackEmpty S Pop S a DeQueue Q b if a b return ERROR return OK Palindrome Test 方法二 使用栈结构方法二 使用栈结构 提示 将一半字符入栈提示 将一半字符入栈 int IsHuiwen char str 判断 t 字符向量是否为回文 若是 返回 1 否则返回 0 SqStack s int i len char temp InitStack s while str i 求向量长度 或用 len strlen str len for i 0 i len 2 i 将 str 中的一半字符入栈 Push s str i if len 2 0 判断 str 的长度