【文章內(nèi)容簡(jiǎn)介】 試數(shù)據(jù)】 迷宮的測(cè)試數(shù)據(jù)如下：左上角(1，1)為入口，右下角(8，9)為出口。 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000【實(shí)現(xiàn)提示】計(jì)算機(jī)解迷宮通常用的是“窮舉求解“方法，即從人口出發(fā)，順著某一個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒(méi)有通路?？梢远S數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為(1，1)，出口點(diǎn)的下標(biāo)為(n，n)。為處理方便起見(jiàn)，可在迷宮的四周加一圈障礙。對(duì)于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通?！具x作內(nèi)容】(l) 編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路；(2) 以方陣形式輸出迷宮及其通路。ch3 串及其應(yīng)用本實(shí)習(xí)單元的目的是熟悉串類(lèi)型的實(shí)現(xiàn)方法和文本模式匹配方法,熟悉一般文字處理軟件的設(shè)計(jì)方法,較復(fù)雜問(wèn)題的分解求精方法。本實(shí)習(xí)單元的難度較大,在教學(xué)安排上可以靈活掌握完成此單元實(shí)習(xí)的時(shí)間。編程技術(shù)訓(xùn)練要點(diǎn):并行的模式匹配技術(shù)()。字符填充技術(shù)(,)。邏輯/物理概念隔離技術(shù)(GetAWord,)?；顓^(qū)操作技術(shù)()。不定長(zhǎng)對(duì)象的成塊存儲(chǔ)分配技術(shù)()。命令識(shí)別與分析技術(shù)(,)。串的動(dòng)態(tài)組織技術(shù)()。合理有效的錯(cuò)誤處理方法()。程序語(yǔ)法結(jié)構(gòu)基本分析技術(shù)().1. 文學(xué)研究助手【問(wèn)題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng),稱(chēng)為文學(xué)研究助手?！净疽蟆坑⑽男≌f(shuō)存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢,即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào),格式自行設(shè)計(jì)?！緶y(cè)試數(shù)據(jù)】以你的C源程序模擬英文小說(shuō),C語(yǔ)言的保留字集作為待統(tǒng)計(jì)的詞匯集?！緦?shí)現(xiàn)提示】約定小說(shuō)中的詞匯一律不跨行。這樣,每讀入一行,就統(tǒng)計(jì)每個(gè)詞在這行中的出現(xiàn)次數(shù)。出現(xiàn)位置所在行的行號(hào)可以用鏈表存儲(chǔ)。若某行中出現(xiàn)了不止一次,不必存多個(gè)相同的行號(hào)。如果讀者希望達(dá)到選做部分(1善和(2)所提出的要求,則首先應(yīng)把KMP算法改寫(xiě)成如下的等價(jià)形式,再將它推廣到多個(gè)模式的情形。i=1。j=1。while(i!=+1amp。amp。j!=){while(j!=0amp。amp。[i]!=[j])j=next[j]。 //j==[i]==[j]j++。i++。//每次進(jìn)入循環(huán)體,i只增加一次}【選作內(nèi)容】(1)模式匹配要基于KMP算法。(2)整個(gè)統(tǒng)計(jì)過(guò)程中只對(duì)小說(shuō)文字掃描一遍以提高效率。(3)假設(shè)小說(shuō)中的每個(gè)單詞或者從行首開(kāi)始,或者前置一個(gè)空格符。利用單詞匹配特點(diǎn)另寫(xiě)一個(gè)高效的統(tǒng)計(jì)程序,與KMP算法統(tǒng)計(jì)程序進(jìn)行效率比較。(4)推廣到更一般的模式集匹配問(wèn)題,并設(shè)待查模式串可以跨行(提示:定義操作GetAChar)。2. 文本格式化【問(wèn)題描述】輸入文件中含有待格式化〈或稱(chēng)為待排版〉的文本,它由多行的文字組成,例如一篇英文文章。每一行由一系列被一個(gè)或多個(gè)空格符所隔開(kāi)的字①組成,任何完整的字都沒(méi)有被分割在兩行(每行最后一個(gè)字與下一行的第一個(gè)字之間在邏輯上應(yīng)該由空格分開(kāi)),每行字符數(shù)不超過(guò)80。除了上述文本類(lèi)字符之外,還存在著起控制作用的字符:符號(hào)@指示它后面的正文在格式化時(shí)應(yīng)另起一段排放,即空一行,并在段首縮入8個(gè)字符位置。@自成一個(gè)字。一個(gè)文本格式化程序可以處理上述輸入文件,按照用戶(hù)指定的版面規(guī)格重排版面z實(shí)現(xiàn)頁(yè)內(nèi)調(diào)整、分段、分頁(yè)等文本處理功能,排版結(jié)果存入輸出文本文件中。試寫(xiě)一個(gè)這樣的程序。【基本要求】(1)輸出文件中字與字之間只留一個(gè)空格符,即實(shí)現(xiàn)多余空格符的壓縮。(2)在輸出文件中,任何完整的字仍不能分割在兩行,行尾不齊沒(méi)關(guān)系,但行首要對(duì)齊(即左對(duì)齊)。(3)如果所要求的每頁(yè)頁(yè)底所空行數(shù)不少于3,則將頁(yè)號(hào)印在頁(yè)底空行中第2行的中間位置上,否則不印。(4)版面要求的參數(shù)要包含：頁(yè)長(zhǎng)(PageLength)一一每頁(yè)內(nèi)文字(不計(jì)頁(yè)號(hào))的行數(shù)。頁(yè)寬(PageWedth)一一每行內(nèi)文字所占最大字符數(shù)。左空白(LeftMargin)一一每行文字前的固定空格數(shù)。頭長(zhǎng)(HeadingLength)一一每頁(yè)頁(yè)頂所空行數(shù)。腳長(zhǎng)(FootingLength)一一每頁(yè)頁(yè)底所空行數(shù)(含頁(yè)號(hào)行)。起始頁(yè)號(hào)(StartingPageNumber)一一首頁(yè)的頁(yè)號(hào)?！緶y(cè)試數(shù)據(jù)】略。注意在標(biāo)點(diǎn)之后加上空格符。【實(shí)現(xiàn)提示】可以設(shè):左空白數(shù)2+頁(yè)寬=160,即行印機(jī)最大行寬,從而只要設(shè)置這樣大的一個(gè)行緩沖區(qū)就足夠了,每加工完一行,就輸出一行。如果輸入文件和輸出文件不是由程序規(guī)定死,而是可由用戶(hù)指定,則有兩種做法:一是像其他參量一樣,將文件名交互地讀入字符串變量中。更好的方式是讓用戶(hù)通過(guò)命令行指定,具體做法依機(jī)器的操作系統(tǒng)而定。應(yīng)該首先實(shí)現(xiàn)GetAWord(w)這一操作,把諸如行尾處理、文件尾處理、多余空格符壓縮等一系列低級(jí)事務(wù)留給它處理,使系統(tǒng)的核心部分集中對(duì)付排版要求。每個(gè)參數(shù)都可以實(shí)現(xiàn)缺省值②設(shè)置。上述排版參數(shù)的缺省值可以分別取56,60,10,5,5和1。【選作內(nèi)容】(1)輸入文件名和輸出文件名要由用戶(hù)指定。(2)允許用戶(hù)指定是否右對(duì)齊,即增加一個(gè)參量右對(duì)齊否(RightJustifying),缺省值可設(shè)為y(yes)。右對(duì)齊指每行最后一個(gè)字的字尾要對(duì)齊,多余的空格要均勻分布在本行中各字之間。(3)實(shí)現(xiàn)字符填充(characterstuffing)技術(shù)。@作為分段控制符之后,限制了原文中不能有這樣的字?，F(xiàn)在去掉這一限制:如果原文中有這樣的字,改用兩個(gè)@并列起來(lái) 表示一個(gè)@字。當(dāng)然,如果原文中此符號(hào)夾在字中,就不必特殊處理了。(4)允許用戶(hù)自動(dòng)按多欄印出一頁(yè)。3. 簡(jiǎn)單行編輯程序【問(wèn)題描述】文本編輯程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具,實(shí)現(xiàn)對(duì)文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱(chēng)為行編輯程序。被編輯的文本文件可能很大,全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法既不經(jīng)濟(jì),也不總能實(shí)現(xiàn)。一種解決方法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存,稱(chēng)為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡(jiǎn)單的行編輯程序。設(shè)文件每行不超過(guò)320個(gè)字符,很少超過(guò)80個(gè)字符?！净疽蟆繉?shí)現(xiàn)以下4條基本編輯命令:(1) 行插入。格式:i行號(hào)回車(chē)文本.回車(chē)將文本插入活區(qū)中第行號(hào)行之后。(2) 行刪除。格式:d行號(hào)l[空格行號(hào)2]回車(chē)刪除活區(qū)中第行號(hào)l行(到第行號(hào)2行)。例如:d10和d1014。(3) 活區(qū)切換。格式n回車(chē)將活區(qū)寫(xiě)入輸出文件,并從輸入文件中讀入下一段,作為新的活區(qū)。(4) 活區(qū)顯示。格式:p回車(chē)逐頁(yè)地(每頁(yè)20行)顯示活區(qū)內(nèi)容,每顯示一頁(yè)之后請(qǐng)用戶(hù)決定是否繼續(xù)顯示以后備頁(yè)(如果存在)。印出的每一行要前置行號(hào)和一個(gè)空格符,行號(hào)固定占4位,增量為1。各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi),只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1,表示插入當(dāng)前屏幕中第一行之前,否則命令參數(shù)非法?！緶y(cè)試數(shù)據(jù)】自行設(shè)定,注意測(cè)試將活區(qū)刪空等特殊情況?！緦?shí)現(xiàn)提示】(1)設(shè)活區(qū)的大小用行數(shù)ActiveMULen(可設(shè)為100)來(lái)描述。考慮到文本文件行長(zhǎng)通常為正態(tài)分布,且峰值在60到70之間,用320ActiveMULen大小的字符數(shù)組實(shí)現(xiàn)存儲(chǔ)將造成大量浪費(fèi)?？梢砸詷?biāo)準(zhǔn)行塊為單位為各行分配存儲(chǔ),每個(gè)標(biāo)準(zhǔn)行塊可含81個(gè)字符。這些行塊可以組成一個(gè)數(shù)組,也可以利用動(dòng)態(tài)鏈表連接起來(lái)。一行文字可能占多個(gè)行塊。行尾可用一個(gè)特殊的ASCII字符(如(012)8)標(biāo)識(shí)。此外,還應(yīng)記住活區(qū)起始行號(hào)。行插入將引起隨后各行行號(hào)的順序下推。(2)初始化函數(shù)包括:請(qǐng)用戶(hù)提供輸入文件名(空串表示無(wú)輸入文件)和輸出文件名,兩者不能相同。然后盡可能多地從輸入文件中讀入各行,但不超過(guò)ActiveMULenLX的值可以自定,例如20。(3)在執(zhí)行行插入命令的過(guò)程中,每接收到一行時(shí)都要檢查活區(qū)大小是否已達(dá)ActiveMaxLen。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過(guò)ActiveMaxLen應(yīng)將插入點(diǎn)之前的活區(qū)部分中第一行輸出到輸出文件中。若插入點(diǎn)為第一行之前,則只得將新插入的這一行輸出。(4)若輸入文件尚未讀完,活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部,以保持閱讀連續(xù)性。否則,它意味著結(jié)束編輯或開(kāi)始編輯另一個(gè)文件。(5)可令前三條命令執(zhí)行后自動(dòng)調(diào)用活區(qū)顯示。【選作內(nèi)容】(1)對(duì)于命令格式非法等一切錯(cuò)誤作嚴(yán)格檢查和適當(dāng)處理。(2)加入更復(fù)雜的編輯操作,如對(duì)某行進(jìn)行串替換；在活區(qū)內(nèi)進(jìn)行模式匹配等，格式可以為S行號(hào)@串1@串2回車(chē)和m串回車(chē)。4. 串基本操作的演示【問(wèn)題描述】如果語(yǔ)言沒(méi)有把串作為一個(gè)預(yù)先定義好的基本類(lèi)型對(duì)待,又需要用該語(yǔ)言寫(xiě)一個(gè)涉及串操作的軟件系統(tǒng)時(shí),用戶(hù)必須自己實(shí)現(xiàn)串類(lèi)型。試實(shí)現(xiàn)串類(lèi)型,并寫(xiě)一個(gè)串的基本操作的演示系統(tǒng)。【基本要求】,實(shí)現(xiàn)串抽象數(shù)據(jù)類(lèi)型的其余基本操作(不使用C語(yǔ)言本身提供的串函數(shù))。參數(shù)合法性檢查必須嚴(yán)格。利用上述基本操作函數(shù)構(gòu)造以下系統(tǒng):它是一個(gè)命令解釋程序,循環(huán)往復(fù)地處理用戶(hù)鍵入的每一條命令,直至終止程序的命令為止。命令定義如下:(1)賦值。 格式: A 串標(biāo)識(shí) 回車(chē)用串標(biāo)識(shí)所表示的串的值建立新串,并顯示新串的內(nèi)部名和串值。例:A ‘Hi!’(2)判相等。格式: E 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē)若兩串相等,則顯示EQUAL,否則顯示UNEQUAL。(3)聯(lián)接。 格式:C 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē)將兩串拼接產(chǎn)生結(jié)果串,它的內(nèi)部名和串值都顯示出來(lái)。(4)求長(zhǎng)度。格式:L〈串標(biāo)識(shí) 回車(chē)顯示串的長(zhǎng)度。(5)求子串。格式:S 串標(biāo)識(shí) +數(shù)1+數(shù)2回車(chē)如果參數(shù)合法,則顯示子串的內(nèi)部名和串值。數(shù)不帶正負(fù)號(hào)。(6)子串定位。格式:I 串標(biāo)識(shí)1 串標(biāo)識(shí)2 回車(chē)顯示第二個(gè)串在第一個(gè)串中首次出現(xiàn)時(shí)的起始位置。(7)串替換。格式: R 串標(biāo)識(shí)1 串標(biāo)識(shí)2 串標(biāo)識(shí)3 回車(chē)將第一個(gè)串中所有出現(xiàn)的第二個(gè)串用第三個(gè)串替換,顯示結(jié)果串的內(nèi)部名和串值,原串不變。(8)顯示。格式:P 回車(chē)顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對(duì)照表。(9)刪除。格式:D 內(nèi)部名 回車(chē)刪除該內(nèi)部名對(duì)應(yīng)的串,即賦值的逆操作。(10)退出。格式:Q 回車(chē)結(jié)束程序的運(yùn)行。在上述命令中,如果一個(gè)自變量是串,則應(yīng)首先建立它?；静僮骱瘮?shù)的結(jié)果(即函數(shù)值)如果是一個(gè)串,則應(yīng)在尚未分配的區(qū)域內(nèi)新辟空間存放。【測(cè)試數(shù)據(jù)】自定。但要包括以下幾組:(1)E ‘’ ‘’回車(chē),應(yīng)顯示EQUAL。(2)E ‘a(chǎn)bc’ ‘a(chǎn)bcd’回車(chē),應(yīng)顯示UNEQUAL。(3)C ‘ ‘ ‘ ‘ 回車(chē),應(yīng)顯示。(4)I ‘a(chǎn)’ ‘’ 回車(chē),應(yīng)報(bào)告:參數(shù)非法。(5)R ‘a(chǎn)aa’ ‘a(chǎn)a’ ‘b’回車(chē),應(yīng)顯示39。ba’(6)R ‘a(chǎn)aabc’ ‘a(chǎn)’ ‘a(chǎn)ab’回車(chē),應(yīng)顯示’aabaabaabbc’。(7)R ‘Faaaaaaaa’ ‘a(chǎn)aaa’ ‘a(chǎn)b’,回車(chē),應(yīng)顯示’abab’?！緦?shí)現(xiàn)提示】【選作內(nèi)容】(1) 串頭表改用單鏈表實(shí)現(xiàn)。(2) 對(duì)命令的格式(即語(yǔ)法)作嚴(yán)格檢查,使系統(tǒng)既能處理正確的命令,也能處理錯(cuò)誤的命令。注意,語(yǔ)義檢查(如某內(nèi)部名對(duì)應(yīng)的串已被刪除而無(wú)定義等)和基本操作參數(shù)合法性檢查仍應(yīng)留給基本操作去做。(3) 支持串名。將串名(可設(shè)不超過(guò)6個(gè)字符)存于串頭表中。命令(1)(3)(5)要增加命令參數(shù)結(jié)果串名。命令(7)中的串標(biāo)識(shí)1 改為串名,并用此名作為結(jié)果串名,刪除原被替串標(biāo)識(shí),用串名代替串標(biāo)識(shí)定義和命令解釋中的內(nèi)部名。每個(gè)命令執(zhí)行完畢時(shí)立即自動(dòng)刪除無(wú)名串。5. 程序分析【問(wèn)題描述】讀入一個(gè)C程序,統(tǒng)計(jì)程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個(gè)數(shù)和平均行數(shù),并利用統(tǒng)計(jì)信息分析評(píng)價(jià)該程序的風(fēng)格。【基本要求】(1) 把 C 程序文件按字符順序讀入源程序。(2) 邊讀入程序,邊識(shí)別統(tǒng)計(jì)代碼行、注釋行和空行,同時(shí)還要識(shí)別函數(shù)的開(kāi)始和結(jié)束,以便統(tǒng)計(jì)其個(gè)數(shù)和平均行數(shù)。(3) 程序的風(fēng)格評(píng)價(jià)分為代碼、注釋和空行三個(gè)方面。每個(gè)方面分為 A,B,C 和 D 四個(gè)等級(jí) , 等級(jí)的劃分標(biāo)準(zhǔn)是 : A級(jí)B級(jí)C級(jí)D級(jí) 代碼(函數(shù)平均長(zhǎng)度)10~15行8~9或16~20行5~7或21~24行5或24行 注釋(占總行數(shù)比率)15~25%10~14或26~30%5~9或31~35%5%或35% 空行(占總行數(shù)比率)15~25%10~14或26~30%5~9或31~35%5%或35%【測(cè)試數(shù)據(jù)】先對(duì)較小的程序進(jìn)行分析。當(dāng)你的程序能正確運(yùn)行時(shí),對(duì)你的程序本身進(jìn)行分析。【實(shí)現(xiàn)提示】為了實(shí)現(xiàn)的方便,可作以下約定:(1) 頭兩個(gè)字符是 FFF 的行稱(chēng)為注釋行(該行不含語(yǔ)句)。除了空行和注釋行外,其余均為代碼行(包括類(lèi)型定義、變量定義和函數(shù)頭)。(2) 每個(gè)函數(shù)代碼行數(shù)(除去空行和注釋行)稱(chēng)為該函數(shù)的長(zhǎng)度。(3) 每行最多只有一個(gè){ 、}、switch 和struet(便于識(shí)別函數(shù)的結(jié)束行)。【選作內(nèi)容】(1) 報(bào)告函數(shù)的平均長(zhǎng)度。