數(shù)據(jù)結(jié)構(gòu)設(shè)計任務(wù)書

2023-2023第二學(xué)期《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計任務(wù)書課程設(shè)計名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

課程設(shè)計學(xué)分：1

課程設(shè)計周（時）數(shù)：1周課程設(shè)計授課單位：計算機專業(yè)教研室

指導(dǎo)方式：集體輔導(dǎo)與個別輔導(dǎo)相結(jié)合課程設(shè)計合用專業(yè)：計算機科學(xué)與技術(shù)

、軟件工程、網(wǎng)絡(luò)工程

課程設(shè)計教材及重要參考資料：《數(shù)據(jù)結(jié)構(gòu)C++版》王紅梅、胡明、王濤編著清華大學(xué)出版社2023年《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏編著，清華大學(xué)出版社，2023年服務(wù)課程名稱：數(shù)據(jù)結(jié)構(gòu)服務(wù)課程講課學(xué)時：56

服務(wù)課程學(xué)分：3.5

一、課程設(shè)計教學(xué)目的及基本規(guī)定1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具有初步的獨立分析和設(shè)計能力；2.初步掌握軟件開發(fā)過程的問題分析、數(shù)據(jù)結(jié)構(gòu)定義、算法流程分析、程序編碼、測試等基本方法和技能；3.提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；4.訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)的規(guī)范完畢課程設(shè)計內(nèi)容，培養(yǎng)軟件工作者所應(yīng)具有的科學(xué)的工作方法和作風(fēng)。二、課程設(shè)計內(nèi)容及安排1.分析題目，設(shè)計解題思緒：根據(jù)設(shè)計題目的規(guī)定，充足地分析和理解問題，明確問題規(guī)定做什么？（而不是怎么做？）限制條件是什么？2.數(shù)據(jù)結(jié)構(gòu)定義：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。寫出每個抽象數(shù)據(jù)類型的定義(涉及數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明)，各個重要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3.算法流程分析：在這個過程中，要綜合考慮題目的具體規(guī)定，使得解決算法流程清楚、合理、簡樸和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡也許做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡也許明確具體。算法流程分析的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；4.編寫代碼：把具體設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；5.程序調(diào)試與測試：采用自底向上，分模塊進(jìn)行，即先調(diào)試低層函數(shù)。可以純熟掌握調(diào)試工具的各種功能，設(shè)計測試數(shù)據(jù)擬定疑點，通過修改程序來證實它或繞過它。調(diào)試對的后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6.結(jié)果分析：程序運營結(jié)果涉及對的的輸入及其輸出結(jié)果和具有錯誤的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析；7.編寫課程設(shè)計報告；三、課程設(shè)計考核方法及成績評估課程設(shè)計結(jié)束時，規(guī)定學(xué)生寫出課程設(shè)計報告（附源程序），可運營的軟件系統(tǒng)課程設(shè)計成績分兩部分，設(shè)計報告占30％，設(shè)計作品占70％。按照優(yōu)秀、良好、中、及格，不及格五級給予成績。四、其他規(guī)定課程設(shè)計時間安排周一布置題目、分析題目指導(dǎo)教師呂冬梅張沛露岳俊華周二分析題目，設(shè)計解題思緒指導(dǎo)教師段淼鄭琦林娜周三數(shù)據(jù)結(jié)構(gòu)定義，算法流程分析指導(dǎo)教師呂冬梅張沛露岳俊華周四編寫代碼，調(diào)試分析指導(dǎo)教師段淼鄭琦林娜周五驗收指導(dǎo)教師呂冬梅張沛露岳俊華段淼鄭琦林娜設(shè)計題目及基本規(guī)定第一題：關(guān)鍵途徑問題當(dāng)一項工程被劃分為若干個子任務(wù)或活動后，人們不僅需要擬定這些活動的先后順序，并且需要進(jìn)一步計算完畢整個工程的時間，擬定哪些活動是影響工程進(jìn)度的關(guān)鍵活動，以便合理組織人力、物力、財力，加快這些活動的進(jìn)度，為準(zhǔn)時或提前完畢整個工程提供保證。規(guī)定：給定一個帶權(quán)的有向圖代表一個工程的AOE網(wǎng)絡(luò)，研究如下問題：（1）完畢整項工程至少需要多少時間？（2）哪些活動是影響工程進(jìn)度的關(guān)鍵活動？示例圖：核心算法：圖的關(guān)鍵途徑第二題：電梯模擬模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個自動電梯，能在每層停留。九個樓層由下至上依次稱為地下層、第一層、第二層、……第八層，其中第一層是大樓的進(jìn)出層，即是電梯的“本壘層”，電梯“空閑”時，將來到該層候命。乘客可隨機地進(jìn)出于任何層。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄。模擬時鐘從0開始，時間單位為0.1秒。人和電梯的各種動作均要消耗一定的時間單位（簡記為t），比如：有人進(jìn)出時，電梯每隔40t測試一次，若無人進(jìn)出，則關(guān)門；關(guān)門和開門各需要20t；每個人進(jìn)出電梯均需要25t；假如電梯在某層靜止時間超過300t，則駛回1層侯命。而題目的最終規(guī)定輸出時：準(zhǔn)時序顯示系統(tǒng)狀態(tài)的變化過程，即發(fā)生的所有人和電梯的動作序列。核心算法：乘客采用棧，等待乘客采用隊列第三題：研究生入學(xué)考試成績解決假設(shè)某大學(xué)計算機應(yīng)用技術(shù)專業(yè)招收研究生n名，現(xiàn)在要根據(jù)報考者的考試成績擇優(yōu)錄取。考試課程有政治、英語、數(shù)學(xué)、專業(yè)綜合四門?？荚嚦煽兎譃閮深悾旱谝活悶槊块T課程都達(dá)成最低錄取線；第二類為有一門或多門課程未達(dá)成最低錄取線。錄取方法是在每門課程達(dá)成最低錄取線的考生中按總分從高到低錄取。試設(shè)計一個成績解決程序?qū)崿F(xiàn)以上功能。根據(jù)錄取方法，打印輸出n份錄取告知書，列出錄取者四門課程的成績及總分（規(guī)定采用堆排序）。并能實現(xiàn)對任一考生或任一門課程成績的查找（規(guī)定兩種查找方式，根據(jù)考號或姓名進(jìn)行查找，采用高效的查找算法）。錄取告知書的格式如下：核心算法：鏈表的查找第四題：哈夫曼編碼與譯碼問題設(shè)計一個哈夫曼編碼、譯碼系統(tǒng)。對一個ASCII編碼的文本文獻(xiàn)中的字符進(jìn)行哈夫曼編碼，生成編碼文獻(xiàn)；反過來，可將編碼文獻(xiàn)譯碼還原為一個文本文獻(xiàn)。從文獻(xiàn)中讀入任意一篇英文短文（文獻(xiàn)為ASCII編碼，擴展名為txt）；記錄并輸出不同字符在文章中出現(xiàn)的頻率（空格、換行、標(biāo)點等也按字符解決）；根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個字符的哈夫曼編碼；將文本文獻(xiàn)運用哈夫曼樹進(jìn)行編碼，存儲成壓縮文獻(xiàn)（編碼文獻(xiàn)后綴名.huf）用哈夫曼編碼來存儲文獻(xiàn)，并和輸入文本文獻(xiàn)大小進(jìn)行比較，計算文獻(xiàn)壓縮率；進(jìn)行譯碼，將huf文獻(xiàn)譯碼為ASCII編碼的txt文獻(xiàn)，與原txt文獻(xiàn)進(jìn)行比較。核心算法：哈夫曼樹的編碼及譯碼第五題：校園導(dǎo)游圖用無向網(wǎng)表達(dá)本學(xué)校校園景點平面圖，選取若干個有代表性的景點抽象成無向帶權(quán)圖，圖中頂點表達(dá)校內(nèi)各頂點，邊上權(quán)值表達(dá)途徑長度?？梢裕海?）為來訪客人查詢各景點的相關(guān)信息；（2）為來訪客人查詢圖中任意兩個景點間的最短途徑（3）為來訪客人查詢圖中任意兩個景點間的所有途徑（4）為來訪客人修改圖中頂點和邊的信息（5）為來訪客人增長景點和途徑（6）為來訪客人刪除景點和途徑（7）為來訪客人輸出相應(yīng)編號景點的信息核心算法：圖的最短途徑第六題：簡樸的文本編輯器內(nèi)容：輸入一頁文字，程序可以記錄出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行。規(guī)定：（1）分別記錄出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）記錄某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一字符或者子串，并將后面的字符前移。（4）插入某一字符或者子串。（5）查找某一字符或者子串。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"所有字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章。通過題目及其規(guī)定可知，本程序應(yīng)實現(xiàn)以下功能：文章內(nèi)容的輸入：涉及字母、標(biāo)點符號、數(shù)字等；文章內(nèi)容的記錄：涉及文章中大寫字母、小寫字母、數(shù)字、標(biāo)點符號、空格以及文章所有字?jǐn)?shù)的個數(shù)的記錄；文章內(nèi)容的解決：涉及對文章內(nèi)容的查找、刪除以及對指定位置進(jìn)行插入操作，其中在查找的過程中記錄出該字符或字符串在文章中出現(xiàn)的次數(shù)；核心算法：鏈表的查找、刪除、插入第七題：運動會分?jǐn)?shù)記錄參與運動會有n個學(xué)校，學(xué)校編號為1……n。比賽提成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）[基本規(guī)定](1)可以輸入各個項目的前三名或前五名的成績；(2)能記錄各學(xué)?？偡?3)可以按學(xué)校編號、學(xué)校總分、男女團隊總分排序輸出；(4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（假如做得更好可以輸入學(xué)校的名稱，運動項目的名稱）輸出形式：有中文提醒，各學(xué)校分?jǐn)?shù)為整形界面規(guī)定：有合理的提醒，每個功能可以設(shè)立菜單，根據(jù)提醒，可以完畢相關(guān)的功能規(guī)定。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能規(guī)定自己設(shè)計，但是規(guī)定運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文獻(xiàn)中。（數(shù)據(jù)文獻(xiàn)的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：規(guī)定使用1、所有合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；核心算法：排序第八題：航空客運訂票系統(tǒng)[問題描述]通過此系統(tǒng)可以實現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文獻(xiàn)中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛到達(dá)城市，航班票價，票價折扣，擬定航班是否滿倉）；可以輸入起飛到達(dá)城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數(shù)據(jù)文獻(xiàn)中，結(jié)構(gòu)自己設(shè)定）可以訂票，假如該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文獻(xiàn)；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文獻(xiàn)[基本規(guī)定]根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完畢功能；核心算法：隊列的操作第九題：模擬旅館管理系統(tǒng)的一個功能——床位的分派與回收[問題描述]某旅館有n個等級的房間，第I等級有ai個房間，每個等級有bi個床位（1≤i≤n）。試模擬旅館管理系統(tǒng)中床位分派和回收的功能，設(shè)計能為單個旅客分派床位，在其離店便回收床位（供下次分派）的算法。[基本規(guī)定]（1）輸入數(shù)據(jù)分派時，輸入旅客姓名、年齡、性別、到達(dá)日期和所需房間等級?；厥諘r，輸入房間等級、房間號和床位號。（2）輸出數(shù)據(jù)分派成功時打印旅客姓名、年齡、到達(dá)日期、房間等級、房間號碼和床位號碼。分派不成功時，如所有等級均無床位，則打印“客滿”信息；如旅客需要的等級均無空床位，則打印“是否樂意更換等級？”的詢問信息。若旅客樂意更換，則重新輸入有關(guān)信息，再進(jìn)行分派，否則分派工作結(jié)束。核心算法：隊列的操作第十題：停車場管理[問題描述]設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原順序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述規(guī)定進(jìn)行管理的模擬程序。[測試數(shù)據(jù)]設(shè)n=2,輸入數(shù)據(jù)為：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。每一組輸入數(shù)據(jù)涉及三個數(shù)據(jù)項：汽車“到達(dá)”或“拜別”信息、汽車牌照號碼及到達(dá)或拜別的時刻，其中，‘A’表達(dá)成達(dá)；‘D’表達(dá)拜別，‘E’表達(dá)輸入結(jié)束。[基本規(guī)定]以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)涉及三個數(shù)據(jù)項：汽車“到達(dá)”或“拜別”信息、汽車牌照號碼及到達(dá)或拜別的時刻，對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出數(shù)據(jù)為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車拜別；則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費用（在便道上停留的時間不收費）。核心算法：棧和隊列的操作。第十一題：學(xué)生成績管理系統(tǒng)[問題描述]編寫一個簡樸的學(xué)生信息管理程序，能實現(xiàn)對學(xué)生信息的簡樸管理。[基本規(guī)定]建立一個4個學(xué)生的信息登記表，每個學(xué)生的信息涉及：學(xué)號，姓名，和3門課程的成績（FOX,C,ENGLISH）。程序運營時顯示一個簡樸的菜單，例如：（1）信息輸入（INPUT）（2）總分記錄（COUNT）（3）總分排序（SORT）（4）查詢(QUERY）其中：（1）對4個學(xué)生的信息進(jìn)行輸入；（2）對每個學(xué)生的3門課程記錄總分；(3)對4個學(xué)生的總分按降序排序并顯示出來；(4)查詢輸入一個學(xué)號后，顯示出該學(xué)生的有關(guān)信息；核心算法：查找和排序第十二題：哈希表的設(shè)計與實現(xiàn)[問題描述]設(shè)計哈希表實現(xiàn)電話號碼查詢系統(tǒng)。[基本規(guī)定]1、設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)擬定的前提下，嘗試各種不同類型解決沖突的方法（至少兩種），考察平均查找長度的變化。核心算法：哈希表的存儲和查找第十三題：通訊錄管理系統(tǒng)該系統(tǒng)至少應(yīng)具有如下功能：1．輸入記錄規(guī)定隨時都能使用該項功能實現(xiàn)記錄的輸入，一次可以輸入一條記錄，也可以輸入多條記錄。2．輸出（1）按自然順序輸出（2）按某種排序順序輸出。至少兩種。3．查詢至少提供兩種查詢方式。4．修改至少提供兩種修改方式。5．刪除既能一次刪除一條記錄，也能一次刪除多條記錄。6．退出通訊錄管理結(jié)束后，正常退出系統(tǒng)。規(guī)定：每個記錄至少包含如下信息：姓名、電話、所在城市、所在單位、年齡、E-mail、備注等。以采單方式實現(xiàn)功能選擇控制。編寫功能獨立的函數(shù)實現(xiàn)各功能。4．記錄最大個數(shù)100。核心算法：鏈表的查找、插入和刪除第十四題：內(nèi)部排序算法比較[問題描述]各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大約執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。[基本規(guī)定]（1）對以下幾種常用的內(nèi)部排序算法進(jìn)行比較：直接插入排序；折半折入排序；希爾排序；起泡排序；快速排序；簡樸選擇排序；堆排序；歸并排序；基數(shù)排序。（2）待排序表的表長不少于100；其中的數(shù)據(jù)要用偽隨機數(shù)產(chǎn)生程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參與的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān)鍵字互換計為3次移動）。[測試數(shù)據(jù)]由隨機產(chǎn)生器決定。第十五題：記錄成績[問題描述]給出n個學(xué)生的m門考試的成績表，每個學(xué)生的信息由學(xué)號、姓名以及各科成績組成。對學(xué)生的考試成績進(jìn)行有關(guān)記錄，并打印登記表。[基本規(guī)定]（1）按總數(shù)高低順序，打印出名次表，分?jǐn)?shù)相同的為同一名次；（2）按名次打印出每個學(xué)生的學(xué)號、姓名、總分以及各科成績。第十六題：大數(shù)相乘問題[問題描述]在用某種程序設(shè)計語言進(jìn)行編程時，也許需要解決非常大或者運算精度規(guī)定非常高的整數(shù)（稱為大整數(shù)），這種大整數(shù)用該語言的基本數(shù)據(jù)類型無法直接表達(dá)。對這樣的兩個大整數(shù)，編寫程序計算兩個大整數(shù)相乘。[基本規(guī)定]輸入第一個數(shù)為：172586輸入第二個數(shù)為：1147程序運營后輸出172586*1147=對的答案。核心算法：用數(shù)組存儲大整數(shù)，數(shù)組元素代表大整數(shù)的一個位，通過數(shù)組元素的運算模擬大整數(shù)的元素。第十七題：矩陣的運算[問題描述]矩陣式很多工程與科學(xué)計算問題中的解決對象。在實際應(yīng)用中，經(jīng)常出現(xiàn)一些階數(shù)很高的矩陣，同時在矩陣中有很多零元素，稱為稀疏矩陣。對于這樣的矩陣可以進(jìn)行壓縮存儲，從而節(jié)省存儲空間，使矩陣的加法運算可以有效的進(jìn)行。[基本規(guī)定](1采用十字鏈表表達(dá)稀疏矩陣，并實現(xiàn)矩陣的加法運算。(2)要檢查有關(guān)運算的條件，并對錯誤的條件產(chǎn)生報警。第十八題：構(gòu)造n個城市連接的最小生成樹[問題描述]一個地區(qū)的n個城市間的距離網(wǎng)，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。[基本規(guī)定]1)城市間的距離網(wǎng)采用鄰接矩陣表達(dá)，鄰接矩陣的存儲結(jié)構(gòu)定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。規(guī)定在屏幕上顯示得到的最小生成樹中涉及了哪些城市間的道路，并顯示得到的最小生成樹的代價。2)表達(dá)城市間距離網(wǎng)的鄰接矩陣(規(guī)定至少6個城市，10條邊)第十九題：字符串的模式匹配[問題描述]在事務(wù)解決程序中，顧客的姓名、貨品的產(chǎn)地等一般都是作為字符串解決的。對于這些關(guān)鍵詞的查詢也就是在主串中尋找子串的過程，即為模式匹配。[基本規(guī)定]（1）輸入多條主串，及一條子串。（2）對于多條主串進(jìn)行模式匹配，假如匹配成功則返回主串內(nèi)容及子串在主串中的位置。假如匹配失敗，則返回0。第二十題：括號匹配的檢查[問題描述]假設(shè)表達(dá)式中允許有兩種括號：圓括號和方括號，其嵌套的順序隨意，即（（）[]）或[（[][]）]等為對的格式，[（]）或（（（]均為不對的的格式。檢查括號是否匹配的方法可用“期待的緊迫限度”這個概念來描述。例如：考慮下列的括號序列：[([][])]12345678當(dāng)計算機接受了第1個括號以后，他期待著與其匹配的第8個括號的出現(xiàn)，然而等來的卻是2個括號，此時第1個括號“[”只能暫時靠邊，而迫切等待與第2個括號相匹配的第7個括號“）”的出現(xiàn)，類似的，因只等來了第3個括號“[”，此時，其期待的緊迫限度較第2個括號更緊迫，則第2個括號只能靠邊，讓位于第3個括號，顯然第3個括號的期待緊迫限度高于第2個括號，而第2個括號的期待緊迫限度高于第1個括號；在接受了第4個括號之后，第3個括號的期待得到了滿足，消解之后，第2個括號的期待匹配就成了最急切的任務(wù)了，??，依次類推?？梢娺@個解決過程正好和棧的特點相吻合。[基本規(guī)定]（1）讀入圓括號和方括號的任意序列，輸出“匹配”或“此串括號匹配不合法”。（2）以下面測試數(shù)據(jù)為例，若輸入（[]（）），結(jié)果應(yīng)輸出“匹配”輸入[（）]，結(jié)果應(yīng)輸出“此串括號匹配不合法”[實現(xiàn)提醒]設(shè)立一個棧，每讀入一個括號，若是左括號，則作為一個新的更急切的期待壓入棧中；若是右括號，并且與當(dāng)前棧頂?shù)淖罄ㄌ栂嗥ヅ洌瑒t將當(dāng)前棧頂?shù)淖罄ㄌ柾顺觯^續(xù)讀下一個括號，假如讀入的右括號與當(dāng)前棧頂?shù)淖罄ㄌ柌黄ヅ?，則屬于不合法的情況。在初始和結(jié)束時，棧應(yīng)當(dāng)是空的。第二十一題：圖書管理系統(tǒng)的設(shè)計與實現(xiàn)【問題描述】設(shè)計一個計算機管理系統(tǒng)完畢圖書管理基本業(yè)務(wù)?！净疽?guī)定】（1）每種書的登記內(nèi)容涉及書號、書名、著作者、現(xiàn)存量、庫存量和借閱信息；（2）系統(tǒng)重要功能如下：①采編入庫：新購一種書，擬定書號后，登記到圖書帳目表中，假如表中已有，則只將庫存量增長；②借閱：假如一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；③歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。第二十二題：客戶消費積分管理系統(tǒng)的設(shè)計與實現(xiàn)【問題描述】針對客戶的消費情況，進(jìn)行客戶管理，根據(jù)客戶的消費積分對客戶實行不同限度的打折優(yōu)惠?！净疽?guī)定】⑴采用一定的存儲結(jié)構(gòu)進(jìn)行客戶信息的存儲；⑵對客戶的信息可以進(jìn)行修改、刪除、添加；⑶可以根據(jù)消費情況進(jìn)行客戶積分的累加；⑷根據(jù)積分情況，對客戶實行不同限度的打折優(yōu)惠；第二十三題：家譜管理系統(tǒng)的設(shè)計與實現(xiàn)【問題描述】設(shè)計并實現(xiàn)一個簡樸的家譜管理系統(tǒng)?！净疽?guī)定】（1）建立家族關(guān)系并能存儲到文獻(xiàn)中。（2）實現(xiàn)家族成員的添加、刪除功能。（3）可以查詢家族成員的雙親、祖先、兄弟、孩子和后代等信息。（4）按某種順序輸出家譜信息（樹的遍歷操作）、以樹型結(jié)構(gòu)輸出家譜資料等功能。第二十三題：算術(shù)表達(dá)式求解【問題描述】給定一個算術(shù)表達(dá)式，通過程序求出最后的結(jié)果?！净疽?guī)定】(1)從鍵盤輸入規(guī)定解的算術(shù)表達(dá)式；(2)采用棧結(jié)構(gòu)進(jìn)行算術(shù)表達(dá)式的求解過程；(3)可以判斷算術(shù)表達(dá)式對的與否；(4)對于對的的表達(dá)式給出最后的結(jié)果、并可以顯示運算的整個過程。第二十四題：病人就醫(yī)管理【問題描述】編寫一個程序?qū)崿F(xiàn)就醫(yī)管理。在病人就醫(yī)過程中，重要發(fā)生三件事：⑴預(yù)檢，分科室，掛號。⑵病人到達(dá)診室，將病歷本交給護(hù)士，排到等待隊列中候診。⑶護(hù)士從等待隊列中取出一位病人的病歷，該病人進(jìn)入診室就診?！净疽?guī)定】規(guī)定程序采用菜單方式，其選項及功能說明如下：⑴掛號------預(yù)檢，分科室，生成就診號。⑵排隊------輸入病人的就診號，加入到病人排隊隊列中。⑶就診-------病人排隊隊列中最前面的病人就診，并將其從隊列中刪除。⑷查看排隊------從隊首到隊尾列出所有的排隊病人的病歷號。⑸下班---------退出運營。第二十五題：銀行業(yè)務(wù)模擬【問題描述】設(shè)銀行有四個服務(wù)窗口，一個等待隊列,每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種業(yè)務(wù)所需的服務(wù)時間不同，優(yōu)先級不同?？蛻舻竭_(dá)銀行后，先到打號機上打號，號票上涉及到達(dá)時間、編號和需要辦理的業(yè)務(wù)，然后在銀行內(nèi)等候。當(dāng)任一服務(wù)窗口空閑時,解決等候客戶中優(yōu)先級最高，排在最前面的客戶的業(yè)務(wù)。寫一個上述銀行業(yè)務(wù)的模擬系統(tǒng),通過模擬