【正文】 j。(*head)next = *head。} SCLNode。： typedef struct node { DataType data。} SCLNode。（3）帶頭結(jié)點(diǎn)單循環(huán)鏈表抽象數(shù)據(jù)類型的結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedef struct node { DataType data。} DataType。數(shù)據(jù)結(jié)構(gòu)：（1）數(shù)據(jù)類型DataType定義如下： typedef struct { int number。（3）void JesephRing(SCLNode *head, int m)，其功能是對帶頭結(jié)點(diǎn)的單循環(huán)鏈表head,以m為初始報(bào)數(shù)上限值實(shí)現(xiàn)問題要求。（2）void SCLLDeleteAfter(SCLNode *p)，其功能是刪除帶頭結(jié)點(diǎn)的單循環(huán)鏈表中指針p所指結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)。測試數(shù)據(jù)：n = 7，七個(gè)人的密碼依次為3,1,7,2,4,8,4 初始報(bào)數(shù)上限值m = 20 算法思想：JesephRing()函數(shù)是實(shí)現(xiàn)問題要求的主要函數(shù)，其算法思想是：從1至m對帶頭結(jié)點(diǎn)的單循環(huán)鏈表循環(huán)計(jì)數(shù)，到m時(shí)，輸出該結(jié)點(diǎn)的編號值，將該結(jié)點(diǎn)的密碼作為新的m值，再從該結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)起重新自1起循環(huán)計(jì)數(shù)；如此下去，直到單循環(huán)鏈表空時(shí)循環(huán)過程結(jié)束。要求設(shè)計(jì)一個(gè)程序模擬此過程，并給出出列人的編號序列。問題描述：設(shè)編號為1,2,…,n(n0)個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)正整數(shù)密碼。經(jīng)過上機(jī)調(diào)試，源程序運(yùn)行正確，并且實(shí)現(xiàn)算法要求的功能，解決課程設(shè)計(jì)題目中給出的問題后，分析算法的時(shí)間復(fù)雜度和空間復(fù)雜度，如有可能對程序進(jìn)行優(yōu)化改進(jìn)。3)模塊之間的調(diào)用關(guān)系：給出算法各模塊之間的關(guān)系圖示。1)確定所需模塊：對于復(fù)雜的程序設(shè)計(jì)，要充分利用模塊化程序設(shè)計(jì)方法和面向?qū)ο笏枷耄皂斚蛳?，逐步?xì)化。2)選擇能夠體現(xiàn)問題本身特點(diǎn)的一種或幾種邏輯結(jié)構(gòu)。分析及設(shè)計(jì)步驟（供參考），給出數(shù)學(xué)模型，設(shè)計(jì)相應(yīng)的數(shù)據(jù)結(jié)構(gòu)。測試數(shù)據(jù)：（1）A表（30，41，15，12，56，80）B表（23，56，78，23，12，33，79，90，55）（2）A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）8．哈夫曼編碼的實(shí)現(xiàn)與應(yīng)用（1）從文件中讀入任意一篇英文短文（至少含3000個(gè)字符，文件為ASCII編碼的文本文件）（2）統(tǒng)計(jì)不同字符在文章中出現(xiàn)的頻率（空格、換行、標(biāo)點(diǎn)等也按字符處理）（3）根據(jù)字符頻率構(gòu)造哈夫曼樹，并給出每個(gè)字符的哈夫曼編碼。（2）假設(shè)元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。（3）多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式。6．一元稀疏多項(xiàng)式簡單計(jì)數(shù)器（1）輸入并建立多項(xiàng)式（2）輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2……，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為第i項(xiàng)的系數(shù)和指數(shù)。5．鏈表操作利用鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。4．二叉樹的遍歷對任意給定的二叉樹（頂點(diǎn)數(shù)自定）建立它的二叉鏈表存貯結(jié)構(gòu)，并利用棧的五種基本運(yùn)算（置空棧、進(jìn)棧、出棧、取棧頂元素、判?？眨?shí)現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結(jié)果。3．圖的廣度遍歷對任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索遍歷。2．圖的深度遍歷對任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運(yùn)算（清空堆棧、壓棧、彈出、取棧頂元素、判棧空）實(shí)現(xiàn)圖的深度優(yōu)先搜索遍歷。（3）比較的指標(biāo)為關(guān)鍵字的比較次數(shù)和記錄的移動(dòng)次數(shù)(一次記錄交換計(jì)為3次移動(dòng))。1．排序算法比較利用隨機(jī)函數(shù)產(chǎn)生30000個(gè)隨機(jī)整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進(jìn)行排序，并且（1）統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。輸出要求：對每一組測試，在一行里輸出終點(diǎn)星球接待站應(yīng)具有的最小容量，使得每艘飛船在到達(dá)時(shí)都可以保證讓全部旅客下船。每個(gè)名稱是由A～Z之間三個(gè)大寫字母組成的字符串，例如：ZJU。每組測試數(shù)據(jù)的第1行包含旅行的起點(diǎn)星球和終點(diǎn)星球的名稱和一個(gè)不超過500的正整數(shù)N（N為0標(biāo)志全部測試結(jié)束，不要對該數(shù)據(jù)做任何處理）。為了估計(jì)預(yù)算，現(xiàn)在旅游狂人需要知道終點(diǎn)星球的接待站應(yīng)該設(shè)計(jì)多大容量，才能使得每艘飛船在到達(dá)時(shí)都可以保證讓全部旅客下船。經(jīng)過謹(jǐn)慎調(diào)查，他目前掌握了一張各衛(wèi)星空間站可以臨時(shí)容納的旅客人數(shù)列表。本設(shè)計(jì)用一個(gè)主控菜單程序控制，共分為6個(gè)子系統(tǒng)。由于廣義表在結(jié)構(gòu)上較線性表復(fù)雜得多，因此，廣義表的運(yùn)算也不如線性表簡單。若網(wǎng)絡(luò)中任意兩機(jī)器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k ponents.”,其中k是網(wǎng)絡(luò)中連通集的個(gè)數(shù)。輸出要求：對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計(jì)算機(jī)的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結(jié)束。請寫出程序判斷：任意指定兩臺計(jì)算機(jī)，它們之間是否可以進(jìn)行文件傳輸？輸入要求：輸入若干測試數(shù)據(jù)組成。輸出要求：對每一組測試給定的A,B,C，在一行里輸出答案，即：如果C在A和B之間的路徑上，輸出Yes,否則輸出No。接下來M行，每行給出A,B,C三個(gè)小村 的編號，中間用空格分開。接下來有N1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。輸入要求：輸入由若干組測試數(shù)據(jù)組成?；疽螅海?）對一個(gè)描述工程的AOE網(wǎng)，應(yīng)判斷其是否能夠順利進(jìn)行。輸出要求：對每一組測試，在一行里輸出被某個(gè)特定變種所感染的機(jī)器數(shù)量。接下去的Q行里，每行給出一個(gè)變種的類型。每組數(shù)據(jù)的第1行包含2個(gè)整數(shù)M和N（1≤M,N≤500），接下來是一個(gè)M*N的矩陣表示網(wǎng)絡(luò)的初始感染狀態(tài)，其中的正、負(fù)整數(shù)的意義如題目描述中所定義。 本題的任務(wù)是：當(dāng)整個(gè)網(wǎng)絡(luò)被感染后，計(jì)算有多少臺機(jī)器被某個(gè)特定變種所感染。（隊(duì)列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：本題目要求對普通的二叉排序樹、AVL樹分別實(shí)現(xiàn)制定操作，并分析比較這兩種不同數(shù)據(jù)結(jié)構(gòu)對應(yīng)的一系列插入和刪除操作的效率。對于迷宮中任一位置，均可約定有東、南、西、北四個(gè)方向可通?？梢远S數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為（1，1），出口點(diǎn)的下標(biāo)為（n,n）。實(shí)現(xiàn)提示： 計(jì)算機(jī)解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個(gè)方向進(jìn)行探索，若能走通，則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直至出口位置，求得一條通路。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向，如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長度為4的車廂序列?；疽螅?，并能顯示壓縮后的相關(guān)地址和值； ，要求能從壓縮后的矩陣中讀出相應(yīng)的值；（限1 人完成）問題描述：給定一個(gè)算術(shù)表達(dá)式，通過程序求出最后的結(jié)果?；疽螅?； 、刪除、添加； ； ；（限1 人完成）問題描述：針對某一種行業(yè)的庫房的產(chǎn)品進(jìn)銷存情況進(jìn)行管理。表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個(gè)城市，10條邊）最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價(jià)。基本要求：城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值?；疽螅豪脝窝h(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)模擬此過程；鍵盤輸入總?cè)藬?shù)、初始報(bào)數(shù)上限值m及各人密碼；按照出列順序輸出各人的編號。（限1 人完成）問題描述：編號為1，2… n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。最終要把創(chuàng)建好的二叉排序樹轉(zhuǎn)換為二叉平衡排序樹。如：1，0000，0000，0000，0000?；疽螅豪秒p向循環(huán)鏈表，設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。（1）.建立文本文件（2）給定單詞的計(jì)數(shù)（3）檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置（4）主控菜單程序的結(jié)構(gòu) ① 頭文件包含 ② 菜單選項(xiàng)包含建立文件、單詞定位、單詞計(jì)數(shù)、退出程序 ③ 選擇14執(zhí)行相應(yīng)的操作，其他字符為非法。 設(shè)計(jì)要求與分析：要求編程建立一個(gè)文本文件，每個(gè)單詞不包含空格且不跨行，單詞由字符序列構(gòu)成且區(qū)分大小寫；統(tǒng)計(jì)給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個(gè)單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。（1）稀疏矩陣的存儲(chǔ)（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉(zhuǎn)置（限1 人完成）要求：實(shí)現(xiàn)樹與二叉樹的轉(zhuǎn)換的實(shí)現(xiàn)。（限1 人完成）現(xiàn)有學(xué)生成績信息文件1（），內(nèi)容如下 姓名 學(xué)號 語文 數(shù)學(xué) 英語張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…學(xué)生成績信息文件2（）,內(nèi)容如下: 姓名 學(xué)號 語文 數(shù)學(xué) 英語陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統(tǒng),要求如下: 1)實(shí)現(xiàn)對兩個(gè)文件數(shù)據(jù)進(jìn)行合并, 2) 3)(至少采用兩種排序方法實(shí)現(xiàn))4)輸入一個(gè)學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實(shí)現(xiàn))5)要求使用結(jié)構(gòu)體,)采用多種方法且算法正確者,（限1 人完成）要求：1)先任意創(chuàng)建一個(gè)圖；2)圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn) 3)要求用有向圖和無向圖分別實(shí)現(xiàn)4)要求用鄰接矩陣、鄰接表多種結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)（限1 人完成）要求：實(shí)現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實(shí)現(xiàn)。2)統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。要求：1)至少采用三種方法實(shí)現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。3)至少用兩種或兩種以上的方法實(shí)現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。用多種方法實(shí)現(xiàn)求出原來這群猴子共摘了多少個(gè)桃子。要求：遍歷的內(nèi)容應(yīng)是千姿百態(tài)的。樹與二叉樹的轉(zhuǎn)換的實(shí)現(xiàn)。、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，應(yīng)包含建樹的實(shí)現(xiàn)。要求：1)首先判定多項(xiàng)式是否稀疏2)分別采用順序和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)； 3)結(jié)果M(x)中無重復(fù)階項(xiàng)和無零系數(shù)項(xiàng)； 4)要求輸出結(jié)果的升冪和降冪兩種排列情況，可供小學(xué)生作業(yè)，并能給出分?jǐn)?shù)。、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)?！净疽蟆?)設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址；2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄?！具M(jìn)一步完成內(nèi)容】 1)系統(tǒng)功能的進(jìn)一步完善； 2)索引表采用樹表。（限1 人完成）【問題描述】設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完成圖書管理基本業(yè)務(wù)。設(shè)計(jì)要求：1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項(xiàng) 2)作為一個(gè)完整的系統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能力 3)上機(jī)能正常運(yùn)行，并寫出課程設(shè)計(jì)報(bào)告（限1 人完成）【問題描述】設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項(xiàng)目，直到選擇退出為止。5)存盤———save()。3)查找以姓名作為關(guān)鍵字 ———search()。設(shè)計(jì)內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能： 1)輸入信息——enter()。編寫一個(gè)通訊錄管理系統(tǒng)。求解算法多種。)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排 序樹T； 2)對二叉排序樹T作中序遍歷，輸出結(jié)果；3)輸入元素x,查找二叉排序樹T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；（限1 人完成）設(shè)計(jì)要求：在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。（限1 人完成）用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)1)以回車(39。（限1 人完成）主要分為兩大功能：1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會(huì)員管理(增加會(huì)員、查詢會(huì)員、刪除會(huì)員、借書信息)；（限1 人完成）實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出。兩者是影響查詢算法性能的關(guān)鍵因素。（限1 人完成）設(shè)計(jì)要求：針對計(jì)算機(jī)系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計(jì)劃，并滿足各學(xué)期課程數(shù)目大致相同。存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；（限1 人完成）功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件