學生搭配問題說明書

*******************實踐教學*******************蘭州理工大學計算機與通信學院2023年春季學期算法與數(shù)據(jù)結構課程設計題目：學生搭配問題專業(yè)班級：計算機四班姓名：趙文基學號：09240412指導教師：張其文成績：____________目錄摘要2序言3正文41.需求分析42.概要設計43.運行環(huán)境54.開發(fā)工具和編程語言55.詳細設計5程序設計過程中的關鍵算法：56.函數(shù)調(diào)用關系圖67.調(diào)試分析78.測試結果8參考文獻12總結13致謝14附件I局部程序源代碼15摘要1.系統(tǒng)的主要任務學生搭配問題內(nèi)容是：一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上。每曲開始時,依次從男生和女生中各出一人配對跳舞,本曲沒成功配對者坐著等待下一曲找舞伴。應用循環(huán)隊列來實現(xiàn)此程序。2.設計方法循環(huán)隊列是一種環(huán)狀的隊列并且對頭元素指向隊尾元素，學生搭配問題是典型的只有采用循環(huán)隊列才能解決的問題,實驗說明該算法的空間復雜度優(yōu)于其他算法，通過這次對學生搭配問題的解決可以更好的理解和運用循環(huán)隊列。關鍵詞：數(shù)據(jù)結構；C語言；循環(huán)隊列序言數(shù)據(jù)結構是一門專業(yè)技術根底課，它對學習者的的要求很明確：學會分析、研究計算機加工的數(shù)據(jù)結構的特性，以便為應用設計所需的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、存儲結構及其相應的算法，并初步掌握算法的時間分析和空間分析的技術。其次，該課程的學習過程也是復雜程序設計的訓練過程，要求學習者編寫的程序結構或設計的程序結構體清楚、正確、易讀，符合軟件工程的標準。循環(huán)隊列是一種重要的鏈式結構，其特殊性在于需附設兩個指針front和rear分別指示對頭元素及隊尾元素的位置且對頭和隊尾相鄰接，臆造的環(huán)狀空間巧妙的解決了插入和刪除元素可能出現(xiàn)的假溢出現(xiàn)象。本設計采用目前最通用的程序設計語言之一——C語言作為數(shù)據(jù)結構和算法的描述語言，循環(huán)隊列作為數(shù)據(jù)存儲結構。充分考慮了循環(huán)隊列的特點僅通過對兩個循環(huán)隊列的出、入列操作，就簡單的實現(xiàn)了要求，動態(tài)的模擬出了舞池兩邊男女生的搭配情況。該程序通俗易懂且實用性強，其他類似的算法均可借鑒和參考使用。并且該程序清單詳細具體、全面、具有很強的可讀性。正文1.需求分析核心問題：循環(huán)隊列的應用數(shù)據(jù)模型〔邏輯結構〕：循環(huán)隊列〔兩個〕，將男生、女生兩組人分別存放，以后實現(xiàn)循環(huán)配對輸出。存儲結構：循環(huán)鏈表核心算法：循環(huán)隊列的入隊，出隊，判隊滿，判隊空。輸入數(shù)據(jù)：男生人數(shù)、女生人數(shù)，歌曲數(shù)量輸出數(shù)據(jù)：每一首歌曲播放時，男生和女生搭配情況〔輸出編號〕當要查找的男女搭配時輸出歌曲編號，和他們搭配的總次數(shù)。通過以上分析，該程序具有可行性。2.概要設計算法設計思想隊列〔Queue〕是只允許在一端進行插入，而在另一端進行刪除的運算限制的線性表。循環(huán)隊列是在隊列的順序存儲結構中，除了用乙組地址連續(xù)的存儲單元一次存放從隊列頭到隊列尾的元素外，尚需附設兩個指針front和rear分別指示隊列頭和隊列尾元素的位置。循環(huán)隊列〔兩個〕，將男生、女生兩組人分別存放，以實現(xiàn)循環(huán)配對輸出。循環(huán)隊列的入隊，出隊，判隊滿，判隊空。要模擬動態(tài)地顯示出現(xiàn)題目中所要求的循環(huán)，我們要先建立兩個循環(huán)隊列SqQueue和SqQueue2.將男生、女生兩組人分別存入這兩個隊列。以實現(xiàn)他們的配對輸出，這是循環(huán)隊列固有的特性。利用循環(huán)隊列的特性，將男女生分別進行入隊列和出隊列操作，且實現(xiàn)搭配輸出。循環(huán)隊列的長度分別設為男女生的個數(shù)即可。在計算機終端輸出的結果是：根據(jù)要求輸出男生女生搭配情況。3.運行環(huán)境硬件開發(fā)環(huán)境：PC機軟件開發(fā)環(huán)境：VisualC++6.0操作系統(tǒng)環(huán)境：Windows74.開發(fā)工具和編程語言軟件開發(fā)工具：VisualC++6.0編程語言：C語言5.詳細設計建立鏈式循環(huán)隊列來分別存儲男生和女生，然后調(diào)用入隊出隊函數(shù)實現(xiàn)循環(huán)隊列的配對輸出。為了充分利用向量空間，克服上述存儲結構上溢現(xiàn)象的方法是將向量空間想象為一個首尾相接的圓環(huán)，存儲在其中成為循環(huán)隊列。再循環(huán)隊列中進行入隊、出隊操作時，頭指針仍要加1，向前移動。只不過當頭指針指向上界時其加1操作變?yōu)橹赶蛳陆?，這樣就可以通過出隊再入隊來實現(xiàn)男生女生的循環(huán)搭配了。程序設計過程中的關鍵算法：關鍵算法之一：初始化隊列VoidInitQueue(LinkQueue&Q){QueuePtrp;P=(QueuePtr)malloc(sizeof(QNode));Q.front=p;Q.rer=p;Q.front->next=NULL;}關鍵算法之二：入隊函數(shù)VoidEnQueue(LinkQueue&Q,intnum){QueuePtrp;P=(QueuePtr)malloc(sizeof(QNode));P->num=num;p->next=NULL;Q.rer->next=p;Q.rer=p;}關鍵算法之三：出隊函數(shù)VoidDeQueue(LinkQueue&Q,int&num){QueuePtrp,q;If(Q.front==Q.rear)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);}關鍵算法之四：輸出第i首曲子時女隊的情況Voidprintf(LinkQueue&F,inti){QueuePtrp;Intn=1;While(n<i){Printf("_");n++;}P=F.front->next;While(F.rear!=p){Printf("%d",p->num);P=p->next;Printf("%d\n",p-num);}函數(shù)調(diào)用關系圖主函數(shù)main主函數(shù)main主界面主界面查找配對每曲配對退出系統(tǒng)數(shù)據(jù)輸入查找配對每曲配對退出系統(tǒng)數(shù)據(jù)輸入圖6.1函數(shù)調(diào)用圖7.調(diào)試分析測試數(shù)據(jù)：編號12345男生〔5人〕abcde女生〔3人〕aabbccA〔錯誤分類〕曲子數(shù)10測試圖如下：圖7.1數(shù)據(jù)測試圖測試中出現(xiàn)的問題描述：女生數(shù)量設定為3，但實際輸入女生數(shù)超過3沒有錯誤警告，說明程序還存在一定的漏洞。在輸入數(shù)據(jù)函數(shù)voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n)中存在不健全，在接收男生或女生數(shù)據(jù)時沒有對數(shù)據(jù)個數(shù)〔m或n〕進行合理性檢測。改良方法：在輸入數(shù)據(jù)函數(shù)voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n)中參加限制語句if(i>m)printf〔“超出限制〞〕;刪除剛輸入數(shù)據(jù)；提示重新輸入；使得輸入男生數(shù)〔女生數(shù)〕大于預設值時進行提醒，并進行修正。8.測試結果測試輸入數(shù)據(jù)：男女生的個數(shù)及姓名、曲子數(shù)和要查找的男女生編號編號12345男生abcde女生aabbcc曲子數(shù)10輸出結果為：每首曲子男女生搭配的情況程序運行界面如下：圖8.1輸入數(shù)據(jù)時界面圖8.2輸出每首曲子配對情況界面圖8.3輸出某曲子配對情況界面圖8.4輸出程序結束情況界面參考文獻〔1〕嚴蔚敏等，數(shù)據(jù)結構〔C語言版〕.北京清華大學出版社,2007年〔2〕嚴蔚敏等，數(shù)據(jù)結構題集〔C語言版〕.北京清華大學出版社，2007年〔3〕譚浩強著，C程序設計〔第三版〕.北京清華大學出版社，2005年〔4〕《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清華大學出版社〔影印版〕.〔5〕數(shù)據(jù)結構與算法分析〔Java版〕,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,張銘,劉曉丹譯電子工業(yè)出版社2001年1月總結運用循環(huán)隊列的根本操作順利的解決學生舞曲搭配問題，主要利用用循環(huán)隊列的環(huán)狀結構，循環(huán)地執(zhí)行出列入列操作并在出隊列時進行配對并輸出配對情況，而整個過程不需要不需要移動元素使程序在空間復雜度上降到最小，采用指針的移動大大加快了程序的執(zhí)行效率。并且對輸入進行了改良，以防止用戶隨意輸入時出現(xiàn)的各種意想不到的錯誤。系統(tǒng)整體上比擬完美，無論是輸入、輸出，還是整個系統(tǒng)的界面，都非常美觀、簡潔、大方。致謝首先，我們要感謝學校給我們提供了此次課程設計的時機，能讓同學們在一起學習與研究，讓我們有時機對所學的理論知識進行實踐。其次，我們還要特別感謝我們的輔導老師張其文老師，在他的精心輔導和幫助下，我們的設計才得以順利完成。對他為我們的設計所提出的珍貴意見表示忠心的感謝！最后、在論文的寫作過程中，也得到了許多同學的珍貴建議，同時還到許多校友的支持和幫助，在此一并致以誠摯的謝意。附件I局部程序源代碼#include<stdio.h>#include<time.h>#include<dos.h>#include<stdlib.h>#include<string.h>#defineMAX200#defineMAXNAME20typedefstructLNode{ intnum;//編號charname[MAXNAME];charsex;//性別，'F'表示女性，'M'表示男性structLNode*next;}LNode,*LinkList;inttime(void)//系統(tǒng)時間函數(shù){time_ttimer;structtm*tblock;/*getstimeofday*/timer=time(NULL);/*convertsdate/timetoastructure*/tblock=localtime(&timer);printf("\t\t\t\t\t當前時刻:%s",asctime(tblock));return0;}voidsleep(clock_twait)//延遲函數(shù){clock_tgoal;goal=wait+clock();while(goal>clock());}voidCreateList_L(LinkList&L1,LinkList&L2,int&m,int&n){printf("\n\n\t\t\t\t^o^參加舞會學生名單^o^\n");printf("\n\n\t\t請輸入女生數(shù)量：");scanf("%d",&m);while(m<1){printf("\n\n\t\t\t\tERROR\n\n\t\t\t請重新輸入女生數(shù)量");sleep(1000);//voidsleep(clock_twait)放在前system("CLS");printf("\n\n\t\t\t\t^o^參加舞會學生名單^o^\n");printf("\n\n\t\t請輸入女生數(shù)量：");scanf("%d",&m);}printf("\t\t請輸入男生數(shù)量：");scanf("%d",&n);while(n<1){printf("\n\n\t\t\t\tERROR\n\n\t\t\t請重新輸入男生數(shù)量");sleep(1000);system("CLS");printf("\n\n\t\t\t\t^o^參加舞會學生名單^o^\n");printf("\n\n\t\t請輸入女生數(shù)量：%d",m);printf("\n\t\t請輸入男生數(shù)量：");scanf("%d",&n);}inti,choice,numw,numn,b[MAX],j;numw=numn=0;chara[MAX][MAXNAME];LinkListp1,p2,q;//,，不,一，樣的p1=p2=L1=L2=NULL;printf("\t\t\t**************");printf("\n\t\t\t*歡送參加舞會*\n");printf("\t\t\t**************\n");printf("\t\t請輸入學生的情況\n");for(i=0;i<(m+n)&&i<MAX;i++){if(i>=5){sleep(500);system("CLS");printf("\n\n\t\t\t\t^o^參加舞會學生名單^o^\n");printf("\n\n\t\t請輸入女生數(shù)量：%d",m);printf("\n\t\t請輸入男生數(shù)量：%d\n",n);printf("\t\t\t**************");printf("\n\t\t\t*歡送參加舞會*\n");printf("\t\t\t**************\n");printf("\t\t請輸入學生的情況\n");for(j=i-4;j<i;j++){printf("\t\t第%d個人姓名:%s\n",j+1,a[j]);printf("\t\t性別<1girl，2boy>:%d\n",b[j]);}}printf("\t\t第%d個人姓名:",i+1);scanf("%s",a[i]);printf("\t\t性別<1girl，2boy>:");scanf("%d",&choice);///////////////scanf("sex:%d",&choice);錯錯b[i]=choice;q=(LinkList)malloc(sizeof(LNode));if(q==NULL)exit(-1);strcpy(q->name,a[i]);if(choice==1){numw++;q->num=numw;if(L1==NULL){L1=q;p1=q;}//不帶頭結點else{p1->next=q;p1=q;}p1->next=L1;//循環(huán)}else{numn++;q->num=numn;if(L2==NULL){L2=q;p2=q;}//不帶頭結點else{p2->next=q;p2=q;}p2->next=L2;//循環(huán)}}}voidPrint1(LinkListL,intm){LinkListp;inti;p=L;for(i=1;i<=m;i++){printf("%s",p->name);printf("%3c",'');p=p->next;}}voidPrint2(LinkList&p,intm,intn){inti;LinkListq;for(i=1;i<=m;i++){printf("%s",p->name);printf("%3c",'');p=p->next;}q=p;for(;i<=n;i++){printf("%s",q->name);printf("%3c",'');q=q->next;}}voidMatch(LinkListL1,LinkListL2,intm,intn){intk,i,j;LinkListp;printf("\n\n\n\n\t\t\t\t^o^每曲配對情況^o^");printf("\n\n\t\t請輸入歌曲的編號：<");scanf("%d",&k);printf(">");while(k<=0){printf("\n\t\t\tERROR!!!\n\t\t請重新輸入歌曲的編號");sleep(1000);system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配對情況^o^");printf("\n\n\t\t請輸入歌曲的編號：<");scanf("%d",&k);printf(">");}if(m<n){p=L2;for(i=1;i<=k;i++){system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配對情況^o^");printf("\n\n\t\t請輸入曲子編號：<%d>",k);printf("\n\n\n\n\n\t\t\t\t第<%2d>曲配對情況\n\n\n",i);printf("\t\t");Print1(L1,m);printf("\n\t\t");for(j=1;j<=m;j++)printf("|");printf("\n\t\t");Print2(p,m,n);printf("\n\n");sleep(1000);}}else{p=L1;for(i=1;i<=k;i++){system("CLS");printf("\n\n\n\n\t\t\t\t^o^每曲配對情況^o^");printf("\n\n\t\t請輸入曲子編號：<%d>",k);printf("\n\n\n\n\n\t\t\t\t第<%2d>曲配對情況\n\n\n",i);printf("\t\t");Print2(p,n,m);printf("\n\t\t");for(j=1;j<=n;j++)printf("|");printf("\n\t\t");Print1(L2,n);sleep(1000);printf("\n\n");}}}voidXXXXXX(LinkListL,intloc,LinkList&p){inti;if(loc==1)p=L;else{p=L;for(i=1;i<loc;i++){p=p->next;}}}voidXHEY(LinkListL1,LinkListL2,intm,intn){intx,y,flag=1,k,loc1,loc2,last;LinkListp1,p2,p11,p22;while(flag!=2){system("CLS");printf("\n\n\n\t\t\t\t^o^查找配對跳舞情況^o^\n\n");printf("\n\t\t請輸入你想知道的女生和男生的編號\n\t\t女生的編號:");scanf("%d",&y);while(y>m||y<1){printf("\t\t\tERROR!!!\n\t\t請重新輸入女生的編號");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配對跳舞情況^o^\n");printf("\n\t\t請輸入你想知道的女生和男生的編號\n\t\t女生的編號:");scanf("%d",&y);}printf("\t\t男生的編號:");scanf("%d",&x);while(x>n||x<1){printf("\t\t\tERROR!!!\n\t\t請重新輸入男生的編號");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配對跳舞情況^o^\n");printf("\n\t\t請輸入你想知道的女生和男生的編號\n\t\t女生的編號:%d\n",y);printf("\t\t男生的編號:");scanf("%d",&x);}printf("\n\t\t歌曲的編號:");scanf("%d",&k);while(k<1){printf("\t\t\tERROR!!!\n\t\t請重新輸入歌曲的編號");sleep(1000);system("CLS");printf("\n\n\n\t\t\t\t^o^查找配對跳舞情況^o^\n");printf("\n\t\t請輸入你想知道的女生和男生的編號\n\t\t女生的編號:%d\n",y);printf("\t\t男生的編號:%d\n",x);scanf("%d",&k);}printf("\n\n\n");if(m<n){last=((k-1)*m)%n;loc1=(x-last+n)%n;XXXXXX(L2,x,p1);if(loc1>0&&loc1<=m){XXXXXX(L1,loc1,p11);}elseprintf("\t\t在第<%4d>曲編號為<%4d>的男生(%s)沒有舞伴\n\n",k,x,p1->name);XXXXXX(L1,y,p2);loc2=(last+y)%m;XXXXXX(L2,loc2,p22);if(loc2==x||loc1==y)printf("\t\t編號為<%4d>的男生(%s)和編號為<%4d>的女生(%s)在第(%4d)首歌配對跳舞\n\n\n",x,p1->name,y,p2->name,k);else{if(loc1>0&&loc1<=m)printf("\t編號為<%4d>的男生(%s)在第(%4d)首歌和編號為<%4d>的女生(%s)配對跳舞\n\n",x,p1->name,k,y,p11->name);printf("\t編號為<%4d>的女生(%s)在第(%4d)首歌和編號為<%4d>的男生(%s)配對跳舞\n\n",x,p2->name,k,y,p22->name);}}else{last=((k-1)*n)%m;loc1=(y-last+m)%m;XXXXXX(L1,y,p1);if(loc1>0&&loc1<=n){XXXXXX(L1,loc1,p11);}elseprintf("\t\t在第<%4d>曲編號為<%4d>的女生(%s)沒有舞伴\n\n",k,x,p1->name);XXXXXX(L2,x,p2);loc2=(last+x)%m;XXXXXX(L1,loc2,p22);if(loc2==y||loc1==x)printf("\t\t編號為<%4d>的男生(%s)和編號為<%4d>的女生(%s)在第(%4d)首歌配對跳舞\n\n\n",x,p1->name,y,p2->name,k);else{printf("\t編號為<%4d>的男生(%s)在第(%4d)首歌和編號為<%4d>的女生(%s)配對跳舞\n\n",x,p2->name,k,y,p22->name);if(loc1>0&&loc1<=m)printf("\t編號為<%4d>的女生(%s)在第(%4d)首歌和編號為<%4d>的男生(%s)配對跳舞\n\n",x,p1->name,k,y,p11->name);}}printf("\n\n\t是否繼續(xù)找配對情況<想1，不想2>：");scanf("%d",&flag);}}intEmptyL(LinkListL){if(L==NULL)return1;elsereturn0;}voidDestroyL(LinkList&L){LinkListp;if(!EmptyL(L)){p=L->next;while(p!=L){L->next=p->next;free(p);p=L->next;}free(L);}}voidJieMian(){for(inti=1;i<=50;i++){//system("colorCF");/*設置背景/字體顏色，1為背景，7為前景，其值可隨便設,系統(tǒng)默認為07*/system("CLS"); printf("\n\n\n\n"); printf("\t\t\t^o^學生搭配問題^o^\n\n"); printf("\t\t\t╔*═*═*═*═*═*═*═*═*═*═*╗\n"); printf("\t\t\t║║\n");printf("\t\t\t║1.參加舞會學生名單║\n");printf("\t\t\t║2.輸出每曲配對情況║\n");printf("\t\t\t║3.查找配對跳舞情況║\n");printf("\t\t\t║4.退出║\n");printf("\t\t\t║║\n"); printf("\t\t\t║*=*請在1~4選項中選擇*=*║\n"); printf("\t\t\t║║\n"); printf("\t\t\t╚*═*═*═*═*═*═*═*═*═*═*╝\n"); printf("\n\n\t\t\t\t\t 趙文基數(shù)據(jù)結構課程設計\n"); //printf("\t\t\t\t\t\t\ttime()"); time(); printf("\n\n輸入選擇的工程：");sleep(1);}}voidJiemian2(){inti;system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次使^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次使用");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次使用^o^");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次使用^o^\n\n\t\t\t\t");sleep(200);system("CLS");printf("\n\n\n\n\n\n\n\n\t\t\t^o^歡送下次使用^o^\n\n\t\t\t\tGoodBye!");sleep(200);system("CLS");for(i=1;