C語言棧和隊(duì)列課后題.ppt

第三章棧和隊(duì)列習(xí)題課 3 3寫出下列程序的輸出結(jié)果 棧的元素類型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 輸出結(jié)果是 stack 3 3解答 先解釋一下你的一個(gè)誤區(qū) Pop 函數(shù)是出棧并且將出棧的元素存放在第二個(gè)行參里 所以在這里x的值不再是c了 而是出棧的元素 過程 首先是三個(gè)壓棧操作 之后棧里的元素為 cak 左邊的為棧底 右邊是棧頂 然后一個(gè)出棧 此時(shí)棧里的元素為 ca x中存的是k 之后兩次壓棧 此時(shí)棧里的元素為 catk 之后一個(gè)出棧 此時(shí)棧里的元素為 cat x中存的是k 最后一次壓棧 此時(shí)棧里的元素為 cats x中存的是k 之后while StackEmpty S Pop S y printf y 結(jié)果是stac Printf x 結(jié)果是k 所以最終的結(jié)果為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 程序段的功能是將一棧中的元素按反序重新排列 也就是原來在棧頂?shù)脑胤诺綏５?棧底的元素放到棧頂 此棧中元素個(gè)數(shù)限制在255個(gè)以內(nèi) 2 程序段的功能是利用棧T 將一個(gè)非空棧S中值等于e變量的元素全部刪去 3 12寫出下列程序段的輸出結(jié)果 隊(duì)列中的元素類型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 輸出結(jié)果為 char 3 12解答 首先三次入隊(duì)操作 結(jié)果為 crh 左邊為對尾 右邊是隊(duì)首 一次出隊(duì)一次入隊(duì)后變?yōu)?hcr 再一次出隊(duì)一次入隊(duì)后變?yōu)?ahc 此時(shí)x中存的是r 語句while QueueEmpty Q DeQueue Q y printf y 執(zhí)行后結(jié)果為 cha Printf x 執(zhí)行后為 r故結(jié)果為 char 3 13 簡述以下算法的功能 棧和隊(duì)列的元素均為int Voidalgo3 Queue 程序段的功能是將一個(gè)循環(huán)隊(duì)列Q經(jīng)過S棧的處理 反向排列 原來的隊(duì)頭變成隊(duì)尾 原來的隊(duì)尾變成隊(duì)頭 1 假設(shè)以順序存儲結(jié)構(gòu)實(shí)現(xiàn)一個(gè)雙向棧 即在一維數(shù)組的存儲空間中存在兩個(gè)棧 它們的棧底分別設(shè)在數(shù)組的兩個(gè)端點(diǎn) 試編寫實(shí)現(xiàn)這個(gè)雙向棧tws的三個(gè)操作 初始化initstack tws 入棧push tws i x 和出棧pop tws i 其中i為0或1 用以分別指示設(shè)在數(shù)組兩端的兩個(gè)棧 typedefstruct 兩棧共享一向量空間 datatypev m ?？捎每臻g0 m 1 inttop 2 twostack 1 intpush twostack s inti datatypex 兩棧共享向量空間 i是0或1 表示兩個(gè)棧 x是進(jìn)棧元素 本算法是入棧操作 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 棧編號輸入錯(cuò)誤 return 0 return 1 入棧成功 算法結(jié)束 2 datatypepop twostack s inti 兩棧共享向量空間 i是0或1 表示兩個(gè)棧 本算法是退棧操作 datatypex if s top 0 1 退棧成功 算法結(jié)束 3 datatypetop twostack s inti 兩棧共享向量空間 i是0或1 表示兩個(gè)棧 本算法是取棧頂元素操作 datatypex if s top 0 1 取棧頂元素成功 算法結(jié)束 3 19假設(shè)一個(gè)算術(shù)表達(dá)式中可以包括三種括號 圓括號 和 方括號 和 和花括號 和 且這三種括號可以按任意的次序嵌套使用 編寫判別給定表達(dá)式中所含括號是否正確配對出現(xiàn)的算法 已知表達(dá)式已存入數(shù)據(jù)元素為字符的順序表中 defineLIST INIT SIZE100 defineLISTINCREMENT10typedefstruct Elemtype elem intlength Intlistsize SqList 題3 19 intmatching SqListexp 順序表exp中存有數(shù)據(jù)元素為字符的表達(dá)式 若表達(dá)式中三種括弧正確嵌套 則返回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如果希望循環(huán)隊(duì)列中的元素都能得到利用 則需要設(shè)置一個(gè)標(biāo)志域tag 并以tag值為0或1來區(qū)分 尾指針和頭指針相同時(shí)的隊(duì)列狀態(tài)是 空 還是 滿 試編寫與此結(jié)構(gòu)相對應(yīng)的入隊(duì)列和出隊(duì)列的算法 并從時(shí)間和空間的角度討論設(shè)標(biāo)志和不設(shè)標(biāo)志這兩種方法的使用范圍 如當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素站的空間較多時(shí) 哪一種方法較好 defineMAXQSIZE100typedefstruct QElemType base intfront intrear inttag CyQueue StatusEnCyQueue CyQueue 隊(duì)列滿 EnCyQueue StatusDeCyQueue CyQueue DeCyQueue分析 當(dāng)循環(huán)隊(duì)列容量較小而隊(duì)列中每個(gè)元素占的空間較多時(shí) 此種表示方法可以節(jié)約較多的存儲空間 較有價(jià)值 判別讀入的字符序列是否為 回文 例如 abcdedcba或abccba是回文 由于回文的字符序列中的分界線不明確 因此無法判定字符序列的 中間位置 即只能按照回文的定義從字符的兩頭出發(fā)進(jìn)行判別 題3 31 算法的基本思想是 將依次讀入的字符分別插入棧和隊(duì)列 然后依次比較 棧頂 和 隊(duì)頭 的字符 然而 按照題目的要求 這個(gè)字符序列是從外部環(huán)境輸入的 為了在輸入結(jié)束的時(shí)候 同時(shí)能得到序列的 頭 和 尾 因此算法中 除了需要用一個(gè)棧之外 還需要一個(gè)隊(duì)列 Statusex331 若從終端依次輸入的字符序列是 回文 則返回TRUE 否則返回FALSEInitStack S InitQueue Q scanf ch while ch Push S ch EnQueue Q ch scanf ch state TRUE while StackEmpty 第四章串 4 12編寫一個(gè)實(shí)現(xiàn)串的置換操作Replace s T V 的算法 有兩種解法 1 重新為修改后的串分配空間 2 就在原串所在的空間進(jìn)行置換 先講第一種 S串 T串 V串 V串 pos pos sub i news串 sub 1 利用已知串的五種基本操作實(shí)現(xiàn)串的置換操作 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