《C語言程序設計》課程設計

1、1 一元稀疏多項式的運算 問題描述：設有兩個帶頭指針的單鏈表表示兩個一元稀疏多項式a、b，實現(xiàn)兩個一元稀疏多項式的處理。實現(xiàn)要求： 輸入并建立多項式； 輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列； 多項式a和b相加，建立多項式a+b，輸出相加的多項式； 多項式a和b相減，建立多項式a-b，輸出相減的多項式； 多項式a和b相乘，建立多項式ab，輸出相乘的多項式； 設計一個菜單，至少具有上述操作要求的基本功能。測試數(shù)據(jù)：(1) (2x+5x8-3.1x11)+(7-5x8+11x9)(2) (6

2、x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)(3)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)2 成績排序假設某年級有4個班，每班有45名同學。本學期有5門課程考試，每門課程成績是百分制。假定每個同學的成績記錄包含：學號、姓名各門課程的成績共7項，其中學號是一個10位的字符串，每個學生都有唯一的學號，并且這4個班的成績分別放在4個數(shù)組中，完成以下操作要求： 編寫一個成績生成函數(shù)，使用隨機數(shù)方法，利用隨機函數(shù)生成學生的各門課程的成績（每門課程的成績都是0100之間的整數(shù)），通過調(diào)用該函數(shù)生成全部學生的成績； 編寫一個平均成績計算函數(shù)，計算每個同學的

3、平均成績并保存在成績數(shù)組中； 用冒泡排序法對4個班的成績按每個同學的平均成績的以非遞增方式進行班內(nèi)排序； 用選擇排序法對4個班的成績按每個同學的平均成績的以非遞增方式進行班內(nèi)排序； 對已按平均成績排好序的4個班的同學的構(gòu)造一個所有按平均成績的以非遞增方式排列的新的單鏈表； 設計一個菜單，至少具有上述操作要求的基本功能。（本題由2人完成）3 迷宮問題 問題描述： 以一個mn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。實現(xiàn)要求： 實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以

4、三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向。 編寫遞歸形式的算法，求得迷宮中所有可能的通路； 以方陣形式輸出迷宮及其通路。測試數(shù)據(jù)迷宮的測試數(shù)據(jù)如下：左上角（1，1）為入口，右下角（8，9）為出口。 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000實現(xiàn)提示：計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通

5、路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路?？梢远S數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（m,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。4 棧及其操作 問題描述：棧(stack)：是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出lifo (last in first out)或先進后出filo (first in last out)線性表。棧頂(top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。棧底(bottom)：是固定端，又

6、稱為表頭?？諚＃寒敱碇袥]有元素時稱為空棧。設棧s=(a1，a2，an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，an的次序進棧，退棧的第一個元素應為棧頂元素an。即棧的修改是按后進先出的原則進行的。棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置上進行。鏈棧的基本形式如下：top空鏈棧topan a3 a2 a1 非空鏈棧實現(xiàn)要求： 鏈?；静僮鞯膶崿F(xiàn)：棧的初始化，生成一個空棧；壓棧，即元素進棧；彈棧，即元素出棧； 十進制整數(shù)n向其它進制數(shù)d(二、八、十六)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題。轉(zhuǎn)換法則：該轉(zhuǎn)換法則對應于一個簡單算法原理：n=(n di

7、v d)*d+n mod d 其中：div為整除運算，mod為求余運算 在文字處理軟件或編譯程序設計時，常常需要檢查一個字符串或一個表達式中的括號是否相匹配?匹配思想：從左至右掃描一個字符串(或表達式)，則每個右括號將與最近遇到的那個左括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ?如果存在)相匹配，同時從棧頂刪除該左括號。算法思想：設置一個棧，當讀到左括號時，左括號進棧。當讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回flase。5航班信息管理問題描述：飛機航班系統(tǒng)的數(shù)據(jù)包括

8、兩部分： 航班信息：航班號、最大載客數(shù)、起飛地點、起飛時間、降落地點、降落時間，單價； 乘客信息：航班號、身份證號碼、姓名、性別、出生年月、座位號。乘客訂票的主要方式是：乘客提出航班號、起飛地點、起飛時間、降落地點、訂票數(shù)等訂票要求，根據(jù)事先保存的航班數(shù)據(jù)決定乘客能否訂票？只有全部滿足了乘客的訂票要求并且所訂航班有足夠的未訂座位之后才能完成訂票處理，并且修改該航班的未訂座位數(shù)（每個航班的未訂座位數(shù)的初始值就是該航班的最大載客數(shù)）；否則，訂票失敗，并且給出不能訂票的原因。要求將航班數(shù)據(jù)保存在數(shù)據(jù)文件中，在處理時按航班的起飛地點建立不同的鏈表。功能要求 ： 增加航班記錄。將新的航班記錄增加到原有的

9、航班數(shù)據(jù)文件中。在進行處理時必須檢查所要增加的航班記錄是否存在，如果已經(jīng)存在，應給出提示信息后停止增加； 航班取消。如果某次航班的乘客數(shù)太少（已訂票的少于本次航班最大載客數(shù)的10%），將取消該航班，但該航班的記錄仍然保存在原有的航班數(shù)據(jù)文件中； 航班查詢。應該有以下幾種基本的查詢方式：按航班號、按起飛地點和起飛時間、按降落地點，按起飛地點和降落地點； 航班訂票。按上述問題描述中的乘客訂票方式完成航班訂票處理。 設計一個菜單，至少具有上述操作要求的基本功能。 6 運動會管理系統(tǒng)問題描述：校際運動會管理系統(tǒng)。設有n個學校參加校際運動會，共有男子競賽項目數(shù)m，女子競賽項目數(shù)w。每個學?？梢詤⒓铀懈?/p>

10、賽項目，也可以只參加部分競賽項目，每個學校對每個項目的參賽運動員不能超過4人，每個運動員最多只能參加3項單項比賽，團體賽不受限制。各項目名次取法有如下幾種：用戶自定義：（各名次權(quán)值由用戶指定） 參賽人數(shù)超過6人，取前5名：第1名得分 7，第2名得分 5，第3名得分3，第4名得分2，第5名得分 1；參賽人數(shù)不超過6人，取前3名：第1名得分 5，第2名得分 3，第3名得分2； 團體項目的名次取法和上面相同，但分數(shù)加倍。功能要求 ： 運動員報名登記，以學校為單位進行運動員報名登記，登記的限制要求按問題描述的要求； 參賽信息查詢，查看參賽學校信息和比賽項目信息； 競賽檢錄，每項比賽開始前完成參賽運動員

11、的檢錄； 競賽成績登記，填寫比賽名次，然后根據(jù)競賽檢錄的運動員人數(shù)和上述的記分方式自動完成各學校的成績登記并實時生成各學校的團體總分； 比賽成績查詢，可以按競賽項目、參賽學校、參賽運動員查看比賽成績； 競賽成績排序，以學校為單位，按總成績的高低，分別排序輸出每個學校的總成績、男子總成績、女子總成績； 設計一個菜單，至少具有上述操作要求的基本功能。（本題由2人完成）7集合運算問題描述：設有兩個用單鏈表表示的集合a、b，其元素類型是int且以非遞減方式存儲，其頭結(jié)點分別為a、b。要求下面各問題中的結(jié)果集合同樣以非遞減方式存儲，結(jié)果集合不影響原集合。實現(xiàn)要求： 編寫集合元素測試函數(shù)in_set，如果

12、元素已經(jīng)在集合中返回0，否則返回1； 編寫集合元素輸入并插入到單鏈表中的函數(shù)insert_set，保證所輸入的集合中的元素是唯一且以非遞減方式存儲在單鏈表中； 編寫集合元素輸出函數(shù)，對建立的集合鏈表按非遞增方式輸出； 編寫求集合a、b的交c=ab的函數(shù)，并輸出集合c的元素； 編寫求集合a、b的并d=ab的函數(shù)，并輸出集合d的元素； 求集合a與b的對稱差e=(a-b)(b-a) 的函數(shù)，并輸出集合d的元素； 設計一個菜單，具有輸入集合元素、求集合a、b的交c、求集合a、b的并d、求集合a與b的對稱差e、退出等基本的功能。測試數(shù)據(jù)：由讀者自定，但集合a、b的元素個數(shù)不得少于16個。8 矩陣的操作設

13、有兩個矩陣a=(aij)mn，b=(bij)pq。實現(xiàn)要求： 編寫矩陣輸入函數(shù)input_mat，通過該函數(shù)完成矩陣的輸入并返回保存矩陣的三元組（不能使用全局變量）； 編寫矩陣輸出函數(shù)output_mat，通過該函數(shù)完成矩陣的輸出，輸出的形式是標準的矩陣形式（即二維數(shù)組的形式）； 求矩陣的轉(zhuǎn)置，矩陣的轉(zhuǎn)置a=(aji)nm，轉(zhuǎn)置前輸出原矩陣，轉(zhuǎn)置后輸出轉(zhuǎn)置矩陣； 求矩陣a、b的和。矩陣a和b能夠相加的條件是：m=p，n=q；矩陣a和b如果不能相加，請給出提示信息；若能夠相加，則求和矩陣c并輸出c；c=a+b=(cij)mn，其中cij=aij+bij 求矩陣a、b的差。矩陣a和b能夠相減的條件

14、是：m=p，n=q；矩陣a和b如果不能相減，請給出提示信息；若能夠相減，則求差矩陣c并輸出c；c=a-b=(cij)mn，其中cij=aij-bij 求矩陣a、b的積。矩陣a和b能夠相乘的條件是：p=n；矩陣a和b如果不能相乘，請給出提示信息；若能夠相乘，則求積矩陣d并輸出d；d=ab=(dij)mq，其中dij=aikbkj，k=1,2,n 設計一個菜單，具有求矩陣的轉(zhuǎn)置、求矩陣的和、求矩陣的積、退出等基本的功能。在求矩陣的和或求矩陣的積時要求能夠先提示輸入兩個矩陣的，然后再進行相應的操作。9 數(shù)據(jù)匯總 問題描述：在數(shù)據(jù)處理中經(jīng)常需要對大量數(shù)據(jù)進行匯總，將相同關鍵字記錄的某些數(shù)據(jù)項的值疊加起

15、來，生成一個分類匯總表。假設某超級市場銷售有m種商品（假設商品的編號為1，2，3，m），有n臺前臺收款機（假設收款機的編號為1，2，3，n）進行收款，以記錄的形式提供給計算機，每個記錄表示某臺收款機的一種商品一次交易的數(shù)量和銷售額。記錄由4個域組成：收款機編號、商品編號、銷售數(shù)量、銷售金額。構(gòu)造一個結(jié)構(gòu)體類型，每次銷售數(shù)據(jù)以一個結(jié)構(gòu)體變量保存在一個數(shù)據(jù)文件中。實現(xiàn)要求： 編寫實現(xiàn)將數(shù)據(jù)記錄插入到數(shù)據(jù)文件的最后的函數(shù)； 編寫以收款機為單位的數(shù)據(jù)分類處理函數(shù)。構(gòu)造n個單鏈表，每個鏈表保存一臺收款機的銷售記錄，這n個單鏈表的頭指針存放在一個指針數(shù)組中，通過數(shù)組的下標就可以知道是哪臺收款機。讀取數(shù)據(jù)文

16、件的記錄，將所有的銷售記錄(數(shù)據(jù)文件中的全部記錄)分解插入到n個單鏈表； 編寫以商品為單位的數(shù)據(jù)分類處理函數(shù)。構(gòu)造m個單鏈表，每個鏈表保存一種商品的銷售記錄，這m個單鏈表的頭指針存放在一個指針數(shù)組中，通過數(shù)組的下標就可以知道是哪種商品。讀取數(shù)據(jù)文件的記錄，將所有的銷售記錄(數(shù)據(jù)文件中的全部記錄)分解插入到m個單鏈表； 統(tǒng)計每臺收款機的銷售總額； 以收款機為單位，將所有收款機按銷售總額的非遞減順序構(gòu)造一個單鏈表并輸出； 以商品為單位，統(tǒng)計每種商品的銷售總額； 以商品為單位，將所有銷售的商品按銷售總額的非遞減順序構(gòu)造一個單鏈表并輸出； 設計一個菜單，具有上述要求的所有功能、退出系統(tǒng)等最基本的功能。

17、10 joseph環(huán) 題目之一：問題描述：編號是1，2，n的n個人按照順時針方向圍坐一圈，一開始任選一個正整數(shù)作為報數(shù)上限（開始）值m(mn)，從第s(sn)個人開始沿順時針方向順序報數(shù)，報到m時停止報數(shù)，報m的人出列，然后在從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。實現(xiàn)要求： 利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m、n、s的初值和每個人的編號，建立單循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的序列輸出。 利用順序表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的

18、編號。輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m、n、s的初值和每個人的編號，建立單循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的序列輸出。測試數(shù)據(jù)：m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？題目之二：問題描述：編號是1，2，n的n個人按照順時針方向圍坐一圈，一開始任選一個正整數(shù)作為報數(shù)上限（開始）值m(mn)，從第s(sn)個人開始沿逆時針方向順序報數(shù)，報到m時停止報數(shù)，報m的人出列，然后在從他在逆時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。實現(xiàn)要求： 利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬

19、此過程，按照出列的順序輸出各個人的編號。輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m、n、s的初值和每個人的編號，建立單循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的序列輸出。 利用順序表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個人的編號。輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m、n、s的初值和每個人的編號，建立單循環(huán)鏈表。輸出形式：建立一個輸出函數(shù)，將正確的序列輸出。測試數(shù)據(jù)：m的初值為31，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？11 背包問題的求解 題目之一：問題描述：假設有一個能裝入總體積為t的背包和n件體積分別為w1 , w2 , , wn 的

20、物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + + wn=t，要求找出所有滿足上述條件的解。例如：當t=10，各件物品的體積1，8，4，3，5，2時，可找到下列4組解：（1，4，3，2）（1，4，5）（8，2）（3，5，2）。問題提示：可利用回溯法的設計思想來解決背包問題。首先將物品排成一列，然后順序選取物品裝入背包，假設已選取了前i 件物品之后背包還沒有裝滿，則繼續(xù)選取第i+1件物品，若該件物品太大不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說明剛剛裝入背包的那件物品不合適，應將它取出棄之一邊，繼續(xù)再從它之后的物品中選取，如此重復，直至求得滿足條件的解，或者無解。題目之二：問題描述：假設有n件物品，這些物品的重量分別是w1 , w2 , , wn，物品的價值分別是v1，v2， ，vn。求從這n件物品中選取一部分物品的方案，使得所選中的物品的總重量不超過限定的重量w（wwi, i=1,