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