第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計學(xué)生搭配問題
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
報 告
設(shè)計題目：
學(xué)生搭配問題
專 業(yè)： 計算機(jī)科學(xué)與技術(shù) 學(xué)生姓名： 班級學(xué)號： 分組成員： 指導(dǎo)教師：
學(xué)生搭配問題課程設(shè)計報告
一、設(shè)計時間
二、設(shè)計地點
三、設(shè)計目的
1.通過這次課程設(shè)計進(jìn)一步熟悉基本概念； 2.熟練掌握C語言編程，了解程序基本的流程；
3.運(yùn)用所學(xué)C語言知識，掌握數(shù)據(jù)結(jié)構(gòu)方法循環(huán)隊列應(yīng)用，算法思路設(shè)計； 4.培養(yǎng)查閱資料，獨(dú)立思考問題的能力。
四、設(shè)計小組成員
五、指導(dǎo)老師
六、設(shè)計課題
學(xué)生搭配問題
七、基本思路及關(guān)鍵問題的解決方法
基本思路：隊列（Queue）是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的運(yùn)算受限的線性表。
循環(huán)隊列是在隊列的順序存儲結(jié)構(gòu)中，除了用乙組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素和隊列尾元素的位置。
循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊，出隊，判隊滿，判隊空。
（1）要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2。
（2）將男生、女生兩組人分別存入這兩個隊列。以實現(xiàn)他們的循環(huán)配對輸出，這是循環(huán)隊列固有的特性。
（3）利用循環(huán)隊列的特性，將男女生分別進(jìn)行入隊列和出隊列操作，且實現(xiàn)搭配輸出。
（4）循環(huán)隊列的長度分別設(shè)為男女生的個數(shù)即可。
（5）在計算機(jī)終端輸出的結(jié)果是：根據(jù)要求輸出男生女生搭配情況
關(guān)鍵問題: 循環(huán)隊列的應(yīng)用
解決方法：數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 循環(huán)隊列（兩個），將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。
存儲結(jié)構(gòu): 循環(huán)鏈表
核心算法: 循環(huán)隊列的入隊，出隊，判隊滿，判隊空。輸入數(shù)據(jù): 男生人數(shù)、女生人數(shù)，歌曲數(shù)量
輸出數(shù)據(jù): 每一首歌曲播放時，男生和女生搭配情況（只輸出編號即可）當(dāng)要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行性。
八、算法及流程圖
九、調(diào)試過程中出現(xiàn)的問題及解決方法
問題：在構(gòu)造隊列時，設(shè)隊列分配的最大空間為男女生的個數(shù)，此時便無法根據(jù)Q.front=Q.rear來判別隊列空間是“空”還是“滿”,因此，在入隊操作即插入一個新元素作為新的隊尾元素時出現(xiàn)了問題，即最后一位同學(xué)無法入隊。
解決方法：將隊列分配的最大空間至少再增加一個
十、測試及運(yùn)行結(jié)果
測試輸入數(shù)據(jù)：男女生的個數(shù)曲子數(shù)和要查找的男女生編號
輸出結(jié)果為：每首曲子男女生搭配的情況 程序運(yùn)行界面：
十一、課程設(shè)計心得體會
通過一周的學(xué)習(xí)和實踐，解決實際問題（學(xué)生搭配問題），讓我對循環(huán)隊列有了更深的了解，對數(shù)據(jù)結(jié)構(gòu)產(chǎn)生了濃厚的興趣，同時也讓我提高了解決實際問題的能力。
我們要不斷的通過上機(jī)來提高自己的學(xué)習(xí)水平，在上機(jī)的同時改正了自己對某些算法的錯誤使用，使自己在通過程序解決問題時抓住關(guān)鍵算法，有了算法設(shè)計思想和流程圖，并用C語言描繪出關(guān)鍵算法
十二、源程序
#include
printf(“隊列為空”);p=Q.front->next;num=p->num;Q.front->next=p->next;q=p->next;if(Q.rear==q)
Q.rear=Q.front;free(p);} void printF(LinkQueue &F,int i)//打印第i首曲子時女隊的情況 { QueuePtr p;int n=1;while(n printf(“_ ”); n++;} p=F.front->next;while(F.rear!=p){ printf(“%d ”,p->num); p=p->next;} printf(“%d n”,p->num);} void printM(LinkQueue &M,int i)//打印第i首曲子時男隊的情況 { QueuePtr p;int n=1;while(n printf(“_ ”); n++;} p=M.front->next;while(M.rear!=p){ printf(“%d ”,p->num); p=p->next;} printf(“%d n”,p->num);} void main(){ int m,n,k,i,a,b;int count=0,num;QueuePtr p,q;LinkQueue F;//女生隊 LinkQueue M;//男生隊 printf(“請輸入女生數(shù)量：”);scanf(“%d”,&m);printf(“請輸入男生數(shù)量：”);scanf(“%d”,&n);printf(“請輸曲子號：”);scanf(“%d”,&k);printf(“請輸入要查找的男生編號：”);scanf(“%d”,&a);printf(“請輸入要查找的女生編號：”);scanf(“%d”,&b);InitQ(F);InitQ(M);for(i=1;i<=m;i++){ EnQueue(F,i);} for(i=1;i<=n;i++){ EnQueue(M,i);} for(i=1;i<=k;i++){ system(“CLS”); printf(“第%d首曲子 n”,i); printF(F,i); printM(M,i); p=F.front->next; q=M.front->next; printf(“目前跳舞的是第%d號女生和第%d號男生n”,p->num,q->num); if(p->num==a&&q->num==b) { count++;printf(“第%d曲是要查找的男女生跳舞n”,i); } sleep(3000); DeQueue(F,num);EnQueue(F,num); DeQueue(M,num); EnQueue(M,num);} printf(“該對男女生共跳舞%d次n”,count);} 十三、參考文獻(xiàn) [1] 數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏 吳偉明 編著，清華大學(xué)出版社 [2] C語言程序設(shè)計（第三版）譚浩強(qiáng) 著，清華大學(xué)出版社 分類號編號 華北水利水電大學(xué) North China Institute of Water Conservancy and Hydroelectric Power 課程設(shè)計 題目舞伴問題 院系信息工程學(xué)院 專業(yè)計算機(jī)科學(xué)與技術(shù) 姓名賈寧 指導(dǎo)教師楊彬 第一章需求分析........................................................................................................................2 1.1問題描述......................................................................................................................2 1.2 基本要求.....................................................................................................................2 1.2.1 輸入及輸出格式..............................................................................................2 1.2.2 程序所完成的功能..........................................................................................2 第二章概要設(shè)計........................................................................................................................3 2.1 數(shù)據(jù)結(jié)構(gòu).....................................................................................................................3 2.2 程序模塊.....................................................................................................................4 2.3 模塊調(diào)用及算法.........................................................................................................5 第三章詳細(xì)設(shè)計........................................................................................................................7 3.1 操作實現(xiàn).............................................................................................................7 3.2 算法實現(xiàn).............................................................................................................8 第四章編碼調(diào)試......................................................................................................................10 4.1 調(diào)試環(huán)境...................................................................................................................10 4.2 調(diào)試方法...................................................................................................................10 4.3 調(diào)試項目及調(diào)試結(jié)果...............................................................................................10 4.3.1 登陸測試........................................................................................................10 4.3.2 加載學(xué)生信息................................................................................................11 4.3.3 學(xué)生配對調(diào)試................................................................................................12 4.3.4 顯示總配對....................................................................................................13 4.3.5 查詢配對........................................................................................................13 第五章總結(jié)..............................................................................................................................15 參考文獻(xiàn)..................................................................................................................................16 附錄系統(tǒng)源代碼......................................................................................................................17 第一章需求分析 1.1問題描述 一班有m個女生、n個男生(m不等于n), 舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時, 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴，設(shè)計一個程序模擬舞伴配對過程。 1.2 基本要求 1.2.1 輸入及輸出格式 輸入男、女學(xué)生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機(jī)編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。在讀入男女生信息時，可以從文件中直接讀取學(xué)生的姓名和性別信息。 輸出顯示時顯示每首歌的配對情況，包括對應(yīng)配對學(xué)生的姓名、性別以及編號?？梢暂敵稣麄€舞池配對過程的所有配對情況。將輸出顯示的內(nèi)容對應(yīng)寫入到指定的文件中。 1.2.2 程序所完成的功能 從文件或者手動輸入班級的學(xué)生信息，包括姓名和性別基本信息，根據(jù)性別使男女生分別坐在舞池兩邊的座位上，學(xué)生的座位編號順序生成，且一旦編號確定，將不再發(fā)生變化。 每一首歌曲播放時，依次從男女生隊列中出來學(xué)生進(jìn)行配對，由于男女生人數(shù)不一致，會使某個隊列中剩下若干學(xué)生配對不成功，配對不成功者等待下首歌時再進(jìn)行配對。該首歌結(jié)束時，配對成功的學(xué)生再回到座位上。然后再依次進(jìn)行配對，未成功者等待下首歌再進(jìn)行配對。 配對成功時，會顯示本首歌的詳細(xì)配對情況，以及整個過程的配對情況，并且可以將配對情況寫入到文件。 根據(jù)男女生的姓名或者某首歌曲的名字可以查詢到對應(yīng)的配對情況。 第二章概要設(shè)計 2.1 數(shù)據(jù)結(jié)構(gòu) 學(xué)生座位隊列： ADT StuQueue{ 數(shù)據(jù)對象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 數(shù)據(jù)關(guān)系：R={ 操作結(jié)果：向Q中循環(huán)加入信息 void EnQueue2(StuQueue&Q,FinalStustu)初始條件：循環(huán)隊列已存在，非首次進(jìn)循環(huán)隊列 操作結(jié)果：向Q中添加信息 FinalStuDeQueue(StuQueue&Q)初始條件：循環(huán)隊列已存在 操作結(jié)果：使隊列頭的元素出隊列，且返回FinalStu類型值 }ADT StuQueue //學(xué)生座位隊列 音樂隊列： ADTMusicList{ 數(shù)據(jù)對象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 數(shù)據(jù)關(guān)系：R={ voidInsertMusic(MusicList&MList,char* name)初始條件：該鏈表已存在 操作結(jié)果：向鏈表中添加數(shù)據(jù) }ADT MusicList； 臨時隊列： ADTTempQList{ 數(shù)據(jù)對象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 數(shù)據(jù)關(guān)系：R={ voidEnTempQueue(TempQList&TQL,FinalStustu)初始條件：隊列TQL已存在操作結(jié)果：向TQL中添加信息 FinalStuDeTempQueue(TempQList&TQL)初始條件：隊列TQL存在 操作結(jié)果：取出隊列的對頭元素，返回FinalStu類型 }ADT TempQList； 2.2 程序模塊 本系統(tǒng)主要包括登陸模塊、學(xué)生入座、自動配對、顯示配對過程以及查詢配對信息模塊。 登陸：輸入正確的用戶名以及密碼，方可進(jìn)入系統(tǒng)，連續(xù)輸入錯誤三次則禁止進(jìn)入系統(tǒng)。 學(xué)生入座：以不同的方式獲取學(xué)生信息后，根據(jù)學(xué)生性別依次進(jìn)入兩個循環(huán)隊列，并為每個學(xué)生唯一編號。 自動配對：每首歌開始時，男女生依次從坐席中出來進(jìn)行本首歌的配對，配對不成功者等待下首歌繼續(xù)配對，下首歌時，上首歌未配對成功者本首歌先進(jìn)行配對。 顯示配對過程：在播放歌曲的過程中，顯示播放的歌曲信息，以及本首歌的配對信息。 查詢配對：根據(jù)男女生的姓名查出兩人的在哪一首歌進(jìn)行過配對，根據(jù)歌曲名稱查詢出本首歌的配對信息。 文件操作：將配對情況及學(xué)生的座位信息寫入文件 根據(jù)系統(tǒng)模塊的劃分，本系統(tǒng)的功能模塊圖如圖2-1所示 舞池配對系統(tǒng)登陸學(xué)生入座自動配對顯示配對過程查詢配對結(jié)果 圖 2-1 功能模塊 2.3 模塊調(diào)用及算法 登陸成功后進(jìn)入主界面，進(jìn)入主界面后，需要先運(yùn)行學(xué)生入座模塊，方能進(jìn)行下邊的操作。學(xué)生入座后會得到相關(guān)的基本信息。之后調(diào)用配對模塊函數(shù)，進(jìn)行學(xué)生的配對。學(xué)生配對成功后，才能利用顯示配對過程進(jìn)行顯示配對的情況，后續(xù)的查詢配對模塊也必須在配對成功的基礎(chǔ)上進(jìn)行。模塊間的調(diào)用流程如圖2-2所示 主函數(shù)登陸函數(shù)入座模塊配對模塊顯示配對查詢結(jié)果 圖 2-2 模塊調(diào)用 在進(jìn)行配對過程中用到算法，在每首歌配對時，依次從男女生隊列中出來一個學(xué)生，進(jìn)入到臨時隊列，從臨時隊列中獲取配對的情況。在本首歌結(jié)束，下首歌開始之前，讓臨時隊列中的男女在分別根據(jù)性別入隊，依次循環(huán)，每次調(diào)用配對函數(shù)，實現(xiàn)學(xué)生的循環(huán)配對。 第三章詳細(xì)設(shè)計 3.1 操作實現(xiàn) 本系統(tǒng)包含七個文件。設(shè)計分有歡迎界面，登陸系統(tǒng)，入隊函數(shù)，配對函數(shù)，顯示函數(shù)，查詢函數(shù)等。登陸界面是整個系統(tǒng)的入口，其主要是讓合法人員進(jìn)入系統(tǒng)，入隊函數(shù)主要讓學(xué)生進(jìn)入男女隊列，配對函數(shù)主要是根據(jù)每首歌曲把男女生進(jìn)行配對，顯示函數(shù)主要是顯示男女生的配對情況，查詢函數(shù)主要是根據(jù)男女生姓名和歌曲名查找配對情況。 系統(tǒng)首先通過程序調(diào)用void main()進(jìn)入歡迎界面和系統(tǒng)登陸界面，根據(jù)用戶的帳號和密碼登陸成功后進(jìn)入主菜單。根據(jù)用戶的選擇可分別進(jìn)入：1.學(xué)生就坐；2.每曲配對；3.顯示結(jié)果；4.查詢配對；5.退出。 選擇“1.學(xué)生就坐”項，會顯示學(xué)生信息來源，包括“1.按班級獲取(推薦)”“2.手動輸入...”兩項可供選擇。其中，1是從文件中獲取學(xué)生信息，2是用戶手動輸入學(xué)生信息。 選擇“2.每曲配對”項，會顯示播放歌曲的類型，有“1.流行”“2.復(fù)古”兩個音樂風(fēng)格可供選擇，當(dāng)用戶選擇其中一個風(fēng)格并確定播放后，會顯示出當(dāng)前播放的歌曲名字和所配對的男女生。 選擇“3.顯示結(jié)果”項，會有“1.學(xué)生座位信息”和“2.學(xué)生配對信息”兩項操作可供選擇。當(dāng)選擇1，會把學(xué)生就坐后的信息顯示出來，選擇2，會把每首歌學(xué)生的配對情況顯示出來。 選擇“4.查詢配對”項，也有兩個操作可供選擇，分別是“1.按學(xué)生姓名”“按歌曲名”兩項。選擇1，會根據(jù)用戶輸入的男女生姓名查看他們的配對情況，選擇2，會根據(jù)用戶輸入的歌曲名稱顯示每首歌曲學(xué)生的配對情況。 選擇“5.退出”項，會出現(xiàn)感謝使用系統(tǒng)界面，并按任意鍵退出系統(tǒng)。本系統(tǒng)的主流程圖如圖3-1 所示 開始?xì)g迎和登陸界面主界面1 ？NN2 ？N3 ？N4 ？N5 ？Y結(jié)束程序Y學(xué)生就坐Y每曲配對Y每曲配對顯示Y查詢配對情況 圖 3-1 主流程 3.2 算法實現(xiàn) 定義學(xué)生結(jié)構(gòu)體FinalStu，將學(xué)生的信息放到本結(jié)構(gòu)體中，定義兩個循環(huán)隊列Boys和Girls隊列，分別存儲男女生的座位信息。定義MusicList循環(huán)鏈表，用于存放音樂信息。定義TempQueue隊列，用于臨時存放從男女生隊列中出來的學(xué)生信息。創(chuàng)建一個存放每首歌配對情況的數(shù)組stuTable[]，用來存放播放該首歌曲時男女生的信息。 每一首歌開始時，男女生依次用Boys和Girls隊列中出對，依次進(jìn)入臨時隊列TempQueue，從TempQueue中讀取男女生的信息，放到stuTable數(shù)組中，表示該首歌的 8 配對情況。下首歌開始時，讓臨時隊列中的學(xué)生再根據(jù)性別依次進(jìn)入男女循環(huán)隊列。同時將存放歌曲的MusicList循環(huán)鏈表指針后移，播放下首歌曲，再執(zhí)行上述操作，便可實現(xiàn)循環(huán)配對。 第四章編碼調(diào)試 4.1 調(diào)試環(huán)境 硬件環(huán)境：Intel 1GHZ處理器（或AMD同類處理器），512M或以上內(nèi)存容量，10G或以上硬盤容量,可連接互聯(lián)網(wǎng)的相關(guān)設(shè)備。 軟件環(huán)境（軟件、操作系統(tǒng)）：Windows XP（或Windows 2003或Windows vista或Windows 7）操作系統(tǒng)，Microsoft Visual Studio 2008。 4.2 調(diào)試方法 為了提高測試效率，降低測試成本，本測試方案采用黑盒法設(shè)計基本的測試方案，再用白盒法補(bǔ)充一些方案。在黑盒法測試方案中，采用等價劃分技術(shù)，把所有可能的數(shù)據(jù)劃分成幾個等價類。 4.3 調(diào)試項目及調(diào)試結(jié)果 4.3.1 登陸測試 用戶根據(jù)用戶名及密碼登陸系統(tǒng)，內(nèi)置用戶為Admin，密碼為888888。登陸成功如圖4-1所示，登陸失敗如圖4-2所示 圖 4-1 登陸成功 圖 4-2 登陸失敗 4.3.2 加載學(xué)生信息 可以從文件或者手動輸入學(xué)生信息，從文件中選擇時，可以選擇不同的文件，其運(yùn)行結(jié)果如圖4-2 及圖4-3 所示 圖 4-3 選擇信息來源 圖 4-4 顯示獲取信息 4.3.3 學(xué)生配對調(diào)試 在進(jìn)行配對之前，需要先將音樂信息加載到系統(tǒng)中，其加載過程如圖4-5所示 圖 4-5 加載音樂 學(xué)生就位及音樂加載成功后，開始播放音樂，并進(jìn)行配對，其音樂播放情況及每首歌曲的配對情況如圖4- 6、圖4-7及圖4-8所示 圖 4-6 配對開始 圖 4-7 播放下一首 圖 4-8 循環(huán)配對 4.3.4 顯示總配對 在整個過程結(jié)束后，停止播放音樂，可以顯示整個過程的配對情況，其結(jié)果如圖4-9所示 圖 4-9 顯示配對結(jié)果 4.3.5 查詢配對 可以根據(jù)男女生的姓名查詢兩人的配對情況，當(dāng)輸入兩個學(xué)生姓名時，顯示在整個過程中的配對情況，其結(jié)果如圖 4-10所示 圖4-10 姓名查詢配對 根據(jù)每一首歌曲情況查詢在本首歌曲中的配對情況，其結(jié)果如圖4-11 所示 圖 4-11 按歌名查找 第五章總結(jié) 這次的課程設(shè)計懂得了理論與實際相結(jié)合是很非常重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為，從而提高自己的實際動手能力和獨(dú)立思考的能力。在整個設(shè)計過程中，構(gòu)思是很花費(fèi)時間的，在構(gòu)思總體架構(gòu)時，需要先將需求分析搞清楚，需要在找到了需要解決的問題后，再想辦法解決該問題。而不是在設(shè)計過程中邊想邊解決，需要先將所有可能的問題都考慮到，再依次解決。在整個系統(tǒng)設(shè)計完成后，如果再遇到新的問題，可以對系統(tǒng)進(jìn)行適當(dāng)?shù)母隆?/p> 調(diào)試時經(jīng)常會遇到這樣那樣的錯誤，有的時候是因為一些最基本的錯誤，如標(biāo)點的中英錯誤，括號的匹配問題，數(shù)據(jù)的輸入錯誤等。當(dāng)然，也有很多地方是因為用錯了解決方法。在設(shè)計的過程中，最能體現(xiàn)出的缺點就是基礎(chǔ)不扎實，本可以避免的錯誤卻一再出現(xiàn)。 在實現(xiàn)舞池配對問題過程中，需要使學(xué)生循環(huán)配對，此程序設(shè)計的是當(dāng)一個光盤的音樂播放結(jié)束時，整個配對過程隨之結(jié)束，而沒有讓學(xué)生再次進(jìn)去坐席，導(dǎo)致不再從新將學(xué)生入座，就無法實現(xiàn)配對。設(shè)計的是在每首歌開始之前學(xué)生進(jìn)入隊列，可以改為當(dāng)某個學(xué)生坐席為空時，隨即讓學(xué)生再次進(jìn)入隊列，可以解決不能重復(fù)換歌曲的問題。 剛開始的時候我直接在開發(fā)環(huán)境下一邊看題一邊寫代碼，瞪了半天什么也沒寫出來，于是我便先開始在紙上畫畫寫寫，將事件的整個過程畫下來，然后考慮怎么才能運(yùn)用代碼來實現(xiàn)，一邊思考一邊寫一些粗略的代碼，最后從上到下執(zhí)行代碼看看是不是符合題目要求。有沒有什么漏洞。等這些完成以后，再在開發(fā)環(huán)境下將代碼完善、編譯和調(diào)試。雖然說代碼還有許多要改進(jìn)的地方，有的功能還不夠完善，可畢竟是自己親自寫出來的，對于程序的條理有了一個清晰的了解，對編程也有了更加深刻的認(rèn)識。 參考文獻(xiàn) [1] 譚浩強(qiáng).C程序設(shè)計(第三版)[M].北京：清華大學(xué)出版社，2005.[2] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京：清華大學(xué)出版社，1997.[3] 陸麗娜.軟件工程.北京：經(jīng)濟(jì)科學(xué)出版社，2005.[4] 姚詩斌.數(shù)據(jù)庫系統(tǒng)基礎(chǔ).計算機(jī)工程與應(yīng)用,1981年第8期 附錄系統(tǒng)源代碼 #include int idCount=1000;//全局變量控制學(xué)生id自增 int length;//記錄每首歌配對的數(shù)量 int index=0;//記錄最終配對表的下標(biāo) usingnamespace std;//舞池就坐后的學(xué)生信息結(jié)構(gòu)體 struct Admin { char name[15];char passWord[15];Admin *next;};Admin *admin;struct FinalStu { char name[15];char sex[3];int id;};FinalStu stu[STU_SIZE];FinalStu stuSeat[STU_SIZE];//用來存放入座后的學(xué)生信息 FinalStu stuTable[STU_SIZE][2];//用來存放沒收歌曲的配對情況 //舞池座位 struct StuQueue { FinalStu *base;int front;int rear;};StuQueue Boys;//男生隊列 StuQueue Girls;//女生隊列 //初始化學(xué)生坐席 void InitQueue(StuQueue &Q){ Q.base=(FinalStu*)malloc(MAXQSIZE*sizeof(FinalStu));if(Q.base==NULL) return;Q.front=Q.rear=0; } //學(xué)生就坐,首次入隊，需要獲取學(xué)生的id void EnQueue(StuQueue &Q,FinalStu stu){ int i=100;if((Q.rear+1)%MAXQSIZE==Q.front) return;strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=idCount++;Q.rear=(Q.rear+1)%MAXQSIZE;} //非首次入隊，不需獲取學(xué)生的id void EnQueue2(StuQueue &Q,FinalStu stu){ strcpy(Q.base[Q.rear].name,stu.name);strcpy(Q.base[Q.rear].sex,stu.sex);Q.base[Q.rear].id=stu.id;Q.rear=(Q.rear+1)%MAXQSIZE;} //從坐席上出來 FinalStu DeQueue(StuQueue &Q){ FinalStu stu;if(Q.rear!=Q.front){ stu=Q.base[Q.front];} Q.front=(Q.front+1)%MAXQSIZE;return stu;} //存放音樂信息 struct Music { char M_Name[15];Music *next;};//存放音樂鏈,循環(huán)鏈表 struct MusicList { Music *head; Music *tail;};MusicList ML;Music *M_p;//初始化指針 void InitMusic(MusicList & MList){ MList.head=MList.tail=(Music *)malloc(sizeof(Music));MList.head->next=NULL;} //向音樂鏈表中添加音樂 void InsertMusic(MusicList &MList,char* name){ Music *p=(Music*)malloc(sizeof(Music));MList.tail->next=p;strcpy(p->M_Name,name);MList.tail=p;MList.tail->next=MList.head;} //臨時隊列，用于存放從男女生隊列中配對成成功的學(xué)生信息 struct TempQueue { FinalStu stu;TempQueue * next;}; struct TempQList { TempQueue *front;TempQueue *rear;};TempQList TempQL;//臨時隊列，用于存放每次出來的男女生信息 void InitQList(TempQList &TQL){ TQL.front=TQL.rear=(TempQueue *)malloc(sizeof(TempQueue));TQL.front->next=NULL;} void EnTempQueue(TempQList & TQL,FinalStu stu){ TempQueue *p=(TempQueue *)malloc(sizeof(TempQueue));p->stu=stu;p->next=NULL;TQL.rear->next=p;TQL.rear=p;} FinalStu DeTempQueue(TempQList &TQL){ FinalStu stu;TempQueue *p;p=TQL.front->next;if(p==TQL.rear){ stu=p->stu; TQL.rear=TQL.front;} else { stu=p->stu; TQL.front->next=p->next;} free(p);return stu;} //==========配對信息存放=================== struct MatchList { char musicName[20];FinalStu stu[2];};MatchList matchTable[SIZE];//從鍵盤讀入學(xué)生信息 void GetInfKey(){ for(int i=0;i cout<<“輸入第”< scanf(“%s”,stu[i].name); cout<<“輸入第”< scanf(“%s”,stu[i].sex);} } //學(xué)生入座 void StudentSit(){ for(int i=0;i if(strcmp(stu[i].sex,“男”)==0) EnQueue(Boys,stu[i]); else EnQueue(Girls,stu[i]);} } //獲取就坐后的男女生性別、姓名、編號,stuSeat[] 存放就坐后的學(xué)生信息，包括學(xué)生編號 void GetStuSeat(){ int i=0; int j=0;i=Boys.front;j=Girls.front; while(i!=Boys.rear){ stuSeat[i]=Boys.base[i]; i++;} while(j!=Girls.rear){ stuSeat[i]=Girls.base[j]; j++; i++;} } //將就座的學(xué)生信息寫入文件 int InFileStuSeat(){ FILE *fp_Seat;int res=0;if((fp_Seat=fopen(“Seat.txt”,“wt”))==NULL){ cout<<“讀取學(xué)生座位信息失?。?！”; return-1;} fprintf(fp_Seat,“姓名t性別t序號n”);for(int i=0;i fprintf(fp_Seat,“%st%st%d”,stuSeat[i].name,stuSeat[i].sex,stuSeat[i].id); fprintf(fp_Seat,“n”); res++;} fclose(fp_Seat);return res;} void PrintStuSeat(){ cout<<“ttt姓名t性別t序號”< cout<<“ttt”< cout< cout<<“打開文件失?。?！”; return;} while(!feof(fp_Admin)){ Admin *p=(Admin *)malloc(sizeof(Admin)); p->next=NULL; fscanf(fp_Admin,“%s%s”,p->name,p->passWord); q->next=p; q=p;} fclose(fp_Admin);} //從文件獲取學(xué)生信息 void ReadStuFile(int res){ FILE *fp;if(res==1){ if((fp=fopen(“student1.txt”,“rt”))==NULL) { cout<<“打開文件失?。?！”< return; } } elseif(res==2){ if((fp=fopen(“student2.txt”,“rt”))==NULL) { cout<<“打開文件失?。?！”< return; } } int i=0;while(!feof(fp)) { fscanf(fp,“%s%s”,stu[i].name,stu[i].sex); i++; if(i>=STU_SIZE) break; } fclose(fp);} //加載音樂信息 int LoadMusic(int cd){ char music[5][20];//存放從文件中獲取的音樂名稱 int res=0;FILE *fp_music;if(cd==1){ if((fp_music=fopen(“music1.txt”,“rt”))==NULL) { cout<<“打開音樂文件失?。?！”< return-1; } } elseif(cd==2){ if((fp_music=fopen(“music2.txt”,“rt”))==NULL) { cout<<“打開音樂文件失?。?！”< return-1; } } for(int j=0;j<5;j++){ if(fread(music[j],20*sizeof(char),1,fp_music)==1) res++; } fclose(fp_music);InitMusic(ML);for(int i=0;i<5;i++){ InsertMusic(ML,music[i]);} return res;} int InFileMatchTable(){ FILE *fp_MTable;if((fp_MTable=fopen(“matchtable.txt”,“wt”))==NULL){ cout<<“打開文件失敗~~~~”< return-1;} fprintf(fp_MTable,“歌曲名稱t姓名t性別t序號t姓名t性別t序號n”);for(int i=0;i fprintf(fp_MTable,“%stt%st%st%dt”,matchTable[i].musicName,matchTable[i].stu[0].name,matchTable[i].stu[0].sex,matchTable[i].stu[0].id); fprintf(fp_MTable,“%st%st%dn”,matchTable[i].stu[1].name,matchTable[i].stu[1].sex,matchTable[i].stu[1].id);} fclose(fp_MTable);return 1;} void StudentSitAgain(){ FinalStu stu;while(TempQL.front!=TempQL.rear){ stu=DeTempQueue(TempQL); if(strcmp(stu.sex,“男”)==0) EnQueue2(Boys,stu); else EnQueue2(Girls,stu);} } //播放歌曲 void PlayMusic(){ cout<<“tt正在播放:t”< void NextMusic(){ M_p=M_p->next;if(M_p==ML.head){ M_p=ML.head->next;} } //學(xué)生配對 void Match(){ //FinalStu student[STU_SIZE];intstatic i=0;int j=0;length=0;while(Boys.front!=Boys.rear&&Girls.front!=Girls.rear){ EnTempQueue(TempQL,DeQueue(Boys));//從男生隊列中出來進(jìn)入臨時隊列 EnTempQueue(TempQL,DeQueue(Girls));//從女生隊列中出來進(jìn)入臨時隊列 length++;//記錄每首歌的配對數(shù) } //從臨時隊列中將信息賦值給表 TempQueue *tem=TempQL.front->next;while(tem){ strcpy(matchTable[index].musicName,M_p->M_Name); strcpy(matchTable[index].stu[0].name,tem->stu.name); strcpy(matchTable[index].stu[0].sex,tem->stu.sex); matchTable[index].stu[0].id=tem->stu.id; //----每曲歌的配對情況 strcpy(stuTable[j][0].name,tem->stu.name); strcpy(stuTable[j][0].sex,tem->stu.sex); stuTable[j][0].id=tem->stu.id; tem=tem->next; //------整個播放過程的配對表 strcpy(matchTable[index].stu[1].name,tem->stu.name); strcpy(matchTable[index].stu[1].sex,tem->stu.sex); matchTable[index].stu[1].id=tem->stu.id; //----每首歌配對表 strcpy(stuTable[j][1].name,tem->stu.name); strcpy(stuTable[j][1].sex,tem->stu.sex); stuTable[j][1].id=tem->stu.id; tem=tem->next; index++; j++;} } //顯示每首歌配對情況 void PrintEachMatch(){ cout< //length為每首歌的配對長度 { cout< cout< 1、學(xué)生就坐”;cout<<“t”<<“ 2、每曲配對”< 3、顯示結(jié)果”;cout<<“t”<<“ 4、查詢配對”< 5、退出”; } //配對顯示 void PrintMatchTable(){ cout<<“歌曲名稱t姓名t性別t序號t姓名t性別t序號”< cout< cout< //從文件讀取數(shù)據(jù) int res; cout<<“請選擇班級：”< cout<<“1.三年一班t2.三年二班”< cin>>res; if(res==1) { ReadStuFile(1); } elseif(res==2) { ReadStuFile(2); } break;case 2: cout<<“開始輸入....”< GetInfKey(); //鍵盤鍵入數(shù)據(jù) break;default: cout<<“輸入有誤，再見”< break;} } void MusicMenu(){ cout<<“請選擇要放入的光盤類型：”< i=LoadMusic(1);else i=LoadMusic(2);if(i){ M_p=ML.head->next;//p指向第一首歌 cout<<“歌曲光盤已就位,是否現(xiàn)在播放(Y/N)”< cin>>ch; InitQList(TempQL);//初始化臨時隊列 if(ch=='Y'||ch=='y') { system(“cls”); PlayMusic(); Match(); PrintEachMatch(); } cout<<“按n進(jìn)行下一首歌曲、、n”; cout<<“按q停止播放音樂、、”< cin>>ch; while(ch=='n'||ch=='N') { system(“cls”); Next(); cout<<“按n進(jìn)行下一首歌曲、、n”; cout<<“按q停止播放音樂、、”< cin>>ch; } if(ch=='q'||ch=='Q') return;} } void Welcome(){ cout<<“tttt歡迎進(jìn)入進(jìn)入舞池~~~~”< Admin *p=admin->next; cout<<“ttt請輸入您的用戶名：”; cin>>userName; cout<<“ttt請輸入您的密碼：”; cin>>key; while(p) { if(strcmp(p->name,userName)==0) break; p=p->next; } if(!p) { system(“cls”); cout<<“ttt輸入的用戶名不存在~~~~~”< continue; } if(p) { if(strcmp(p->passWord,key)==0) { system(“cls”); cout<<“tttt歡迎回來.”; Sleep(500); system(“cls”); cout<<“tttt歡迎回來..”; Sleep(500); system(“cls”); cout<<“tttt歡迎回來...”; Sleep(500); //system(“cls”); break; } else { system(“cls”); cout<<“ttt輸入的密碼錯誤、、、”< continue; } } } if(i>=3){ cout<<“ttt您今天的機(jī)會已經(jīng)用完，再見”; exit(0);} } void ShowMessage(){ system(“cls”);int res;cout<<“ttt選擇要操作的信息:”< cout<<“ttt座位信息如下:”< PrintStuSeat(); char ch; cout<<“是否將該信息寫入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileMatchTable()) { cout<<“數(shù)據(jù)已寫入文件...”< } } } elseif(res==2){ PrintMatchTable(); char ch; cout<<“是否將該信息寫入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileMatchTable()) cout<<“數(shù)據(jù)已寫入文件...”< } Sleep(3000);} } void Quit(){ system(“CLS”); printf(“nnnnnnnnttt ^o^”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使^”); Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使用”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使用^o^”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使用^o^nntttt -----”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使用^o^nntttt -----GoodBye!”);Sleep(200);system(“CLS”); printf(“nnnnnnnnttt ^o^歡迎下次使用^o^nntttt -----GoodBye!n”);} void CheckByName() //根據(jù)姓名查詢配對情況 { char boyName[15];char girlName[15];cout<<“請輸入男生姓名:”;cin>>boyName;cout<<“請輸入女生姓名:”;cin>>girlName;int count=0;for(int i=0;i if(strcmp(matchTable[i].stu[0].name,boyName)==0&& strcmp(matchTable[i].stu[1].name,girlName)==0) { count++; } } if(count==0){ cout<<“未找到配對情況:”;} else { cout<<“ttt查詢的學(xué)生的配對情況如下:”< cout<<“歌曲名稱t姓名t性別t編號t姓名t性別t編號”< for(int j=0;j { if(strcmp(matchTable[j].stu[0].name,boyName)==0&& strcmp(matchTable[j].stu[1].name,girlName)==0) { cout< cout< } } } } void CheckByMusic(){ char MusicName[15];cout<<“請輸入歌名:”;cin>>MusicName;int count=0;for(int i=0;i if(strcmp(matchTable[i].musicName,MusicName)==0) { count++; } } if(count==0){ cout<<“未找到該歌曲~~~~”; } else { cout<<“ttt查詢的學(xué)生的配對情況如下:”< cout<<“歌曲名稱t姓名t性別t編號t姓名t性別t編號”< for(int j=0;j { if(strcmp(matchTable[j].musicName,MusicName)==0) { cout< cout< } } } } //主界面選項 void MainChoose(){ int ins;LoadAdmin();while(1){ system(“cls”); MainMenu(); cout< cin>>ins; switch(ins) { case 1: system(“cls”); StudentChose(); InitQueue(Boys); InitQueue(Girls); StudentSit(); //學(xué)生分別入座 GetStuSeat();//獲取學(xué)生座位信息 cout<<“ttt男女生已分別就位....”< cout<<“ttt座位信息如下:”< PrintStuSeat(); char ch; cout<<“是否將該信息寫入文件(Y/N):”; cin>>ch; if(ch=='Y'||ch=='y') { if(InFileStuSeat()) cout<<“數(shù)據(jù)已寫入文件...”< } Sleep(3000); break; case 2: system(“cls”); cout<<“tttt請先放入歌曲光盤...”< MusicMenu(); break; case 3: ShowMessage(); break; case 4: system(“cls”); cout<<“ttt請選擇查詢的方式:”< cout<<“ttt1.按學(xué)生姓名t2.按歌曲名”< int i; cin>>i; switch(i) { case 1: CheckByName(); break; case 2: CheckByMusic(); break; } //CheckByMusic(); getch(); break; case 5: system(“color FC”); Quit(); exit(0); break; } } } void main(){ MainChoose();} 數(shù) 據(jù) 結(jié) 構(gòu) 課程設(shè)計報告 題 目： 一元多項式計算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學(xué) 號： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時 間： 一、課程設(shè)計題目分析 本課程設(shè)計要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項式的加法、減法、乘法、除法運(yùn)算等功能。 二、設(shè)計思路 本程序采用C語言來完成課程設(shè)計。 1、首先，利用順序存儲結(jié)構(gòu)來構(gòu)造兩個存儲多項式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運(yùn)算分成五個主要的模塊：實現(xiàn)多項式輸入模塊、實現(xiàn)加法的模塊、實現(xiàn)減法的模塊、實現(xiàn)乘法的模塊、實現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實現(xiàn)其功能，盡量減少程序運(yùn)行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實現(xiàn)對多項式輸入輸出以及加、減、乘、除，調(diào)試程序并將不足的地方加以修改。 三、設(shè)計算法分析 1、相關(guān)函數(shù)說明： (1)定義數(shù)據(jù)結(jié)構(gòu)類型為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)類型變量 typedef struct Polynomial{} (2)其他功能函數(shù) 插入函數(shù)void Insert(Polyn p,Polyn h) 比較函數(shù)int compare(Polyn a,Polyn b) 建立一元多項式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項式，void Print(Polyn P) 銷毀多項式函數(shù)釋放內(nèi)存，void Destroy(Polyn p) 主函數(shù)，void main（） 2、主程序的流程基函數(shù)調(diào)用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個結(jié)構(gòu)體變量中coef表示每一項前的系數(shù)，expn表示每一項的指數(shù)，polyn為結(jié)點指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對象名。 (2)當(dāng)用戶輸入兩個一元多項式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數(shù)為m的一元多項式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點 這就建立一元多項式的關(guān)鍵步驟 (3)由于多項式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項式按指數(shù)進(jìn)行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進(jìn)行處理，此處由于反復(fù)使用指針對各個結(jié)點進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實現(xiàn)： 在該程序中，最關(guān)鍵的一步是實現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實現(xiàn)；對于乘除算法的大致流程都是：首先建立多項式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實現(xiàn)了多項式計算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計算合并的鏈表逐個結(jié)點依次輸出，便得到整鏈表，也就是最后的計算式計算結(jié)果。由于考慮各個結(jié)點的指數(shù)情況不同，分別進(jìn)行了判斷處理。 四、程序新點 通過多次寫程序，發(fā)現(xiàn)在程序在控制臺運(yùn)行時總是黑色的，本次寫程序就想著改變一下，于是經(jīng)過查資料利用system(“Color E0”);可以函數(shù)解決，這里“E0，”E是控制臺背景顏色，0是控制臺輸出字體顏色。 五、設(shè)計中遇到的問題及解決辦法 首先是，由于此次課程設(shè)計里使用指針使用比較多，自己在指針多的時候易腦子混亂出錯，對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進(jìn)行 4 代碼編寫。 其次是，在寫除法模塊時比較復(fù)雜，自己通過查資料最后成功寫出除法模塊功能。 最后是，前期分析不足開始急于寫代碼，中途出現(xiàn)各種問題，算是給自己以后設(shè)計時的一個經(jīng)驗吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應(yīng)用C語言設(shè)計一元多項式基本計算程序，使我更加鞏固了C語言程序設(shè)計的知識，以前對指針這一點使用是比較模糊，現(xiàn)在通過此次課程設(shè)計對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識的加深。本次的課程設(shè)計，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計開發(fā)程序方面有了一定的小經(jīng)驗和想法，對自己以后學(xué)習(xí)其他語言程序設(shè)計奠定了一定的基礎(chǔ)。 八、指導(dǎo)老師評語及成績 附錄：（課程設(shè)計代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數(shù)相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數(shù)為0的話釋放結(jié)點 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結(jié)點插入 } 7 } //建立一個頭指針為head、項數(shù)為m的一元多項式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結(jié)點以接收數(shù)據(jù) printf(“請輸入第%d項的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點 } return head;} //銷毀多項式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項數(shù)計數(shù)器 if(!q)//若多項式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項 9 if(q->coef!=1&&q->coef!=-1)//系數(shù)非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項式已空，但b多項式非空 else return 1;//b多項式已空，但a多項式非空 } //求解并建立多項式a+b，返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當(dāng)相加系數(shù)為0時，釋放該結(jié)點 } return headc;} //求解并建立多項式a-b，返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數(shù)取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復(fù)pb的系數(shù) p->coef*=-1;13 return pd;} //求解并建立多項式a*b，返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項 } } return hf;} //求解并建立多項式a/b，返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點,存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點，存儲余數(shù) pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數(shù)是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL printf(“請輸入A(x)的項數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項式B printf(“n”);printf(“**********************************************n”);printf(“* 多項式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執(zhí)行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項式A(x):“);Print(pa);*n”); printf(“多項式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 1.赫夫曼編碼器 設(shè)計一個利用赫夫曼算法的編碼和譯碼系統(tǒng)，重復(fù)地顯示并處理以下項目，直到選擇退出為止。要求： 1)將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中) 2)初始化：鍵盤輸入字符集大小26、26個字符和26個權(quán)值（統(tǒng)計一篇英文文章中26個字母），建立哈夫曼樹； 3)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 4)輸出編碼（首先實現(xiàn)屏幕輸出，然后實現(xiàn)文件輸出）； 5)界面優(yōu)化設(shè)計。 代碼如下： #include typedef struct HTNode //結(jié)構(gòu)體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權(quán)值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功！”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹，進(jìn)行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請輸入權(quán)值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功！”);} void Coding_H(int n,HTNode *HT) //對結(jié)點進(jìn)行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 舞伴問題
第三篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計