【正文】 ；若已滿員或余票額少于訂票額，則需重新詢問客戶要求。歸還函數(shù)可取名為myFree，其作用是把該分量入錢。例如對于客戶結(jié)點(diǎn)，定義pool為CustNodepoolfMAX]；// 結(jié)構(gòu)類型CustNode含四個域：aITHIne，durtime，amount，next或者定義四個同樣長的，以上述域名為名字的數(shù)組。兩個隊(duì)列和一個事件表均要用動態(tài)存儲結(jié)構(gòu)實(shí)現(xiàn)。開始營業(yè)后的第一今事件是客戶到達(dá)，營業(yè)時間從0到closetime?！緶y試數(shù)據(jù)】 一天營業(yè)開始時銀行擁有的款額為10000(元)，營業(yè)時間為600(分鐘)。假設(shè)檢查不需要時間。處理每個客戶業(yè)務(wù)時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立刻排入第二個隊(duì)等候，直至滿足時才離開銀行；否則業(yè)務(wù)處理完后立刻離開銀行。第一種是申請從銀行得到一筆資金，即取款或借款。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程?！净疽蟆繉ⅠR隨機(jī)放在國際象棋的88棋盤Board[8][8]的某個方格中，馬按走棋規(guī)則進(jìn)行移動。應(yīng)首先實(shí)現(xiàn)棧和隊(duì)列的基本操作。(1) (2) 【測試數(shù)據(jù)】B(ehnxgz)B解釋成tsaedsaeezegexenehetsaedsae若將小寫字母與漢字建立下表所示的對應(yīng)關(guān)系，則魔王說的話是“天上一只鵝地上一只鵝鵝追鵝趕鵝下鵝蛋鵝恨鵝天上一只鵝地上一只鵝”。試寫一個魔王語言的解釋系統(tǒng)，把他的話解釋成人能聽得懂的話。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)“或“離去“信息、汽車牌照號碼以及到達(dá)或離去的時刻。1. 停車場管理【問題描述】設(shè)停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進(jìn)出。(4) 將“池塘”改為“荷塘”，雨點(diǎn)滴在荷葉上的效果是濺起四散的水珠，響聲也不同。(4) 用一個適當(dāng)?shù)慕Y(jié)構(gòu)管理當(dāng)前存在的雨點(diǎn)，使系統(tǒng)能利用它按時更新每個雨點(diǎn)的狀態(tài)，一旦有雨點(diǎn)的水圈全部消失，就從結(jié)構(gòu)中刪去?！緦?shí)現(xiàn)提示】 (1) 每個雨點(diǎn)的存在周期可分為三個階段：從天而降、入水有聲和圈圈微瀾，需要一個記錄存儲其相關(guān)參數(shù)、當(dāng)前狀態(tài)和下一狀態(tài)的更新時刻。(5) 計算器的仿真界面。(3) 多項(xiàng)式a和b相乘，建立乘積多項(xiàng)式ab ?！净疽蟆恳辉∈瓒囗?xiàng)式簡單計算器的基本功能是：(1) 輸入并建立多項(xiàng)式 ；(2) 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，cl，el，c2，e2，…，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci 和ei，分別是第 i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列；(3) 多項(xiàng)式a和b相加，建立多項(xiàng)式a +b；(4) 多項(xiàng)式a和b相減，建立多項(xiàng)式a b 。不能給長整數(shù)位數(shù)規(guī)定上限。但若這樣存放，即相當(dāng)于按32768進(jìn)制數(shù)存放，在十進(jìn)制數(shù)與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便。(5) 1，0001，0001；－1，0001，0000； 應(yīng)輸出 1 ?！緶y試數(shù)據(jù)】(1) 0；0； 應(yīng)輸出 0 。4. 長整數(shù)四則運(yùn)算【問題描述】 設(shè)計一個實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。【選作內(nèi)容】(1) 集合的元素判定和子集判定運(yùn)算。 (2) 演示程序以用戶和計算機(jī)的對話方式執(zhí)行。 此題所用的循環(huán)鏈表中不需要 “頭結(jié)點(diǎn)”，請注意空表和非空表的界限?！净疽蟆?利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號。2. 約瑟夫環(huán)【問題描述】約瑟夫 (Joseph) 問題的一種描述是：編號為 1，2，… ，n 的n個人按順時針方向圍坐一 圈，每人持有一個密碼(正整數(shù))。【測試數(shù)據(jù)】對于n=4，m=3，w =2，編號為奇數(shù)的項(xiàng)目取前五名，編號為偶數(shù)的項(xiàng)目取前三名，設(shè)計一組實(shí)例數(shù)據(jù)。比賽分成m個男子項(xiàng)目和w個女子項(xiàng)目，項(xiàng)目編號分別為1～m和m+1～m+w。編寫課程設(shè)計報告。能夠熟練掌握調(diào)試工具的各種功能。程序編碼：把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。概要設(shè)計：采用結(jié)構(gòu)化設(shè)計方法，按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，設(shè)計軟件層次結(jié)構(gòu)和模塊間的調(diào)用關(guān)系，定義主程序，畫出模塊之間的調(diào)用關(guān)系圖。 嚴(yán)禁抄襲，否則成績作廢。二 課程設(shè)計要求認(rèn)真分析課題內(nèi)容和要求，明確設(shè)計任務(wù)。仔細(xì)分析課題，合理設(shè)計算法。設(shè)計達(dá)到一定工作量。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試。同時加入一些注解，使程序中邏輯概念清楚。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果。四 教材及參考文獻(xiàn)[1] 嚴(yán)蔚敏，《數(shù)據(jù)結(jié)構(gòu) C語言》，清華大學(xué)出版社；[2] 譚浩強(qiáng)，《c語言程序設(shè)計》，清華大學(xué)出版社；[3] 《數(shù)據(jù)結(jié)構(gòu)》，高教出版社；[4] 李春保，《數(shù)據(jù)結(jié)構(gòu)習(xí)題》，清華大學(xué)出版社；[5] 嚴(yán)蔚敏，《數(shù)據(jù)結(jié)構(gòu)習(xí)題》，清華大學(xué)出版社；[6] 王立柱，《c語言與數(shù)據(jù)結(jié)構(gòu)》，清華大學(xué)出版社；[7] 李春葆，《數(shù)據(jù)結(jié)構(gòu)（C語言篇)習(xí)題與解析》，清華大學(xué)出版社；注：還可以查閱與數(shù)據(jù)結(jié)構(gòu)有關(guān)的書籍、論文、網(wǎng)絡(luò)資料。由于各項(xiàng)目參加人數(shù)差別較大，有些項(xiàng)目取前五名，得分順序?yàn)?，5，3，2，1；還有些項(xiàng)目只取前三名，得分順序?yàn)?，3，2。【實(shí)現(xiàn)提示】可以假設(shè)n≤20，m≤30，w≤20，姓名長度不超過 20 個字符。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)?！緶y試數(shù)據(jù)】 m 的初值為 20；n=7，7 個人的密碼依次為：3，1，7，2，4，8，4， 首先 m 值為 6( 正確的出列順序應(yīng)為 6，1，4，7，2，3，5) ?！具x作內(nèi)容】向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分。【測試數(shù)據(jù)】 (1)Set1=magazine，Set2=paper， Set1∪Set2=aegimnprz，Setl ∩Set2=ae，Set1Set2=gimnz。(2) 求集合的補(bǔ)集。【基本要求】利用雙向循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲，每個結(jié)點(diǎn)含一個整型變量。(2)－2345，6789； －7654，3211； 應(yīng)輸出 －1，0000，0000 。(6) 9999，9999，9999；－9999，9999，9999；應(yīng)輸出 －1，9999，9999，9998 。故可以在每個結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制數(shù)。 【選作內(nèi)容】(1) 實(shí)現(xiàn)長整數(shù)的四則運(yùn)算；(2) 實(shí)現(xiàn)長整數(shù)的乘方和階乘運(yùn)算；(3) 整型量范圍是－ (2n－1) ~ (2n－1)， 其中，n是由程序讀人的參量?！緶y試數(shù)據(jù)】(1)(2x+5x8－) + (7－5x8+11x9)=(－+11x9+2x+7)(2)(6x3－x+－) －(6x3+－x2+)=(+12x3x)(3)(1 +x + x2+x3+x4+x5)+(x3－x4)=(1+x+x2+x5) (4)(x+x3)+(x－x3)=0(5)(x+x100)+(x100 +x200)=(x+2x100+x200)(6)(x+x2+x3)+0=x+x2+x3(7) 互換上述測試數(shù)據(jù)中的前后兩個多項(xiàng)式【實(shí)現(xiàn)提示】 用帶表頭結(jié)點(diǎn)的單鏈表存儲多項(xiàng)式。(4) 多項(xiàng)式的輸出形式為類數(shù)學(xué)表達(dá)式。6. 池塘夜降彩色雨【問題描述】設(shè)計一個程序，演示美麗的“池塘夜雨”景色：色彩繽紛的雨點(diǎn)飄飄灑灑地從天而降， 滴滴入水有聲，濺起圈圈微瀾。 (2) 在圖形狀態(tài)編程?！具x作內(nèi)容】(1) 增加“電閃雷鳴”景象。ch2 棧和隊(duì)列及其應(yīng)用僅僅認(rèn)識到棧和隊(duì)列是兩種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)習(xí)的目的在于使讀者深入了解錢和隊(duì)列的特性，以便在實(shí)際問題背景下靈活運(yùn)用他們；同時還將鞏固對這兩種結(jié)構(gòu)的構(gòu)造方法的理解。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列(大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端)，若車場內(nèi)己停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開人；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其他車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用(在便道上停留的時間不收費(fèi))。【基本要求】用下述兩條具體規(guī)則和上述規(guī)則形式(2)實(shí)現(xiàn)。tdsaezgxnh天地上一只鵝追趕下蛋恨【實(shí)現(xiàn)提示】將魔王的語言自右至左進(jìn)棧，總是處理?xiàng)ｍ斪址！具x作內(nèi)容】(1)由于問題的特殊性，可以實(shí)現(xiàn)棧和隊(duì)列的順序存儲空間共享。要求每個方格只進(jìn)入一次，走遍棋盤上全部64個方格?！净疽蟆恳宰址蛄械男问綇慕K端輸入語法正確的、不含變量的整數(shù)表達(dá)式。第二種是向銀行投入一筆資金，即存款或還款。每接待完一個第二種業(yè)務(wù)的客戶，則順序檢查和處理(如果可能)第二個隊(duì)列中的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊(duì)列的隊(duì)尾。營業(yè)時間結(jié)束時所有客戶立即離開銀行。其他模擬參量自定，注意測定兩種極端的情況：一是兩個到達(dá)事件之間的間隔時間很短，而客戶的交易時間很長，另一個恰好相反，設(shè)置兩個到達(dá)事件的間隔時間很長，而客戶的交易時間很短。到達(dá)事件發(fā)生時隨機(jī)地設(shè)置此客戶的交易時間和距下一到達(dá)事件之間的時間間隔。注意弄清應(yīng)該在什么條件下設(shè)置離開事件，以及第二個隊(duì)列用怎樣的存儲結(jié)構(gòu)實(shí)現(xiàn)時可以獲得較高的效率。初始時，將所有分量的next域鏈接起來，形成一個靜態(tài)鏈找，設(shè)置一個樓頂元素下標(biāo)指示量top，top=0表示找空。用FORTRAN和BASIC等語言實(shí)現(xiàn)時只能如此地自行組織。若需要，可登記排隊(duì)候補(bǔ)；③承辦退票業(yè)務(wù)：根據(jù)客戶提供的情況(日期、航班)，為客戶辦理退票手續(xù)，然后查詢該航班是否有人排隊(duì)候補(bǔ)，首先詢問排在第一的客戶，若所退票額能滿足他的要求，則為他辦理訂票手續(xù)，否則依次詢問其他排隊(duì)候補(bǔ)的客戶。由于預(yù)約人數(shù)無法預(yù)計，隊(duì)列也應(yīng)以鏈表作存儲結(jié)構(gòu)。讀者還可充分發(fā)揮自己的想象力，增加你的系統(tǒng)的功能和其他服務(wù)項(xiàng)目。【基本要求】(1) 模擬某校五層教學(xué)樓的電梯系統(tǒng)。對每個人來說，他有一個能容忍的最長等待時間，一旦等候電梯時間過長，他將放棄?！緶y試數(shù)據(jù)】 模擬時鐘Time的初值為0，終值可在500~10000范圍內(nèi)逐步增加。有人按下某個按鈕時，相應(yīng)的變量就置為1，一旦要求滿足后，電梯就把該變量清為0。一旦收到往另一層的命令，就轉(zhuǎn)入GoingUp或GoingDown狀態(tài)，執(zhí)行相應(yīng)的操作。其他重要的變量有：Floor ——電梯的當(dāng)前位置(樓層)；DI ——值為0，除非人們正在進(jìn)入和離開電梯；D2 ——值為0，如果電梯已經(jīng)在某層停候30Ot以上；D3 ——值為0，除非電梯門正開著又無人迸出電梯；State ——電梯的當(dāng)前狀態(tài)(GoingUp，GoingDOWEl，Idle)。M2. [按電鈕并等候]此時應(yīng)對以下不同情況作不同的處理：①Floor=InFloor且電梯的下一個活動是E6(電梯在本層，但正在關(guān)門〉；②Floor=InFloor且D3手0(電梯在本層，正有人迸出)；③其他情況，可能D2=0或電梯處于活動El(在1層停候)。 M5. [進(jìn)入電梯]從Queue[InFloor〕刪除該人，并把他插入到lElevator(電梯)校中。E2. [要改變狀態(tài)?]如果電梯處于GoingUp(或GoingDown〉狀態(tài)，但該方向的樓層卻無人等待，則要看反方向樓層是否有人等候，而決定置State為GoingDown(或GoingUp〉還是Idle。E5. [關(guān)門]每隔40個t檢查D1，直到是D1=O(若D1手0，則仍有人出入〉。如果State=Idle，則即使已經(jīng)執(zhí)行了Controler，也轉(zhuǎn)到E1。 E8. [下降一層]除了方向相反之外，與E7類似，但那里的51和14個t，此時分別改為61和23個t(電梯下降比上升慢)。 C2. [應(yīng)該開門?]如果電梯處于E1且CallUp[1]，CallDown[1]或Caucar[1]非0，則預(yù)置20個t后啟動E3，并返回。 C5. [電梯靜止?]如果電梯處于E1而且j手1，則預(yù)置20個t后啟動E6。 (2) 某高校的一座30層住宅樓有三部自動電梯，每梯最多載客15人。8. 迷宮問題 【問題描述】以一個mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為z(1，1，1)，(1，2，2)，(2，2，2)，(3，2，3)，(3，1，2)，假如所有可能的通路都探索到而未能到達(dá)出口，則所設(shè)定的迷宮沒有通路。【選作內(nèi)容】(l) 編寫遞歸形式的算法，求得迷宮中所有可能的通路；(2) 以方陣形式輸出迷宮及其通路。字符填充技術(shù)(,)。命令識別與分析技術(shù)(,)。試寫一個實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng),稱為文學(xué)研究助手。【測試數(shù)據(jù)】以你的C源程序模擬英文小說,C語言的保留字集作為待統(tǒng)計的詞匯集。若某行中出現(xiàn)了不止一次,不必存多個相同的行號。while(i!=+1amp。[i]!=[j])j=next[j]。(2)整個統(tǒng)計過程中只對小說文字掃描一遍以提高效率。2. 文本格式化【問題描述】輸入文件中含有待格式化〈或稱為待排版〉的文本,它由多行的文字組成,例如一篇英文文章。一個文本格式化程序可以處理上述輸入文件,按照用戶指定的版面規(guī)格重排版面z實(shí)現(xiàn)頁內(nèi)調(diào)整、分段、分頁等文本處理功能,排版結(jié)果存入輸出文本文件中。(3)如果所要求的每頁頁底所空行數(shù)不少于3,則將頁號印在頁底空行中第2行的中間位置上,否則不印。頭長(HeadingLength)一一每頁頁頂