C语言栈和队列课后题.ppt

第三章栈和队列习题课 3 3写出下列程序的输出结果 栈的元素类型SElemType为char Voidmain StackS Charx 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 3解答 先解释一下你的一个误区 Pop 函数是出栈并且将出栈的元素存放在第二个行参里 所以在这里x的值不再是c了 而是出栈的元素 过程 首先是三个压栈操作 之后栈里的元素为 cak 左边的为栈底 右边是栈顶 然后一个出栈 此时栈里的元素为 ca x中存的是k 之后两次压栈 此时栈里的元素为 catk 之后一个出栈 此时栈里的元素为 cat x中存的是k 最后一次压栈 此时栈里的元素为 cats x中存的是k 之后while StackEmpty S Pop S y printf y 结果是stac Printf x 结果是k 所以最终的结果为stack 3 4简述以下算法的功能 1 Statusalgo1 StackS inti n A 255 n 0 While StackEmpty S n Pop S A n For i 1 i n i Push S A i 2 Statusalgo2 StackS inte StackT intd InitStack T while StackEmpty S Pop S d if d e Push T d while StackEmpty T Pop T d Push S d 3 4题答案是 1 程序段的功能是将一栈中的元素按反序重新排列 也就是原来在栈顶的元素放到栈底 栈底的元素放到栈顶 此栈中元素个数限制在255个以内 2 程序段的功能是利用栈T 将一个非空栈S中值等于e变量的元素全部删去 3 12写出下列程序段的输出结果 队列中的元素类型QElemType为char Voidmain QueueQ InitQueue Q Charx e y c EnQueue Q h EnQueue Q r EnQueue Q y DeQueue Q x EnQueue Q x DeQueue Q x EnQUeue Q a While QueueEmpty Q DeQueue Q y Printf y Printf x 输出结果为 char 3 12解答 首先三次入队操作 结果为 crh 左边为对尾 右边是队首 一次出队一次入队后变为 hcr 再一次出队一次入队后变为 ahc 此时x中存的是r 语句while QueueEmpty Q DeQueue Q y printf y 执行后结果为 cha Printf x 执行后为 r故结果为 char 3 13 简述以下算法的功能 栈和队列的元素均为int Voidalgo3 Queue 程序段的功能是将一个循环队列Q经过S栈的处理 反向排列 原来的队头变成队尾 原来的队尾变成队头 1 假设以顺序存储结构实现一个双向栈 即在一维数组的存储空间中存在两个栈 它们的栈底分别设在数组的两个端点 试编写实现这个双向栈tws的三个操作 初始化initstack tws 入栈push tws i x 和出栈pop tws i 其中i为0或1 用以分别指示设在数组两端的两个栈 typedefstruct 两栈共享一向量空间 datatypev m 栈可用空间0 m 1 inttop 2 twostack 1 intpush twostack s inti datatypex 两栈共享向量空间 i是0或1 表示两个栈 x是进栈元素 本算法是入栈操作 if abs s top 0 s top 1 1 return 0 栈满 else switch i case0 s v s top 0 x break case1 s v s top 1 x break default printf 栈编号输入错误 return 0 return 1 入栈成功 算法结束 2 datatypepop twostack s inti 两栈共享向量空间 i是0或1 表示两个栈 本算法是退栈操作 datatypex if s top 0 1 退栈成功 算法结束 3 datatypetop twostack s inti 两栈共享向量空间 i是0或1 表示两个栈 本算法是取栈顶元素操作 datatypex if s top 0 1 取栈顶元素成功 算法结束 3 19假设一个算术表达式中可以包括三种括号 圆括号 和 方括号 和 和花括号 和 且这三种括号可以按任意的次序嵌套使用 编写判别给定表达式中所含括号是否正确配对出现的算法 已知表达式已存入数据元素为字符的顺序表中 defineLIST INIT SIZE100 defineLISTINCREMENT10typedefstruct Elemtype elem intlength Intlistsize SqList 题3 19 intmatching SqListexp 顺序表exp中存有数据元素为字符的表达式 若表达式中三种括弧正确嵌套 则返回1 否则返回0 state 1 i 1 InitStack S while i exp length switchofexp elem i case左括弧 Push S exp elem i i break case if NOTStackEmpty S case 3 29如果希望循环队列中的元素都能得到利用 则需要设置一个标志域tag 并以tag值为0或1来区分 尾指针和头指针相同时的队列状态是 空 还是 满 试编写与此结构相对应的入队列和出队列的算法 并从时间和空间的角度讨论设标志和不设标志这两种方法的使用范围 如当循环队列容量较小而队列中每个元素站的空间较多时 哪一种方法较好 defineMAXQSIZE100typedefstruct QElemType base intfront intrear inttag CyQueue StatusEnCyQueue CyQueue 队列满 EnCyQueue StatusDeCyQueue CyQueue DeCyQueue分析 当循环队列容量较小而队列中每个元素占的空间较多时 此种表示方法可以节约较多的存储空间 较有价值 判别读入的字符序列是否为 回文 例如 abcdedcba或abccba是回文 由于回文的字符序列中的分界线不明确 因此无法判定字符序列的 中间位置 即只能按照回文的定义从字符的两头出发进行判别 题3 31 算法的基本思想是 将依次读入的字符分别插入栈和队列 然后依次比较 栈顶 和 队头 的字符 然而 按照题目的要求 这个字符序列是从外部环境输入的 为了在输入结束的时候 同时能得到序列的 头 和 尾 因此算法中 除了需要用一个栈之外 还需要一个队列 Statusex331 若从终端依次输入的字符序列是 回文 则返回TRUE 否则返回FALSEInitStack S InitQueue Q scanf ch while ch Push S ch EnQueue Q ch scanf ch state TRUE while StackEmpty 第四章串 4 12编写一个实现串的置换操作Replace s T V 的算法 有两种解法 1 重新为修改后的串分配空间 2 就在原串所在的空间进行置换 先讲第一种 S串 T串 V串 V串 pos pos sub i news串 sub 1 利用已知串的五种基本操作实现串的置换操作 StringTypeReplace StringTypeS StringTypeT StringTypeV T为非空串 若主串S中存在与T相等的子串 则均以串V替换之 本算法返回被置换后的新串 n StrLength S m StrLength T i pos 1 StrAssign news while i n m 1 SubString sub S i m if StrCompare sub T 0 i else whileS中不再存在与T相等的子串 Replace news Concat news SubString S pos