第一篇：數據結構課程設計分類題目
線性表
順序表：
1、設有一元素為整數的線性表L=(a1,a2,a3,?,an),存放在一維數組A[N]中,設計一個算法,以表中an作為參考元素,將該表分為左、右兩部分,其中左半部分每個元素小于等于an,右半部分每個元素都大于an, an位于分界位置上(要求結果仍存放在A[N]中)。
2、設線性表存于A[1..size]的前num各分量中，且遞增有序。請設計一個算法，將x插入到線性表的適當位置上，以保持線性表的有序性。
3、線性表(a1,a2,a3,?,an)中元素遞增有序且按順序存儲于計算機內。要求設計一算法完成：（1）用最少時間在表中查找數值為x的元素。
（2）若找到將其與后繼元素位置相交換。
（3）若找不到將其插入表中并使表中元素仍遞增有序。
4、已知數組A[0:n-1]的元素類型為int，試設計算法將其調整為左右兩個部分，左邊所有元素為奇數，右邊所有元素為偶數。
5、設計一個算法從順序表L中刪除所有值為x的元素
6、設計一個算法從順序表L中刪除所有值為x到y之間（x<=y）的元素
鏈表：
1、假設有兩個按元素值遞增次序排列的線性表，均以單鏈表形式存儲。請編寫算法將這兩個單鏈表歸并為一個按元素值遞減次序排列的單鏈表，并要求利用原來兩個單鏈表的結點存放歸并后的單鏈表。
2、已知L1、L2分別為兩循環單鏈表的頭結點指針，m,n分別為L1、L2表中數據結點個數。要求設計一算法，用最快速度將兩表合并成一個帶頭結點的循環單鏈表。
3、設L為單鏈表的頭結點地址，其數據結點的數據都是正整數且無相同的，設計一個將該鏈表整理成數據遞增的有序單鏈表的算法。
5、設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的元素類型為整型，要求B、C表利用A表的結點）。
6、試編寫在帶頭結點的單鏈表中刪除（一個）最小值結點的（高效）算法。
7、設L為單鏈表的頭結點地址，請寫一算法，將鏈表中數據域值最小的那個鏈結點移到鏈表的最前面。要求：不得額外申請新的鏈結點。
8、已知兩個單鏈表A和B,其頭指針分別為heada和headb，編寫一個過程從單鏈表A中刪除自第i個元素起的共len個元素，然后將單鏈表A插入到單鏈表B的第j個元素之前。
9、已知遞增有序的單鏈表A,B分別存儲了一個集合，請設計算法以求出兩個集合A和B 的差集A-B（即僅由在A中出現而不在B中出現的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數。
10、已知一個單鏈表中每個結點存放一個整數，并且結點數不少于2，請設計算法以判斷該鏈表中第二項起的每個元素值是否等于其序號的平方減去其前驅的值，若滿足則返回ture，否則返回false.11、兩個整數序列A=a1,a2,a3,?,am和B=b1,b2,b3,?,bn已經存入兩個單鏈表中，設計一個算法，判斷序列B是否是序列A的子序列。
12、已知p指向雙向循環鏈表中的一個結點，其結點結構為data、llink、rlink三個域，寫出算法change(p),交換p所指向的結點和它的前綴結點的順序。
13、設有一個由正整數組成的無序單鏈表，編寫完成下列功能的算法：
（1）找出最小值結點，且打印該數值；
（2）若該數值是奇數，則將其與直接后繼結點的數值交換；
（3）若該數值是偶數，則將其直接后繼結點刪除。
14、在一個遞增有序的線性表中，有數值相同的元素存在。若存儲方式為單鏈表，設計算法去掉數值相同的元素，使表中不再有重復的元素。例如：（7，10，10，21，30，42，42，42，51，70）將變作（7，10，21，30，42，51，70）。
15、設有一個正整數序列組成的有序單鏈表（按遞增次序有序，且允許有相等的整數存在），試編寫能實現下列功能的算法 ：（要求用最少的時間和最小的空間）
(1)確定在序列中比正整數x大的數有幾個（相同的數只計算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的數有5個）；
(2)在單鏈表將比正整數x小的數按遞減次序排列；
(3)將正整數（比）x大的偶數從單鏈表中刪除。
16、編寫一個算法來交換單鏈表中指針P所指結點與其后繼結點，HEAD是該鏈表的頭指針，P指向該鏈表中某一結點。
17、．已知三個帶頭結點的線性鏈表A、B和C中的結點均依元素值自小至大非遞減排列（可能存在兩個以上值相同的結點），編寫算法對A表進行如下操作：使操作后的鏈表A中僅留下三個表中均包含的數據元素的結點，且沒有值相同的結點，并釋放所有無用結點。限定算法的時間復雜度為O（m+n+p），其中m、n和p分別為三個表的長度。
棧和隊列
1、設計一個算法，利用棧的基本運算將指定棧中的內容逆轉。
2、設計一個算法，利用棧的基本運算返回指定棧中棧底元素。
3、設有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區[O..maxsize-1],為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設計S1,S2有關入棧和出棧的操作算法。
4、設從鍵盤輸入一整數的序列：a1, a2, a3，?，an,試編寫算法實現：用棧結構存儲輸入的整數，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數并出棧。算法應對異常情況（入棧滿等）給出相應的信息。
4、設表達式以字符形式已存入數組E[n]中，‘#’為表達式的結束符，試寫出判斷表達式中括號（‘（’和‘）’）是否配對的C語言描述算法：EXYX(E);(注：算法中可調用棧操作的基本算法。)
5、從鍵盤上輸入一個逆波蘭表達式，用偽碼寫出其求值程序。規定：逆波蘭表達式的長度不超過一行，以$符作為輸入結束，操作數之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：234 34+2*$
6、寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數組中）。
7、設計一個算法，判斷一個算術表達式中的括號是否配對。算術表達式保存在帶頭結點的單循環鏈表中，每個結點有兩個域：ch和link，其中ch域為字符類型。
8、請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運算來實現該隊列的三個運算：enqueue:插入一個元素入隊列； dequeue:刪除一個元素出隊列；queue_empty：判隊列為空。（請寫明算法的思想及必要的注釋）
9、假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾結點，但不設頭指針，如圖所示（編者略），請寫出相應的入隊列和出隊列算法。
10、如果允許在循環隊列的兩端都可以進行插入和刪除操作。要求：
（1）寫出循環隊列的類型定義；（2）寫出“從隊尾刪除”和“從隊頭插入”的算法。
11、在一個循環鏈隊中只有尾指針（記為rear，結點結構為數據域data，指針域next），請給出這種隊列的入隊和出隊操作的實現過程。
12、已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的操作編寫一個算法，將隊列Q中的所有元素逆置。
13、已知求兩個正整數m與n的最大公因子的過程用自然語言可以表述為反復執行如下動作：第一步：若n等于零，則返回m；第二步：若m小于n，則m與n相互交換；否則，保存m，然后將n送m，將保存的m除以n的余數送n。
（1）將上述過程用遞歸函數表達出來（設求x除以y的余數可以用x MOD y 形式表示）。（2）寫出求解該遞歸函數的非遞歸算法。
14、試將下列遞歸過程改寫為非遞歸過程。void test(int &sum){ int x； scanf(x)；
if(x=0)sum=0 else {test(sum);sum+=x;} printf(sum)； }
樹和二叉樹
1、二叉樹用二叉鏈表存儲，寫一個算法將二叉樹中的葉子結點按從右至左的順序建立一個單鏈表。
2、知二叉樹用二叉鏈表存儲，寫出求二叉樹寬度的算法。所謂寬度是指在二叉樹的各層上，具有結點數最多的那一層上的結點總數。
3、叉樹用二叉鏈表存儲，寫一個算法交換各結點的左右子樹。
4、二叉樹用二叉鏈表存儲，若結點的左孩子的數據域的值大于右孩子數據域的值，則交換其左右子樹。
5、叉樹用二叉鏈表存儲，編寫一算法，判別給定的二叉樹是否為完全二叉樹。
6、個結點的完全二叉樹以一維數組為存儲結構，編寫一非遞歸算法實現對該樹的先序遍歷。
7、編寫一算法，在二叉樹中查找值為x的結點，并打印值為x的結點的所有祖先結點。
8、編寫中序遍歷二叉樹的非遞歸算法。
9、編寫先序遍歷二叉樹的非遞歸算法。
10、編寫后序二叉樹的非遞歸算法。
11、叉樹用二叉鏈表存儲，任給一個二叉樹表示的四則運算表達式，編寫算法，由該二叉樹輸出該表達式，若原表達式有括號亦加上。
12、有n個結點的完全二叉樹存放在一維數組A[1..n]中，試據此建立一棵用二叉鏈表表示的二叉樹，根由tree指向。
13、二叉樹排序方法如下：
（1）將第一個數據放在樹根。
（2）將隨后讀入的數據與樹根中的數據相比較，若比樹根大，則置于右子樹，反之則置于左子樹，建成一棵二叉樹；
（3）利用中序遍歷打印排序結果。用C語言編寫二叉樹的排序程序。
14、二叉樹結點的平衡因子（bf）定義為該結點的左子樹高度與右子樹高度之差。編寫算法計算二叉樹中各個結點的平衡因子。
15、設計算法：統計一棵二叉樹中所有葉結點的數目及非葉結點的數目。
16、已知二叉樹以二叉鏈表存儲，編寫算法完成：對于樹中每一個元素值為x的結點，刪去以它為根的子樹，并釋放相應的空間。
17、試編寫算法，對一棵以孩子—兄弟鏈表表示的樹統計葉子的個數。
18、設一棵二叉樹中各結點的值互不相同，其前序序列和中序序列分別存于兩個一維數組pre[1..n ]和mid[1..n ]中，試遍寫算法建立該二叉樹的二叉鏈表。
19、試設計一個算法打印出由根結點出發到達葉結點的所有路徑。
20、試寫出算法，求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結點的值。
21、給定一組項及其權值，假定項都存放于二叉樹的樹葉結點，則具有最小帶權外部路徑長度的樹稱為huffman 樹。編寫構造huffman 樹 的算法。
22、已知一中序線索二叉樹,寫一算法完成對它的中序掃描。
23、已知中序線索二叉樹T右子樹不空。設計算法，將S所指的結點作為T的右子樹中的一個葉子結點插入進去，并使之成為T的右子樹的（中序序列）第一個結點（同時要修改相應的線索關系）。
24、寫出算法，求出中序線索二叉樹中給定值為x的結點之后繼結點，返回該后繼結點的指針。線索樹中結點結構為：（ltag,lc,data,rc,rtag）。其中，data存放結點的值；lc，rc為指向左、右孩子或該結點前驅或后繼的指針；ltag，rtag為標志域，各值為：0，則lc，rc為指向左、右孩子的指針；值為1，則lc，rc為指向某前驅后繼結點的指針
25、設后序線索樹中結點構造為(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值為0時,Lchild、Rchild 分別為兒子指針；否則分別為直接前驅,直接后繼的線索。請寫出在后序線索樹上找給定結點p^ 的直接前驅q 的算法。
圖
1、設無向圖G有n個頂點，m條邊。試編寫用鄰接表存儲該圖的算法。（設頂點值用1～n或0～n-1編號）
2、已知有向圖有n個頂點,請寫算法,根據用戶輸入的偶對建立該有向圖的鄰接表。即接受用戶輸入的
3、給出以十字鏈表作存儲結構，建立圖的算法，輸入(i,j,v)其中i,j為頂點號，v為權值。
4、設有向G圖有n個點(用1,2,?,n表示),e條邊,寫一算法建立有向圖的逆鄰接表。
5、設已給出圖的鄰接矩陣，要求將圖的鄰接矩陣轉化為鄰接表，試實現其算法。
6、編寫算法，將圖的鄰接矩陣存儲改為鄰接表的存儲。
7、試寫一算法，判斷以鄰接表方式存儲的有向圖中是否存在由頂點Vi到頂點Vj的路徑（i<>j）。
8、已知無向圖采用鄰接表存儲方式，試寫出刪除邊（i，j）的算法。
9、假設有向圖以鄰接表存儲，試編寫算法刪除弧
10、假設有向圖以十字鏈表存儲，試編寫算法，插入弧
12、設有向圖用鄰接表表示,圖有n個頂點,表示為1至n,試寫一個算法求頂點k的入度(1 13、寫出圖的深度優先搜索DFS算法的非遞歸算法。 14、已知帶權圖用鄰接矩陣表示，編寫函數實現用Kruskal算法構造最小生成樹的算法。 15、編寫函數實現用Prim算法構造最小生成樹的算法。 16、編寫函數實現從指定頂點到其余各頂點的最短路徑的Dijkstra 算法。 17、實現圖的拓撲排序算法。 查找和排序 1、設計一個二分查找的遞歸算法。 2、設計一個算法，利用二分查找算法在一個有序表中插入一個元素x，并保持表的有序性。 3、實現散列表的相關算法 （1）給定一個序列，和散列函數，并利用線性探測再散列處理沖突，建立散列表。（2）編寫函數，查找某一個關鍵字（3）編寫函數，刪除找某一個關鍵字 4、設計一個順序查找算法 5、編寫一個算法，統計 一個字符串中出現字符的次數。 6、實現二叉查找樹的相關算法（1）給定序列，創建一二叉查找樹（2）判定一棵樹是否為二叉查找樹 （3）采用遞歸和非遞歸算法，查找某一個關鍵字（4）編寫函數，刪除找某一個關鍵字 7、編寫函數實現直接插入算法、希爾排序算法。 8、編寫函數實現冒泡排序算法、快速排序算法。 9、編寫函數實現堆排序算法。 10、編寫函數實現二路歸并排序算法。 11、編寫函數實現基數排序算法。 12、編寫函數實現可變長度的字符串序列快速排序算法。 數據結構課程設計題目 1.運動會分數統計（限1 人完成） 任務：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20） 功能要求： 1)可以輸入各個項目的前三名或前五名的成績； 2)能統計各學?？偡?，3)可以按學校編號或名稱、學校總分、男女團體總分排序輸出； 4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數據存入文件并能隨時查詢 6)規定：輸入數據形式和范圍：可以輸入學校的名稱，運動項目的名稱 輸出形式：有合理的提示，各學校分數為整形 界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。 存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構； 測試數據：要求使用 1、全部合法數據； 2、整體非法數據； 3、局部非法數據。進行程序測試，以保證程序的穩定。測試數據及測試結果請在上交的資料中寫明； 2.飛機訂票系統（限1 人完成） 任務：通過此系統可以實現如下功能： 錄入： 可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定） 查詢： 可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況； 訂票：（訂票情況可以存在一個數據文件中，結構自己設定） 可以訂票，如果該航班已經無票，可以提供相關可選擇航班； 退票： 可退票，退票后修改相關數據文件； 客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。 修改航班信息： 當航班信息改變可以修改航班數據文件 要求： 根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能； 3.文章編輯（限1 人完成） 功能：輸入一頁文字，程序可以統計出文字、數字、空格的個數。 靜態存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統計出其中英文字母數和空格數及整篇文章總字數；（2）統計某一字符串在文章中出現的次數，并輸出該次數；（3）刪除某一子串，并將后面的字符前移。 存儲結構使用線性表，分別用幾個子函數實現相應的功能； 輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。 輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”（3）輸出刪除某一字符串后的文章； 4.宿舍管理查詢軟件（限1 人完成） 1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： A.采用交互工作方式 B.建立數據文件，數據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現以下操作)A.按姓名查詢 B.按學號查詢 C.按房號查詢 3)打印任一查詢結果（可以連續操作） 5.校園導航問題（限1 人完成） 設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。 6.教學計劃編制問題（限1 人完成） 設計要求：針對計算機系本科課程，根據課程之間的依賴關系（如離散數學應在數據結構之前開設）制定課程安排計劃，并滿足各學期課程數目大致相同。 7.散列法的實驗研究（限1 人完成） 散列法中，散列函數構造方法多種多樣，同時對于同一散列函數解決沖突的方法也可以不同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數構造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。 8.圖書借閱管理系統（限1 人完成） 主要分為兩大功能： 1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)； 9.學生成績管理（限1 人完成） 實現功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。 10.活期儲蓄帳目管理（限1 人完成） 活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統設計要求： 1)能比較迅速地找到儲戶的帳戶，以實現存款、取款記賬； 2)能比較簡單，迅速地實現插入和刪除，以實現開戶和銷戶的需要。 11.二叉排序樹的實現（限1 人完成） 用順序和二叉鏈表作存儲結構 1)以回車('n')為輸入結束標志,輸入數列L，生成一棵二叉排 序樹T； 2)對二叉排序樹T作中序遍歷，輸出結果； 3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執行操作2)；否則輸出信息“無x”； 12.最小生成樹問題（限1 人完成） 設計要求：在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。存儲結構采用多種。求解算法多種。 13.通訊錄的制作（限1 人完成） 設計目的：用〈〈數據結構〉〉中的雙向鏈表作數據結構，結合C語言基本知識。編寫一個通訊錄管理系統。以把所學數據結構知識應用到實際軟件開發中去。設計內容：本系統應完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display();3)查找以姓名作為關鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設計要求： 1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項 2)作為一個完整的系統，應具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設計報告 14.哈夫曼編碼/譯碼器（限1 人完成）【問題描述】 設計一個利用哈夫曼算法的編碼和譯碼系統，重復地顯示并處理以下項目，直到選擇退出為止。【基本要求】 1)將權值數據存放在數據文件(文件名為data.txt，位于執行程序的當前目錄中)2)分別采用動態和靜態存儲結構 3)初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼； 6)設字符集及頻度如下表： 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設計的優化。 15.圖書管理系統（限1 人完成）【問題描述】 設計一個計算機管理系統完成圖書管理基本業務?！净疽蟆?/p> 1)每種書的登記內容包括書號、書名、著作者、現存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統主要功能如下： *采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現存量； *歸還：注銷對借閱者的登記，改變該書的現存量。【進一步完成內容】 1)系統功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序 6)軟件測試報告（包括所用到的數據及結果） 16.散列表的設計與實現（限1 人完成）【問題描述】 設計散列表實現電話號碼查找系統?！净疽蟆?/p> 1)設每個記錄有下列數據項：電話號碼、用戶名、地址； 2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄。【進一步完成內容】 1)系統功能的完善； 2)設計不同的散列函數，比較沖突率； 3)在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。 17.順序結構、動態鏈表結構下的一元多項式的加法、減法、乘法的實現。（限1 人完成） 設有一元多項式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn 請實現求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。要求： 1)首先判定多項式是否稀疏 2)分別采用順序和動態存儲結構實現； 3)結果M(x)中無重復階項和無零系數項； 4)要求輸出結果的升冪和降冪兩種排列情況 18.利用棧求表達式的值，可供小學生作業，并能給出分數。（限1 人完成） 要求：建立試題庫文件，隨機產生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數，能回顧歷史，給出與歷史分數比較后的評價 19.簡易文本編輯器（限1 人完成）要求： 1)具有圖形菜單界面； 2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數。 20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。（限1 人完成） 要求：遍歷的內容應是千姿百態的。 樹與二叉樹的轉換的實現。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。 要求：遍歷的內容應是千姿百態的。 21.學生搭配問題（限1 人完成） 一班有m個女生,有n個男生(m不等于n),現要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統模擬動態地顯示出上述過程,要求如下: 1)輸出每曲配對情況 2)計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值.3)盡量設計出多種算法及程序,可視情況適當加分 提示:用隊列來解決比較方便.22.猴子吃桃子問題（限1 人完成） 有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現求出原來這群猴子共摘了多少個桃子。 要求： 1)采用數組數據結構實現上述求解 2)采用鏈數據結構實現上述求解 3)采用遞歸實現上述求解 23.數制轉換問題（限1 人完成） 任意給定一個M進制的數x，請實現如下要求 1)求出此數x的10進制值（用MD表示）2)實現對x向任意的一個非M進制的數的轉換。 3)至少用兩種或兩種以上的方法實現上述要求（用棧解決，用數組解決，其它方法解決）。 24.排序綜合（限1 人完成） 利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求： 1)至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。 2)統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。 25.學生成績管理系統（限1 人完成）現有學生成績信息文件1（1.txt），內容如下 姓名 學號 語文 數學 英語 張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......… 學生成績信息文件2（2.txt）,內容如下: 姓名 學號 語文 數學 英語 陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統,要求如下: 1)實現對兩個文件數據進行合并,生成新文件3.txt 2)抽取出三科成績中有補考的學生并保存在一個新文件4.txt 3)合并后的文件3.txt中的數據按總分降序排序(至少采用兩種排序方法實現)4)輸入一個學生姓名后,能查找到此學生的信息并輸出結果(至少采用兩種查找方法實現)5)要求使用結構體,鏈或數組等實現上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現（限1 人完成）要求： 1)先任意創建一個圖； 2)圖的DFS,BFS的遞歸和非遞歸算法的實現 3)要求用有向圖和無向圖分別實現 4)要求用鄰接矩陣、鄰接表多種結構存儲實現 27.線索二叉樹的應用（限1 人完成） 要求：實現線索樹建立、插入、刪除、恢復線索的實現。 28.稀疏矩陣應用（限1 人完成） 要求：實現三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉置 29.樹的應用（限1 人完成） 要求：實現樹與二叉樹的轉換的實現。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現，應包含建樹的實現。 30.文本文件單詞的檢索與計數 設計要求與分析： 要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構成且區分大小寫；統計給定單詞在文本文件中出現的總次數；檢索輸出某個單詞出現在文本中的行號、在該行中出現的次數以及位置。該設計要求可分為三個部分實現：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數，輸入一個不含空格的單詞，統計輸出該單詞在文本中的出現次數；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現的次數以及在該行中的相應位置。（1）.建立文本文件（2）給定單詞的計數 （3）檢索單詞出現在文本文件中的行號、次數及其位置（4）主控菜單程序的結構 ① 頭文件包含 ② 菜單選項包含 建立文件、單詞定位、單詞計數、退出程序 ③ 選擇1-4執行相應的操作，其他字符為非法。 31.任意長的整數加法（限1 人完成） 問題描述：設計一個程序實現兩個任意長的整數的求和運算。 基本要求：利用雙向循環鏈表，設計一個實現任意長的整數進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。 32.二叉平衡排序樹（限1 人完成） 問題描述：從一棵空樹開始創建，在創建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調整。最終要把創建好的二叉排序樹轉換為二叉平衡排序樹。基本要求：1.創建（插入、調整、改組） 2.輸出 33.串的查找和替換（限1 人完成） 問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。 34.約瑟夫環（限1 人完成） 問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選一個正整數作為報數的上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數，如此下去，直至所有人全部出列為止，設計一個程序求出出列順序。 基本要求： 1、利用單循環鏈表作為存儲結構模擬此過程； 2、鍵盤輸入總人數、初始報數上限值m及各人密碼； 3、按照出列順序輸出各人的編號。 35.構造可以使n個城市連接的最小生成樹（限1 人完成） 問題描述：給定一個地區的n個城市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。基本要求： 1、城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。 2、表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊） 3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。 36.客戶消費積分管理系統（限1 人完成） 問題描述：針對客戶的消費情況，進行客戶管理，根據客戶的消費積分對客戶實行不同程度的打折優惠。基本要求： 1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據消費情況進行客戶積分的計算； 4.根據積分情況實行不同程度的打折優惠； 37.產品進銷存管理系統（限1 人完成） 問題描述：針對某一種行業的庫房的產品進銷存情況進行管理?；疽螅?/p> 1.采用一定的存儲結構對庫房的貨品及其數量進行分類管理； 2.可以進行產品類的添加、產品的添加、產品數量的添加； 3.能夠查詢庫房每種產品的總量、進貨日期、銷出數量、銷售時間等； 38.特殊矩陣的壓縮存儲算法的實現（限1 人完成）問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間?；疽螅?/p> 1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值； 39.算術表達式的求解（限1 人完成） 問題描述：給定一個算術表達式，通過程序求出最后的結果?；疽螅?/p> 1． 從鍵盤輸入要求解的算術表達式； 2． 采用棧結構進行算術表達式的求解過程； 3． 能夠判斷算術表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結果； 40.實時監控報警系統（限1 人完成）問題描述：建立一個報警和出警管理的系統 基本要求： 1.采用一定的存儲結構存儲報警信息，要求有內容、時間； 2.有一次的出警就應該在待處理的信息中刪除這條信息； 3.記錄出警信息； 4.待處理信息過多時會發出警告； 41.車廂調度（限1 人完成） 問題描述：假設停在鐵路調度站入口處的車廂序列的編號一次為1，2，3，4。設計一個程序，求出所有可能由此輸出的長度為4的車廂序列。 42.迷宮問題（棧）問題描述： 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論?；疽螅?/p> 首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數據的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數據： 迷宮的測試數據如下：左下角（1，1）為入口，右下角（8，9）為出口。實現提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發，順著某個方向進行探索，若能走通，則繼續往前進；否則沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。 可以二維數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容： （1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求： 本題目要求對普通的二叉排序樹、AVL樹分別實現制定操作，并分析比較這兩種不同數據結構對應的一系列插入和刪除操作的效率。要求測試對N個不同整數進行下列操作的效率：（1）按遞增順序插入N個整數，并按同樣順序刪除；（2）按遞增順序插入N個整數，并按相反順序刪除；（3）按隨機順序插入N個整數，并按隨機順序刪除； 要求N從1000到10000取值，并以數據規模N為橫軸，運行時間為縱軸，畫出3種不同數據結構對應的操作效率比較圖。 45.病毒測試程序 本題的任務是： 當整個網絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求： 輸入由若干組測試數據組成。 每組數據的第1行包含2個整數M和N（1≤M,N≤500），接下來是一個M*N的矩陣表示網絡的初始感染狀態，其中的正、負整數的意義如題目描述中所定義。 下面一行給出一個正整數Q，是將要查詢的變種的個數。接下去的Q行里，每行給出一個變種的類型。當M或N為0時，表示全部測試結束，不要對該數據做任何處理。輸出要求： 對每一組測試，在一行里輸出被某個特定變種所感染的機器數量。 46關鍵路徑問題（限1 人完成） 問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動。基本要求： （1）對一個描述工程的AOE網，應判斷其是否能夠順利進行。 （2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發生時間、最遲發生時間。 47.神秘國度的愛情故事 輸入要求：輸入由若干組測試數據組成。 每組數據的第1行包含一正整數N（1≤N≤50000），代表神秘國度中小村的個數，每個小村即從0到N-1編號。接下來有N-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數M（1≤M≤500000），代表著該組測試問題的個數。接下來M行，每行給出A,B,C三個小村 的編號，中間用空格分開。當N為0時，表示全部測試結束，不要對該數據做任何處理。 輸出要求：對每一組測試給定的A,B,C，在一行里輸出答案，即：如果C在A和B之間的路徑上，輸出Yes,否則輸出No。 48.并查集：檢查網絡 題目要求：給定一個計算機網絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？ 輸入要求：輸入若干測試數據組成。對于每一組測試，第1行包含一個整數N（≤10000），即網絡中計算機的總臺數，因而每臺計算機可用1到N之間的一個正整數表示。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計算機的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結束。當N為0時，表示全部測試結束，不要對該數據做任何處理。 輸出要求：對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。 當讀到S時，檢查整個網絡。若網絡中任意兩機器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k components.”,其中k是網絡中連通集的個數。兩組測試數據之間請輸出一空行分隔。 49.廣義表的應用 由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度 50.網絡流：宇宙旅行 題目要求： 在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經過謹慎調查，他目前掌握了一張各衛星空間站可以臨時容納的旅客人數列表。但旅客從一個星球飛往另一個星球時，需要在若干衛星空間站臨時停靠中轉，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求： 輸入若干組測試數據組成。 每組測試數據的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數N（N為0標志全部測試結束，不要對該數據做任何處理）。 接下來的N行里，數據格式為：sourcei capacityi，其中sourcei和destinationi是衛星空間站的名稱或起點、終點星球的名稱，正整數capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由A～Z之間三個大寫字母組成的字符串，例如：ZJU。測試數據中不包含任何到達起點星球的信息以及任何從終點星球出發的信息。輸出要求： 對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。 數據結構課程設計題目 以下8個題目任選其一。 1．排序算法比較 利用隨機函數產生30000個隨機整數，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進行排序，并且（1）統計每一種排序上機所花費的時間。 （2）統計在完全正序，完全逆序情況下記錄的比較次數和移動次數。（3）比較的指標為關鍵字的比較次數和記錄的移動次數(一次記錄交換計為3次移動)。 （4）對結果作簡單分析，包括對各組數據得出結果波動大小的解釋。2．圖的深度遍歷 對任意給定的圖（頂點數和邊數自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判?？眨崿F圖的深度優先搜索遍歷。畫出搜索順序示意圖。3．圖的廣度遍歷 對任意給定的圖（頂點數和邊數自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現圖的廣度優先搜索遍歷。畫出搜索順序示意圖。4．二叉樹的遍歷 對任意給定的二叉樹（頂點數自定）建立它的二叉鏈表存貯結構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判?？眨崿F二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結果。畫出搜索順序示意圖。5．鏈表操作 利用鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數、輸出等運算反復實現鏈表的這些操作（插入、刪除、查找、計數、輸出單獨寫成函數的形式），并能在屏幕上輸出操作前后的結果。畫出搜索順序示意圖。6．一元稀疏多項式簡單計數器（1）輸入并建立多項式 （2）輸出多項式，輸出形式為整數序列：n，c1，e1，c2，e2……cn，en，其中n是多項式的項數，ci，ei分別為第i項的系數和指數。序列按指數降序排列。（3）多項式a和b相加，建立多項式a+b，輸出相加的多項式。（4）多項式a和b相減，建立多項式a-b，輸出相減的多項式。用帶頭結點的單鏈表存儲多項式。測試數據： （1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．實現兩個鏈表的合并 基本功能要求：（1）建立兩個鏈表A和B，鏈表元素個數分別為m和n個。 （2）假設元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線性表C，使得： 當m>=n時，C=x1,y1,x2,y2,…xn,yn,…,xm 當n>m時，C=y1,x1,y2,x2,…ym,xm,…,yn 輸出線性表C： （1）用直接插入排序法對C進行升序排序，生成鏈表D，并輸出鏈表D。測試數據： （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．哈夫曼編碼的實現與應用 （1）從文件中讀入任意一篇英文短文（至少含3000個字符，文件為ASCII編碼的文本文件） （2）統計不同字符在文章中出現的頻率（空格、換行、標點等也按字符處理）（3）根據字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼。 （4）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率 （5）根據相應哈夫曼編碼，對編碼后的文件進行解碼，恢復成ASCII編碼的英文短文后輸出。 分析及設計步驟（供參考） 1.分析問題，給出數學模型，設計相應的數據結構。 1)分析問題特點，用數學表達式或其它形式描述其數學模型。2)選擇能夠體現問題本身特點的一種或幾種邏輯結構。 3)依據邏輯結構和問題特點，設計并選擇相應的存儲結構（順序存儲結構和鏈式存儲結構對應的算法實現有區別）。 2.算法設計 1)確定所需模塊：對于復雜的程序設計，要充分利用模塊化程序設計方法和面向對象思想，自頂向下，逐步細化。 2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調用關系：給出算法各模塊之間的關系圖示。3.上機實現程序 為提高工作效率，充分利用上機調試時間，在上機之前應列出程序清單。 4.用有代表性的各種測試數據去驗證算法及程序的正確性 5.算法分析及優化 經過上機調試，源程序運行正確，并且實現算法要求的功能，解決課程設計題目中給出的問題后，分析算法的時間復雜度和空間復雜度，如有可能對程序進行優化改進。 課程設計報告范例（參考） 約瑟夫環問題。 問題描述：設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數密碼。開始時任意給出一個報數上限值m，從第一個人開始順時針方向自1起順序報數，報到m時停止報數，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數；如此下去，直到所有人全部出列為止。要求設計一個程序模擬此過程，并給出出列人的編號序列?；疽螅?/p> （1）初始報數上限值m和測試數據在程序中確定；（2）用帶頭結點的單循環鏈表作數據元素的存儲結構；（3）把帶頭結點的單循環鏈表作為抽象數據類型設計。測試數據： n = 7，七個人的密碼依次為3,1,7,2,4,8,4 初始報數上限值m = 20 算法思想： JesephRing()函數是實現問題要求的主要函數，其算法思想是：從1至m對帶頭結點的單循環鏈表循環計數，到m時，輸出該結點的編號值，將該結點的密碼作為新的m值，再從該結點的下一個結點起重新自1起循環計數；如此下去，直到單循環鏈表空時循環過程結束。模塊劃分： （1）帶頭結點的單循環鏈表抽象數據類型SCLinList，其中包括基本操作的函數有：初始化操作函數、插入一個結點操作函數、刪除一個結點操作函數、取一個結點數據操作函數和判表是否非空操作函數。該抽象數據類型文件名為SCLinList.h。 （2）void SCLLDeleteAfter(SCLNode *p)，其功能是刪除帶頭結點的單循環鏈表中指針p所指結點的下一個結點。這是對帶頭結點的單循環鏈表抽象數據類型SCLinList，補充本問題需要的一個操作函數。（3）void JesephRing(SCLNode *head, int m)，其功能是對帶頭結點的單循環鏈表head,以m為初始報數上限值實現問題要求。 （4）void main(void)，主函數，功能是給出測試數據值，建立測試數據值的帶頭結點單循環鏈表，調用JesephRing()函數實現問題要求。數據結構： （1）數據類型DataType定義如下： typedef struct { int number;int cipher;} DataType; （2）帶頭結點單循環鏈表抽象數據類型SCLinList。 （3）帶頭結點單循環鏈表抽象數據類型的結點結構定義如下： typedef struct node { DataType data;struct node *next;} SCLNode;源程序： 源程序存放在兩個文件中，文件SCLinList.h是帶頭結點單循環鏈表抽象數據類型，文件Exam3-9.c是主程序。 文件SCLinList.h： typedef struct node { DataType data;struct node *next;} SCLNode;/*結點結構定義*/ void SCLLInitiate(SCLNode **head)/*初始化*/ { if((*head =(SCLNode *)malloc(sizeof(SCLNode)))== NULL)exit(1);(*head)->next = *head;} int SCLLInsert(SCLNode *head, int i, DataType x)/*插入一個結點*/ { SCLNode *p, *q;int j;p = head->next;j = 1;while(p!= head && j < i1 && i!= 1){ printf(“插入位置參數錯！”);return 0;} if((q =(SCLNode *)malloc(sizeof(SCLNode)))== NULL)exit(1);q->data = x;q->next = p->next;p->next = q;return 1;} int SCLLDelete(SCLNode *head, int i, DataType *x)/*刪除一個結點*/ { SCLNode *p, *q;int j;p = head;j = 0;while(p->next!= head && j < i1){ printf(“刪除位置參數錯！”);return 0;} q = p->next;p->next = p->next->next;*x = q->data;free(q);return 1;} int SCLLGet(SCLNode *head, int i, DataType *x)/*取一個結點數據元素值*/ { SCLNode *p;int j;p = head;j = 0;while(p->next!= head && j < i){ p = p->next;j++;} if(j!= i){ printf(“取元素位置參數錯！”);return 0;} *x = p->data;return 1;} int SCLLNotEmpty(SCLNode *head)/*鏈表非空否*/ { if(head->next == head)return 0;else return 1;} 文件Exam3-9.c： #include printf(“ %d ”, curr->data.number);m = curr->data.cipher;curr = curr->next;if(curr == head)curr = curr->next;SCLLDeleteAfter(pre);} } void main(void){ DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}};int n = 7, m = 20, i;SCLNode *head;SCLLInitiate(&head);/*初始化*/ for(i = 1;i <= n;i++)/*循環插入建立單循環鏈表鏈表*/ SCLLInsert(head, i, test[i-1]);JesephRing(head, m);/*約瑟夫環問題函數*/ } 測試情況： 程序輸出為： 6 1 4 7 2 3 5 各種排序比較結果（參考） 直接插入的比較圖表***030002500直接插入的移動圖表比較次數2000系列1******4738291100次數移動次數2000系列1******4738291100次數 冒泡的比較次數***00冒泡的移動圖表***00比較次數移動次數*********1100執行次數系列*********91100次數系列1 SHELL的比較次數12001000800***01200SHELL的移動圖表比較次數移動次數******1100執行次數系列******564738291100次數系列1 快速排序的比較次數800700600快速排序的移動圖表540520500比較次數移動次數******4738291100執行次數系列******8291100次數簡單選擇的移動圖表350300250系列1 簡單選擇的比較次數***0比較次數移動次數300025002000******4738291100執行次數堆排序的比較次數107010601050系列1200系列1******8291100次數 堆排序的移動圖表***0比較次數移動次數*********00執行次數系列117401720******65564738291100次數系列1 數據結構課程設計題目 數據結構課程設計題目(大題目).doc 一、公司銷售管理系統 項目開發基本要求 1．客戶信息管理：對客戶的基本信息進行添加、修改和刪除。2．產品信息管理：對產品的基本信息進行添加、修改和刪除。3．供應商信息管理：對供應商的基本信息進行添加、修改和刪除。4．訂單信息管理：對訂單的基本信息進行添加、修改和刪除。 二、高校科研管理系統 系統主要用于幫助高?；蚩蒲袉挝还芾砗途S護各項科研相關資料 項目開發基本要求 1．系統用戶管理模塊：為系統新用戶設置用戶名及口令；操作員更改自己的系統口令。2．數據字典管理模塊：管理項目性質包括：分為國家自然科學基金、863、部省科委及企業集團四種情況；范圍包括：分為全國、國際、地方三種情況；檢索源包括：分為EI、SCI、核心和一般四種情況。 3．項目參加人員管理模塊包括：顯示添加修改刪除查詢。4．項目基本情況模塊包括：顯示添加修改刪除查詢。5．項目獲獎情況模塊包括：顯示添加修改刪除查詢。6．期刊論文管理模塊包括：顯示添加修改刪除查詢。7．著作管理模塊包括：顯示添加修改刪除查詢。 8．科研工作量統計模塊：按照學?？蒲泄ぷ髁坑嬎戕k法，為每位科研人員進行科研工作量的計算和統計。 9．科研積分統計模塊：按照學校科研積分計算辦法，為每位科研人員進行科研計分的計算和統計。 三、網絡五子棋對戰 四、不同排序算法模擬 五、科學計算器 數據結構課程設計題目 1.運動會分數統計 任務：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20） 功能要求： 1)可以輸入各個項目的前三名或前五名的成績； 2)能統計各學?？偡?，3)可以按學校編號或名稱、學?？偡?、男女團體總分排序輸出； 4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數據存入文件并能隨時查詢 6)規定：輸入數據形式和范圍：可以輸入學校的名稱，運動項目的名稱 輸出形式：有合理的提示，各學校分數為整形 界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。 存儲結構：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構； 測試數據：要求使用 1、全部合法數據； 2、整體非法數據； 3、局部非法數據。進行程序測試，以保證程序的穩定。測試數據及測試結果請在上交的資料中寫明； 2.飛機訂票系統 任務：通過此系統可以實現如下功能： 錄入： 可以錄入航班情況（數據可以存儲在一個數據文件中，數據結構、具體數據自定） 查詢： 可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）； 可以輸入起飛抵達城市，查詢飛機航班情況； 訂票：（訂票情況可以存在一個數據文件中，結構自己設定） 可以訂票，如果該航班已經無票，可以提供相關可選擇航班； 退票： 可退票，退票后修改相關數據文件； 客戶資料有姓名，證件號，訂票數量及航班情況，訂單要有編號。 修改航班信息： 當航班信息改變可以修改航班數據文件 要求： 根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能； 3.文章編輯 功能：輸入一頁文字，程序可以統計出文字、數字、空格的個數。 靜態存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統計出其中英文字母數和空格數及整篇文章總字數；（2）統計某一字符串在文章中出現的次數，并輸出該次數；（3）刪除某一子串，并將后面的字符前移。 存儲結構使用線性表，分別用幾個子函數實現相應的功能； 輸入數據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數字及標點符號。 輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數”、“數字個數”、“空格個數”、“文章總字數”（3）輸出刪除某一字符串后的文章； 4.宿舍管理查詢軟件 1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： A.采用交互工作方式 B.建立數據文件，數據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現以下操作)A.按姓名查詢 B.按學號查詢 C.按房號查詢 3)打印任一查詢結果（可以連續操作） 5.校園導航問題 設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。 6.教學計劃編制問題 設計要求：針對計算機系本科課程，根據課程之間的依賴關系（如離散數學應在數據結構之前開設）制定課程安排計劃，并滿足各學期課程數目大致相同。 7.散列法的實驗研究 散列法中，散列函數構造方法多種多樣，同時對于同一散列函數解決沖突的方法也可以不同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數構造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。 8.圖書借閱管理系統 主要分為兩大功能： 1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)； 9.學生成績管理 實現功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。 10.活期儲蓄帳目管理 活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統設計要求： 1)能比較迅速地找到儲戶的帳戶，以實現存款、取款記賬； 2)能比較簡單，迅速地實現插入和刪除，以實現開戶和銷戶的需要。 11.二叉排序樹的實現 用順序和二叉鏈表作存儲結構 1)以回車('n')為輸入結束標志,輸入數列L，生成一棵二叉排 序樹T； 2)對二叉排序樹T作中序遍歷，輸出結果； 3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執行操作2)；否則輸出信息“無x”； 12.最小生成樹問題 設計要求：在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。存儲結構采用多種。求解算法多種。 13.通訊錄的制作 設計目的：用〈〈數據結構〉〉中的雙向鏈表作數據結構，結合C語言基本知識。編寫一個通訊錄管理系統。以把所學數據結構知識應用到實際軟件開發中去。設計內容：本系統應完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display(); 3)查找以姓名作為關鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設計要求： 1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項 2)作為一個完整的系統，應具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設計報告 14.哈夫曼編碼/譯碼器 【問題描述】 設計一個利用哈夫曼算法的編碼和譯碼系統，重復地顯示并處理以下項目，直到選擇退出為止?！净疽蟆?/p> 1)將權值數據存放在數據文件(文件名為data.txt，位于執行程序的當前目錄中)2)分別采用動態和靜態存儲結構 3)初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼； 6)設字符集及頻度如下表： 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設計的優化。 15.圖書管理系統 【問題描述】 設計一個計算機管理系統完成圖書管理基本業務?！净疽蟆?/p> 1)每種書的登記內容包括書號、書名、著作者、現存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統主要功能如下： *采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現存量； *歸還：注銷對借閱者的登記，改變該書的現存量?！具M一步完成內容】 1)系統功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序 6)軟件測試報告（包括所用到的數據及結果） 16.散列表的設計與實現 【問題描述】 設計散列表實現電話號碼查找系統。【基本要求】 1)設每個記錄有下列數據項：電話號碼、用戶名、地址； 2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄?！具M一步完成內容】 1)系統功能的完善； 2)設計不同的散列函數，比較沖突率； 3)在散列函數確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。 17.順序結構、動態鏈表結構下的一元多項式的加法、減法、乘法的實現。 設有一元多項式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn 請實現求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。 要求： 1)首先判定多項式是否稀疏 2)分別采用順序和動態存儲結構實現； 3)結果M(x)中無重復階項和無零系數項； 4)要求輸出結果的升冪和降冪兩種排列情況 18.利用棧求表達式的值，可供小學生作業，并能給出分數。 要求：建立試題庫文件，隨機產生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數，能回顧歷史，給出與歷史分數比較后的評價 19.簡易文本編輯器 要求： 1)具有圖形菜單界面； 2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數。 20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。 要求：遍歷的內容應是千姿百態的。 樹與二叉樹的轉換的實現。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現，應包含建樹的實現。 要求：遍歷的內容應是千姿百態的。 21.學生搭配問題 一班有m個女生,有n個男生(m不等于n),現要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統模擬動態地顯示出上述過程,要求如下: 1)輸出每曲配對情況 2)計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值.3)盡量設計出多種算法及程序,可視情況適當加分 提示:用隊列來解決比較方便.22.猴子吃桃子問題 有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現求出原來這群猴子共摘了多少個桃子。 要求： 1)采用數組數據結構實現上述求解 2)采用鏈數據結構實現上述求解 3)采用遞歸實現上述求解 23.數制轉換問題 任意給定一個M進制的數x，請實現如下要求 1)求出此數x的10進制值（用MD表示）2)實現對x向任意的一個非M進制的數的轉換。 3)至少用兩種或兩種以上的方法實現上述要求（用棧解決，用數組解決，其它方法解決）。 24.排序綜合 利用隨機函數產生N個隨機整數（20000以上），對這些數進行多種方法進行排序。要求： 1)至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。 2)統計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。 25.學生成績管理系統 現有學生成績信息文件1（1.txt），內容如下 姓名 學號 語文 數學 英語 張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......… 學生成績信息文件2（2.txt）,內容如下: 姓名 學號 語文 數學 英語 陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統,要求如下: 1)實現對兩個文件數據進行合并,生成新文件3.txt 2)抽取出三科成績中有補考的學生并保存在一個新文件4.txt 3)合并后的文件3.txt中的數據按總分降序排序(至少采用兩種排序方法實現) 4)輸入一個學生姓名后,能查找到此學生的信息并輸出結果(至少采用兩種查找方法實現)5)要求使用結構體,鏈或數組等實現上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現 要求： 1)先任意創建一個圖； 2)圖的DFS,BFS的遞歸和非遞歸算法的實現 3)要求用有向圖和無向圖分別實現 4)要求用鄰接矩陣、鄰接表多種結構存儲實現 27.線索二叉樹的應用 要求：實現線索樹建立、插入、刪除、恢復線索的實現。 28.稀疏矩陣應用 要求：實現三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉置 29.樹的應用 要求：實現樹與二叉樹的轉換的實現。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現，應包含建樹的實現。 30.文本文件單詞的檢索與計數 設計要求與分析： 要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構成且區分大小寫；統計給定單詞在文本文件中出現的總次數；檢索輸出某個單詞出現在文本中的行號、在該行中出現的次數以及位置。該設計要求可分為三個部分實現：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數，輸入一個不含空格的單詞，統計輸出該單詞在文本中的出現次數；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現的次數以及在該行中的相應位置。（1）.建立文本文件（2）給定單詞的計數 （3）檢索單詞出現在文本文件中的行號、次數及其位置（4）主控菜單程序的結構 ① 頭文件包含 ② 菜單選項包含 建立文件、單詞定位、單詞計數、退出程序 ③ 選擇1-4執行相應的操作，其他字符為非法。 31.任意長的整數加法 問題描述：設計一個程序實現兩個任意長的整數的求和運算。 基本要求：利用雙向循環鏈表，設計一個實現任意長的整數進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。 32.二叉平衡排序樹 問題描述：從一棵空樹開始創建，在創建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調整。最終要把創建好的二叉排序樹轉換為二叉平衡排序樹。基本要求：1.創建（插入、調整、改組）2.輸出 33.串的查找和替換 問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。 34.約瑟夫環 問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數）。一開始任選一個正整數作為報數的上限值m，從第一個人開始按順時針方向自1開始順序報數，報到m時停止報數，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數，如此下去，直至所有人全部出列為止，設計一個程序求出出列順序?；疽螅?/p> 1、利用單循環鏈表作為存儲結構模擬此過程； 2、鍵盤輸入總人數、初始報數上限值m及各人密碼； 3、按照出列順序輸出各人的編號。 35.構造可以使n個城市連接的最小生成樹 問題描述：給定一個地區的n個城市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?/p> 1、城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。 2、表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊） 3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。 36.客戶消費積分管理系統 問題描述：針對客戶的消費情況，進行客戶管理，根據客戶的消費積分對客戶實行不同程度的打折優惠?；疽螅?/p> 1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據消費情況進行客戶積分的計算； 4.根據積分情況實行不同程度的打折優惠； 37.產品進銷存管理系統 問題描述：針對某一種行業的庫房的產品進銷存情況進行管理?；疽螅?/p> 1.采用一定的存儲結構對庫房的貨品及其數量進行分類管理； 2.可以進行產品類的添加、產品的添加、產品數量的添加； 3.能夠查詢庫房每種產品的總量、進貨日期、銷出數量、銷售時間等； 38.特殊矩陣的壓縮存儲算法的實現 問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間。基本要求： 1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值； 39.算術表達式的求解 問題描述：給定一個算術表達式，通過程序求出最后的結果。基本要求： 1． 從鍵盤輸入要求解的算術表達式； 2． 采用棧結構進行算術表達式的求解過程； 3． 能夠判斷算術表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結果； 40.實時監控報警系統 問題描述：建立一個報警和出警管理的系統 基本要求： 1.采用一定的存儲結構存儲報警信息，要求有內容、時間； 2.有一次的出警就應該在待處理的信息中刪除這條信息； 3.記錄出警信息； 4.待處理信息過多時會發出警告； 41.車廂調度 問題描述：假設停在鐵路調度站入口處的車廂序列的編號一次為1，2，3，4。設計一個程序，求出所有可能由此輸出的長度為4的車廂序列。 42.迷宮問題（棧）問題描述： 以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論?；疽螅?/p> 首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數據的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數據： 迷宮的測試數據如下：左下角（1，1）為入口，右下角（8，9）為出口。實現提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發，順著某個方向進行探索，若能走通，則繼續往前進；否則沿著原路退回，換一個方向繼續探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。 可以二維數組存儲迷宮數據，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容： （1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求： 本題目要求對普通的二叉排序樹、AVL樹分別實現制定操作，并分析比較這兩種不同數據結構對應的一系列插入和刪除操作的效率。要求測試對N個不同整數進行下列操作的效率：（1）按遞增順序插入N個整數，并按同樣順序刪除；（2）按遞增順序插入N個整數，并按相反順序刪除；（3）按隨機順序插入N個整數，并按隨機順序刪除； 要求N從1000到10000取值，并以數據規模N為橫軸，運行時間為縱軸，畫出3種不同數據結構對應的操作效率比較圖。 45.病毒測試程序 本題的任務是： 當整個網絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求： 輸入由若干組測試數據組成。 每組數據的第1行包含2個整數M和N（1≤M,N≤500），接下來是一個M*N的矩陣表示網絡的初始感染狀態，其中的正、負整數的意義如題目描述中所定義。 下面一行給出一個正整數Q，是將要查詢的變種的個數。接下去的Q行里，每行給出一個變種的類型。當M或N為0時，表示全部測試結束，不要對該數據做任何處理。輸出要求： 對每一組測試，在一行里輸出被某個特定變種所感染的機器數量。 46關鍵路徑問題 問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動。基本要求： （1）對一個描述工程的AOE網，應判斷其是否能夠順利進行。 （2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發生時間、最遲發生時間。 47.神秘國度的愛情故事 輸入要求：輸入由若干組測試數據組成。 每組數據的第1行包含一正整數N（1≤N≤50000），代表神秘國度中小村的個數，每個小村即從0到N-1編號。接下來有N-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數M（1≤M≤500000），代表著該組測試問題的個數。接下來M行，每行給出A,B,C三個小村 的編號，中間用空格分開。 當N為0時，表示全部測試結束，不要對該數據做任何處理。 輸出要求：對每一組測試給定的A,B,C，在一行里輸出答案，即：如果C在A和B之間的路徑上，輸出Yes,否則輸出No。 48.并查集：檢查網絡 題目要求：給定一個計算機網絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？ 輸入要求：輸入若干測試數據組成。對于每一組測試，第1行包含一個整數N（≤10000），即網絡中計算機的總臺數，因而每臺計算機可用1到N之間的一個正整數表示。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計算機的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結束。當N為0時，表示全部測試結束，不要對該數據做任何處理。 輸出要求：對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。 當讀到S時，檢查整個網絡。若網絡中任意兩機器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k components.”,其中k是網絡中連通集的個數。兩組測試數據之間請輸出一空行分隔。 49.廣義表的應用 由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度 50.網絡流：宇宙旅行 題目要求： 在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經過謹慎調查，他目前掌握了一張各衛星空間站可以臨時容納的旅客人數列表。但旅客從一個星球飛往另一個星球時，需要在若干衛星空間站臨時停靠中轉，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求： 輸入若干組測試數據組成。 每組測試數據的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數N（N為0標志全部測試結束，不要對該數據做任何處理）。 接下來的N行里，數據格式為：sourcei capacityi，其中sourcei和destinationi是衛星空間站的名稱或起點、終點星球的名稱，正整數capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由A～Z之間三個大寫字母組成的字符串，例如：ZJU。 測試數據中不包含任何到達起點星球的信息以及任何從終點星球出發的信息。輸出要求： 對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。 51：算術運算測試 功能要求：該程序用圖形界面實現十道100以內加減法數學題，能根據題目計算出答案，與輸入答案對比，判斷做題是否正確，最后計算分數。 界面要求：用圖形界面實現。52：猜數游戲 功能要求：計算機產生隨機數，猜中即勝，猜不中，提示是大了還是小了，繼續猜，直至猜到，給出所用時間和評語。 界面要示：用圖形界面實現。 53、學生成績管理 功能要求： 1)輸入十個同學的學號，姓名，四科成績（應用數學、大學英語、Java程序設計、計算機應用基礎） 2)計算出平均成績。以平均成績降序輸出成績表。3)輸出全組各科平均分，最高分和最低分。4)輸入姓名查詢成績 界面要示：用圖形界面實現。54．矩陣的運算 采用鏈表表示稀疏矩陣，并實現矩陣的加法，乘法，求逆運算, 要求：要檢查有關運算的條件，并對錯誤的條件產生報警。 55．建立二叉樹和線索二叉樹 分別用以下方法建立二叉樹并用圖型顯示出來： 用先序遍歷的輸入序列 用層次遍歷的輸入序列 用先序和中序遍歷的結果 最后對所建立的二叉樹進行中序線索化，并對此線索樹進行中序遍歷(不使用棧)。 56．銀行業務模擬： 客戶業務分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。 銀行有兩個服務窗口，相應的有兩個隊列。客戶到達銀行后先排第一個隊。處理每個客戶業務時，如果屬于第一種，且申請額超出銀行現存資金總額而得不到滿足，則立即排入第二隊等候，直至滿足時才離開銀行，否則業務處理完后立即離開銀行。每接待完一個第二種業務的客戶，則順序檢查和處理（如果可能）第二個隊列的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶（第二種業務）被接待之前的數額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查（因為此時已不可能還有能滿足者）轉而繼續接待第一個隊列的客戶。任何時刻都只開一個窗口。假設檢查不需要時間。營業時間結束時所有客戶立即離開銀行。寫一個上述銀行業務的事件驅動模擬系統，通過模擬方法求出客戶在銀行內逗留的平均時間。 57.假設一個賓館有n個標準的客房，每個標準客房有m個標準間，利用鏈表、棧或者隊列等數據結構設計出具有訂房和退房等功能的管理系統。 數據結構課程設計 一、教學目的和要求 課程設計是加強學生實踐能力的一個強有力手段。綜合課設1主要針對數據結構和c/c++語言開展的實踐性課程。要求學生掌握數據結構的應用、算法的編寫、類C語言的算法轉換成C（C++）程序并上機調試的基本方法。課程設計要求學生在完成程序設計的同時能夠寫出比較規范的課程設計報告。培養學生綜合運用所學理論知識解決復雜實際問題的實踐能力、研究性學習能力和團隊合作能力。 二、課程設計要求 1、選好題目：每題一人，每班每個題目只允許一人選做，學習委員將選題情況在課設第一天統計上交。 2、課設報告獨立思考，獨立完成：課設報告出現雷同超過60%，不論什么原因，一律不及格。班和班之間，相同題目的同學，可以組成小組，相互討論，共同完成課程設計中各任務的設計和調試要求。小組成員間，算法思路可以相同，程序可以類似，但不能完全一樣。課設報告不能雷同超過60%。 3、做好上機準備：每次上機前，要事先編制好準備調試的程序，認真想好調試步驟和有關環境的設置方法，準備好有關的文件。 4、設計要點： ⑴需求分析： 在該部分中敘述總共幾個模塊，每個模塊的功能要求。 ⑵系統設計 總體設計：定義某個數據結構的抽象數據類型及其他算法的功能說明。 詳細設計：在此定義存儲結構，每個部分的算法設計說明（建議描述算法采用流程圖）。⑶編碼實現 各個算法實現的源程序，對每個題目要有相應的源程序（每個功能模塊采用不同的函數實現）。源程序要按照程序的規則來編寫，要結構清晰，重點函數的重點變量，重點功能部分要加上清晰的程序注釋。程序能夠運行，要有基本的容錯功能，盡量避免出現操作失誤時出現死循環。⑷調試分析 給出實現功能的一組或多組測試數據，程序調試后，將按照此測試數據進行測試的結果列出來。時間復雜度分析，每個模塊設計和調試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進設想。 ⑸課設總結：課程設計過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調試能力的思考、對數據結構這門課程的思考、在課程設計過程中對《數據結構》課程的認識等內容。 5、實現的結果必須進行檢查和演示；程序源代碼和程序的說明文件必須上交，作為考核內容的一部分；（上交時文件夾的取名規則為：“課設題目（***設計完成）”，如“資源管理系統的設計與實現（張三設計完成）”。該文件夾下包括三個目錄：“源代碼”、“可執行文件”、“張三_課程設計報告”。由學習委員按規定時間統一上交）。 6、報告提交 形式: 紙介質(要求B5紙張打印，加封皮)和電子文檔。 三、考核方法和內容 根據課程設計過程中學生的學生態度、題目完成情況、課程設計報告書的質量和回答問題的情況等按照10%、40%、30%、20%加權綜合打分。成績評定實行優秀、良好、中等、及格和不及格五個等級。 評分標準： 優秀：答辯所有問題都能答出+報告良好 良好：答辯所有問題都能答出+報告一般 中等：答辯大部分問題能答出+報告良好 及格：答辯大部分問題能答出+報告一般 不及格：答辯幾乎答不出問題 或者 報告幾乎都是代碼 或者 雷同部分達到60% 課設報告的裝訂順序如下： 任務書（簽名，把題目要求貼在相應位置，注意下劃線）-----目錄（注意目錄的格式，頁碼）----- 1、設計任務（題目要求）----- 2、需求分析（準備選用什么數據邏輯結構？數據元素包含哪些屬性？需要哪些函數？為什么要這樣設計？最后列出抽象數據類型定義）----- 3、系統設計（設計實現抽象數據類型，包含選擇什么物理存儲方式？數據元素的結構體或類定義，以及各函數的設計思路，算法，程序流程圖等）---- 4、編碼實現（重要函數的實現代碼）----- 5、調試分析（選擇多組測試數據、運行截圖、結果分析）----- 6、課設總結（心得體會）----- 7、謝辭----- 8、參考文獻； 課設報告打印要求： B5紙張打印，報告總頁數控制在10—15頁內，報告中不能全是代碼，報告中代碼總量控制在150行內。版式：無頁眉，有頁碼，頁碼居中 字號：小四，單倍行距 字體：宋體+Times new Romar 截圖：截圖要配圖的編號和圖的題目，如：“圖1 Insert函數流程圖” 四、課程設計的題目 1、運動會分數統計 2、集合的并、交和差運算的程序 3、長整數的加法運算 4、一元多項式計算器 5、車廂調度問題 6、文章編輯 7、識別廣義表的頭或尾的演示 8、哈夫曼樹及其編碼 9、校園導游咨詢 10、地圖著色問題 11、內部排序算法比較 12、哈希表的設計與實現——線性探測再散列 13、哈希表的設計與實現——二次探測再散列 14、哈希表的設計與實現——鏈地址法 15、火車售票系統 16、圖書管理系統 17、客戶消費積分管理系統 18、產品進銷存管理系統 19、學生成績管理系統的設計與實現 20、通訊錄管理系統的設計與實現——線性表 21、通訊錄管理系統的設計與實現——哈希表 22、簡單目錄管理系統的設計與實現 23、最短旅程的求解 24、迷宮求解 25、家譜管理系統的設計與實現 26、宿舍管理查詢軟件 27、語言中平衡符號的問題 28、算術表達式求解 29、表達式求值，可供小學生作業，并能給出分數 30、數制轉換問題 31、病人就醫管理 32、九宮格問題 33、銀行業務模擬 34、停車場管理 35、關鍵路徑問題 36、地鐵站建設問題 37、服裝銷售系統 38、歌星大獎賽 39、機房機位預約模擬系統 40、歌曲信息管理系統 41、簡單的試題庫管理系統 42、學生點名系統 43、猜數游戲 五、數據結構課程設計的具體內容 要求：全部采用數據結構課程中的內容實現，采用C或C++實現，邏輯結構只能選線性結構、樹型結構、圖型結構、集合結構中的一種，不能用數據庫。 1、運動會分數統計 問題描述： 參加運動會的n個學校編號為1～n。比賽分成m個男子項目和w個女子項目，項目編號分別為1～m和m+1～m＋w。由于各項目參加人數差別較大，有些項目取前五名，得分順序為11，7，4，2，1；還有些項目只取前三名，得分順序為5，3，2。哪些項目取前五名或前三名由學生自己設定。寫一個統計程序產生各種成績單和得分報表?；疽螅?/p> (1)各項目結束時，輸入前三名或前五名的項目編號、運動員姓名、校名和名次（成績）；(2)產生各學校的成績單，內容包括每個學校所取得的每項成績的項目號、名次（成績）、姓名和得分，并統計各學校總分； (3)可以按學校編號、男女團體總分排序輸出；(4)可以按學校編號查詢學校某個項目的情況；(5)可以按項目編號查詢取得前三或前五名的學校；(6)演示程序以用戶和計算機的對話方式執行。 2、集合的并、交和差運算的程序 問題描述： 編制一個能演示執行集合的并、交和差運算的程序。基本要求： ⑴集合的元素限定為大小寫字母符[′a′….′z ′′A′….′Z ′]，集合的大小n<53。 ⑵集合輸入的形式為一個以“回車符”為結束標志的字符串，串中字符順序不限，且允許出現重復字符或非法字符，程序應能自動濾去。 ⑶輸出的運算結果字符串中將不含重復字符或非法字符。⑷演示程序以用戶和計算機的對話方式執行。 3、長整數的加法運算 問題描述： 設計一個實現任意長的整數進行加法、減法運算的演示程序。 基本要求： ⑴利用鏈表實現長整數的存儲，每個結點含一個整型變量。提醒：任何整型變量int的范圍是-(2^15-1)~(2^15-1)。 ⑵輸入和輸出形式按照中國對于長整數的表示習慣，每四位一組,組間用逗號隔開。如：-2345，6789，3211； ⑶演示程序以用戶和計算機的對話方式執行。 4、一元多項式計算器 問題描述： 設有一元多項式Am(x)和Bn(x).Am(x)= A0+A1x1+A2x2+A3x3+… +Amxm Bn(x)= B0+B1x1+B2x2+B3x3+… +Bnxn 試求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。基本要求： ⑴首先判定多項式是否稀疏； ⑵分別采用順序和鏈式結構實現； ⑶結果M(x)中無重復階項和無零系數項； ⑷要求輸出結果的升冪和降冪兩種排列情況。⑸演示程序以用戶和計算機的對話方式執行。 5、車廂調度問題 問題描述： 假設停在鐵路調度站(如教科書中圖3.1(b)所示)入口處的車廂系列的編號依次為1，2，3，…n。設計一個程序,求出所有可能由此輸出的長度為n 的車廂系列。基本要求： ⑴設計一個程序，求出由一個編號依次為1，2，、、、，n的車廂序列可能產生的所有出棧系列。⑵利用雙向棧存儲結構實現調度站和輸出序列這兩個棧的空間共享。 ⑶對于每個輸出序列演示出所有操作序列的變化過程。 6、文章編輯 問題描述： 輸入一頁文字，可以統計出文字、數字、空格的個數?；疽螅?/p> ⑴靜態存儲一頁文章，每行最多不超過80個字符，共N行。⑵分別統計出其中英文字母和空格數及整篇文章總字數。⑶統計某一字符串在文章中出現的次數，并輸出該次數。 ⑶刪除某一子串，并將后面的字符前移。 ⑷存儲結構使用線性表，分別用幾個子函數實現相應的功能。 7、廣義表的應用 要求實現的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度等。 本設計用一個主控菜單程序控制，共分為6個子系統。（1）建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度 演示程序以用戶和計算機的對話方式執行。 8、哈夫曼樹及其編碼 問題描述： 設計一個利用哈夫曼算法的編碼系統，重復地顯示并處理以下項目，直到選擇退出為止。基本要求： ⑴初始化：鍵盤輸入或文件輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； ⑵編碼：利用建好的哈夫曼樹生成哈夫曼編碼； ⑶輸出樹形的哈夫曼樹及哈夫曼編碼； ⑷設字符集及頻度如下表： 字符 空格 A B C D E F G H I J K L M 頻度 197 64 13 22 32 103 21 15 47 57 5 1 20 32 字符 N O P Q R S T U V W X Y Z 頻度 1 15 48 16 80 23 8 18 1 51 1 9、校園導游咨詢 問題描述： 設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。基本要求： ⑴設計華東交通大學南區的校園平面圖，所含景點不少于10個。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。⑵為來訪客人提供圖中任意景點相關信息的查詢。 ⑶為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。 10、地圖著色問題 問題描述： 設計地圖著色軟件，對江西地圖中11個地級市進行著色，要求相鄰地級市所使用的顏色不同，并保證使用的顏色最少?；疽螅?/p> ⑴地圖采用圖型數據結構，每個地級市為一個節點，邊表示對應的兩個地級市相鄰。⑵設計著色算法，保證鄰接點不是同一種顏色。⑶演示程序以用戶和計算機的對話方式進行。 11、內部排序算法比較 問題描述： 試通過隨機數據比較各算法的關鍵字比較次數和關鍵字移動次數，以取得直觀感受?；疽螅?/p> ⑴至少采用三種方法實現上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。 ⑵待排序表的表長不小于100，其中的數據要用偽隨機數產生程序產生；至少要用5組不同的輸入數據作比較；比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數（關鍵字交換計為3次移動）。⑶最后對結果作出簡單分析，包括對各組數據得出結果波動大小的解釋。 12、哈希表的設計與實現——線性探測再散列 問題描述： 設計哈希表實現電話號碼查找系統?；疽螅?/p> ⑵ 設每個記錄有下列數據項：電話號碼、用戶名、地址； ⑶ 從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立不同的哈希表； ⑷ 采用線性探測再散列的方法解決沖突； ⑸ 查找并顯示給定電話號碼的記錄； ⑹ 查找并顯示給定用戶名的記錄。 13、哈希表的設計與實現——二次探測再散列 問題描述： 設計哈希表實現電話號碼查找系統?；疽螅?/p> (1)設每個記錄有下列數據項：電話號碼、用戶名、地址； (2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立不同的哈希表；(3)采用二次探測再散列的方法解決沖突；(4)查找并顯示給定電話號碼的記錄；(5)查找并顯示給定用戶名的記錄。 14、哈希表的設計與實現——鏈地址法 問題描述： 設計哈希表實現電話號碼查找系統。基本要求： (1)設每個記錄有下列數據項：電話號碼、用戶名、地址； (2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立不同的哈希表；(3)采用鏈地址法解決沖突； (4)查找并顯示給定電話號碼的記錄；(5)查找并顯示給定用戶名的記錄。 15、火車售票系統 問題描述： 通過此系統可以實現售票、退票、車票剩余情況查詢等功能。每張車票包含車次、車廂、座位信息?；疽螅?/p> ⑴在售票、退票、查詢剩余票等環節中，都必須顯示出車票的信息，即車次、車廂、座位情況。⑵為簡單起見，在此假設所有出售的車票均為同一車次的車票。⑶購票時，可以顯示余票信息，并可以選擇買哪張票。 ⑷退票時，必須是車站售出的車票才能退，否則視為無效票，不能退票，而且退票可以再次銷售。⑸演示程序以用戶和計算機的對話方式進行。 16、圖書管理系統 問題描述： 設計一個計算機管理系統完成圖書管理基本業務?；疽螅?/p> ⑴每種書的登記內容包括書號、書名、著作者、現存量、庫存量和借閱信息； ⑵對書號建立索引順序表以提高查找效率； ⑶系統主要功能如下： ①采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； ②借閱：如果一種書的現存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現存量； ③歸還：注銷對借閱者的登記，改變該書的現存量。⑷演示程序以用戶和計算機的對話方式進行。 17、客戶消費積分管理系統 問題描述： 針對客戶的消費情況，進行客戶管理，根據客戶的消費積分對客戶實行不同程度的打折優惠?；疽螅?/p> ⑴采用一定的存儲結構進行客戶信息的存儲； ⑵對客戶的信息可以進行修改、刪除、添加； ⑶能夠根據消費情況進行客戶積分的累加； ⑷根據積分情況，對客戶實行不同程度的打折優惠； ⑸演示程序以用戶和計算機的對話方式進行。 18、產品進銷存管理系統 問題描述： 針對某一種行業的庫房的產品進銷存情況進行管理?；疽螅?/p> ⑴采用一定的存儲結構對庫房的貨品及其數量進行分類管理； ⑵可以實現進庫房時，產品類的添加、產品的添加、產品數量的添加； ⑶能夠查詢庫房每種產品的總量、進貨日期、銷出數量、銷售時間等； ⑷可以實現產品出庫房時，產品數量修改以及達到臨界值提醒的功能； ⑸演示程序以用戶和計算機的對話方式進行。 19、學生成績管理系統的設計與實現 問題描述： 能夠實現對學生成績的常用管理功能?；疽螅?/p> ⑴采用一定的存儲結構對學生成績進行管理； ⑵可以進行成績的錄入、查詢、修改、刪除等操作； ⑶可以查詢某門課程的平均分，學生的排名，不同分數段的學生人數及學生信息等； ⑷可以查詢某學生的各課程分數，總分及學生的班級排名等； ⑸可以按學號排序輸出全部學生的成績信息、總分及班級排名等。⑹演示程序以用戶和計算機的對話方式進行。20、通訊錄管理系統的設計與實現——線性表 任務：利用線性表完成通訊錄的一般性管理工作：(1)添加信息； (2)顯示信息：可以按照手機或聯系人的姓名拼音排序顯示；(3)查找：用名字和手機號分別作為查找的依據，進行查找；(4)編輯信息；(5)刪除信息；(6)保存到文件； 要求： (1)每條記錄至少包括姓名、手機、QQ、電子郵箱、城市、郵編等信息。(2)界面友好，演示程序以用戶和計算機的對話方式進行，可反復操作。 21、通訊錄管理系統的設計與實現——哈希表 任務：利用哈希表完成通訊錄的一般性管理工作：(1)添加信息； (2)顯示信息：可以按照手機或聯系人的姓名拼音排序顯示；(3)查找：用名字和手機號分別作為查找的依據，進行查找；(4)編輯信息；(5)刪除信息；(6)保存到文件； 要求： (1)每條記錄至少包括姓名、手機、QQ、電子郵箱、城市、郵編等信息。(2)界面友好，演示程序以用戶和計算機的對話方式進行，可反復操作。 22、簡單目錄管理系統的設計與實現 任務：利用樹型結構設計并實現一個簡單的目錄管理系統，該系統可以對所有目錄進行管理，如目錄的新建、刪除、查詢、目錄名稱修改、按某種順序輸出所有目錄（樹的遍歷操作）、以樹型結構輸出所有目錄等功能。 23、最短旅程的求解 任務：有n個城市（編號從1到n），它們之間通過雙向的道路相連。那里只有n－1條道路，但是，它們的連接方式使得從任意城市都可以走到其他的任何城市。一天，某個游客到了編號為k的城市。他計劃從城市k開始，游遍所有的城市m1，m2，m3……，mi，…（不一定要按這個順序旅游）。每個城市mi都是不同的，并且，也與k不同。他想要以最短的路程旅行完所有的城市（從城市k開始）。請你幫助計算一下，旅游完上述的城市最短需要多少路程。 24、迷宮求解 任務：以一個m*n的長方陣表示迷宮，設置兩個門，一個入口，另一個是出口。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。 要求： ⑴首先實現一個棧類型，然后編寫一個求解迷宮的非遞歸程序。 ⑵求得的通路以三元組(i,j,d)的形式輸出，其中(i,j)指示迷宮中的一個坐標，d表示走到下一坐標的方向。 ⑶輸出迷宮圖，以#號表示障礙物，? ?空格表示非障礙物，*表示通路。 25、家譜管理系統的設計與實現 任務：設計并實現一個簡單的家譜管理系統?；疽螅?/p> （1）建立家族關系并能存儲到文件中。（2）實現家族成員的添加、刪除功能。 （3）可以查詢家族成員的雙親、祖先、兄弟、孩子和后代等信息。（4）按某種順序輸出家譜信息（樹的遍歷操作）、以樹型結構輸出家譜資料等功能。（5）界面友好，演示程序以用戶和計算機的對話方式進行，可反復操作。 26、宿舍管理查詢軟件 任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求：(1)采用交互工作方式； (2)可以增加、刪除、修改信息； (3)建立數據文件,數據文件按關鍵字（姓名、學號、房號）進行排序；(4)查詢: a.按姓名查詢 ；b.按學號查詢 ；c按房號查詢(5)輸出任一查詢結果（可以連續操作）。 27、語言中平衡符號的問題 要求：設C語言程序代碼中包含如下符號/* */，()，[]，{}，編寫程序檢測一段C代碼中上述符號是否正確。 28、算術表達式求解 問題描述：給定一個算術表達式，通過程序求出最后的結果?；疽螅?/p> (1)從鍵盤輸入要求解的算術表達式； (2)采用棧結構進行算術表達式的求解過程；(3)能夠判斷算術表達式正確與否；(4)對于錯誤表達式給出提示； (5)對于正確的表達式給出最后的結果,并可以顯示運算的整個過程。(6)演示程序以用戶和計算機的對話方式進行。 29、表達式求值，并能給出分數，可供小學生作業練習的小程序 要求： ⑴建立試題庫文件，從文件中，隨機抽取n個題目； ⑵題目涉及加減乘除，帶括號的混合運算； ⑶隨時可以退出程序； ⑷保留歷史分數，能回顧歷史，給出與歷史分數比較后的評價； ⑸界面友好，演示程序以用戶和計算機的對話方式進行，可反復操作。 30、數制轉換問題 任意給定一個M進制的數x，實現如下要求：(1)求出此數x的10進制值； (2)實現對X向任意的一個非M進制的數的轉換； (3)至少用兩種或兩種以上的方法實現上述要求（用棧解決，用數組解決，其它方法解決）；(4)提供交互界面，以便人機交互。 31、病人就醫管理 編寫一個程序實現就醫管理。在病人就醫過程中，主要發生三件事： ⑴預檢，分科室，掛號。不同科室都是從1號開始掛號。如，內科1號，外科1號，五官科1號等； ⑵病人到達診室，將病歷本交給護士，排到等待隊列中候診。⑶護士從等待隊列中取出一位病人的病歷，該病人進入診室就診。要求程序采用菜單方式，其選項及功能說明如下： ⑴掛號------預檢，分科室，生成就診號。 ⑵排隊------輸入病人的就診號，加入到病人排隊隊列中。 ⑶就診-------病人排隊隊列中最前面的病人就診，并將其從隊列中刪除。⑷查看排隊------從隊首到隊尾列出所有的排隊病人的病歷號。⑸下班---------退出運行。 32、九宮格問題 在一個3×3的九宮格中有1—8這8個數字，混亂排序，一個空格隨機地擺放在一個格子里?，F要求將該九宮格調整為正常按逆序的格式。調整的規則是：每次只能將與空格（上、下或左、右）相鄰的一個數字平移到空格中。編程實現這一問題的求解，并輸出求解過程。 33、銀行業務模擬 問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業務，每種業務所需的服務時間不同，優先級不同?？蛻舻竭_銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業務，然后在銀行內等候。當任一服務窗口空閑時,處理等候客戶中優先級最高，排在最前面的客戶的業務。寫一個上述銀行業務的模擬系統,通過模擬方法求出客戶在銀行內逗留的平均時間和每個窗口辦理的客戶數及辦理的每種業務數?；疽螅好總€客戶到達銀行的時間和需要辦理的業務隨機產生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數和每種業務數。 34、停車場管理 設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端）；若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上依次等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場；每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。 35、關鍵路徑問題 問題描述： 設計一個程序，求出完成整項工程至少需要多少時間，以及整項工程中的關鍵活動?；疽螅?/p> ⑴對一個描述工程的AOE網，應判斷其是否能夠順利進行。⑵若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發生時間、最遲發生時間。 36、地鐵站建設問題 問題描述： 以南昌為例，假設要在南昌各轄區之間修建地鐵來加快經濟發展，但由于建設地鐵的費用昂貴，因此需要設計一個程序，合理安排地鐵的建設路線，使乘客可以沿地鐵到達各個轄區，并使總的建設費用最小。基本要求： ⑴從包含各轄區的外部地圖文件中讀入轄區名稱和各轄區間的直接距離。⑵根據讀入的各轄區的距離信息，計算出應該建設哪些轄區間的地鐵路線。⑶輸出應該建設的地鐵路線及所需要建設的總里程信息。37.服裝銷售系統 要求：包含三類用戶：管理員、店長、銷售員； （1）管理員功能：自身密碼修改；其他用戶的添加、刪除；用戶信息的修改、統計；商品信息的添加、修改、刪除、查找、統計。 （2）店長功能：登錄、注銷、自身密碼修改、自身信息修改；商品信息的修改、統計；查看日報表、月報表、商品銷售量報表、營業員業績報表；查找、瀏覽、修改商品儲備信息。 （3）銷售員功能：商品瀏覽、查找、出售商品，以及查看自己本日報表、本月報表。38.歌星大獎賽 要求： （1）在歌星大獎賽中，每位歌手演唱完，有10個評委為參賽的選手打分，分數為1~100分。選手最后得分為：去掉一個最高分和一個最低分后其余8個分數的平均值。歌手的人數在大獎賽開始時確定。（2）同時對評委評分進行裁判，即在10個評委中找出最公平（即評分最接近平均分）和最不公平（即與平均分的差距最大）的評委。 （3）建立數據文件，保存各位歌星比賽時的所有評委分數，包括最高分，最低分和最后得分，并對比賽結果進行排序輸出； （4）界面友好，演示程序以用戶和計算機的對話方式進行，可反復操作。 39.機房機位預約模擬系統 20臺機器，從早8點到晚8點，每兩個小時一個時間段。需要實現如下功能：（1）查詢，根據輸入時間，輸出機位信息； （2）機位預定，根據輸入的日期和時間段查詢是否有空機位，若有則預約，若無則提供最近時間段的空機時間段。另外，如果用戶要求在非空時間上機，則將用戶信息插入該時間段的等待列表。（3）退出預定，根據輸入的時間撤銷該時間的預定。 （4）查詢是否有等待信息，若有則按順序顯示聯系方式，若無則顯示提示信息。40.歌曲信息管理系統 制作一個歌曲信息管理系統，要求提供以下功能： （1）歌曲信息包括歌曲名、作者、演唱者、發行年月等。（2）可以對歌曲信息進行輸入、刪除、瀏覽。 （3）可以根據歌曲名、作者、演唱者查詢歌曲信息。（4）提供按作者分組顯示功能。（5）用文件存儲信息。41.簡單的試題庫管理系統 試題庫管理系統要求對試題進行集中、有序、有效的管理，更新方便、查詢快捷、組卷靈活，降低勞動強度。 實現新試題庫的建立，界面友好、操作方便。按試題的難易程度、題型、章節等分類錄入、修改、刪除試題，通過文本文件導入試題，并可以實現對相關試題的查詢。按照要求自動組卷、生成文本格式試卷并輸出，便于用戶存檔和編輯。同時，該系統還具備一定的安全性，通過用戶名和密碼登錄。42.學生點名系統 要求： （1）讀入外部文件存儲的學生信息，顯示學生歷史點名記錄；（2）可選擇學生班級，對不同班級的學生進行點名。 （3）對學生按學號顯示名字，進行點名，并接收鍵盤輸入的信息，分別代表缺課、請假、正常；（4）將點名結果連帶日期一起回存到外部文件。（5）提供交互界面，以便人機交互。43.猜數游戲 由計算機“想”一個數，并給出數值范圍，請人猜，如果人猜對了，則一局游戲結束。否則，計算機給出提示，告訴人所猜的數是太大還是太小，直到人猜對為止。計算機記錄游戲者每次猜的次數，以此反映出猜數者“猜”的水平。 要求： （1）把猜數記錄最好的前五名的數據保存在外部文件中，包括游戲者的名字，成績和排名，并排序輸出。 （2）提供交互界面，以便人機交互。第二篇：數據結構課程設計題目.
第三篇：數據結構課程設計題目
第四篇：數據結構課程設計參考題目
第五篇：數據結構課程設計題目
點擊咨詢 