《C語(yǔ)言程序設(shè)計(jì)》課程設(shè)計(jì)

1、1 一元稀疏多項(xiàng)式的運(yùn)算 問題描述：設(shè)有兩個(gè)帶頭指針的單鏈表表示兩個(gè)一元稀疏多項(xiàng)式a、b，實(shí)現(xiàn)兩個(gè)一元稀疏多項(xiàng)式的處理。實(shí)現(xiàn)要求： 輸入并建立多項(xiàng)式； 輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為第i項(xiàng)的系數(shù)和指數(shù)。序列按指數(shù)降序排列； 多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式； 多項(xiàng)式a和b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式； 多項(xiàng)式a和b相乘，建立多項(xiàng)式ab，輸出相乘的多項(xiàng)式； 設(shè)計(jì)一個(gè)菜單，至少具有上述操作要求的基本功能。測(cè)試數(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 成績(jī)排序假設(shè)某年級(jí)有4個(gè)班，每班有45名同學(xué)。本學(xué)期有5門課程考試，每門課程成績(jī)是百分制。假定每個(gè)同學(xué)的成績(jī)記錄包含：學(xué)號(hào)、姓名各門課程的成績(jī)共7項(xiàng)，其中學(xué)號(hào)是一個(gè)10位的字符串，每個(gè)學(xué)生都有唯一的學(xué)號(hào)，并且這4個(gè)班的成績(jī)分別放在4個(gè)數(shù)組中，完成以下操作要求： 編寫一個(gè)成績(jī)生成函數(shù)，使用隨機(jī)數(shù)方法，利用隨機(jī)函數(shù)生成學(xué)生的各門課程的成績(jī)（每門課程的成績(jī)都是0100之間的整數(shù)），通過調(diào)用該函數(shù)生成全部學(xué)生的成績(jī)； 編寫一個(gè)平均成績(jī)計(jì)算函數(shù)，計(jì)算每個(gè)同學(xué)的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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