數(shù)據(jù)結構課程設計報告---joseph環(huán)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：23 大小：112.00KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩22頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　數(shù)據(jù)結構課程設計報告　　班級：信息安全101班 　　學號： 02 　　姓名： 　　時間： 2011年12月25日　　～201

2、2年1月6日 　　2012年01月06日　　joseph環(huán)　　問題描述　　任務：編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限

3、值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。　　要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。　　測試數(shù)據(jù)：</p&g

4、t;　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？　　要求：　　輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n ，輸入每個人的密碼，建立單循環(huán)鏈表。　　輸出形式：建立一個輸出函數(shù)，將正確的輸

5、出序列　　二、需求分析　　利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。首先創(chuàng)建一個空鏈表，初始化鏈表，構造出一個只有頭結點的空鏈表，建立好一個約瑟夫環(huán)。1. 輸入的形式和輸入值的范圍本程序中，輸入報數(shù)上限值m和人數(shù)上限l，密碼，均限定為正整數(shù)，輸入的形式為一個以

6、“回車符”為結束標志的正整數(shù)。2. 輸出的形式從屏幕顯示出列順序。3. 程序功能提供用戶從鍵盤輸入，Joseph約瑟夫環(huán)的必要數(shù)據(jù)，并顯示出列順序。三、概要設計以單向循環(huán)鏈表實現(xiàn)該結構。1. 抽象數(shù)據(jù)類型的定義為：ADT LNode{ 數(shù)據(jù)對象：D={ai | ai∈CharSet，i= 1，2，…，n，n≥0} 數(shù)

7、據(jù)關系：R1={< ai-1 ，ai > | ai ∈D， I=2，…，n}　　四、源程序　　#include<stdio.h> 　　#include<stdlib.h> 　　typ

8、edef struct Node 　　{ 　　int key;//每個人持有的密碼 　　int num;//這個人的編號 　　struct Node *next;//指向下一個節(jié)點 　　}No

9、de,*Link; 　　void InitList(Link &L) //創(chuàng)建一個空的鏈表 　　{ 　　L=(Node *)malloc(sizeof(Node)); 　　if(!L) exit(1);

10、　　L->key=0; 　　L->num=0; 　　L->next=L; 　　} 　　void Creater(int n,Link &L) //初始化鏈表 <

11、;p>　　{ 　　Link p,q; 　　q=L; 　　for(int i=1;i<=n;i++) 　　{ <p&g

12、t;　　p=(Node *)malloc(sizeof(Node)); 　　if(!p) exit(1); 　　printf("the key_%d is:",i); 　　scanf("%d",&p->key);

13、p->num=i; 　　L->next=p; 　　L=p; 　　} 　　L->next=q->next; 　　f

14、ree(q); 　　} 　　void main() 　　{ 　　Link L,p,q; 　　int n,x; <

15、;/b>　　L=NULL; 　　InitList(L);//構造出一個只有頭結點的空鏈表 　　printf("please input the totle number of people:"); 　　sca

16、nf("%d",&n);//總共的人數(shù)n 　　printf("the start key is:"); 　　scanf("%d",&x);//初始密碼為x 　　Creater(n,L);//建立好一個約瑟夫環(huán) &l

17、t;p>　　p=L; 　　for(int i=1;i<=n;i++) 　　{ 　　for(int j=1;j<x;j++) 　　p=p->next;

18、　　q=p->next; 　　x=q->key; 　　printf("%d ",q->num); 　　p->next=q->next; 　　free(q); <

19、;/p>　　} 　　}　　五、測試數(shù)據(jù)　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4　　輸出：6 7

20、4 1 5 3 2　　一元多項式計算　　問題描述　　能夠按照指數(shù)降序排列建立多項式；能夠完成兩個多項式的相加、相減和相乘，并將結果輸出。　　設計思路</

21、p>　　這個程序的關鍵是多項式的創(chuàng)建和排列，以及相乘時系數(shù)相乘和指數(shù)相加、相加時相同指數(shù)的系數(shù)相加、相減時相同指數(shù)的系數(shù)相減。由于多項式擁有指數(shù)和系數(shù)（假設基數(shù)已定），所以可以定義一個包含指數(shù)系數(shù)的結構體，用單鏈表存儲多項式的數(shù)據(jù)，所以結構體包含next指針。數(shù)據(jù)插入時比較兩數(shù)的指數(shù)，按照降序排序，從表頭的next開始，直至找到合適的位置，然后開始鏈表中數(shù)值的插入，如果相等則直接將指數(shù)相加，如果大于就將新數(shù)據(jù)

22、插入到當前指向的前面，否則將新數(shù)據(jù)插入到最后。輸入完數(shù)據(jù)后選擇計算方式（相乘、相加、相減），多項式運算時要循環(huán)遍歷整個多項式，多項式的每一組數(shù)據(jù)都要和另一個多項式整組數(shù)據(jù)相運算（每一個運算值都存儲到新建的“多項式”鏈表中），直到兩個多項式都遍歷完結束。　　數(shù)據(jù)結構設計　　在模擬多項式對象時，為了簡化處理，只取最核心的

23、兩個數(shù)據(jù)：多項式的系數(shù)和指數(shù)。前面提到，要用單鏈表操作，所以要加上個next指針，再由該結構體定義一個結點類型和指針類型。具體數(shù)據(jù)結構定義如下：　　typedef struct node{　　int xs; /*系數(shù)*/　　int zs;/*指數(shù)*/

24、;　　struct node * next; /*next指針*/　　}Dnode,* Dnodelist;　　功能函數(shù)設計　　（1）鏈表初始化函數(shù)Creat_node()　　帶有頭結點的頭指針指

25、向空（NULL）。　?。?）多項式數(shù)據(jù)的創(chuàng)建函數(shù)Creat_Dmeth()　　當鏈表初始化成功后，開始創(chuàng)建多項式。分別循環(huán)輸入兩個多項式的系數(shù)和指數(shù)，其中要用到插入函數(shù)。　　（3）數(shù)據(jù)的插入函數(shù)Insert_node()　　當創(chuàng)建多項式時，要用到此函數(shù)，即利用插入的方式

26、將多項式的數(shù)據(jù)連接起來。再輸入一組數(shù)據(jù)后，程序自動調用此函數(shù)，插入時也進行著排序，從表頭的next開始，一一比較指數(shù)大小，直到大于或等于當前指向的數(shù)據(jù)或遍歷完所有數(shù)據(jù)時停止，然后開始鏈表中數(shù)值的插入，如果相等則直接將指數(shù)相加，如果大于就將新數(shù)據(jù)插入到當前指向的前面，否則將新數(shù)據(jù)插入到最后。　?。?）多項式的顯示函數(shù)Show()　　從多項式表頭的next開

27、始，直到指向空（NULL），將系數(shù)與指數(shù)一一顯示。　?。?）選擇運算方式的函數(shù)select()　　三種選擇：1為相乘，2為相加，3為相減；每一種選擇調用相應的運算函數(shù)。　　（6）多項式的運算函數(shù)：新建鏈表存儲計算后的多項式　　1、多項式相乘Mulresult()</

28、p>　　創(chuàng)建兩個指針分別指向兩個多項式表頭的next，使用兩個while函數(shù)嵌套循環(huán)，遍歷每一組數(shù)據(jù)，每遍歷一次都將兩組數(shù)據(jù)的系數(shù)相乘，指數(shù)相加，再利用插入函數(shù)將系數(shù)與指數(shù)存儲到新建多項式的鏈表中。　　2、多項式相加Addresult()　　創(chuàng)建兩個指針分別指向兩個多項式表頭的next，分別使用兩個while函數(shù)獨自循環(huán)，遍歷

29、各自的每一組數(shù)據(jù)，每遍歷一次都將系數(shù)與指數(shù)存儲到新建多項式的鏈表中。因為存儲時利用到插入函數(shù)，而插入函數(shù)中有相同指數(shù)的系數(shù)相加功能，所以直接將兩個多項式的數(shù)據(jù)依次插入到新的多項式中即可完成多項式相加。　　3、多項式相減Subresult()　　創(chuàng)建兩個指針分別指向兩個多項式表頭的next，以兩個指針同時不為空為條件循環(huán)遍歷，如果當前多項式1的指數(shù)小于多項

30、式2，則將當前多項式2的系數(shù)置負，指數(shù)不變，存入新建多項式中，指向多項式2的指針指向下一個；如果如果當前多項式1的指數(shù)大于多項式2，則將當前多項式1的系數(shù)指數(shù)不變，存入新建多項式中，指向多項式1的指針指向下一個；否則將多項式1的系數(shù)減去2的系數(shù)后存入新建多項式中，指數(shù)不變存入，再將兩個指針同時指向下一個。結束循環(huán)后判斷是哪一個多項式遍歷完了，將未遍歷完的多項式剩下的數(shù)據(jù)全部插入到新建多項式中。

31、　（7）主函數(shù)main()　　創(chuàng)建兩個多項式的鏈表并且初始化，分別調用相應的多項式創(chuàng)建函數(shù)，創(chuàng)建成功后選擇運算方式，再將運算結果輸出顯示。　　程序代碼　　#include<stdio.h>　　#include<std

32、lib.h>　　typedef struct node{　　int xs;　　int zs;　　struct node * next;　　}Dnod

33、e,* Dnodelist; /*定義結構體*/　　Dnodelist Creat_node(void) /*鏈表初始化*/　　{　　Dnodelist D;

34、D=(Dnodelist)malloc(sizeof(Dnode));　　if(D)　　D->next=NULL;　　return D;　　}</

35、p>　　int Insert_node(Dnodelist D,int xs,int zs) /*插入函數(shù)*/　　{　　Dnodelist p;　　Dnodelist q;　　Dnodelis

36、t r;　　p=D;　　while(p->next) 　　{　　r=p;&l

37、t;p>　　p=p->next;　　if(zs==p->zs) /*指數(shù)相等，系數(shù)直接相加，結束*/　　{　　p->xs=p->xs+xs;　　return 1;<

38、;/b>　　}　　else if(zs>p->zs) /*指數(shù)大于當前數(shù)據(jù)的，將數(shù)據(jù)插入當前數(shù) 據(jù)之前，結束*/　　{　　q=Creat_n

39、ode();　　q->xs=xs;　　q->zs=zs;　　r->next=q;　　q->next=p;　　re

40、turn 1;　　}　　}/*while(p->next)*/　　q=Creat_node(); /*要插入的數(shù)據(jù)指數(shù)最小，直接插入至鏈表最后*/　　q->xs=

41、xs;　　q->zs=zs;　　q->next=p->next;　　p->next=q;　　return 1;

42、　　free(p);　　free(q);　　free(r);　　}　　Dnodelist Creat_Dmeth(int

43、 length) /*創(chuàng)建多項式*/　　{　　int i,m,n;　　Dnodelist D;　　D=Creat_node();　　for(i=0;i<leng

44、th;i++) /*以三組數(shù)據(jù)為例*/　　{　　scanf("%d,%d",&m,&n);　　Insert_node(D,m,n); /*調用插入函數(shù)，將輸入的系數(shù)指數(shù)插入鏈表*/<

45、/p>　　}　　return D;　　}　　Dnodelist Mulresult(Dnodelist D1,Dnodelist D2) /*多項式相乘*/</p

46、>　　{　　Dnodelist D;　　Dnodelist p,q;　　int x,z;　　D=Creat_node();

47、p=D1->next;　　q=D2->next;　　while(q)　　{　　while(p)<b

48、>　　{　　x=p->xs*q->xs; /*系數(shù)相乘，指數(shù)相加*/　　z=p->zs+q->zs;　　Insert_node(D,x,z);　　p=p->next;&l

49、t;p>　　}　　p=D1->next;　　q=q->next;　　}　　return D;<

50、;b>　　}　　Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多項式相加*/　　{　　Dnodelist D;　　Dnodelist p,q;</

51、p>　　int x,z;　　D=Creat_node();　　p=D1->next;　　q=D2->next;　　while(q)&

52、lt;p>　　{　　x=q->xs;　　z=q->zs;　　Insert_node(D,x,z);　　q=q->next;</

53、p>　　}　　while(p)　　{　　x=p->xs;　　z=p-

54、>zs;　　Insert_node(D,x,z);　　p=p->next; /*直接插入數(shù)據(jù)，利用插入函數(shù)可完成該功能*/　　}　　return

55、 D;　　}　　Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多項式相減*/　　{　　Dnodelist D;</p

56、>　　Dnodelist p,q;　　int x,z;　　D=Creat_node();　　p=D1->next;　　q=D2->next;　　whil

57、e(p&&q)　　{　　if((p->zs)<(q->zs)) /*指數(shù)?。?的數(shù)據(jù)在2中不存在），直接插入*/　　{　　x=-(q->x

58、s); /*由于是式1減式2，所以系數(shù)置負*/　　z=q->zs;　　Insert_node(D,x,z);　　q=q->next;　　}</p&

59、gt;　　else if((p->zs)>(q->zs)) /*指數(shù)大（2的數(shù)據(jù)在1中不存在），直接插入*/ 　　{　　x=p->xs;　　z=p->zs;

60、　　Insert_node(D,x,z);　　p=p->next;　　}　　else /*指數(shù)相同的先將系數(shù)相減，再插入*/<

61、;p>　　{　　z=q->zs;　　x=(p->xs)-(q->xs);　　Insert_node(D,x,z);　　p=p->next;&l

62、t;p>　　q=q->next;　　}　　}/*while(p&&q)*/　　while(p)　　{<

63、;p>　　x=p->xs;　　z=p->zs;　　Insert_node(D,x,z);　　p=p->next;　　}</p&g

64、t;　　while(q)　　{　　x=-(q->zs);　　z=q->zs;　　Insert_node(D,x,z);<

65、;/p>　　q=q->next;　　} /*將未遍歷完的數(shù)據(jù)直接插入*/　　return D;　　}　　Dnodel

66、ist select(Dnodelist D1,Dnodelist D2) /*選擇函數(shù)*/　　{　　Dnodelist D;　　int s;　　printf("請選擇:\n1:相乘

67、\n2:相加\n3:相減\n");　　scanf("%d",&s);　　switch(s)　　{　　case 1: D=Mulresult(D1,D2);

68、 /*調用相乘函數(shù)*/　　printf("相乘結果(系數(shù),指數(shù)):\n");　　break;　　case 2: D=Addresult(D1,D2); /*調用相加函數(shù)*/<p&

69、gt;　　printf("相加結果(系數(shù),指數(shù)):\n");　　break;　　case 3: D=Subresult(D1,D2); /*調用相減函數(shù)*/　　printf("相減結果(系數(shù),指數(shù)):\n")

70、;　　break;　　default:　　printf("無此選項\n");　　break;&l

71、t;b>　　}　　return D;　　}　　void Show(Dnodelist D) /*顯示（輸出）函數(shù)*/

72、　　{　　Dnodelist r;　　r=D->next;　　while(r)　　{　　printf("(%d,%d)

73、+",r->xs,r->zs);　　r=r->next;　　}　　printf("\n");　　}　　vo

74、id main()　　{　　Dnodelist D1,D2,D;　　int length;　　D1=Creat_node();　　D2=Creat_node(); /*D1為多項式1，D

75、2為多項式2，初始化*/　　printf("輸入多項式1的組數(shù)：\n");　　scanf("%d",&length);　　printf("輸入多項式1系數(shù),指數(shù)：(%d組)\n",length);　　D1

76、=Creat_Dmeth(length); /*創(chuàng)建多項式1*/　　printf("輸入多項式2的組數(shù)：\n");　　scanf("%d",&length);　　printf("輸入多項式2系數(shù),指數(shù)：(%d組)\n",leng

77、th);　　D2=Creat_Dmeth(length); /*創(chuàng)建多項式2*/ 　　D=select(D1,D2); /*選擇運算方式*/　　Show(D); /*輸出顯示*/&l

78、t;p>　　int getch();　　}　　運行與測試　　程序運行時，先提示第一個多項式的組數(shù)，確定組數(shù)后才可輸入相應的數(shù)據(jù)，之后是多項式2；輸入完數(shù)據(jù)后，程序提示選擇運算方式。選擇錯誤則提示“無此選項”，運行結束，選擇正確的選項

79、將進行相應的運算并輸出顯示。　　錯誤選擇：　　相乘：　　相加：　　相減：<

80、;b>　　設計總結　　我的這次數(shù)據(jù)結構課程設計的題目是:《約瑟夫環(huán)》，《一元多項式》，通過對題目的設計，我加深了了對數(shù)據(jù)結構及儲存結構的理解，進一步地理解和掌握了課本中所學的各種數(shù)據(jù)結構，尤其是對單鏈表　　、單循環(huán)鏈表上基本運算的實現(xiàn)，學會了如何把學到的東西用于解決實際問題，鍛煉了自己的動手能力。<

81、p>　　通過這次數(shù)據(jù)結構課程設計，我感受最深的就是對于單鏈表，單循環(huán)鏈表，結構體等的使用，可以說對單鏈表，單循環(huán)鏈表有了比以前更進一步地認識，以前只是一知半解，如果只給個題目自己根本不知道怎么把程序完整的編出來，所以這次課程設計最大的收獲就在于對循環(huán)表有一定的理解，包括其中的一系列操作，如建立一個單鏈表，循環(huán)列表，建一個結構體，刪除鏈表中的結點，增加結點等。　　在調試程序的時候，因為機房里

82、的變成版本是舊的，我自己電腦上的版本是最新的，我電腦上的版本要求比較高，之前自己以為是代碼錯了，后來才知道算法沒有什么錯誤。雖然約瑟夫環(huán)問題不是很難，但調試的時候還是會出現(xiàn)很多問題，因此我們不能認為容易就可以不認真對待。在以后的學習中要能不斷的發(fā)現(xiàn)問題，提出問題，解決問題，從不足之處出發(fā)，在不斷學習中提高自己。　　兩周的課程設計很短暫，加上期末考試任務比較繁重，但期間的內容很充實的，在其中我學習

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結構課程設計報告---joseph環(huán)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結構課程設計報告---joseph環(huán)

文檔簡介

溫馨提示

最新文檔

評論

免費下載