數(shù)據(jù)結(jié)構(gòu)大型實(shí)驗(yàn)任務(wù)書-2014年(第三稿).doc

2014年數(shù)據(jù)結(jié)構(gòu)大型實(shí)驗(yàn)任務(wù)書 編制者：劉端陽 使用班級：計(jì)算機(jī)學(xué)院各班級大型實(shí)驗(yàn)基本要求1. 原則上可以1位同學(xué)組成實(shí)驗(yàn)小組，進(jìn)行分工合作，但必需保證每位組員都充分參與實(shí)驗(yàn)過程，每位組員應(yīng)對實(shí)驗(yàn)程序的結(jié)構(gòu)、算法、主要技術(shù)完全掌握，方可參加實(shí)驗(yàn)驗(yàn)收。但一個小組內(nèi)最終只能一個人得到優(yōu)秀成績。2. 每組可參考下面大型實(shí)驗(yàn)題目和要求，選擇一道實(shí)驗(yàn)題目，共同設(shè)計(jì)開發(fā)。 3. 大型實(shí)驗(yàn)時間從第8周開始至16周，要求在考試之前全部驗(yàn)收結(jié)束。原則上，申請大型實(shí)驗(yàn)驗(yàn)收后，若實(shí)驗(yàn)沒有達(dá)到規(guī)定的要求，不可再次申請驗(yàn)收，故請大家務(wù)必確認(rèn)程序正確（程序代碼和運(yùn)行結(jié)果）后，再申請驗(yàn)收。報告規(guī)范 實(shí)習(xí)報告的開頭應(yīng)該給出題目、班級、姓名、學(xué)號、和完成日期，如果是多人完成的，必須寫明所有同組人員的班級、姓名和學(xué)號，并標(biāo)明誰是主要負(fù)責(zé)人，其它為參與者。實(shí)驗(yàn)報告要求有以下五個內(nèi)容：1 實(shí)驗(yàn)內(nèi)容分析：明確實(shí)驗(yàn)題目目的，設(shè)計(jì)實(shí)驗(yàn)的基本數(shù)據(jù)結(jié)構(gòu)、類、以及程序的基本流程，程序流程要求以程序流程圖明確表示，類及類間關(guān)系需明確圖示，并給出各函數(shù)之間的調(diào)用關(guān)系?？梢赃m當(dāng)粘貼關(guān)鍵代碼進(jìn)行說明；2 實(shí)驗(yàn)驗(yàn)證分析：（1）輸入的形式和輸入值的范圍；（2）輸出的形式；（3）程序所能達(dá)到的功能；（4）測試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯誤的輸入及其輸出結(jié)果。調(diào)試分析（1）討論分析調(diào)試過程中的主要技術(shù)問題以及具體的解決方法（至少個）；（2）技術(shù)難點(diǎn)分析（至少個）；（3）印象最深刻的個調(diào)試錯誤，及修正方法；測試結(jié)果：（1）展示程序的運(yùn)行結(jié)果，包括輸入和輸出，分析數(shù)據(jù)的正確性；（2）應(yīng)用邊界數(shù)據(jù)、或極端數(shù)據(jù)測試系統(tǒng)，分析結(jié)果的正確性。附錄：附上源代碼，并標(biāo)明源代碼的所屬文件，并且源代碼必須有注釋。提交內(nèi)容1. 電子壓縮包：包括實(shí)驗(yàn)報告電子稿和所有源代碼文件(包括.h文件和.cpp文件)。2. 壓縮文件名為： “學(xué)號+姓名”；如果是多人合作的，則壓縮文件名為：“負(fù)責(zé)人學(xué)號+負(fù)責(zé)人姓名+參與者1學(xué)號+參與者1姓名+參與者2學(xué)號+參與者2姓名”?？己朔绞? 以小組方式進(jìn)行面試，教師提問，結(jié)合工作分工和系統(tǒng)完成情況評分。2 原則上前50%完成的小組均可獲得優(yōu)秀成績，但小組內(nèi)只能一人得優(yōu)。第 5 頁 共 5 頁題目一、 用戶登錄系統(tǒng)的模擬【問題描述】在登錄服務(wù)器系統(tǒng)時，都需要驗(yàn)證用戶名和密碼，如telnet遠(yuǎn)程登錄服務(wù)器。用戶輸入用戶名和密碼后，服務(wù)器程序會首先驗(yàn)證用戶信息的合法性。由于用戶信息的驗(yàn)證頻率很高，系統(tǒng)有必要有效地組織這些用戶信息，從而快速查找和驗(yàn)證用戶。另外，系統(tǒng)也會經(jīng)常會添加新用戶、刪除老用戶和更新用戶密碼等操作，因此，系統(tǒng)必須采用動態(tài)結(jié)構(gòu)，在添加、刪除或更新后，依然能保證驗(yàn)證過程的快速。請采用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)模擬用戶登錄系統(tǒng)，其功能要求包括用戶登錄、用戶密碼更新、用戶添加和用戶刪除等。【基本要求】1. 要求自己編程實(shí)現(xiàn)二叉樹結(jié)構(gòu)及其相關(guān)功能，以存儲用戶信息，不允許使用標(biāo)準(zhǔn)模板類的二叉樹結(jié)構(gòu)和函數(shù)。同時要求根據(jù)二叉樹的變化情況，進(jìn)行相應(yīng)的平衡操作，即AVL平衡樹操作，四種平衡操作都必須考慮。測試時，各種情況都需要測試，并附上測試截圖；2. 要求采用類的設(shè)計(jì)思路，不允許出現(xiàn)類以外的函數(shù)定義，但允許友元函數(shù)。主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用，不允許出現(xiàn)對其它函數(shù)的調(diào)用。3. 要求采用多文件方式：.h文件存儲類的聲明，.cpp文件存儲類的實(shí)現(xiàn)，主函數(shù)main存儲在另外一個單獨(dú)的cpp文件中。如果采用類模板，則類的聲明和實(shí)現(xiàn)都放在.h文件中。4. 要求源程序中有相應(yīng)注釋；5. 不強(qiáng)制要求采用類模板，也不要求采用可視化窗口；6. 要求測試?yán)右容^詳盡，各種極限情況也要考慮到，測試的輸出信息要詳細(xì)易懂，表明各個功能的執(zhí)行正確；7. 要求采用Visual C+ 6.0及以上版本進(jìn)行調(diào)試；【實(shí)現(xiàn)提示】1. 用戶信息(即用戶名和密碼)可以存儲在文件中，當(dāng)程序啟動時，從文件中讀取所有的用戶信息，并建立合適的查找二叉樹；2. 驗(yàn)證過程時，需要根據(jù)登錄的用戶名，檢索整個二叉樹，找到匹配的用戶名，進(jìn)行驗(yàn)證；更新用戶密碼時，也需要檢索二叉樹，找到匹配項(xiàng)后進(jìn)行更新，同時更新文件中存儲的用戶密碼。3. 添加用戶時，不僅需要在文件中添加，也需要在二叉樹中添加相應(yīng)的節(jié)點(diǎn)；刪除用戶時，也是如此；【運(yùn)行結(jié)果要求】要求能夠?qū)崿F(xiàn)用戶登錄驗(yàn)證、添加用戶、刪除用戶和更新用戶密碼功能，實(shí)驗(yàn)報告要求有詳細(xì)的功能測試截圖?！究己艘蟆恳蟪绦蚰苷＿\(yùn)行，全面完成題目要求?！绢}目難度】 難，成績等級高二、 優(yōu)先級作業(yè)調(diào)度系統(tǒng)的模擬【問題描述】Windows、Linux等操作系統(tǒng)都支持同時運(yùn)行多個作業(yè)，但作業(yè)的執(zhí)行順序卻因調(diào)度算法的不同而不同。通常，操作系統(tǒng)都采用優(yōu)先級作業(yè)調(diào)度，即操作系統(tǒng)根據(jù)作業(yè)的長短來設(shè)置優(yōu)先級大小，優(yōu)先級高的作業(yè)先執(zhí)行，優(yōu)先級低的作業(yè)后執(zhí)行。作業(yè)調(diào)度的詳細(xì)情況如下描述：一個作業(yè)Ji的長度為ti =（si，ei），si 為作業(yè)運(yùn)行的開始時間（進(jìn)入時間），ei 為作業(yè)運(yùn)行的結(jié)束時間（離開時間），ti則為完成作業(yè)Ji所需要的執(zhí)行時間（單位：秒）。作業(yè)調(diào)度的基本任務(wù)是從作業(yè)隊(duì)列中選取一個來執(zhí)行，如果沒有作業(yè)則執(zhí)行空操作操作。而優(yōu)先級作業(yè)調(diào)度，是指每次選取優(yōu)先級最高的作業(yè)來調(diào)度，優(yōu)先級可以用優(yōu)先數(shù)（每個作業(yè)一個優(yōu)先數(shù)pi）來表示，優(yōu)先數(shù)越小，優(yōu)先級越高。作業(yè)Ji 進(jìn)入系統(tǒng)時，即si 時刻，系統(tǒng)給該作業(yè)指定其初始優(yōu)先數(shù)pi = ti，從而使越短的作業(yè)優(yōu)先級越高。該優(yōu)先數(shù)在作業(yè)等待調(diào)度執(zhí)行的過程中會不斷減小，調(diào)整公式為：pi = pi - wi，其中wi 為作業(yè)Ji的等待時間：wi = 當(dāng)前時間-si。一旦作業(yè)被調(diào)度，該作業(yè)就一直執(zhí)行，不能被搶占，只有當(dāng)前執(zhí)行的作業(yè)完成時，才產(chǎn)生下一輪調(diào)度。所以需要在每次調(diào)度前動態(tài)調(diào)整各作業(yè)的優(yōu)先數(shù)。在每次調(diào)度的時候，如果出現(xiàn)相同優(yōu)先級的作業(yè)，則按照先進(jìn)先出(FIFO: First In First Out)的原則進(jìn)行調(diào)度?！净疽蟆?. 要求自己編程實(shí)現(xiàn)堆結(jié)構(gòu)及其相關(guān)功能，從而實(shí)現(xiàn)優(yōu)先級隊(duì)列，不允許使用標(biāo)準(zhǔn)模板類的堆函數(shù)和優(yōu)先級隊(duì)列；測試時，各種情況都需要測試，并附上測試截圖；2. 要求采用類的設(shè)計(jì)思路，不允許出現(xiàn)類以外的函數(shù)定義，但允許友元函數(shù)。主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用，不允許出現(xiàn)對其它函數(shù)的調(diào)用。3. 要求采用多文件方式：.h文件存儲類的聲明，.cpp文件存儲類的實(shí)現(xiàn)，主函數(shù)main存儲在另外一個單獨(dú)的cpp文件中。如果采用類模板，則類的聲明和實(shí)現(xiàn)都放在.h文件中。4. 要求源程序中有相應(yīng)注釋；5. 不強(qiáng)制要求采用類模板，也不要求采用可視化窗口；6. 要求測試?yán)右容^詳盡，各種極限情況也要考慮到，測試的輸出信息要詳細(xì)易懂，表明各個功能的執(zhí)行正確，包括何時作業(yè)進(jìn)入，何時調(diào)度哪個作業(yè)，何時離開，每個作業(yè)等待多長時間，優(yōu)先數(shù)的動態(tài)變化情況等；7. 要求采用Visual C+ 6.0及以上版本進(jìn)行調(diào)試；【實(shí)現(xiàn)提示】1. 優(yōu)先級隊(duì)列可以采用最小堆來實(shí)現(xiàn)；2. 作業(yè)長度，即完成時間，可以用隨機(jī)的方式產(chǎn)生，并由此設(shè)定各個作業(yè)的初始優(yōu)先級；3. 可以在一輪調(diào)度的間隙隨機(jī)地插入一定數(shù)量的作業(yè)，保證隊(duì)列不會長時間空閑，也不會太長。4. 優(yōu)先級隊(duì)列要求完成主要的功能，包括作業(yè)的插入、最小優(yōu)先級作業(yè)的提取和刪除、各個作業(yè)優(yōu)先級的修改等；5. 作業(yè)的執(zhí)行過程，可以調(diào)用sleep函數(shù)來模擬；【考核要求】要求程序能正常運(yùn)行，全面完成題目要求，實(shí)現(xiàn)各項(xiàng)主要功能。實(shí)驗(yàn)報告要求有詳細(xì)的功能測試截圖。【題目難度】次難，成績等級次高三、 大整數(shù)的運(yùn)算【問題描述】密碼學(xué)分為兩類密碼：對稱密碼和非對稱密碼。對稱密碼主要用于數(shù)據(jù)的加/解密，而非對稱密碼則主要用于認(rèn)證、數(shù)字簽名等場合。非對稱密碼在加密和解密時，是把加密的數(shù)據(jù)當(dāng)作一個大的正整數(shù)來處理，這樣就涉及到大整數(shù)的加、減、乘、除和指數(shù)運(yùn)算等，同時，還需要對大整數(shù)進(jìn)行輸出。請采用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)大整數(shù)的加、減、乘、除和指數(shù)運(yùn)算，以及大整數(shù)的輸入和輸出?！净疽蟆?. 要求采用鏈表來實(shí)現(xiàn)大整數(shù)的存儲和運(yùn)算，不允許使用標(biāo)準(zhǔn)模板類的鏈表類(list)和函數(shù)。同時要求可以從鍵盤輸入大整數(shù)，也可以文件輸入大整數(shù)，大整數(shù)可以輸出至顯示器，也可以輸出至文件。大整數(shù)的存儲、運(yùn)算和顯示，可以同時支持二進(jìn)制和十進(jìn)制，但至少要支持十進(jìn)制。大整數(shù)輸出顯示時，必須能清楚地表達(dá)出整數(shù)的位數(shù)。測試時，各種情況都需要測試，并附上測試截圖；2. 要求大整數(shù)的長度可以不受限制，即大整數(shù)的十進(jìn)制位數(shù)不受限制，可以為十幾位的整數(shù)，也可以為500多位的整數(shù)，甚至更長；3. 大整數(shù)的運(yùn)算和顯示時，只需要考慮正的大整數(shù)。如果可能的話，請以秒為單位顯示每次大整數(shù)運(yùn)算的時間；4. 要求采用類的設(shè)計(jì)思路，不允許出現(xiàn)類以外的函數(shù)定義，但允許友元函數(shù)。主函數(shù)中只能出現(xiàn)類的成員函數(shù)的調(diào)用，不允許出現(xiàn)對其它函數(shù)的調(diào)用。5. 要求采用多文件方式：.h文件存儲類的聲明，.cpp文件存儲類的實(shí)現(xiàn)，主函數(shù)main存儲在另外一個單獨(dú)的cpp文件中。如果采用類模板，則類的聲明和實(shí)現(xiàn)都放在.h文件中。6. 要求源程序中有相應(yīng)注釋；7. 不強(qiáng)制要求采用類模板，也不要求采用可視化窗口；8. 要求測試?yán)右容^詳盡，各種極限情況也要考慮到，測試的輸出信息要詳細(xì)易懂，表明各個功能的執(zhí)行正確；9. 要求采用Visual C+ 6.0及以上版本進(jìn)行調(diào)試；【實(shí)現(xiàn)提示】1. 大整數(shù)的加減運(yùn)算可以分解為普通整數(shù)的運(yùn)算來實(shí)現(xiàn)；而大整數(shù)的乘、除和指數(shù)運(yùn)算，可以分解為大整數(shù)的加減運(yùn)算。2. 大整數(shù)的加、減、乘、除和指數(shù)運(yùn)算，一般是在求兩大整數(shù)在取余操作下的加、減、乘、除和指數(shù)運(yùn)算，即分別求 (a +b) mod n, (a - b) mod n, (a * b) mod n, (a / b) mod n 和(a b) mod n。其中a b 是求a的b次方，而n稱之為模數(shù)。說明：取余操作(即mod操作)是計(jì)算相除之后所得的余數(shù)，不同于除法運(yùn)算的是，取余操作得到的是余數(shù)，而不是除數(shù)。如7 mod 5 = 2。模數(shù)n的設(shè)定，可以為2m 或10m，m允許每次計(jì)算時從鍵盤輸入。模數(shù)n的取值一般為2512(相當(dāng)于十進(jìn)制150位左右),21024(相當(dāng)于十進(jìn)制200300位),22048(相當(dāng)于十進(jìn)制300500位)。為了測試，