課外實踐安排

1、數(shù)據(jù)結構課程課外實踐安排（2011-2012學年第一學期）課外實踐學時：32學時課外實踐目的：綜合應用數(shù)據(jù)結構課程中所學的數(shù)據(jù)結構：線性表、棧、隊列、串、數(shù)組、廣義表、樹、二叉樹、圖、查找表中的一種或多種數(shù)據(jù)結構完成一個較大問題的求解（其實這里的問題也并不太大，所用的數(shù)據(jù)結構可能是其中的多個，也可能是其中的一個兩個）。從而培養(yǎng)學生綜合應用基本數(shù)據(jù)結構分析、解決實際問題的能力，并進一步加深對所學知識的理解和掌握。課外實踐要求：1、課外實踐以組為單位開展，每組24名同學，自由組合，確定組長一名。2、每組從附件1列出的題目中任意選擇其中一個完成（鼓勵大家選擇對你自己而言有一定挑戰(zhàn)性的題目），每個題目

2、最多由3組同學選做。強調獨立思考，組內分工明確，每組自己完成。3、鼓勵大家參考教材上、參考書上和所選題目相關的內容和算法。不鼓勵大家一拿到實驗題目就去網(wǎng)上或參考書上找相關程序源代碼，通過思考該問題并最終解決該問題不僅可以鍛煉大家，從而提高大家的水平，而且大家對該問題的解決也會有成就感！4、實現(xiàn)你所選題目要求的功能，并能夠進行較完善友好的輸入輸出驗證。5、完成你所選的課外實踐題目后，就該題目給出設計報告（設計報告格式另給），并按時上交。6、每組同學須仔細閱讀所選題目的要求，認真主動完成設計要求。有問題及時主動通過各種方式與教師聯(lián)系溝通。同學們要發(fā)揮自主學習的能力，充分利用課外時間，安排好課外實踐

3、的時間，并在設計過程中不斷檢測自己的計劃完成情況，及時的向教師匯報。 課外實踐按照教學要求需要思考和上機調試程序至少32學時，代碼量要求在6003000行。7、課外實踐的考核需要按組進行答辯，安排在第16周或17周進行。附件1：數(shù)據(jù)結構課程課外實踐可選題目一、運動會分數(shù)統(tǒng)計系統(tǒng) 任務：參加運動會有n個學校，學校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m=20,n=20） 功能要求：1).可以輸入各個項目的

4、前三名或前五名的成績； 2)能統(tǒng)計各學?？偡郑?3)可以按學校編號、學?？偡?、男女團體總分排序輸出； 4).可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內的整數(shù)（如果做得更好可以輸入學校的名稱，運動項目的名稱） 輸出形式：有中文提示，各學校分數(shù)為整數(shù) 界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。 存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結

5、構；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明；二、學籍信息管理【實驗目的】綜合考察數(shù)據(jù)存儲、以及對各種存儲結構的建立、插入、刪除、排序、查找等操作?！緦嶒炓蟆吭O計一個簡單的學籍管理系統(tǒng)。包括建立、插入、修改，查找、輸出、排序（按不同關鍵字）【實驗內容】1. 從學生基本信息文件讀入數(shù)據(jù)以建立學籍信息。下面是一個例子：學號 姓名 性別 宿舍號碼 電話號碼 張成成 男 501 李成華 女 101 王成鳳 女 101 張明明 男 502 陳東 男 501 每個學生信息至少包括：學號、姓名、性別。文件

6、至少包括10個學生。2. 從學生成績信息文件讀入其內容建立學生的成績信息。以下一個例子：（至少包含20項信息）學號 課程編號 課程名稱 學分平時成績 實驗成績 卷面成績 綜合成績 實得學分 A01 大學物理 3 66 78 82 B03 高等數(shù)學 4 78 -1 90 B03 高等數(shù)學 4 45 -188 C01 VF 3 65 7666功能要求極其說明： （1）數(shù)據(jù)錄入功能：錄入每個學生的學號、課程編號、課程名稱、學分、平時成績、實驗成績、卷面成績共7個數(shù)據(jù)。實得成績、實得學分根據(jù)條件自動運算。 綜合成績的計算： a.如果本課程的實驗成績?yōu)?1，則表無實驗成績，綜合成績=平時成績*30%+卷

7、面成績*70% b.如果實驗成績不為-1，表示本課程有實驗成績，綜合成績=平時成績*15%+實驗成績*15%+卷面成績*70%實得學分的計算：采用等級學分制。 綜合成績在90100之間，應得學分=學分*100% 綜合成績在8090之間，應得學分=學分*80% 綜合成績在7080之間，應得學分=學分*75% 綜合成績在6070之間，應得學分=學分*60% 綜合成績在60分以下，應得學分=學分*0%3. 查詢功能：分為學生基本情況查詢和成績查詢兩種 4. 刪除功能：根據(jù)輸入的學生姓名或學好刪除相應的學生信息。5. 排序功能：能實現(xiàn)選擇按綜合成績或實得學分升序或降序排序并顯示數(shù)據(jù)。三、隊列應用（用隊

8、列模擬超市交款處的顧客流）使用一個隊列模擬一隊通過丹尼斯超市交款處的顧客流。為了創(chuàng)建這個模擬，我們必須模擬排隊時間和顧客通過流。我們可以通過一個循環(huán)模擬時間，每通過一個顧客代表一定的時間間隔例如，一分鐘。我們可以使用一個隊列模擬顧客流，隊列中的一個數(shù)據(jù)項代表一位顧客。為了完成這個模擬，我們需要知道顧客加入交款處隊列的頻率、交款結算服務情況和離開的頻率。假設交款隊列有以下屬性。 每分鐘有一個顧客完成交款并離開（假設此時至少有一個顧客等待服務）。 每分鐘有零個到兩個顧客加入，沒有顧客到達的概率是50% , 一個顧客到達的概率是 25 % ，兩個顧客到達的概率是 25 。（如何模擬？）我們可以使用下

9、面的算法模擬一個時間段 n 分鐘內的顧客流。初始化隊列為空。for （minute = 0 ; minute n ; + + minute） 如果隊列不空，對頭顧客交款并離開（即出對）；產(chǎn)生一個0-3范圍內的隨機數(shù)k；如果k=1，一個顧客加入交款隊列（入對）；如果k=2，兩個顧客加入交款隊列（入對）；如果k=0或3，不增加任何顧客到交款隊列； 調用 rand ( ）函數(shù)是產(chǎn)生偽隨機數(shù)的一種簡單的方法,rand函數(shù)在中。我們的模擬程序應該在每一個模擬分鐘期間內更新下列信息，即每一次通過循環(huán)。 完成交款服務的總顧客數(shù) 這些顧客花費在排隊等待的時間總和 顧客花費在排隊等待的最長時間為了計算顧客等待的

10、時間長度，我們需要存儲“minute”，作為這個客戶隊列數(shù)據(jù)項的一部分，表示顧客加入的時間。如果你使用程序模擬一列顧客流，試著完成下面的表格。請注意，平均等待時間是等待時間總和除以總的服務顧客數(shù)。時間（分鐘） 總的顧客服務時間 平均等待時間 最長等待時間3060120480四、應用哈夫曼樹實現(xiàn)文件的壓縮 實驗目的：掌握二叉樹的鏈式存儲結構和常用算法。利用哈夫曼樹設計最優(yōu)壓縮編碼。實驗內容：1) 編寫函數(shù)，實現(xiàn)建立哈夫曼樹和顯示哈夫曼樹的功能。2) 編寫函數(shù)，實現(xiàn)生成哈夫曼編碼的功能。3) 編寫主函數(shù)，從終端輸入一段英文文本；統(tǒng)計各個字符出現(xiàn)的頻率，然后構建哈夫曼樹并求出對應的哈夫曼編碼；顯示哈

11、夫曼樹和哈夫曼編碼。選做內容：修改程序，選擇實現(xiàn)以下功能：4) 編碼：用哈夫曼編碼對一段英文文本進行壓縮編碼，顯示編碼后的文本編碼序列；5) 統(tǒng)計：計算并顯示文本的壓縮比例；6) 解碼：將采用哈夫曼編碼壓縮的文本還原為英文文本。 算法說明：1) 二叉樹和哈夫曼樹的相關算法見講義。2) 編碼的方法是：從頭開始逐個讀取文本字符串中的每個字符，查編碼表得到它的編碼并輸出。重復處理直至文本結束。3) 解碼的方法是：將指針指向哈夫曼樹的樹根，從頭開始逐個讀取編碼序列中的每位，若該位為1則向右子樹走，為0則向左子樹走。當走到葉子節(jié)點時，取出節(jié)點中的字符并輸出。重新將指針放到樹根，繼續(xù)以上過程直至編碼序列處

12、理完畢。4) 壓縮比例的計算：編碼后的文本長度為編碼序列中的0和1的個數(shù)，原文本長度為字符數(shù)*8。兩者之比即為壓縮比。五、數(shù)據(jù)壓縮【實驗目的】1）調研數(shù)據(jù)壓縮原理與相關算法的實現(xiàn)；2）實現(xiàn)一個壓縮/解壓縮程序【實驗要求】1. 閱讀相關資料，理解數(shù)據(jù)壓縮的意義和過程。2. 調研幾個著名的數(shù)據(jù)壓縮算法，寫一份調研報告，說明其算法及所使用的數(shù)據(jù)結構。3. 實現(xiàn)一個壓縮/解壓縮程序，算法任意。4. 程序要求：控制臺界面。首先實現(xiàn)對單文件壓縮的功能。命令行格式：壓縮： 程序名 -c 輸入文件 輸出文件名解壓縮： 程序名 -d 輸入文件 輸出文件名里內容表示可選?？刂婆_輸出：壓縮： 原始文件大小、壓縮后文

13、件大小、壓縮比例、消耗時間解壓縮： 解壓前文件大小，解壓后文件大小、壓縮比例、消耗時間選做：1）將多個文件壓縮到一個文件；2）檢查壓縮文件完整性，測試其能夠完成解壓縮；3）對文件測試，不壓縮，輸入其若壓縮后的壓縮率；4）列出壓縮文件內所包含的文件名；4）實現(xiàn)對整個目錄進行壓縮的功能。文件格式：對壓縮文件起一個后綴名。若在命令行中沒指定輸入文件的話，輸出文件名應該是 輸入文件名+.后綴名 的格式；若在命令行中指定輸出文件名的話，后綴也應自動加上。實現(xiàn)的壓縮比例越高、壓縮事件越短越好。六、HTML文件中有序列表的語法樹提取及基于樹的檢索【實驗說明】HTML語言用來描述Web文檔的通用格式和布局。詳

14、細的介紹可以參照一些書本或者網(wǎng)上資料。HTML中基本的語法單位稱為標簽?？偟膩碚f，標簽用于指定內容的類別。對于每個類別，針對特定的內容，瀏覽器都有默認的顯示方式。標簽的使用語法是利用一對尖括號“”將標簽名稱包圍起來。大部分標簽都是成對的：包括開始標簽和結束標簽，如和。開始標簽和結束標簽之間的信息稱為標簽的內容。這里僅考慮一個HTML語言的子集，該子集包含以下標簽：, ：標識文檔的根元素；, ：包含了文檔的頭部分，該部分提供了文檔的相關信息，而沒有提供文檔的內容；, ：文檔的標題元素，其內容顯示在瀏覽器的頂部；, ：文檔的主體部分，提供了文檔的內容；, ：有序列表標簽，用于創(chuàng)建有序列表，列表中的

15、條目是通過標簽, 指定的?？梢郧短子行蛄斜?。標簽后不能直接嵌套，而必須通過嵌套。例如，下面的示例演示了嵌套的有序列表： test for nested lists Section 1Section 1.1Section 1.2Section 2顯示結果是：1. Anhui Province1. City Hefei 2. City Wuhu2. Shanghai對應的語法樹為：Anhui ProvinceShanghaiCity HefeiCity Wuhu圖2.1通過上面的HTML語言子集，可以設計結構化的Web文檔。對于這樣的文檔，我們可以提取其結構信息，建立對應的結構化數(shù)據(jù)存儲，并可以在

16、此基礎上進一步做相應應用如查詢操作等?！緦嶒災康摹渴炀殤镁€性結構、樹等數(shù)據(jù)結構?！緦嶒瀮热荨?. 根據(jù)前面介紹的HTML語言子集，編寫合法的文檔，作為輸入文件。也可以使用附錄中所給的內容建立文檔作為輸入；2. 然后用相應算法提取其結構化信息，生成如圖2.1的樹形結構。3. 在已經(jīng)建立的結構化存儲數(shù)據(jù)結構上，做單詞查詢操作。輸入一個查詢關鍵字（如”City”），要求返回所有匹配的單詞所在原HTML文檔中的位置信息（如，City: Section 1.2 the first word and Section 1.2 the first word）。4. 下面給出一個實現(xiàn)的算法。這里考慮一個簡單的

17、情況，即中只有一個有向列表，對于標簽中有多個列表的情況，通過簡單的修改此算法可以解決：1） 對于這樣一個HTML文檔，, , 是無關緊要的，在讀取文檔內容時可以忽略。核心的結構化信息在有序列表中。2） 遇到第一個時，生成頭節(jié)點，頭節(jié)點內容為空，curParent=curNode都指向該節(jié)點；3） 每當遇到一個，生成curParent指向的節(jié)點的一個子節(jié)點curNode，后內容即為該節(jié)點的內容；4） 每當遇到一個，curParent=curNode，準備以curParent為根的子樹（遞歸操作）；5） 每當遇到一個，則curNode指向的節(jié)點生成完畢（即不再往下遞歸地生成子樹），繼續(xù)讀文件（注意

18、，后的第一個應忽略，因為其后必然有一個）；6） 每當遇到一個，則以curParent 為根的子樹生成完畢，curParent=curParent-parent；7） 當讀到時，整個樹生成完畢，返回其頭指針。針對前面示例的html文件，其語法樹生成過程圖示如下：1curParentcurNodeAnhui Province12curParentcurNode(a) 讀到第一個，生成空的頭節(jié)點1 。 (b) 讀到后第一個，生成第一個 子節(jié)點2，并將其后內容作為節(jié)點內容。Anhui Province123City HefeicurParentcurNodeCity WuhuCity HefeiAnh

19、ui Province1234curParentcurNode(c) 遇到，curParent=curNode，準備 (d) 再次讀到，生成以curParent以curParent為根生成子樹；讀到，生 為根的子節(jié)點4；讀到，非成以curParent為根的子節(jié)點3；讀到 后第一個，curNode指向的節(jié)點，非后的第一個，curNode指向 生成完畢。的節(jié)點生成完畢。 Anhui ProvinceCity WuhuCity Hefei1234curParentcurNodeAnhui ProvinceCity WuhuCity HefeiShanghai1234curParentcurNode5

20、(e) 讀到，則以curParent為根的子樹 (f) 讀到，生成以curParent為根的生成完畢，curParent=curParent-parent， 子節(jié)點5，內容為”Section 2”；再讀到即curParent從2變?yōu)?；再往下讀到， ，curNode節(jié)點生成結束；讀到此為后第一個，忽略掉，繼續(xù)往后 ，以curParent（節(jié)點1）為根的讀文件。 子樹生成完畢；讀到，整個樹 生成完畢，返回頭指針。六、迷宮問題。傳說在遠古時候，米諾斯國王統(tǒng)治著愛琴海南端的克里特島。他建造了一座有無數(shù)宮室的迷宮，在迷宮中喂養(yǎng)了一頭人身牛頭的惡獸米諾牛。為了供奉它，米諾斯要希臘的雅典每九年進貢七對童男

21、女喂米諾牛。當時，雅典有位名叫忒休斯的王子，他不忍人民遭受這種災難，毅然決定跟隨第四批被進貢的童男女去克里特殺死米諾牛。在克里特，英勇的忒休斯贏得了米諾斯的女兒的愛慕。她交給忒休斯一個線團，讓他按下面規(guī)則邊走邊放線：（1）每到一個岔口，找沒有鋪上線的路走；若找不到未鋪上線的路，就沿原來的路返回到前一個岔口。（2）不走已鋪上兩條線的路。用這種方法，忒休斯終于殺死米諾牛，勝利的走出迷宮七、學生數(shù)據(jù)結構成績管理系統(tǒng)基本要求(1)學生信息及成績的錄入要求包括的學生信息有：學號、姓名、性別、出生日期、民族及數(shù)據(jù)結構成績（具體內容可自行假設，至少錄入10名以上學生）所錄入的學生按學號散列存儲（散列函數(shù)為：

22、學號%5 取整，如 1002%5 =2），采用拉鏈法解決沖突。(2)學生成績的查詢要求根據(jù)提供的學號完成學生成績的查詢（必須采用哈希查找）(3)學生成績的分段統(tǒng)計和排序輸出統(tǒng)計出各分數(shù)段學生人數(shù)（60分以下，6070，7180，.)采用任何一種排序方法，將學生成績從高到低排序輸出八、哈希表應用問題描述針對某個集體中人名設計一個哈希表，使得平均查找長度不超過R，并完成相應的建表和查表程序。基本要求假設人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有300個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構造，用線性探測再散列法或鏈地址法處理沖突。測試數(shù)據(jù)取讀者周圍較熟悉的300個人名。選作

23、內容（1） 從教科書上介紹的集中哈希函數(shù)構造方法中選出適用者并設計幾個不同的哈希函數(shù)，比較他們的地址沖突率（可以用更大的名字集進行實驗）。（2） 研究這300個人名的特點，努力找一個哈希函數(shù)，使得對于不同的拼音名一定不發(fā)生地址沖突。（3） 在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考察平均查找長度的變化和造好的哈希表中關鍵字的聚集性。九、內部排序算法比較問題描述各種內部排序算法的時間復雜度分析結果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關鍵字比較次數(shù)和關鍵字移動次數(shù)，以取得直觀感受?；疽螅?） 對以下10種常用的內部排序算法任意選擇6種進行比較：直接插

24、入排序；折半折入排序；二路插入排序；希爾排序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序；基數(shù)排序。（2） 待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字移動次數(shù)（關鍵字交換計為3次移動）。測試數(shù)據(jù)由隨機產(chǎn)生器決定。實現(xiàn)提示主要工作是設法在程序中適當?shù)牡胤讲迦胗嫈?shù)操作。程序還可以包括計算幾組數(shù)據(jù)得出結果波動大小的解釋。注意分塊調試的方法。十、校園導游程序 問題描述用無向網(wǎng)表示安陽師范學院校園景點或建筑物平面圖，圖中頂點表示主要景點或建筑物，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的

25、道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題?；疽螅?） 查詢各景點的相關信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 查詢圖中任意兩個景點間的所有路徑。（4） 增加、刪除、更新有關景點和道路的信息。（5） 求多個景點的最佳（最短）游覽路徑。十一、實現(xiàn)第7章圖中的部分算法，這些算法至少包括以下兩組：（1） 深度和廣度優(yōu)先搜索遍歷圖；（2） 構造最小生成樹的兩種算法（3） 拓撲排序算法；（4） 求解關鍵路徑；（5） 求解最短路徑。十二、合理設計手機鍵盤【題意描述】我們的手機鍵盤上將26個字母如下左圖設置在8個鍵盤上，但每個字母的按鍵頻率是不同的，因此如果按照右

26、圖的方式設置字母在鍵盤上的相對位置可能會使所有字母的按鍵頻率與按鍵次數(shù)乘積之和達到最小，從而更加方便客戶使用。我們的任務是根據(jù)輸入的鍵盤數(shù)和字符數(shù)及每個字符的使用頻率來確定最合理的分配方式，使分配后所有字符的頻率和按鍵次數(shù)的乘積之和最小。在每個鍵盤上，處于第i個位置上的字符按鍵次數(shù)為i，在分配的過程中我們不能更改字符的相對位置。 該題目詳細描述如下：I-KeyboardTime Limit: 2000MSMemory Limit: 32768KTotal Submissions: 3235Accepted: 1690DescriptionMost of you have probably tr

27、ied to type an SMS message on the keypad of a cellular phone. It is sometimes very annoying to write longer messages, because one key must be usually pressed several times to produce a single letter. It is due to a low number of keys on the keypad. Typical phone has twelve keys only (and maybe some

28、other control keys that are not used for typing). Moreover, only eight keys are used for typing 26 letters of an English alphabet. The standard assignment of letters on the keypad is shown in the left picture: 12abc3def4ghi5jkl6mno7pqrs8tuv9wxyz*0space#12abcd3efg4hijk5lm6nopq7rs8tuv9wxyz*0space#Ther

29、e are 3 or 4 letters assigned to each key. If you want the first letter of any group, you press that key once. If you want the second letter, you have to press the key twice. For other letters, the key must be pressed three or four times. The authors of the keyboard did not try to optimise the layou

30、t for minimal number of keystrokes. Instead, they preferred the even distribution of letters among the keys. Unfortunately, some letters are more frequent than others. Some of these frequent letters are placed on the third or even fourth place on the standard keyboard. For example, S is a very commo

31、n letter in an English alphabet, and we need four keystrokes to type it. If the assignment of characters was like in the right picture, the keyboard would be much more comfortable for typing average English texts. ACM have decided to put an optimised version of the keyboard on its new cellular phone

32、. Now they need a computer program that will find an optimal layout for the given letter frequency. We need to preserve alphabetical order of letters, because the user would be confused if the letters were mixed. But we can assign any number of letters to a single key. InputThere is a single positiv

33、e integer T on the first line of input. It stands for the number of test cases to follow. Each test case begins with a line containing two integers K, L (1 = K = L 1, either Pi = Pi-1+1 or Pi = 1 there are at most K numbers Pi such that Pi = 1 the sum of products SP = F1*P1+F2*P2+.+FL*PL is minimal

34、for any other sequence Q meeting these criteria and with the same sum SQ = SP, there exists such M, 1 = M = L that for any J, M J QM. The output for every test case must start with a single line saying Keypad #I:, where I is a sequential order of the test case, starting with 1. Then there must be ex

35、actly K lines, each representing one letter, in the same order that was used in input. Each line must contain the character representing the key, a colon, one space and a list of letters assigned to that particular key. Letters are not separated from each other. Print one blank line after each test

36、case, including the last one. Sample Input18 26ABCDEFGHIJKLMNOPQRSTUVWXYZ337158915751614621297177319042989123209158815132996326910801212726308343681334518752427733871Sample OutputKeypad #1:2: ABCD3: EFG4: HIJK5: LM6: NOPQ7: RS8: TUV9: WXYZ十三、二叉排序樹的應用(基于二叉排序樹的個人通信錄) 在日常生活中，個人通信錄是我們不可少的，不管是紙式的個人通信錄 還是

37、我們手機中的個人通信錄，查尋是其最基本的操作，幾乎所有的操作都是在查尋的基礎上進行的，所以，查尋時間的快慢很大程度上決定了整個通信錄的性能。所以，一個有著良好界面、查尋速快的通信錄，是人們所追求的。本設計應用折半查尋法 的技術思想進行查尋，從本思想出發(fā)，可以有兩種數(shù)據(jù)組織方式：一是應用鏈表進行組織數(shù)據(jù)，由于折半查尋法的特殊性，所要進行查尋的數(shù)據(jù)列必須是有序的數(shù)據(jù)列，這樣要求對數(shù)據(jù)列進行排序。出于系統(tǒng)實時查尋的考慮，每次對通信錄進行改變后都得進行重新排序，這樣才能保證數(shù)據(jù)列是實時有序的。這樣當操作量大時，排序所消耗的時間對整個系統(tǒng)有很大的影響。 二是應用二叉排序樹來組織數(shù)據(jù)，由于二叉排序樹是應用

38、折半查尋法思想進行對數(shù)據(jù)進行存儲的，所以，其左孩子大于雙親結點、右孩子小于雙親結點（或者左孩子小于雙親結點、右孩子大于雙親結點），這樣就可以應用折半查尋法的思想進行查尋，從而減少對排序時所消耗的時間。 本設計采用第二種方法，即應用二叉排序樹進行組織數(shù)據(jù)，在此基礎上進行對個人通信錄的各種操作。由于刪除操作是本設計的重點，刪除操作的成功與否直接影響到整個系統(tǒng)的成敗，所以在此進行詳細分析一下刪除操作的實現(xiàn)。 此功能函數(shù)主要應用于刪除將要進行刪除的記錄，此操作較其它幾個操作難一點，同時也是此次設計的重點，所以，本函數(shù)的成敗可以直接影響到本次設計的成敗，同時，在進行二叉排序樹進行組織時，如果不從系統(tǒng)的整

39、體進行考慮，只想到簡單地實現(xiàn)刪除功能，將會出現(xiàn)錯誤。 在設計初期，由于沒有考慮所有可能的情況，所以在進行刪除最后一個結點時，總會出現(xiàn)內存不能引用的錯誤。最后想到應用浪費一個結點空間的技術進行處理此問題，就是根結點用來保存二叉排序樹的某些信息，而不保存記錄，與我們單鏈表中的頭結點一樣，這樣做解決了上面所說的問題，同時在進行查尋雙親結點時也帶來了很大的方便。 有關二叉排序樹的刪除的有關問題，請讀者參考相關的參考文獻 ，在此不再進行說明，本節(jié)重點在于說明本課程設計中有關刪除的問題。 在本設計中，刪除的首要條件是找到將要進行刪除結點的雙親結點，由于根結點不用于存儲記錄，所以，可以不用進行判斷根結點的情

40、況，進行查尋雙親結點時，從根結點開始，首先進行判斷根結點的左右子樹是否為空，如果根結點的左右子樹為空，則返回 NULL ，如果根結點的左子樹（右子樹）不為空，則將其左子樹（右子樹）的記錄的學號與將要進行刪除的學號進行比較，如果相等，則返回根結點；否則進行比較，如果左子樹（右子樹）不為空，且左子樹（右子樹）的學號大于（小于）要進行刪除的學號，則進行遞歸在左子樹（右子樹）中進行查尋，直到查尋到或者當前結點的左右子樹為空時結束。如果當前結點的學號與要進行刪除的學號不相等，且當前結點的左右子樹為空，則返回空，結束查尋過程。 經(jīng)過對雙親結點的查尋，如果沒有此記錄，則進行提示，否則進行刪除操作 1 5 ，

41、在進行刪除時，有以下幾種可能，以下操作中假設每次把要進行刪除結點進行刪除后，同時也釋放了此結點所占用的內存空間，防止內存在運行過程中丟失。 第一：要進行刪除的結點為葉結點，直接把其從二叉排序樹中進行刪除。 第二：此結點只有左子樹或者右子樹，這種情況下只需將只需把此結點的左子樹或者右子樹替換為雙親結點的左子樹。 第三：此結點有左子樹同時有也右子樹，此種操作比較復雜，其中有兩種方法進行刪除，本課程設計中應用的方法是從某子樹中找出一個結點（假設為 Temp ），將其值代替要進行刪除結點的值，再把 Temp 結點進行刪除。 十四、DNA分子的最佳比對問題描述： DNA分子是人類遺傳信息的載體，它間接地

42、指導蛋白質的合成。DNA分子是由四種核苷酸組成的長鏈，這四種核苷酸分別是腺嘌呤核苷酸（用A代表）、鳥嘌呤核苷酸（用G代表）、胞嘧啶核苷酸（用C代表）和胸腺嘧啶核苷酸（用T代表）。習慣上用一個字符集為A，T，C，G的字符串來表示一個DNA分子序列，如CGTTAGA。 在生物進化過程中，DNA分子可能發(fā)生各種各樣的突變。這種突變形成了生物遺傳信息的改變，從而使生物得以分化，構成了生物的多樣性。主要的突變有三種：（1）在一個DNA序列中插入一個新的核苷酸，（2）DNA序列中丟失了一個核苷酸，（3）DNA序列中的某個核苷酸被另一個核苷酸所取代。 所謂兩個DNA序列的一個比對是尋找一種排列方式，使得兩個

43、DNA序列在同樣的位置上有相同的核苷酸，而若在同樣的位置上兩個DNA序列的核苷酸不同，則是由三種突變之一得到。例如，對兩個DNA序列T=ATCAG，T=ACTAG，可以按如下方式比對， 比對1： T T A A T - （“-”表示空白） C C - T A A G G也可以按如下方式比對 比對2： T T A A T C C T A A G G如果兩個DNA序列在相同的位置上有越多相同的核苷酸對，則表明它們之間越相似，即它們存在功能上的相似性和進化史上的親緣關系。 對于兩個DNA序列的一個比對，規(guī)定如下得分方式：（1）一個同樣的位置上有相同的核苷酸對，則可得1分；（2）一個同樣的位置上有不同

44、的核苷酸對，則得0分；（3）如果在某個位置上一個序列有核苷酸，而另一個序列在該位置上為“-”，則得-2分。例如，比對1的得分是0分，比對2的得分是3分。 編程任務：對于兩個DNA序列，尋找一種比對方式，使得它們的得分最高。數(shù)據(jù)輸入：輸入數(shù)據(jù)由文件名為INPUT3.*的文本文件提供，共有2行。第1行為DNA序列T, 第2行為DNA序列T。序列的長度不大于5000。序列中的字母是英文小寫或者大寫字母。結果輸出:程序運行結束時，在屏幕上輸出兩個DNA序列比對的最高得分。輸入文件示例輸出示例INPUT3.001AtcagActag3Human Gene Functions Time Limit:100

45、0MS Memory Limit:10000KTotal Submit:2255 Accepted:1440DescriptionIt is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining th

46、eir functions, because these can be used to diagnose human diseases and to design new drugs for them. A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determin

47、e its function. One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions many researchers have been submi

48、tting their genes and functions to the database and the database is freely accessible through the Internet. A database search will return a list of gene sequences from the database that are similar to the query gene. Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed. Your job is to make a program that c