第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 背包問題的求解
2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
背包問題的求解
摘要 組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點(diǎn)，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價值，同時也在于它們能在現(xiàn)實(shí)生活中廣泛的應(yīng)用。背包問題是一個典型的組合優(yōu)化問題，本課程設(shè)計用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關(guān)鍵詞 背包問題；
遞歸算法；
1問題描述
1.1問題描述
背包問題：設(shè)有不同價值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。
1.2基本思想
（1）分別輸入n件物品的重量和價值。（2）采用遞歸尋找物品的方案。
（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價值為多少。
2問題分析
背包問題的求解是一個很經(jīng)典的案例。對于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個。
設(shè)n件物品的重量分別為w0,w1,?,wn-1,物品的價值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設(shè)方案的的總價值存于變量maxv,當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw;至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價值的期望值設(shè)為tv，算法引入tv是當(dāng)一旦當(dāng)前方案的總價值的期望值也小于前面方案的總價值maxv時，急需考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個方案。因?yàn)楫?dāng)方案的總價值不比maxv大時，該方案不會不會再被考察。這同時保證函數(shù)后找到的方案一定會比前面的方案更好。2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 對于第i件物品的選擇有兩種可能：
（1）物品i被選擇，這種可能性僅當(dāng)包含它不會超過方案總重量的限制時才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇；
（2）物品i不被選擇，這種可能性僅當(dāng)不包物品i也有可能會找大價值更大的方案的情況。
就此，通過不斷地對從第一件開始的物品到第n件物品進(jìn)行選擇或是不選擇，從而從各個方案的比較中選擇出最優(yōu)方案。
采用option[]和cop[]兩個數(shù)組，來輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個“旗幟”作用，用來區(qū)別于未被選擇的物品，從而達(dá)到輸出被選擇的函數(shù)。而cop[]則像是一個中間變量，它在遞歸過程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個橋梁作用。
3數(shù)據(jù)結(jié)構(gòu)描述
背包問題結(jié)構(gòu)體：
struct{
int weight;
int value;
}a[N];4算法設(shè)計
4.1程序流程圖
2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
圖4-1 程序流程圖
4.2算法設(shè)計
根據(jù)問題分析中的思想寫出遞歸算法如下：
find（物品當(dāng)前選擇已達(dá)到的重量和tw,本方案可能達(dá)到的總價值為tv）｛
/*考慮物品i包含在當(dāng)前方案中的可能性*/ if（包含物品i是可接受的）｛
將物品i包含在當(dāng)前方案中；
if(i 以當(dāng)前方案作為臨時最佳方案保存； 恢復(fù)物品i不包含狀態(tài)； ｝ 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 /*考慮物品i不包含在當(dāng)前方案中的可能性*/ if（不包含物品i僅是可考慮的） if(i 以當(dāng)前方案作為臨時最佳方案保存； ｝ void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) /*物品i包含在當(dāng)前方案的可能性*/ { cop[i]=1;if(i /*物品i不包含在當(dāng)前方案的可能性*/ if(i opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細(xì)程序清單 詳細(xì)程序清單見附錄。 6程序運(yùn)行結(jié)果 背包問題求解界面如圖6-1所示。 圖6-1 背包問題求解界面 程序調(diào)試成功。 在課程設(shè)計代碼調(diào)試過程中也出了不少差錯，比如頭文件很容易忽略，同學(xué)指出才發(fā)現(xiàn)；一些符號像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯誤有時也會發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些錯誤已經(jīng)全部改正。在此過程中我們學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識，這些在程序的優(yōu)化方面幫助很大。 7心得體會 通過此次課程設(shè)計的實(shí)踐，感觸較深。不僅使我們加深了對書本知識的理解，而且鍛煉了我們編寫程序、調(diào)試程序的能力。同時，此次課程設(shè)計也充分彌補(bǔ)了課堂教學(xué)中知識的缺陷。這次課程設(shè)計由于時間有限，對有些地方考慮的還不夠周到。 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問題中的背包問題，背包問題是一個典型的組合優(yōu)化問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。所以我們試著用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識以及遞歸法來解決普通的背包問題。背包問題的遞歸思想確實(shí)有點(diǎn)難以理解，為了理解這個思想，我們確實(shí)花了很長時間，不過很高興最后經(jīng)過我們的討論掌握了這個思想。 參考文獻(xiàn) [1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn).北京：清華大學(xué)出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京： 清華大學(xué)出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析（修訂版）.北京：清華大學(xué)出版，2000:45-66 Knapsack problem solving Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 附錄：詳細(xì)程序清單 #include /*可實(shí)現(xiàn)最大總價值*/ int opion[N]，cop[N]; struct{ int weight; int value; }a[N];int n; void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) { cop[i]=1;if(i /*方案的選擇*/ /*當(dāng)前方案的選擇*/ /*背包問題結(jié)構(gòu)體*/ /*物品種數(shù)*/ /*物品i包含在當(dāng)前方案的可能性*/ 7 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 if(tv-a[i].value>maxv) /*物品i不包含在當(dāng)前方案的可能性*/ if(i 第%d種物品（重量，價值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k printf(“最佳裝填方案是：n”);for(k=0;k 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 迷宮求解 學(xué)院：湖北工業(yè)大學(xué)計算機(jī)學(xué)院 教師：沈華老師 班級：12網(wǎng)絡(luò)工程1班 學(xué)號：1210322118 姓名：饒進(jìn)陽 時間：2013年12月22日 目 錄 問題描述 .........................................................思路解析 .........................................................程序流程 .........................................................核心代碼 .........................................................源程序代碼........................................................程序運(yùn)行實(shí)例.....................................................課設(shè)總結(jié) .........................................................3 4 5 6 12 14 迷宮求解 問題描述： 可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出； 要求： 在上交資料中請寫明：存儲結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結(jié)果、算法的時間復(fù)雜度、另外可以提出算法的改進(jìn)方法； 比如這是一個迷宮 電腦找出的出路 思 路 設(shè)定當(dāng)前位置的初值為入口位置： do｛ 若當(dāng)前位置可通，則｛ 將當(dāng)前位置插入棧頂；} 若該位置是出口位置，則結(jié)束； 否則切換當(dāng)前位置的東鄰塊為新的當(dāng)前位置； 否則｛ 若棧不空且棧頂位置還有其他方向未被探索，則設(shè)定新的當(dāng)前位置為沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；} 若{ 棧不空但棧頂位置的四周均不可通，則刪去棧頂位置；} 若{ 棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空；｝ ｝while(棧不空)｛棧空說明沒有路徑存在｝ PS：類似動態(tài)求解方法 程序流程 第一次用visio做程序框圖，所以只把程序的大概流程畫出來了。 核心代碼 //棧相關(guān)操作 int initlStack(Stack *S)int pushStack(Stack S, coordinate e)int popStack(Stack S, coordinate *e)int getTop(Stack S, coordinate *e)void show(Stack S) //創(chuàng)建一個迷宮 int creatMaze(Maze *m) //打印出一個迷宮 void showMaze(Maze *m) //求當(dāng)前結(jié)點(diǎn)的下一個通路 coordinate passNext(Maze *m, int i, int j)//求迷宮路徑 int solveMaze(Maze *m, Stack S)//模擬出路徑 void showRoad(Maze m, Stack S) 程序源碼： #include #define MAX 100 #define SIZE sizeof(Node)//**************************** //棧 typedef struct { int x;//行 int y;//列 }coordinate;//坐標(biāo) typedef struct node{ coordinate data;struct node *next;}Node, *Stack; //棧的相關(guān)操作 //棧初始化 //帶頭結(jié)點(diǎn)的鏈棧 int initlStack(Stack *S){(*S)=(Node *)malloc(SIZE);if((*S)== NULL){ return 1;}(*S)->next = NULL;return 0;} //入棧 int pushStack(Stack S, coordinate e){ Node *p; p =(Node *)malloc(SIZE);p->data.x = e.x;p->data.y = e.y;p->next = S->next;S->next = p;return 0;} //出棧 int popStack(Stack S, coordinate *e){ Node *p;if(S->next == NULL){ printf(“nStack is empty!n”); return 2;} e->x = S->next->data.x;e->y = S->next->data.y;p = S->next;S->next = p->next;free(p);return 0;} //讀取棧頂 int getTop(Stack S, coordinate *e){ e->x = S->next->data.x;e->y = S->next->data.y;return 0;} //顯示 void show(Stack S){ Node *p;p = S->next;while(p!= NULL){ printf(“%d %d <-”, p->data.x, p->data.y); p = p->next;} printf(“startn”);} //*************************** //*************************** //迷宮 typedef struct { int row;int col;int arr[MAX][MAX];}Maze; //創(chuàng)建一個迷宮 int creatMaze(Maze *m){ int i, j;printf(“nplease input Maze's row and col:n”);scanf(“%d%d”, &(m->row), &(m->col));printf(“nplease input the Maze's message:(0 is ok),(1 is no)n”);for(i = 0;i <= MAX1;j++){ m->arr[i][j] = 1; } } for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ scanf(“%d”, &(m->arr[i][j])); } } return 0;} //顯示迷宮信息 void showMaze(Maze *m){ int i, j;printf(“nthe Maze you hava input:n”);for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ printf(“%d ”, m->arr[i][j]); } printf(“n”);} printf(“nlike this:n”);for(i = 1;i <= m->row;i++){ for(j = 1;j <= m->col;j++){ if(m->arr[i][j]!= 0){ printf(“■ ”); } else { printf(“□ ”); } } printf(“n”);} } //求當(dāng)前結(jié)點(diǎn)的下個通路 //順時針找 coordinate passNext(Maze *m, int i, int j){ coordinate k;if(m->arr[i][j+1] == 0){//東 k.x = i; k.y = j+1; return k;} if(m->arr[i+1][j] == 0){//南 k.x = i+1; k.y = j; return k;} if(m->arr[i][j-1] == 0){//西 k.x = i; k.y = j-1; return k;} if(m->arr[i-1][j] == 0){//北 k.x = i-1; k.y = j; return k;} else {//不存在 k.x =-1; k.y =-1; return k;} } //求解迷宮 int solveMaze(Maze *m, Stack S){ int i, j;int boolean;coordinate a;i = 1;j = 1;do { if(m->arr[i][j] == 0){ a.x = i; a.y = j; m->arr[i][j] = 2; pushStack(S, a); if(i == m->row && j == m->col){ return 0; } } a = passNext(m, i, j); if(a.x!=-1){ i = a.x; j = a.y; continue; } else if(a.x ==-1){ boolean = popStack(S, &a); if(2 == boolean){ return 0; } getTop(S, &a); i = a.x; j = a.y; } }while(S->next!= NULL);return 0;} //模擬出路徑 void showRoad(Maze m, Stack S){ coordinate e;int i, j;if(S->next == NULL){ printf(“nSorry!you can't go out the Maze!n”);} while(S->next!= NULL){ popStack(S, &e); m.arr[e.x][e.y] =-1;} for(i = 1;i <= m.row;i++){ for(j = 1;j <= m.col;j++){ if(m.arr[i][j] >= 0){ printf(“■ ”); } else { printf(“□ ”); } } printf(“n”);} } //*************************** //主函數(shù) int main(){ Maze m;Stack S;printf(“※ 歡迎玩耍迷宮求解游戲 ※n”);initlStack(&S);creatMaze(&m);showMaze(&m);solveMaze(&m, S);printf(“nthe root is here:n”);show(S);showRoad(m, S);return 0;} 程序運(yùn)行結(jié)果： 第一步：輸入迷宮行列大小 第二步：輸入迷宮信息 第四步：程序會自動求出路徑 課 設(shè) 總 結(jié) 敬愛的沈華老師您好，感謝您這半年對我們的教誨，說實(shí)話，很喜歡上您的課，您上課的風(fēng)采深深的吸引了我，每次上您的課，我都聽得特別認(rèn)真。好吧，言歸正傳，談?wù)勥@次課程設(shè)計的感想。 首先看到這道題的時候，真心沒多少思路，我抱著試一試的態(tài)度，去網(wǎng)上搜索相關(guān)的算法。網(wǎng)上資源蠻多的，剛開始就搜索到了，嚴(yán)蔚敏老師的相關(guān)算法講解視頻，雖然她講的是思想（就是他并沒有源程序的實(shí)現(xiàn)），但是足夠讓我理解了基本算法流程。 其實(shí)先開始都不知道怎么下筆，但是我還是想著從基本棧開始寫吧，慢慢寫著，程序大概思想框架就成型了，最后在實(shí)現(xiàn)求解迷宮路徑的時候，著手用筆在草稿紙上面模擬，然后才敲到編譯器中，最好幾經(jīng)調(diào)試，終于得到了想要的結(jié)果。 做完這次課設(shè)后，深刻的體會到一些道理，在信息時代，解決問題的最好方法是運(yùn)用現(xiàn)代的信息資源。并且在實(shí)際中，開始沒思路的事，慢慢完成小部分，那么你的總體思維會漸漸地成型。 做事做人，平心氣和的干，總會得到成功！ 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二 求解約瑟夫問題 問題描述：使用代表頭節(jié)點(diǎn)的循環(huán)單鏈表解決此問題。設(shè)有n個人圍坐在一張圓桌周圍，現(xiàn)從某個人開始從1報數(shù)，數(shù)到m的人離開。接著從出列的下一個人開始重新從1開始報數(shù)，數(shù)到m的人又出列，如此下去直到所有的人都出列為止。求出他們的出列序列。 問題分析：例如，當(dāng)n=8,m=4時，若從第一個人開始報數(shù)（設(shè)從1開始編號），則得到的序列是：4，8，5，2，1，3，7，6。算法： void Josephus(int n, int m,int s) { //生成表頭節(jié)點(diǎn)，空單循環(huán)鏈表 LNode * HL = new LNode; HL-> next = HL; int i;//生成含有 n 個節(jié)點(diǎn)的、節(jié)點(diǎn)值依次為1，2……，n的帶表頭節(jié)點(diǎn)的循環(huán)單鏈表 For(i = n;i>=1;i--) { LNode * newptr = new LNode; Newptr-> data = i; newptr-> next = HL-> next; HL-> next = newptr;} //從表頭開始順序查找出第s個節(jié)點(diǎn)，對應(yīng)第一個開始報數(shù)的人 LNode * ap = HL, *cp = HL->next;for(i= 1;i ap = cp; cp = cp->next;if(cp = = HL){ ap = HL;cp = HL->next;} } //依次使n-1個人出列 for(i=1;i //順序查找出待出列的人，即為循環(huán)結(jié)束后cp所指向的節(jié)點(diǎn) for(int j=1;j cout << cp->data <<” “;//從單鏈表中刪除cp節(jié)點(diǎn) ap-> next = cp-> next;delete cp;//使cp指向被刪除節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn) cp = ap-> next;//若cp指向了表頭節(jié)點(diǎn)，則后移ap和cp指針 if(cp = = HL){ ap = HL;cp = HL-> next;} } //使最后一人出列 count << HL->next-> data << end1; //刪除表頭節(jié)點(diǎn)和表頭附加節(jié)點(diǎn) delete HL->next; delete HL;} 補(bǔ)充操作系統(tǒng)練習(xí)： 1、有一個虛擬存儲系統(tǒng), 每個進(jìn)程在內(nèi)存占有3頁數(shù)據(jù)區(qū)、1頁程序區(qū).剛開始時數(shù)據(jù)區(qū)為空.有以下訪頁序列: 1、5、4、1、2、3、2、1、5、4、2、4、6、5、1 試給出下列情形下的缺頁次數(shù): (1)系統(tǒng)采用先進(jìn)先出(FIFO)淘汰算法.(2)系統(tǒng)采用最近最少使用(LRU)淘汰算法.(3)若采用優(yōu)化(OPT)淘汰算法呢? 2、設(shè)系統(tǒng)中有三類資源A、B和C，又設(shè)系統(tǒng)中有5個進(jìn)程P1，P2，P3，P4和P5.在T0時刻系統(tǒng)狀態(tài)如下： 最大需求量 已分配資源量 剩余資源量 A B C A B C A B C P1 8 P2 4 P3 10 1 P4 3 P5 5(1)系統(tǒng)是否處于安全狀態(tài)？如是，則給出進(jìn)程安全序列.(2)如果進(jìn)程P5申請1個資源類A、1個資源類B和1個資源類C，能否實(shí)施分配？為什么？ 3、在一個兩道的批處理操作系統(tǒng)中，有6個作業(yè)進(jìn)入系統(tǒng)，它們的進(jìn)入時刻、估計運(yùn)行時間和優(yōu)先級如下表所示.作業(yè)號 進(jìn)入時刻 估計運(yùn)行時間 優(yōu)先級 JOB1 8：00 90分鐘 JOB2 8：10 30分鐘 JOB3 8：30 20分鐘 JOB4 8：50 15分鐘 JOB5 9：20 10分鐘 JOB6 9：40 5分鐘系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)一旦被調(diào)度運(yùn)行就不再退出.但當(dāng)有新的作業(yè)投入運(yùn)行時，可以按照優(yōu)先級進(jìn)行進(jìn)程調(diào)度.（1）試給出各個作業(yè)的運(yùn)行時間序列.（例如：JOB1：8：00-8：30，9：10-9：20，…） （2）試計算出作業(yè)的平均周轉(zhuǎn)時間. 分類號編號 華北水利水電大學(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 操作實(shí)現(xiàn).............................................................................................................7 3.2 算法實(shí)現(xiàn).............................................................................................................8 第四章編碼調(diào)試......................................................................................................................10 4.1 調(diào)試環(huán)境...................................................................................................................10 4.2 調(diào)試方法...................................................................................................................10 4.3 調(diào)試項(xiàng)目及調(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ā)生變化。 每一首歌曲播放時，依次從男女生隊(duì)列中出來學(xué)生進(jìn)行配對，由于男女生人數(shù)不一致，會使某個隊(duì)列中剩下若干學(xué)生配對不成功，配對不成功者等待下首歌時再進(jìn)行配對。該首歌結(jié)束時，配對成功的學(xué)生再回到座位上。然后再依次進(jìn)行配對，未成功者等待下首歌再進(jìn)行配對。 配對成功時，會顯示本首歌的詳細(xì)配對情況，以及整個過程的配對情況，并且可以將配對情況寫入到文件。 根據(jù)男女生的姓名或者某首歌曲的名字可以查詢到對應(yīng)的配對情況。 第二章概要設(shè)計 2.1 數(shù)據(jù)結(jié)構(gòu) 學(xué)生座位隊(duì)列： 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)隊(duì)列已存在，非首次進(jìn)循環(huán)隊(duì)列 操作結(jié)果：向Q中添加信息 FinalStuDeQueue(StuQueue&Q)初始條件：循環(huán)隊(duì)列已存在 操作結(jié)果：使隊(duì)列頭的元素出隊(duì)列，且返回FinalStu類型值 }ADT StuQueue //學(xué)生座位隊(duì)列 音樂隊(duì)列： 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； 臨時隊(duì)列： ADTTempQList{ 數(shù)據(jù)對象：D={ ai|ai∈ElemSet，i=1,2..n;n≥0 } 數(shù)據(jù)關(guān)系：R={ voidEnTempQueue(TempQList&TQL,FinalStustu)初始條件：隊(duì)列TQL已存在操作結(jié)果：向TQL中添加信息 FinalStuDeTempQueue(TempQList&TQL)初始條件：隊(duì)列TQL存在 操作結(jié)果：取出隊(duì)列的對頭元素，返回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)隊(duì)列，并為每個學(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)行配對過程中用到算法，在每首歌配對時，依次從男女生隊(duì)列中出來一個學(xué)生，進(jìn)入到臨時隊(duì)列，從臨時隊(duì)列中獲取配對的情況。在本首歌結(jié)束，下首歌開始之前，讓臨時隊(duì)列中的男女在分別根據(jù)性別入隊(duì)，依次循環(huán)，每次調(diào)用配對函數(shù)，實(shí)現(xiàn)學(xué)生的循環(huán)配對。 第三章詳細(xì)設(shè)計 3.1 操作實(shí)現(xiàn) 本系統(tǒng)包含七個文件。設(shè)計分有歡迎界面，登陸系統(tǒng)，入隊(duì)函數(shù)，配對函數(shù)，顯示函數(shù)，查詢函數(shù)等。登陸界面是整個系統(tǒng)的入口，其主要是讓合法人員進(jìn)入系統(tǒng)，入隊(duì)函數(shù)主要讓學(xué)生進(jìn)入男女隊(duì)列，配對函數(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é)生就坐”項(xiàng)，會顯示學(xué)生信息來源，包括“1.按班級獲取(推薦)”“2.手動輸入...”兩項(xiàng)可供選擇。其中，1是從文件中獲取學(xué)生信息，2是用戶手動輸入學(xué)生信息。 選擇“2.每曲配對”項(xiàng)，會顯示播放歌曲的類型，有“1.流行”“2.復(fù)古”兩個音樂風(fēng)格可供選擇，當(dāng)用戶選擇其中一個風(fēng)格并確定播放后，會顯示出當(dāng)前播放的歌曲名字和所配對的男女生。 選擇“3.顯示結(jié)果”項(xiàng)，會有“1.學(xué)生座位信息”和“2.學(xué)生配對信息”兩項(xiàng)操作可供選擇。當(dāng)選擇1，會把學(xué)生就坐后的信息顯示出來，選擇2，會把每首歌學(xué)生的配對情況顯示出來。 選擇“4.查詢配對”項(xiàng)，也有兩個操作可供選擇，分別是“1.按學(xué)生姓名”“按歌曲名”兩項(xiàng)。選擇1，會根據(jù)用戶輸入的男女生姓名查看他們的配對情況，選擇2，會根據(jù)用戶輸入的歌曲名稱顯示每首歌曲學(xué)生的配對情況。 選擇“5.退出”項(xiàng)，會出現(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 算法實(shí)現(xiàn) 定義學(xué)生結(jié)構(gòu)體FinalStu，將學(xué)生的信息放到本結(jié)構(gòu)體中，定義兩個循環(huán)隊(duì)列Boys和Girls隊(duì)列，分別存儲男女生的座位信息。定義MusicList循環(huán)鏈表，用于存放音樂信息。定義TempQueue隊(duì)列，用于臨時存放從男女生隊(duì)列中出來的學(xué)生信息。創(chuàng)建一個存放每首歌配對情況的數(shù)組stuTable[]，用來存放播放該首歌曲時男女生的信息。 每一首歌開始時，男女生依次用Boys和Girls隊(duì)列中出對，依次進(jìn)入臨時隊(duì)列TempQueue，從TempQueue中讀取男女生的信息，放到stuTable數(shù)組中，表示該首歌的 8 配對情況。下首歌開始時，讓臨時隊(duì)列中的學(xué)生再根據(jù)性別依次進(jìn)入男女循環(huán)隊(duì)列。同時將存放歌曲的MusicList循環(huán)鏈表指針后移，播放下首歌曲，再執(zhí)行上述操作，便可實(shí)現(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)試項(xiàng)目及調(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è)計懂得了理論與實(shí)際相結(jié)合是很非常重要的，只有理論知識是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為，從而提高自己的實(shí)際動手能力和獨(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)常會遇到這樣那樣的錯誤，有的時候是因?yàn)橐恍┳罨镜腻e誤，如標(biāo)點(diǎn)的中英錯誤，括號的匹配問題，數(shù)據(jù)的輸入錯誤等。當(dāng)然，也有很多地方是因?yàn)橛缅e了解決方法。在設(shè)計的過程中，最能體現(xiàn)出的缺點(diǎn)就是基礎(chǔ)不扎實(shí)，本可以避免的錯誤卻一再出現(xiàn)。 在實(shí)現(xiàn)舞池配對問題過程中，需要使學(xué)生循環(huán)配對，此程序設(shè)計的是當(dāng)一個光盤的音樂播放結(jié)束時，整個配對過程隨之結(jié)束，而沒有讓學(xué)生再次進(jìn)去坐席，導(dǎo)致不再從新將學(xué)生入座，就無法實(shí)現(xiàn)配對。設(shè)計的是在每首歌開始之前學(xué)生進(jìn)入隊(duì)列，可以改為當(dāng)某個學(xué)生坐席為空時，隨即讓學(xué)生再次進(jìn)入隊(duì)列，可以解決不能重復(fù)換歌曲的問題。 剛開始的時候我直接在開發(fā)環(huán)境下一邊看題一邊寫代碼，瞪了半天什么也沒寫出來，于是我便先開始在紙上畫畫寫寫，將事件的整個過程畫下來，然后考慮怎么才能運(yùn)用代碼來實(shí)現(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;//男生隊(duì)列 StuQueue Girls;//女生隊(duì)列 //初始化學(xué)生坐席 void InitQueue(StuQueue &Q){ Q.base=(FinalStu*)malloc(MAXQSIZE*sizeof(FinalStu));if(Q.base==NULL) return;Q.front=Q.rear=0; } //學(xué)生就坐,首次入隊(duì)，需要獲取學(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;} //非首次入隊(duì)，不需獲取學(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;} //臨時隊(duì)列，用于存放從男女生隊(duì)列中配對成成功的學(xué)生信息 struct TempQueue { FinalStu stu;TempQueue * next;}; struct TempQList { TempQueue *front;TempQueue *rear;};TempQList TempQL;//臨時隊(duì)列，用于存放每次出來的男女生信息 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));//從男生隊(duì)列中出來進(jìn)入臨時隊(duì)列 EnTempQueue(TempQL,DeQueue(Girls));//從女生隊(duì)列中出來進(jìn)入臨時隊(duì)列 length++;//記錄每首歌的配對數(shù) } //從臨時隊(duì)列中將信息賦值給表 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);//初始化臨時隊(duì)列 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< } } } } //主界面選項(xiàng) 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è)計報告 題 目： 一元多項(xiàng)式計算 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 2012級普本班 學(xué) 號： 201201011367 姓 名： 左帥帥 指導(dǎo)老師： 郝慎學(xué) 時 間： 一、課程設(shè)計題目分析 本課程設(shè)計要求利用C語言或C++編寫，本程序?qū)崿F(xiàn)了一元多項(xiàng)式的加法、減法、乘法、除法運(yùn)算等功能。 二、設(shè)計思路 本程序采用C語言來完成課程設(shè)計。 1、首先，利用順序存儲結(jié)構(gòu)來構(gòu)造兩個存儲多項(xiàng)式A(x)和 B(x)的結(jié)構(gòu)。 2、然后把輸入，加，減，乘，除運(yùn)算分成五個主要的模塊：實(shí)現(xiàn)多項(xiàng)式輸入模塊、實(shí)現(xiàn)加法的模塊、實(shí)現(xiàn)減法的模塊、實(shí)現(xiàn)乘法的模塊、實(shí)現(xiàn)除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數(shù)的嵌套調(diào)用來實(shí)現(xiàn)其功能，盡量減少程序運(yùn)行時錯誤的出現(xiàn)。 4、最后編寫main()主函數(shù)以實(shí)現(xiàn)對多項(xiàng)式輸入輸出以及加、減、乘、除，調(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) 建立一元多項(xiàng)式函數(shù)Polyn Create(Polyn head,int m) 求解并建立多項(xiàng)式a+b，Polyn Add(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a-b，Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項(xiàng)式a*b，Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項(xiàng)式a/b，void Device(Polyn pa,Polyn pb) 輸出函數(shù)輸出多項(xiàng)式，void Print(Polyn P) 銷毀多項(xiàng)式函數(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表示每一項(xiàng)前的系數(shù)，expn表示每一項(xiàng)的指數(shù)，polyn為結(jié)點(diǎn)指針類型，屬于抽象數(shù)據(jù)類型通常由用戶自行定義，Polynomial表示的是結(jié)構(gòu)體中的數(shù)據(jù)對象名。 (2)當(dāng)用戶輸入兩個一元多項(xiàng)式的系數(shù)和指數(shù)后，建立鏈表，存儲這兩個多項(xiàng)式，主要說明如下： Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項(xiàng)式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結(jié)點(diǎn)以接收數(shù)據(jù) Insert(p,head);調(diào)用Insert函數(shù)插入結(jié)點(diǎn) 這就建立一元多項(xiàng)式的關(guān)鍵步驟 (3)由于多項(xiàng)式的系數(shù)和指數(shù)都是隨即輸入的，所以根據(jù)要求需要對多項(xiàng)式按指數(shù)進(jìn)行降冪排序。在這個程序模塊中，使用鏈表，根據(jù)對指數(shù)大小的比較，對各種情況進(jìn)行處理，此處由于反復(fù)使用指針對各個結(jié)點(diǎn)進(jìn)行定位，找到合適的位置再利用void Insert(Polyn p,Polyn h)進(jìn)行插入操作。(4)加、減、乘、除、的算法實(shí)現(xiàn)： 在該程序中，最關(guān)鍵的一步是實(shí)現(xiàn)四則運(yùn)算和輸出，由于加減算法原則是一樣，減法可通過系數(shù)為負(fù)的加法實(shí)現(xiàn)；對于乘除算法的大致流程都是：首先建立多項(xiàng)式a*b，a/b，然后使用鏈表存儲所求出的乘積，商和余數(shù)。這就實(shí)現(xiàn)了多項(xiàng)式計算模塊的主要功能。 (5)另一個子函數(shù)是輸出函數(shù) PrintPolyn（）； 輸出最終的結(jié)果，算法是將最后計算合并的鏈表逐個結(jié)點(diǎn)依次輸出，便得到整鏈表，也就是最后的計算式計算結(jié)果。由于考慮各個結(jié)點(diǎn)的指數(shù)情況不同，分別進(jìn)行了判斷處理。 四、程序新點(diǎ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)驗(yàn)吧。 六、測試（程序截圖） 1.數(shù)據(jù)輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結(jié) 通過本次應(yīng)用C語言設(shè)計一元多項(xiàng)式基本計算程序，使我更加鞏固了C語言程序設(shè)計的知識，以前對指針這一點(diǎn)使用是比較模糊，現(xiàn)在通過此次課程設(shè)計對指針理解的比較深刻了。而且對于數(shù)據(jù)結(jié)構(gòu)的相關(guān)算法和函數(shù)的調(diào)用方面知識的加深。本次的課程設(shè)計，一方面提高了自己獨(dú)立思考處理問題的能力；另一方面使自己再設(shè)計開發(fā)程序方面有了一定的小經(jīng)驗(yàn)和想法，對自己以后學(xué)習(xí)其他語言程序設(shè)計奠定了一定的基礎(chǔ)。 八、指導(dǎo)老師評語及成績 附錄：（課程設(shè)計代碼） #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結(jié)點(diǎn)指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數(shù)為0的話釋放結(jié)點(diǎn) 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é)點(diǎn) { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數(shù)為新時將結(jié)點(diǎn)插入 } 7 } //建立一個頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 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é)點(diǎn)以接收數(shù)據(jù) printf(“請輸入第%d項(xiàng)的系數(shù)與指數(shù):”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調(diào)用Insert函數(shù)插入結(jié)點(diǎn) } return head;} //銷毀多項(xiàng)式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; } } //輸出多項(xiàng)式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項(xiàng)數(shù)計數(shù)器 if(!q)//若多項(xiàng)式為空，輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數(shù)大于0且不是第一項(xiàng) 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多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;//b多項(xiàng)式已空，但a多項(xiàng)式非空 } //求解并建立多項(xiàng)式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é)點(diǎn) 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é)點(diǎn) } return headc;} //求解并建立多項(xiàng)式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;} //求解并建立多項(xiàng)式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é)點(diǎn) 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ù)相同的項(xiàng) } } return hf;} //求解并建立多項(xiàng)式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é)點(diǎn),存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結(jié)點(diǎn)，存儲余數(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)的項(xiàng)數(shù):”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項(xiàng)式A printf(“n”);printf(“請輸入B(x)的項(xiàng)數(shù):”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項(xiàng)式B printf(“n”);printf(“**********************************************n”);printf(“* 多項(xiàng)式操作菜單 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(”多項(xiàng)式A(x):“);Print(pa);*n”); printf(“多項(xiàng)式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項(xiàng)式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項(xiàng)式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項(xiàng)式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è)計-迷宮求解范文
第三篇：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二 求解約瑟夫問題
第四篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 舞伴問題
第五篇：2012數(shù)據(jù)結(jié)構(gòu)課程設(shè)計
點(diǎn)擊咨詢 