數(shù)據(jù)結構課程設計報告運動會分數(shù)統(tǒng)計 一元多項式 迷宮求解 文章編輯 紙牌游戲等

1、數(shù)據(jù)結構課程設計報告南京林業(yè)大學數(shù)據(jù)結構課程設計報告專業(yè)： 計算機科學與技術課程名稱： 數(shù)據(jù)結構姓名： 學號： 090801126指導老師： 時間: 2011年1月 目錄要點： 一. 具體內容（題目） 1 二. 需求分析（功能要求） 2三. 概要設計（程序設計思想） 3四. 詳細設計（源代碼） 6五. 調試分析（運行結果顯示及說明） 31六 課設總結 34具體內容：題目1: 運動會分數(shù)統(tǒng)計*任務：參加運動會有n個學校，學校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7，5，3，2，1，取前三名的積

2、分分別為：5，3，2，；哪些取前五名或前三名由學生自己設定。（m=20，n=20）；題目2：一元多項式*任務：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加，相減，并將結果輸入；題目4：迷宮求解任務：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；題目5：文章編輯*功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共n行；題目6：joseph環(huán) 任務：編號是1，2，n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m，從第一個仍開始順時針方向自

3、1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有的人出列為止。設計一個程序來求出出列的順序。題目7:猴子選大王*任務：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第n個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。 題目8：建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以） *任務：要求能夠輸入樹的各個結點，并能夠輸出用不同方法遍歷的遍歷序列；題目9:紙牌游戲*任務：編號為1-52張牌，正面向上，從第2張開

4、始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過，輸出：這時正面向上的牌有哪些？需求分析:運動會分數(shù)統(tǒng)計1）可以輸入前三名或前五名的成績；2）能統(tǒng)計各學?？偡?；3）可以按學校編號，學校總分，男女團體總分排序輸出；4) 可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢查詢取得前三名或前五名的學校。規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內的整數(shù)輸出形式：有中文提示，各學校分數(shù)為整形界面要

5、求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求；一元多項式計算能夠完成兩個多項式的相加，相減，并將結果輸入；迷宮求解要求：在上交資料中請寫明：存儲結構、基本算法（可以使用程序流程圖）、源程序、測試數(shù)據(jù)和結果、算法的時間復雜度、另外可以提出算法的改進方法；文章編輯（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)并輸出該次數(shù)，用函數(shù)letter_num()，figure_num（），space_num（），total_num（）來實現(xiàn)。（3）刪除某一子串，并將后面的字符前移,用delstr()來實現(xiàn)。存儲結構使用線性表，分別用

6、幾個子函數(shù)實現(xiàn)相應的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出全部字母數(shù)、數(shù)字個數(shù)、空格個數(shù)、文章總字數(shù)（3）輸出刪除某一字符串后的文章；joseph環(huán)利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。輸入數(shù)據(jù)：建立輸入處理數(shù)據(jù)，輸入m的初值，n，輸入每個人的密碼，建立單循環(huán)鏈表。輸出是什么：建立一個輸出函數(shù)，將正確的輸出序列；猴子選大王輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，nm輸出形式：中文提示按照m個猴子，數(shù)n 個數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個函數(shù)來實現(xiàn)此功能；首

7、先用一個數(shù)組來存放猴子的編號,從1到m,然后用hzxdw()按題目要求,用兩個雙重循環(huán)來實現(xiàn)猴子大王的選舉.建立二叉樹typedef struct node 是定義二叉樹的存儲結構creat(bitree *bt)是用來建立二叉樹的輸入的levelorder(bitnode *bt,int m)是用來建立層序遍歷序列的preorder(bitree bt)是用來實現(xiàn)非遞歸先序遍歷的main是主函數(shù)紙牌游戲直接用函數(shù)main()按照題目要求的規(guī)則, 只使用數(shù)組和用幾個循環(huán)來實現(xiàn).概要設計：運動會分數(shù)統(tǒng)計：先分配存儲的空間；輸入運動項目個數(shù)、參加的學校的個數(shù)、男子比賽項目的個數(shù)、女子比賽項目的個數(shù)

8、；循環(huán)每個項目的輸入；自行選擇取前三名還是前五名，循環(huán)輸入姓名、成績、學校；通過調用子函數(shù)進行計算；輸出結果。一元多項式計算：通過typedef struct polynode來定義單鏈表存儲多項式的結點結構。利用尾插法建立一元多項式的鏈表，先建立多項式的頭結點，當表不為空的時候，申請新的結點，并分配存儲空間，在當前的尾表做插入，最后將表的最后一個結點的next置null，以表示結束。兩個多項式的相加：當兩個多項式均未掃描結束時若指數(shù)不等則到下一個結點，若指數(shù)相等且不為零時，相應的系數(shù)相加，若系數(shù)都為零時，則刪除接點p與q，并將指針指向下一個結點，否則將q結點加入到和多項式中。若多項式a中還有

9、剩余，則將剩余的結點加入到和多項式中否則，將b中的結點加入到和多項式中。兩個多項式的相減與相加類似；總流程圖：文章編輯: 用串來存放一篇文章,文章錄入以#作為結束,然后統(tǒng)計文章各種數(shù)據(jù),直到#號為止,查找用戶要統(tǒng)計的和刪除的字符都是一樣的思想,刪除某一子串，并將后面的字符前移。joseph環(huán)：建立單循環(huán)鏈表，依次根據(jù)提示輸入m，n，及code值。猴子選大王： 猴子的存放采用鏈式存儲結構，利用循環(huán)鏈表來實現(xiàn)建立的，其表示方法是遞歸定義的： typedef struct mnode int data; struct mnode *next;mnode; 根據(jù)題目要求，要讓這m只猴子順序圍坐一圈，那

10、就得用循環(huán)鏈表king(linklist l,int n)在主函數(shù)中，根據(jù)提示先輸入猴子的總的數(shù)量m，再輸入數(shù)的數(shù)n，最后調用子函數(shù)進行選擇，輸出猴子王的編號。建立二叉樹：在typedef struct node中定義二叉樹bitree的左右結點分別為lchild、rchild。在輸入函數(shù)中，把輸入.代表空；若輸入不為空，則分配存儲空間，并使其產生左右結點。在層序遍歷函數(shù)中，先定義一個數(shù)組，然后遍歷他的左孩子結點，若不為空就放到數(shù)組中，再遍歷右孩子結點，若不為空也放到數(shù)組中。二叉樹的層序遍歷是由上至下一層一層地遍歷的。主函數(shù)中，先提示輸入一個樹調用二叉樹輸入函數(shù)，然后調用層序遍歷函數(shù)，再調用遞

11、歸先序遍歷函數(shù)。紙牌游戲:通過循環(huán)和連續(xù)乘-1進行翻牌，把值為1的定義為朝上的牌。先定義52個牌；把每個牌都賦值為1；通過循環(huán)（52張牌的循環(huán)和基數(shù)的循環(huán)），并判斷基數(shù)，每翻一次牌都乘-1，最后為1的數(shù)就是朝上的牌。 時間復雜度為o1；程序實現(xiàn)思想:首先必須確定實現(xiàn)這個課程設計的主算法是使用鏈式存儲結構還是棧又或是數(shù)組和廣義表。根據(jù)題目要求需要實現(xiàn)的功能有：1、 數(shù)據(jù)錄入：輸入各種數(shù)據(jù)；此處即創(chuàng)建鏈表的過程，調用一個成員函數(shù)負值。在此處還有一個方法實現(xiàn)，即先輸入數(shù)據(jù)，然后再調用構造實現(xiàn)。2、數(shù)據(jù)統(tǒng)計：存儲方式的選擇，是使用鏈式存儲結構還是棧又或是數(shù)組和廣義表；遵守先定義后調用的原則；數(shù)組定義時

12、注意下標的起始值和上限；鏈表定義時注意結點中的項；準確運用結點。3、 數(shù)據(jù)輸出：按要求的格式打印 調用do循環(huán)和for循環(huán)，通過遍歷鏈表實現(xiàn)輸出，用printf語句輸出。4、 查找,修改,刪除：這三個功能的核心是尋找成員，先遍歷鏈表，然后尋找對應的id號來找到結點，然后再對結點實行刪除，修改操作。詳細設計（源程序）：1.運動會分數(shù)統(tǒng)計：#include #include #include #include #include #define max 50 #define null 0 typedef struct node1 int school; /*學校編號*/ int record; /*

13、項目成績*/ struct node1 *next; schools; typedef struct int item; /*項目編號*/ schools *firstschool; item; typedef struct int z; /* 項目總數(shù) */ item amax; allitems; typedef struct node2 int item; /*該學校獲獎的項目*/ int record; /*項目成績*/ struct node2 *next; items; typedef struct int school; /*學校編號*/ int score; /*學?？偡?/

14、int boys; /*男團體總分*/ int girls; /*女團體總分*/ items *firstitem; schnode; typedef struct int n; /* 學?？倲?shù) */ schnode bmax; allnode; allitems *g1; allnode *g2; void funct1(allitems *g1,allnode *g2) /* 輸入各個項目成績 */ schools *p1; items *p2; int i,j,k,m,w,h,x; printf(n* enter the information of every item *nn); p

15、rintf(enter the total number of male-items m:); scanf(%d,&m); if(m20) printf(enter error,m=20,please enter again:); scanf(%d,&m); printf(enter the total number of female-items w:); scanf(%d,&w); if(w20) printf(enter error,wn); if(g2-nn20) printf(entr error,nn); g1-z=m+w; printf(item number for boys

16、1-%d,girls %d-%d,m,m+1,g1-z); printf(nn* record *n(0 stands for ending); for(k=1;kz;k+) /* 對兩個鄰接表置初態(tài) */ g1-ak.item=k; g1-ak.firstschool=null; for(k=1;kn;k+) g2-bk.school=k; g2-bk.firstitem=null; g2-bk.score=g2-bk.boys=g2-bk.girls=null; g2-b0.score=g2-b0.boys=g2-b0.girls=null; while(i!=0) printf(nite

17、m:); scanf(%d,&i); if(i!=0) printf(1.the three or 2.the five n); printf(please choose 1 or 2:); scanf(%d,&j); if(j!=1&j!=2) printf(enter error,please enter again:); scanf(%d,&j); if(j=1) /* 該項目只有前三名時執(zhí)行此語句 */ h=3; do printf(arrange %d:school(school is number),h); scanf(%d,&x); p1=(schools *)malloc(si

18、zeof(schools); p1-school=x; p2=(items *)malloc(sizeof(items); p2-item=i; if(h=3) p2-record=p1-record=2; if(h=2) p2-record=p1-record=3; if(h=1) p2-record=p1-record=5; p1-next=g1-ai.firstschool; g1-ai.firstschool=p1; p2-next=g2-bx.firstitem; g2-bx.firstitem=p2; g2-bx.score=g2-bx.score+p2-record; /* 累計

19、總分 */ if(ibx.boys=g2-bx.boys+p2-record; /* 累計男團體總分 */ else g2-bx.girls=g2-bx.girls+p2-record; /* 累計女團體總分 */ h-; while(x!=0&h!=0); if(j=2) /* 該項目有前五名時執(zhí)行此語句 */ h=5; do printf(arrange %d:school(school is number),h); scanf(%d,&x); p1=(schools *)malloc(sizeof(schools); p1-school=x; p2=(items *)malloc(siz

20、eof(items); p2-item=i; if(h=5) p2-record=p1-record=1; if(h=4) p2-record=p1-record=2; if(h=3) p2-record=p1-record=3; if(h=2) p2-record=p1-record=5; if(h=1) p2-record=p1-record=7; p1-next=g1-ai.firstschool; g1-ai.firstschool=p1; p2-next=g2-bx.firstitem; g2-bx.firstitem=p2; g2-bx.score=g2-bx.score+p2-r

21、ecord; /* 累計總分 */ if(ibx.boys=g2-bx.boys+p2-record; /* 累計男團體總分 */ else g2-bx.girls=g2-bx.girls+p2-record; /* 累計女團體總分 */ h-; while(x!=0&h!=0); void save() /* 存儲數(shù)據(jù)文件 */ file *fp1,*fp2; if(fp1=fopen(sports1,wb)=null) printf(cannot open file.n); return; if(fwrite(g1,sizeof(allitems),1,fp1)!=1) printf(fi

22、le write error.n); fclose(fp1); if(fp2=fopen(sports2,wb)=null) printf(cannot open file.n); return; if(fwrite(g2,sizeof(allnode),1,fp2)!=1) printf(file write error.n); fclose(fp2); void funct2(allnode *g2) /* 輸出各學?？偡?*/ int k; printf(nn* output the score *n); printf(schoolt score n); for(k=1;kn;k+) p

23、rintf(%dtt %dn,k,g2-bk.score); printf(n); printf(press any butter to the main menu.); getch(); void funct3(allnode *g2) /* 按學校編號排序輸出 */ int k; items *p2; printf(nn* arranging output by school *n); printf(schoolttt the grade of item n); for(k=1;kn;k+) printf(%dt,k); p2=g2-bk.firstitem; while(p2!=null

24、) printf(item %d:get the grade of %d ,p2-item,p2-record); p2=p2-next; printf(n); printf(n); printf(press any butter to the main menu.); getch(); void funct4(allnode *g2) /* 按學?？偡峙判蜉敵?*/ int i,j,k; printf(nn* arranging output by the score *n); printf(schoolt score n); for(i=2;in;i+) g2-b0.score=g2-bi

25、.score; g2-b0.boys=g2-bi.boys; g2-b0.girls=g2-bi.girls; g2-b0.school=g2-bi.school; j=i-1; while(g2-b0.scorebj.score&j0) g2-bj+1.score=g2-bj.score; g2-bj+1.boys=g2-bj.boys; g2-bj+1.girls=g2-bj.girls; g2-bj+1.school=g2-bj.school; j-; g2-bj+1.score=g2-b0.score; g2-bj+1.boys=g2-b0.boys; g2-bj+1.girls=g2

26、-b0.girls; g2-bj+1.school=g2-b0.school; for(k=1;kn;k+) printf(%d tt%dn,g2-bk.school,g2-bk.score); printf(press any butter to the main menu.); getch(); void funct5(allnode *g2) /* 按男團體總分排序輸出 */ int i,j,k; printf(n* arranging output by boys *n); printf(schoolt boys n); for(i=2;in;i+) g2-b0.score=g2-bi

27、.score; g2-b0.boys=g2-bi.boys; g2-b0.girls=g2-bi.girls; g2-b0.school=g2-bi.school; j=i-1; while(g2-b0.boysbj.boys&j0) g2-bj+1.score=g2-bj.score; g2-bj+1.boys=g2-bj.boys; g2-bj+1.girls=g2-bj.girls; g2-bj+1.school=g2-bj.school; j-; g2-bj+1.score=g2-b0.score; g2-bj+1.boys=g2-b0.boys; g2-bj+1.girls=g2-b

28、0.girls; g2-bj+1.school=g2-b0.school; for(k=1;kn;k+) printf(%dtt %dn,g2-bk.school,g2-bk.boys); printf(press any butter to the main menu.); getch(); void funct6(allnode *g2) /* 按女團體總分排序輸出 */ int i,j,k; printf(n* arranging output by girls *n); printf(schoolt girls n); for(i=2;in;i+) g2-b0.score=g2-bi.

29、score; g2-b0.boys=g2-bi.boys; g2-b0.girls=g2-bi.girls; g2-b0.school=g2-bi.school; j=i-1; while(g2-b0.girlsbj.girls&j0) g2-bj+1.score=g2-bj.score; g2-bj+1.boys=g2-bj.boys; g2-bj+1.girls=g2-bj.girls; g2-bj+1.school=g2-bj.school; j-; g2-bj+1.score=g2-b0.score; g2-bj+1.boys=g2-b0.boys; g2-bj+1.girls=g2-

30、b0.girls; g2-bj+1.school=g2-b0.school; for(k=1;kn;k+) printf(%dtt %dn,g2-bk.school,g2-bk.girls); printf(press any butter to the main menu.); getch(); void funct7(allnode *g2) /* 按學校編號查詢學校某個項目情況 */ int i,j,k; items *p2; printf(n * look for the grade of a item by school *n); printf(enter the school yo

31、u are looking for:); scanf(%d,&i); printf(enter the item you are looking for:); scanf(%d,&j); p2=g2-bi.firstitem; while(p2!=null) if(p2-item=j) printf(school:%dt item:%dt record:%dn,i,p2-item,p2-record); p2=p2-next; printf(n); printf(press any butter to the main menu.); getch(); void funct8(allitems

32、 *g1) /* 按項目編號查詢取得名次的學校 */ int i,k; schools *p1; printf(n* look for the win-school by item *n); printf(enter the item you are looking for:); scanf(%d,&i); printf(item tttthe win-schooln); printf(%dt,i); p1=g1-ai.firstschool; while(p1!=null) printf( school %d:get the grade of %d ,p1-school,p1-record)

33、; p1=p1-next; printf(nn); printf(press any butter to the main menu.); getch(); void main() int t; allitems *g1; allnode *g2; for(;) printf(tt the score of the sports n); /* 運動會分數(shù)統(tǒng)計*/ printf(tt* * * * * * * * * * * * * * * * * * * * * * * * * * * * * n); printf(tt n); printf(tt* * * * * * * * * * * *

34、 * * * * * * * * * * * * * * * * * n); printf(tt* 1.entering each record and save it *n); /* .輸入各個項目成績并存儲文件 */ printf(tt* 2.accumulating the score of each school *n); /* 統(tǒng)計各學校總分*/ printf(tt* 3.arranging output by the school *n); /* 按學校編號排序輸出*/ printf(tt* 4.arranging output by the score *n); /* 按學校總分

35、排序輸出*/ printf(tt* 5.arranging output by boys *n); /* 按男團體總分排序輸出*/ printf(tt* 6.arranging output by girls *n); /* 按女團體總分排序輸出*/ printf(tt* 7.looking for the score of a item by school *n); /* 按學校編號查詢學校某個項目情況*/ printf(tt* 8.looking for the win-school by item *n); /* 按項目編號查詢取得名次的學校*/ printf(tt* 0.exit *n

36、); printf(tt* * * * * * * * * * * * * * * * * * * * * * * * * * * * * n); printf(tt please choose (0-8):); loop:scanf(%d,&t); switch(t) case 1:funct1(g1,g2);save();break; case 2:funct2(g2);break; case 3:funct3(g2);break; case 4:funct4(g2);break; case 5:funct5(g2);break; case 6:funct6(g2);break; case

37、 7:funct7(g2);break; case 8:funct8(g1);break; case 0:exit(0); default: printf(enter error,please enter again:); goto loop; 2.一元多項式計算#include#include#include#define len sizeof(struct poly)struct poly int coef; int index; struct poly * next;void print_poly(struct poly *head) struct poly *p1; printf(%d

38、次%d項式：,head-index,head-coef); p1=head-next; while(p1!=null) if(p1-coef0) if(p1-index!=1&p1-index!=0) printf(%dx%d+,p1-coef,p1-index); else if(p1-index=1) printf(%dx+,p1-coef); else printf(%d+,p1-coef); else if(p1-coefindex!=1&p1-index!=0) printf(%d)x%d+,p1-coef,p1-index); else if(p1-index=1) printf(

39、%d)x+,p1-coef); else printf(%d)+,p1-coef); p1=p1-next; printf(b n);struct poly * creat_poly() struct poly *p1,*p2,*head; head=(struct poly *)malloc(len); head-coef=head-index=0; head-next=null; printf(請輸入要創(chuàng)建的多項式（如a(x)=5x17+9x8+3x+7,請輸入517 98 31 70 00:n); p1=(struct poly *)malloc(len); scanf(%d%d,&p1

40、-coef,&p1-index); while(p1-coef!=0) p2=head; while(p2-next!=null) if(p2-next-indexindex) break; p2=p2-next; p1-next=p2-next; p2-next=p1; (head-coef)+; if(p1-indexhead-index) head-index=p1-index; p1=(struct poly *)malloc(len); scanf(%d%d,&p1-coef,&p1-index); p1-next=null; return(head);struct poly * add_poly(struct poly *head1,struct poly *head2) struct poly *p1,*p2,*head3,*p3; p1=head1-next; p2=head2-next; head3=(struct poly *)malloc(len); p3=head3; head3-coef=head3-index=0; head3-next=null; while(p1!=null&