XX年數(shù)據(jù)結(jié)構課程設計題目及報告范例.doc

1. 運動會分數(shù)統(tǒng)計【問題描述】參加運動會的n個學校編號為1n。比賽分成m個男子項目和w個女子項目，項目編號分別為1m和m+1m+w。由于各項目參加人數(shù)差別較大，有些項目取前五名，得分順序為7，5，3，2，1；還有些項目只取前三名，得分順序為5，3，2。寫一個統(tǒng)計程序產(chǎn)生各種成績單和得分報表?！净疽蟆?) 可以輸入各個項目的前三名或前五名的成績；2) 能統(tǒng)計各學校總分，3) 可以按學校編號或名稱、學?？偡帧⒛信畧F體總分排序輸出；4) 可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W校。5) 數(shù)據(jù)存入文件并能隨時查詢 6) 規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱輸出形式：有中文提示，各學校分數(shù)為整型。界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。存儲結(jié)構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。測試數(shù)據(jù)：【測試數(shù)據(jù)】要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。例如，對于n=4，m=3，w =2，編號為奇數(shù)的項目取前五名，編號為偶數(shù)的項目取前三名，設計一組實例數(shù)據(jù)?！緦崿F(xiàn)提示】可以假設n20，m30，w20，姓名長度不超過 20 個字符。每個項目結(jié)束時，將其 編號、類型符(區(qū)分取前五名還是前三名) 輸入，并按名次順序輸入運動員姓名、校名(和成 績)?！具x作內(nèi)容】 允許用戶指定某項目采取其他名次取法。2. 集合的并、交和差運算【問題描述】編制一個能演示執(zhí)行集合的并、交和差運算的程序?！净疽蟆?1) 集合的元素限定為小寫字母字符 a.z 。(2) 演示程序以用戶和計算機的對話方式執(zhí)行?！緶y試數(shù)據(jù)】(1)Set1=magazine，Set2=paper，Set1Set2=aegimnprz，Setl Set2=ae，Set1-Set2=gimnz。(2)Set1= 012oper4a6tion89，Set2=error data，Set1Set2=adeinoprt，Setl Set2=aeort，Set1-Set2=inp?！緦崿F(xiàn)提示】以有序鏈表表示集合。【選作內(nèi)容】(1) 集合的元素判定和子集判定運算。(2) 求集合的補集。(3) 集合的混合運算表達式求值。(4) 集合的元素類型推廣到其他類型 ， 甚至任意類型。3. 一元稀疏多項式計算器【問題描述】設計一個一元稀疏多項式簡單計算器?！净疽蟆恳辉∈瓒囗検胶唵斡嬎闫鞯幕竟δ苁牵?1) 輸入并建立多項式 ；(2) 輸出多項式，輸出形式為整數(shù)序列：n，cl，el，c2，e2，cn，en，其中n是多項式的項數(shù)，ci 和ei，分別是第 i 項的系數(shù)和指數(shù)，序列按指數(shù)降序排列；(3) 多項式a和b相加，建立多項式a +b；(4) 多項式a和b相減，建立多項式a -b ?！緶y試數(shù)據(jù)】(1)(2x+5x83.1x11) + (75x8+11x9)=(3.lx11+11x9+2x+7)(2)(6x-3x+4.4x21.2x9) (-6x-3+5.4x2x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x)(3)(1 +x + x2+x3+x4+x5)+(-x3x4)=(1+x+x2+x5) (4)(x+x3)+(-xx3)=0(5)(x+x100)+(x100 +x200)=(x+2x100+x200)(6)(x+x2+x3)+0=x+x2+x3(7) 互換上述測試數(shù)據(jù)中的前后兩個多項式【實現(xiàn)提示】用帶表頭結(jié)點的單鏈表存儲多項式?！具x作內(nèi)容】(1) 計算多項式在x處的值。(2) 求多項式 a 的導函數(shù) 。(3) 多項式a和b相乘，建立乘積多項式ab 。(4) 多項式的輸出形式為類數(shù)學表達式。例如 ，多項式 -3x8+6x318 的輸出形式為，x15+(8)x714的輸出形式為。注意，數(shù)值為1的非零次項的輸出形式中略去系數(shù)1，如項1x8的輸出形式為x8，項 1x3的輸出形式為x3。(5) 計算器的仿真界。4. 池塘夜降彩色雨【問題描述】設計一個程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點飄飄灑灑地從天而降， 滴滴入水有聲，濺起圈圈微瀾。 【基本要求】(1) 雨點的空中出現(xiàn)位置、降范過程的可見程度、入水位置、顏色、最大水圈等，都是隨機確定的 ；(2) 多個雨點按照各自的隨機參數(shù)和存在狀態(tài)，同時演示在屏幕上?！緶y試數(shù)據(jù)】適當調(diào)整控制雨點密度、最大水圈和狀態(tài)變化的時間間隔等參數(shù)?！緦崿F(xiàn)提示】(1) 每個雨點的存在周期可分為三個階段：從天而降、入水有聲和圈圈微瀾，需要一個記錄存儲其相關參數(shù)、當前狀態(tài)和下一狀態(tài)的更新時刻。(2) 在圖形狀態(tài)編程。雨點下降的可見程度應是斷斷續(xù)續(xù)、依稀可見；圈圈水波應是由里至外逐漸擴大和消失。(3) 每個雨點發(fā)生時，生成其記錄，并預置下一個雨點的發(fā)生時間。(4) 用一個適當?shù)慕Y(jié)構管理當前存在的雨點，使系統(tǒng)能利用它按時更新每個雨點的狀態(tài)，一旦有雨點的水圈全部消失，就從結(jié)構中刪去?！具x作內(nèi)容】(1) 增加“電閃雷鳴”景象。(2) 增加風的效果，展現(xiàn)“風雨飄搖”的情景。(3) 增加雨點密度的變化：時而“和風細雨”， 時而“暴風驟雨”。(4) 將“池塘”改為“荷塘”，雨點滴在荷葉上的效果是濺起四散的水珠，響聲也不同。5. 銀行業(yè)務模擬【問題描述】客戶業(yè)務分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。銀行有兩個服務窗口，相應地有兩個隊列?？蛻舻竭_銀行后先排第一個隊。處理每個客戶業(yè)務時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個隊等候，直至滿足時才離開銀行；否則業(yè)務處理完后立刻離開銀行。每接待完一個第二種業(yè)務的客戶，則順序檢查和處理(如果可能)第二個隊列中的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶(第二種業(yè)務)被接待之前的數(shù)額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查(因為此時已不可能還有能滿足者)轉(zhuǎn)而繼續(xù)接待第一個隊列的客戶。任何時刻都只開一個窗口。假設檢查不需要時間。營業(yè)時間結(jié)束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務的事件驅(qū)動模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗留的平均時間?！净疽蟆坷脛討B(tài)存儲結(jié)構實現(xiàn)模擬。【測試數(shù)據(jù)】一天營業(yè)開始時銀行擁有的款額為10000(元)，營業(yè)時間為600(分鐘)。其他模擬參量自定，注意測定兩種極端的情況：一是兩個到達事件之間的間隔時間很短，而客戶的交易時間很長，另一個恰好相反，設置兩個到達事件的間隔時間很長，而客戶的交易時間很短?！緦崿F(xiàn)提示】事件有兩類：到達銀行和離開銀行。初始時銀行現(xiàn)存資金總額為total。開始營業(yè)后的第一今事件是客戶到達，營業(yè)時間從0到closetime。到達事件發(fā)生時隨機地設置此客戶的交易時間和距下一到達事件之間的時間間隔。每個客戶要辦理的款額也是隨機確定的，用負值和正值分別表示第一類和第二類業(yè)務。變量total，closetime以及上述兩個隨機量的上下界均交互地從終端讀入，作為模擬參數(shù)。兩個隊列和一個事件表均要用動態(tài)存儲結(jié)構實現(xiàn)。注意弄清應該在什么條件下設置離開事件，以及第二個隊列用怎樣的存儲結(jié)構實現(xiàn)時可以獲得較高的效率。注意：事件表是按時間順序有序的?！具x作內(nèi)容】自己實現(xiàn)動態(tài)數(shù)據(jù)類型。例如對于客戶結(jié)點，定義pool為CustNodepoolfMAX；/ 結(jié)構類型CustNode含四個域：aITHIne，durtime，amount，next或者定義四個同樣長的，以上述域名為名字的數(shù)組。初始時，將所有分量的next域鏈接起來，形成一個靜態(tài)鏈找，設置一個樓頂元素下標指示量top，top=0表示找空。動態(tài)存儲分配函數(shù)可以取名為myMalloc，其作用是出錢，將錢頂元素的下標返回。若返回的值為0，則表示無空間可分配。歸還函數(shù)可取名為myFree，其作用是把該分量入錢。用FOR-TRAN和BASIC等語言實現(xiàn)時只能如此地自行組織。6. 馬踏棋盤【問題描述】 設計一個國際象棋的馬踏遍棋盤的演示程序?！净疽蟆繉ⅠR隨機放在國際象棋的88棋盤Board88的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤上全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個88的方陣，輸出之。7. 魔王語言解釋【問題描述】有一個魔王總是使用自己的一種非常精練而抽象的語言講話，沒有人能昕得懂，但他的語言是可以逐步解釋成人能聽懂的語言，因為他的語言是由以下兩種形式的規(guī)則由人的語言逐步抽象上去的：(1) (2) 在這兩種形式中，從左到右均表示解釋。試寫一個魔王語言的解釋系統(tǒng)，把他的話解釋成人能聽得懂的話?！净疽蟆坑孟率鰞蓷l具體規(guī)則和上述規(guī)則形式(2)實現(xiàn)。設大寫字母表示魔王語言的詞匯；小寫字母表示人的語言詞匯；希臘字母表示可以用大寫字母或小寫字母代換的變量。魔王語言可含人的詞匯。(1) (2) 【測試數(shù)據(jù)】B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應關系，則魔王說的話是“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。tdsaezgxnh天地上一只鵝追趕下蛋恨【實現(xiàn)提示】將魔王的語言自右至左進棧，總是處理棧頂字符。若是開括號，則逐一出棧，將字母順序入隊列，直至閉括號出棧，并按規(guī)則要求逐一出隊列再處理后入棧。其他情形較簡單，請讀者思考應如何處理。應首先實現(xiàn)棧和隊列的基本操作?！具x作內(nèi)容】(1)由于問題的特殊性，可以實現(xiàn)棧和隊列的順序存儲空間共享。(2)代換變量的數(shù)目不限，則在程序開始運行時首先讀入一組第一種形式的規(guī)則，而不是把規(guī)則固定在程序中(第二種形式的規(guī)則只能固定在程序中)。8. 航空客運訂票系統(tǒng)【問題描述】航空客運訂票的業(yè)務活動包括：查詢航線、客票預訂和辦理退票等。試設計一個航空客運訂票系統(tǒng)，以使上述業(yè)務可以借助計算機來完成。【基本要求】(1)每條航線所涉及的信息有：終點站名、航班號、飛機號、飛行周日(星期幾)、乘員定額、余票量、已訂票的客戶名單(包括姓名、訂票量、艙位等級1，2或3)以及等候替補的客戶名單(包括姓名、所需票量)；(2)系統(tǒng)能實現(xiàn)的操作和功能如下：錄入：可以錄入航班情況，全部數(shù)據(jù)可以只放在內(nèi)存中，最好存儲在文件中；查詢航線：根據(jù)旅客提出的終點站名輸出下列信息：航班號、飛機號、星期幾飛行，最近一天航班的日期和余票額；承辦訂票業(yè)務：根據(jù)客戶提出的要求(航班號、訂票數(shù)額)查詢該航班票額情況，若尚有余票，則為客戶辦理訂票手續(xù)，輸出座位號；若已滿員或余票額少于訂票額，則需重新詢問客戶要求。若需要，可登記排隊候補；承辦退票業(yè)務：根據(jù)客戶提供的情況(日期、航班)，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊候補，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊候補的客戶?！緶y試數(shù)據(jù)】由讀者自行指定。【實現(xiàn)提示】兩個客戶名單可分別由線性表和隊列實現(xiàn)。為查找方便，已訂票客戶的線性表應按客戶姓名有序，并且，為插入和刪除方便，應以鏈表作存儲結(jié)構。由于預約人數(shù)無法預計，隊列也應以鏈表作存儲結(jié)構。整個系統(tǒng)需匯總各條航線的情況登錄在一張線性表上，由于航線基本不變，可采用順序存儲結(jié)構，并按航班有序或按終點站名有序。每條航線是這張表上的一個記錄，包含上述8個域、其中乘員名單域為指向乘員名單鏈表的頭指針，等候替補的客戶名單域為分別指向隊頭和隊尾的指針?！具x作內(nèi)容】當客戶訂票要求不能滿足時，系統(tǒng)可向客戶提供到達同一目的地的其他航線情況。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務項目。9. 藥店的藥品銷售統(tǒng)計系統(tǒng)【問題描述】 設計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名。 【基本要求】 在本設計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。10. 文學研究助手【問題描述】文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng),稱為文學研究助手?！净疽蟆坑⑽男≌f存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢,即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號,格式自行設計?！緶y試數(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!=s.curlen+1&j!=t.curlerl十1)while(j!=0&s.chi!=t.chj)j=nextj; /j=O或s.chi=t.chjj+;i+;/每次進入循環(huán)體,i只增加一次【選作內(nèi)容】(1)模式匹配要基于KMP算法。(2)整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。(3)假設小說中的每個單詞或者從行首開始,或者前置一個空格符。利用單詞匹配特點另寫一個高效的統(tǒng)計程序,與KMP算法統(tǒng)計程序進行效率比較。(4)推廣到更一般的模式集匹配問題,并設待查模式串可以跨行(提示:定義操作GetAChar)。11. 文本格式化【問題描述】輸入文件中含有待格式化或稱為待排版的文本,它由多行的文字組成,例如一篇英文文章。每一行由一系列被一個或多個空格符所隔開的字組成,任何完整的字都沒有被分割在兩行(每行最后一個字與下一行的第一個字之間在邏輯上應該由空格分開),每行字符數(shù)不超過80。除了上述文本類字符之外,還存在著起控制作用的字符:符號指示它后面的正文在格式化時應另起一段排放,即空一行,并在段首縮入8個字符位置。自成一個字。一個文本格式化程序可以處理上述輸入文件,按照用戶指定的版面規(guī)格重排版面z實現(xiàn)頁內(nèi)調(diào)整、分段、分頁等文本處理功能,排版結(jié)果存入輸出文本文件中。試寫一個這樣的程序?！净疽蟆?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ù)】略。注意在標點之后加上空格符。【實現(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)技術。作為分段控制符之后,限制了原文中不能有這樣的字。現(xiàn)在去掉這一限制:如果原文中有這樣的字,改用兩個并列起來表示一個字。當然,如果原文中此符號夾在字中,就不必特殊處理了。(4)允許用戶自動按多欄印出一頁。12. 簡單行編輯程序【問題描述】文本編輯程序是利用計算機進行文字加工的基本軟件工具,實現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大,全部讀入編輯程序的數(shù)據(jù)空間(內(nèi)存)的作法既不經(jīng)濟,也不總能實現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存,稱為活區(qū)。試按照這種方法實現(xiàn)一個簡單的行編輯程序。設文件每行不超過320個字符,很少超過80個字符?！净疽蟆繉崿F(xiàn)以下4條基本編輯命令:(1) 行插入。格式:i.將插入活區(qū)中第行之后。(2) 行刪除。格式:d刪除活區(qū)中第行(到第行)。例如: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ù)包括:請用戶提供輸入文件名(空串表示無輸入文件)和輸出文件名,兩者不能相同。然后盡可能多地從輸入文件中讀入各行,但不超過ActiveMULen-LX的值可以自定,例如20。(3)在執(zhí)行行插入命令的過程中,每接收到一行時都要檢查活區(qū)大小是否已達ActiveMaxLen。如果是,則為了在插入這一行之后仍保持活區(qū)大小不超過ActiveMaxLen應將插入點之前的活區(qū)部分中第一行輸出到輸出文件中;若插入點為第一行之前,則只得將新插入的這一行輸出。(4)若輸入文件尚未讀完,活區(qū)切換命令可將原活區(qū)中最后幾行留在活區(qū)頂部,以保持閱讀連續(xù)性;否則,它意味著結(jié)束編輯或開始編輯另一個文件。(5)可令前三條命令執(zhí)行后自動調(diào)用活區(qū)顯示?！具x作內(nèi)容】(1)對于命令格式非法等一切錯誤作嚴格檢查和適當處理。(2)加入更復雜的編輯操作,如對某行進行串替換；在活區(qū)內(nèi)進行模式匹配等，格式可以為S和m。13. 串基本操作的演示【問題描述】如果語言沒有把串作為一個預先定義好的基本類型對待,又需要用該語言寫一個涉及串操作的軟件系統(tǒng)時,用戶必須自己實現(xiàn)串類型。試實現(xiàn)串類型,并寫一個串的基本操作的演示系統(tǒng)?！净疽蟆吭诮炭茣?.2.2節(jié)用堆分配存儲表示實現(xiàn)HString串類型的最小操作子集的基礎上,實現(xiàn)串抽象數(shù)據(jù)類型的其余基本操作(不使用C語言本身提供的串函數(shù))。參數(shù)合法性檢查必須嚴格。利用上述基本操作函數(shù)構造以下系統(tǒng):它是一個命令解釋程序,循環(huán)往復地處理用戶鍵入的每一條命令,直至終止程序的命令為止。命令定義如下:(1)賦值。 格式: A 用所表示的串的值建立新串,并顯示新串的內(nèi)部名和串值。例:A Hi!(2)判相等。格式: E 若兩串相等,則顯示EQUAL,否則顯示UNEQUAL。(3)聯(lián)接。 格式:C 將兩串拼接產(chǎn)生結(jié)果串,它的內(nèi)部名和串值都顯示出來。(4)求長度。格式:L串標識 顯示串的長度。(5)求子串。格式:S +如果參數(shù)合法,則顯示子串的內(nèi)部名和串值。不帶正負號。(6)子串定位。格式:I 顯示第二個串在第一個串中首次出現(xiàn)時的起始位置。(7)串替換。格式: R 將第一個串中所有出現(xiàn)的第二個串用第三個串替換,顯示結(jié)果串的內(nèi)部名和串值,原串不變。(8)顯示。格式:P 顯示所有在系統(tǒng)中被保持的串的內(nèi)部名和串值的對照表。(9)刪除。格式:D 刪除該內(nèi)部名對應的串,即賦值的逆操作。(10)退出。格式:Q 結(jié)束程序的運行。在上述命令中,如果一個自變量是串,則應首先建立它?；静僮骱瘮?shù)的結(jié)果(即函數(shù)值)如果是一個串,則應在尚未分配的區(qū)域內(nèi)新辟空間存放。【測試數(shù)據(jù)】自定。但要包括以下幾組:(1)E ,應顯示EQUAL。(2)E abcabcd,應顯示UNEQUAL。(3)C ,應顯示。(4)I a ,應報告:參數(shù)非法。(5)R aaa aa b,應顯示ba(6)R aaabc a aab,應顯示aabaabaabbc。(7)R Faaaaaaaa aaaaab,應顯示abab。【實現(xiàn)提示】【選作內(nèi)容】(1) 串頭表改用單鏈表實現(xiàn)。(2) 對命令的格式(即語法)作嚴格檢查,使系統(tǒng)既能處理正確的命令,也能處理錯誤的命令。注意,語義檢查(如某內(nèi)部名對應的串已被刪除而無定義等)和基本操作參數(shù)合法性檢查仍應留給基本操作去做。(3) 支持串名。將串名(可設不超過6個字符)存于串頭表中。命令(1)(3)(5)要增加命令參數(shù);命令(7)中的 改為,并用此名作為結(jié)果串名,刪除原被替串標識,用代替定義和命令解釋中的內(nèi)部名。每個命令執(zhí)行完畢時立即自動刪除無名串。14. 程序分析【問題描述】讀入一個C程序,統(tǒng)計程序中代碼、注釋和空行的行數(shù)以及函數(shù)的個數(shù)和平均行數(shù),并利用統(tǒng)計信息分析評價該程序的風格?！净疽蟆?1) 把 C 程序文件按字符順序讀入源程序;(2) 邊讀入程序,邊識別統(tǒng)計代碼行、注釋行和空行,同時還要識別函數(shù)的開始和結(jié)束,以便統(tǒng)計其個數(shù)和平均行數(shù)。(3) 程序的風格評價分為代碼、注釋和空行三個方面。每個方面分為 A,B,C 和 D 四個等級 , 等級的劃分標準是 : A級B級C級D級 代碼(函數(shù)平均長度)1015行89或1620行57或2124行24行 注釋(占總行數(shù)比率)1525%1014或2630%59或3135%35% 空行(占總行數(shù)比率)1525%1014或2630%59或3135%35%【測試數(shù)據(jù)】先對較小的程序進行分析。當你的程序能正確運行時,對你的程序本身進行分析?！緦崿F(xiàn)提示】為了實現(xiàn)的方便,可作以下約定:(1) 頭兩個字符是 FFF 的行稱為注釋行(該行不含語句)。除了空行和注釋行外,其余均為代碼行(包括類型定義、變量定義和函數(shù)頭)。(2) 每個函數(shù)代碼行數(shù)(除去空行和注釋行)稱為該函數(shù)的長度。(3) 每行最多只有一個 、switch 和struet(便于識別函數(shù)的結(jié)束行)?！具x作內(nèi)容】(1) 報告函數(shù)的平均長度。(2) 找出最長函數(shù)及其在程序中的位置。(3) 允許函數(shù)的嵌套定義,報告最大的函數(shù)嵌套深度。15. 稀疏矩陣運算器【問題描述】稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用 稀疏 特點進行存儲和計算可以大大 節(jié)省存儲空間 , 提高計算效率。實現(xiàn)一個能進行稀疏矩陣基本運算的運算器?！净疽蟆恳詭羞壿嬫溄有畔⒌娜M順序表表示稀疏矩陣,實現(xiàn)兩個矩陣相加、相減和相乘的運算。稀疏矩陣的輸入形式采用三元組表示 , 而運算結(jié)果的矩陣則以通常的陣列形式列出。【實現(xiàn)提示】1. 首先應輸入矩陣的行數(shù)和列數(shù) , 并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否相匹配?？稍O矩陣的行數(shù)和列數(shù)均不超過 20 。2. 程序可以對三元組的輸入順序加以限制 , 例如 , 按行優(yōu)先。注意研究教科書 5.3.2節(jié)中的算法 , 以便提高計算效率。3. 在用三元組表示稀疏矩陣時 , 相加或相減所得結(jié)果矩陣應該另生成 , 乘積矩陣也 可用二維數(shù)組存放。【選作內(nèi)容】1. 按教科書 5.3.2 節(jié)中的描述方法 , 以十字鏈表表示稀疏矩陣。2. 增添矩陣求逆的運算 , 包括不可求逆的情況。在求逆之前 , 先將稀疏矩陣的內(nèi)部表示改為十字鏈表。16. 多維數(shù)組【問題描述】設計并模擬實現(xiàn)整型多維數(shù)組類型?！?基本要求】盡管 C 等程序設計語言已經(jīng)提供了多維數(shù)組 , 但在某些情況下 , 定義用戶所需的多維數(shù)組很有用的。通過設計并模擬實現(xiàn)多維數(shù)組類型 , 可以深刻理解和掌握多維數(shù)組。整型多維數(shù)組應具有以下基本功能 :(1) 定義整型多維數(shù)組類型 , 各維的下標是任意整數(shù)開始的連續(xù)整數(shù) ;(2) 下標變量賦值 , 執(zhí)行下標范圍檢查 ;(3 同類型數(shù)組賦值 ;(4) 子數(shù)組賦值 , 例如 ,a1.n=a 2.n+1;a2.43.5=b1.32.4; (5) 確定數(shù)組的大小?！?測試數(shù)據(jù)】由讀者指定。【實現(xiàn)提示】各基本功能可以分別用函數(shù)模擬實現(xiàn) , 應仔細考慮函數(shù)參數(shù)的形式和設置。 定義整型多維數(shù)組類型時 , 其類型信息可以存儲在如下定義的類型的記錄中：define MaxDim 5Typedef structint dim , BoundPtr lower ,Upper;ConstPtr constants;)NArray,*NarrayPtr;整型多維數(shù)組變量的存儲結(jié)構類型可定義為:Typedef structElemType *elem;Int num;NArrayType TypeRecord;NArrayType;【選作內(nèi)容】(1) 各維的下標是任意字符開始的連續(xù)字符。(2) 數(shù)組初始化。(3) 可修改數(shù)組的下標范圍。 17. 簡單LISP算術表達式計算器【問題描述】設計一個簡單的 LISP 算術表達式計算器。簡單 LISP 算術表達式(以下簡稱表達式)定義如下:(1) 定義一個自然數(shù)(2)(運算符 表達式 表達式)例如,6,(+45),(+(+25)8) 都是表達式,其值分別為6,9和15?！净疽蟆繉崿F(xiàn)LISP加法表達式的求值?！緶y試數(shù)據(jù)】6,(+45),(+(+25)8),(+2(+58),(+(+(+12)(+34)(+(+56)(+78)【 實現(xiàn)提示】寫一個遞歸函數(shù):int Evaluate(FILE * CharFile)字符文件 CharFile 的每行是一個如上定義的表達式。每讀入CharFile 的一行,求出并返回表達式的值?？梢栽O計以下輔助函數(shù)status isNumber(char ReadInChar); /視ReadInchar 是否是數(shù)字而返回 TRUE 或 FALSE 。int TurnToInteger(char IntChar); / 將字符0.9 轉(zhuǎn)換為整數(shù) 0.9【選做內(nèi)容】(1) 標準整數(shù)類型的 LISP 加法表達式的求值。(2) 標準整數(shù)類型的 LISP 四則運算表達式的求值。(3) LISP 算術表達式的語法檢查。18. 重言式判別【問題描述】一個邏輯表達式如果對于其變元的任一種取值都為真，則稱為重言式；反之，如果對于其變元的任一種取值都為假，則稱為矛盾式；然而，更多的情況下，既非重言式，也非矛盾式。試寫一個程序，通過真值表判別一個邏輯表達式屬于上述哪一類?！净疽蟆?1) 邏輯表達式從終端輸入，長度不超過一行。邏輯運算符包括 |，& 和 ，分別表示或、與和非，運算優(yōu)先程度遞增，但可由括號改變，即括號內(nèi)的運算優(yōu)先。邏輯變元 為大寫字母。表達式中任何地方都可以含有多個空格符。(2) 若是重言式或矛盾式，可以只顯示True forever，或False forever，否則顯示 Satisfactible 以及變量名序列，與用戶交互。若用戶對表達式中變元取定一組值，程序就求出并顯示邏輯表達式的值。【測試數(shù)據(jù)】(1) (A|A)&(B|B)(2) (A&A)&C(3) A|B|C|D|E|A(4) A&B&C&B(5) (A|B)&(A|B)(6) A&B|A&B;O ,0;0,1;1,0;1,1 。19. 哈夫曼編/譯碼器【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成 本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼(復原)。對于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個完整的編 /譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)?！净疽蟆恳粋€完整的系統(tǒng)應具有以下功能：(1)I：初始化(Initialization)。從終端讀入字符集大小n , 以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。(2)E：編碼(Encoding)。利用已建好的哈夫曼樹(如不在內(nèi)存，則從文件hfmTree中讀人)，對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。(3)D: 譯碼(Decoding)。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進行譯碼，結(jié)果存入文件TextFile中。(4)P：打印代碼文件(Print)。將文件CodeFile以緊湊格式顯示在終端上，每行 50 個代碼。同時將此字符形式的編碼文件寫入文件 CodePrin 中。(5)T：打印哈夫曼樹(Tree printing)。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表形式)顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數(shù)據(jù)】(1)利用教科書例 6-2 中的數(shù)據(jù)調(diào)試程序。(2)用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹 , 并實現(xiàn)以下報文的編碼和譯碼：THIS PROGRAM IS MY FAVORITE。字符ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161【選作內(nèi)容】(1)上述文件CodeFile中的每個0或1實際上占用了一個字節(jié)的空間，只起到示意或模擬的作用。為最大限度地利用編碼存儲能力，試改寫你的系統(tǒng)，將編碼結(jié)果以二進制形式存放在文件CodeFile中。(2)修改你的系統(tǒng)，實現(xiàn)對你的系統(tǒng)的原程序的編碼和譯碼(主要是將行尾符編/譯碼問題)。(3)實現(xiàn)各個轉(zhuǎn)換操作的源/目文件，均由用戶在選擇此操作時指定。20. 圖遍歷的演示【問題描述】很多涉及圖上操作的算法都是以圖的遍歷操作為基礎的。試寫一個程序，演示在連通的無向圖上訪問全部結(jié)點的操作?！净疽蟆恳脏徑佣嘀乇頌榇鎯Y(jié)構，實現(xiàn)連通無向圖的深度優(yōu)先和廣度優(yōu)先遍歷。以用戶指定的結(jié)點為起點，分別輸出每種遍歷下的結(jié)點訪問序列和相應生成樹的邊集。【測試數(shù)據(jù)】任選國內(nèi)城市，起點為合肥，暫時忽略里程?！緦崿F(xiàn)提示】設圖的結(jié)點20-30個，每個結(jié)點用一個編號表示(如果一個圖有n個結(jié)點，則它們的編號分別為1，2，n)。通過輸入圖的全部邊(存于數(shù)據(jù)文件中，從文件讀寫)輸入一個圖，每個邊為一個數(shù)對，可以對邊的輸入順序作出某種限制。注意，生成樹的邊是有向邊，端點順序不能顛倒?！具x作內(nèi)容】(1)借助于棧類型(自己定義和實現(xiàn))，用非遞歸算法實現(xiàn)深度優(yōu)先遍歷。(2)以鄰接表為存儲結(jié)構，建立深度優(yōu)先生成樹和廣度優(yōu)先生成樹，再按凹入表或樹形打印生成樹。21. 教學計劃編制問題【問題描述】大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序?！净疽蟆?1)輸入?yún)?shù)包括：學期總數(shù)，一學期的學分上限，每門課的課程號(固定占3位的字母數(shù)字串)、學分和直接先修課的課程號。(2)允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。(3)若根據(jù)給定的條件問題無解，則報告適當?shù)男畔?，否則將教學計劃輸出到用戶指定的文件中。計劃的表格格式自行設計?！緶y試數(shù)據(jù)】學期總數(shù)：65；學分上限：103；該專業(yè)共開設12門課，課程號從CO1到C12，學分順序為2，3，4，3，2，3，4，4，7，5，2，3。先修關系見教科書圖7.26。22. 校園導游咨詢【問題描述】設計一個校園導游程序，為來訪的客人提供各種信息查詢服務?！净疽蟆?1) 設計你所在學校的校園平面圖,所含景點不少于10個。以圖中頂點表示校內(nèi)各景點,存放景點名稱、代號、簡介等信息;以邊表示路徑,存放路徑長度等相關信息。(2)為來訪客人提供圖中任意景點相關信息的查詢。(3)為來訪客人提供圖中任意景點的問路查詢,即查詢?nèi)我鈨蓚€景點之間的一條最短的簡單路徑。【測試數(shù)據(jù)】以合肥學院南艷湖校區(qū)為例?！緦崿F(xiàn)提示】一般情況下,校園的道路是雙向通行的,可設校園平面圖是一個無向網(wǎng)。頂點和邊均 含有相關信息。【選作內(nèi)容】(1) 求校園圖的關節(jié)點。(2) 提供圖中任意景點問路查詢 , 即求任意兩個景點之間的所有路徑。(3) 提供校園圖中多個景點的最佳訪問路線查詢 , 即求途經(jīng)這多個景點的最佳 ( 短 )路徑。(4) 校園導游圖的景點和道路的修改擴充功能。(5) 擴充道路信息 , 如道路類別 ( 車道、人行道等 ) 、沿途景色等級 , 以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等。(6) 擴充每個景點的鄰接景點的方向等信息 , 使得路徑查詢結(jié)果能提供詳盡的導向信息。(7) 實現(xiàn)校園導游圖的仿真界面。23. 圖書管理【問題描述】圖書管理基本業(yè)務活動包括:對一本書的采編入庫、清除庫存、借閱和歸還等等。試設計一個圖書管理系統(tǒng)，將上述業(yè)務活動借助于計算機系統(tǒng)完成?！净疽蟆?每種書的登記內(nèi)容至少包括書號、書名、著者、現(xiàn)存量和總庫存量等五項。2作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項基本業(yè)務活動都是通過書號(即關鍵字進行的，所以要用B樹24樹對書號建立索引，以獲得高效率。3系統(tǒng)應實現(xiàn)的操作及其功能定義如下: 采編入庫z新購入一種書，經(jīng)分類和確定書號之后登記到圖書賬目中去。如果這種書在賬中已有，則只將總庫存量增加。 清除庫存:某種書已無保留價值，將它從圖書賬目中注銷。 借閱:如果一種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號和歸還期限。 歸還z注銷對借閱者的登記，改變該書的現(xiàn)存量。 顯示:以凹入表的形式顯示B樹。這個操作是為了調(diào)試和維護的目的而設置的?！緶y試數(shù)據(jù)】入庫書號:35，16，18，70，5，50，22，60，13，17，12，45，25，氈，15，90，30，7然后清除:45，90，50，22，42其余數(shù)據(jù)自行設計。由空樹開始，每插入刪除一個關鍵字后就顯示B樹的狀態(tài)?！緦崿F(xiàn)提示】(1)24樹的查找算法是基礎，入庫和清除操作都要調(diào)用。難點在于刪除關鍵字的算法，因而只要算法對2-3樹適用就可以了，暫時不必追求高階B樹也適用的刪除算法。(2)每種書的記錄可以用動(或靜)態(tài)鏈式結(jié)構。借閱登記信息可以鏈接在相應的那種書的記錄之后?！具x作內(nèi)容】(l)將一次會話過程(即程序一次運行)中的全部人機對話記入一個日志文件log中去。(2)增加列出某著者全部著作名的操作。思考如何提高這一操作的效率，參閱教科書12.6.2節(jié)。(3增加列出某種書狀態(tài)的操作。狀態(tài)信息除了包括這種書記錄的全部信息外還包括最早到期(包括已逾期)的借閱者證號，日期可用整數(shù)實現(xiàn)，以求簡化。(4)增加預約借書功能。24. 多關鍵字排序【問題描述】多關鍵字的排序有其一定的實用范圍。例如:在進行高考分數(shù)處理時，除了需對總分進行排序外，不同的專業(yè)對單科分數(shù)的要求不同，因此尚需在總分相同的情況下，按用戶提出的單科分數(shù)的次序要求排出考生錄取的次序。【基本要求】(1)假設待排序的記錄數(shù)不超過10000，表中記錄的關鍵字數(shù)不超過5，各個關鍵字的范圍均為0至100。按用戶給定的進行排序的關鍵字的優(yōu)先關系，輸出排序結(jié)果。(2)約定按LSD法進行多關鍵字的排序。在對各個關鍵字進行排序時采用兩種策略:其一是利用穩(wěn)定的內(nèi)部排序法，其二是利用分配和收集的方法。并綜合比較這兩種策略。【測試數(shù)據(jù)】由隨機數(shù)產(chǎn)生器生成。【實現(xiàn)提示】用5至8組數(shù)據(jù)比較不同排序策略所需時間。由于是按LSD方法進行排序，則對每個關鍵字均可進行整個序列的排序，但在利用通常的內(nèi)部排序方法進行排序時，必須選用穩(wěn)定的排序方法。借助分配和收集策略進行的排序，如同一趟基數(shù)排序，由于關鍵字的取值范圍為0至100，則分配時將得到104個鏈表?！具x作內(nèi)容】增添按MSD策略進行排序，并和上述兩種排序策略進行綜合比較。25手機通訊錄的制作設計目的：用數(shù)據(jù)結(jié)構中的雙向鏈表作數(shù)據(jù)結(jié)構。編寫一個手機通訊錄管理系統(tǒng)。以把所學數(shù)據(jù)結(jié)構知識應用到實際軟件開發(fā)中去。設計內(nèi)容：本系統(tǒng)應完成一下幾方面的功能：（1）. 添加信息（2）. 顯示信息：它可以按按固定電話排列、按手機、聯(lián)系人名字的拼音順序排列。（3）. 查找：可以不同的關鍵字作為查找的依據(jù)，進行查找;（4）. 編輯信息（5）. 刪除信息（6）. 保存到文件：將以上信息保存到文件，以便下次運行程序時能載入此通信錄設計要求：（1）. 每條信息至包含 ：姓名（NAME ）,手機號，固定電話號，電子郵箱，QQ號碼，城市（CITY）郵編（EIP）幾項（2）. 作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能力（3）. 上機能正常運行，并寫出課程設計報告26 奇數(shù)階幻方求解要求必須在空間復雜度為O(N)的要求下實現(xiàn)N階幻方的輸出。Problem description 幻方是一種很有意思的數(shù)字矩陣，在很早著名的九宮八卦陣就與幻方有關。幻方的定義為： 1 到 N*N 的整數(shù)填入N*N的方格中，每行和每列以及對角線的數(shù)字之和必須是相等的。你作為八卦公司的頂級程序員，現(xiàn)在需要你解決一個問題，將任意奇數(shù)階的幻方找出來。 Input 輸入包括多個測試集，每行為一個正奇數(shù)N(1 = N 1000)，0作為輸入的結(jié)束且不需要處理。 Output 對于輸入的每一個N， 輸出一個它所對應的N階幻方，如果存在多個，任意一個即可。每個幻方為N*N的矩陣，