數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)(楊輝三角約瑟夫環(huán))

1、實(shí)驗(yàn)一楊輝三角形(Pascalstriangle)需求分析輸入的形式和輸入值的范圍本程序中，需輸入的楊輝三角級(jí)數(shù)level為正整數(shù)，由鍵盤(pán)輸入，以回車(chē)結(jié)束輸出的形式通過(guò)屏幕輸出楊輝三角程序所能達(dá)到的功能用戶從鍵盤(pán)輸入需要的楊輝三角級(jí)數(shù)，從屏幕輸出楊輝三角4.測(cè)試數(shù)據(jù)輸入：5輸出：1112113311464115101051概要設(shè)計(jì)以鏈隊(duì)列結(jié)構(gòu)實(shí)現(xiàn)該實(shí)驗(yàn)抽象數(shù)據(jù)類(lèi)型定義基本操作：ADTQueue數(shù)據(jù)對(duì)象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關(guān)系：R1=vai-1,ai|ai-1,aiD,i=2；,n約定其中ai端為隊(duì)列頭，an端為隊(duì)列尾InitQueue(&Q)操作結(jié)果：構(gòu)造一

2、個(gè)空隊(duì)列QDestroyQueue(&Q)初始條件：隊(duì)列Q已存在操作結(jié)果：隊(duì)列Q被銷(xiāo)毀，不再存在ClearQueue(&Q)初始條件：隊(duì)列Q已存在操作結(jié)果：將Q清為空隊(duì)列QueueEmpty(Q)初始條件：隊(duì)列Q已存在操作結(jié)果：若Q為空隊(duì)列，則返回TRUE否則FALSEQueueLength(Q)初始條件：隊(duì)列Q已存在操作結(jié)果：返回Q的元素個(gè)數(shù)，即隊(duì)列長(zhǎng)度GetHead(Q,&e)初始條件：Q為非空隊(duì)列操作結(jié)果：用e返回Q的隊(duì)頭元素EnQueue(&Q,e)初始條件：隊(duì)列Q已存在操作結(jié)果：插入元素e為Q的新隊(duì)尾元素DeQueue(&Q,&e)初始條件：Q為非空隊(duì)列操作結(jié)果：刪除Q的隊(duì)頭元素，并

3、用e返回其值QueueTraverse(Q,visit()初始條件：Q已存在且非空操作結(jié)果：從隊(duì)頭到隊(duì)尾，依次對(duì)Q的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗。ADTQueue主程序流程voidmain()初始化；輸入數(shù)據(jù)；執(zhí)行功能；顯示結(jié)果；各程序模塊間調(diào)用關(guān)系主程序各功能模塊三、詳細(xì)設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型定義定義數(shù)據(jù)類(lèi)型QNode整形數(shù)據(jù)data;指針變量*next;QNode,*QueuePtr;typedefstruct設(shè)定隊(duì)頭指針設(shè)定隊(duì)尾指針LinkQueue;各功能模塊算法(1)/構(gòu)造空隊(duì)列QintInitQueue獲取數(shù)據(jù)結(jié)構(gòu)類(lèi)型QNode；設(shè)定頭結(jié)點(diǎn)，頭尾

4、指針指向頭結(jié)點(diǎn)；(2)/插入e為Q的隊(duì)尾元素intEnQueue分配動(dòng)態(tài)內(nèi)存空間；確認(rèn)分配成功；隊(duì)尾元素賦值；定義隊(duì)尾指針；/銷(xiāo)毀Q的隊(duì)頭元素并用e返回其值intDeQueue若頭尾元素相等返回ERRO；R隊(duì)頭元素賦p；P值賦e；銷(xiāo)毀隊(duì)頭元素；用e返回Q的隊(duì)頭元素intGetHead若頭尾元素不相等隊(duì)頭元素賦e返回；否則不返回；主函數(shù)voidmain()定義整形變量n,j,i,t,x,level;通過(guò)鍵盤(pán)輸入楊輝三角級(jí)數(shù)level初始化隊(duì)列插入1為隊(duì)列隊(duì)尾元素/輸出楊輝三角令n=1；當(dāng)n=level+1時(shí)循環(huán)，每輪循環(huán)結(jié)束n+1插入1為隊(duì)列隊(duì)尾元素令j=1；當(dāng)j=level-n+1時(shí)循環(huán)，每輪

5、循環(huán)結(jié)束j+1輸出空格以調(diào)整三角結(jié)構(gòu)；令i=1；當(dāng)i1/輸出行尾的1，完成一行的輸出用x獲取并銷(xiāo)毀Q的隊(duì)頭元素；輸出x；將1插入隊(duì)尾；輸出換行以調(diào)整結(jié)構(gòu)；函數(shù)調(diào)用關(guān)系圖Main函數(shù)調(diào)用InitQueue函數(shù)調(diào)用EnQueue函數(shù)調(diào)用DeQueue函數(shù)調(diào)用GetHead函數(shù)結(jié)束四、調(diào)試分析程序的編寫(xiě)及調(diào)試基本正常，開(kāi)始時(shí)由于細(xì)節(jié)問(wèn)題導(dǎo)致楊輝三角結(jié)構(gòu)上出現(xiàn)些許問(wèn)題：主函數(shù)輸出的楊輝三角有頂角（即首行為1），后調(diào)整循環(huán)判定條件并增加if語(yǔ)句消除首行使三角輸出正常楊輝三角結(jié)構(gòu)混亂，不整齊，后通過(guò)設(shè)定輸出字符數(shù)調(diào)整正常五、用戶使用說(shuō)明根據(jù)提示輸入所需楊輝三角級(jí)數(shù)即可示例：請(qǐng)輸入所需的楊輝三角級(jí)數(shù)：7六、

6、測(cè)試結(jié)果操作及輸出流程詳見(jiàn)如下截圖七、附錄源程序如下：#include#include/引用的函數(shù)庫(kù)typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;/隊(duì)頭指針QueuePtrrear;/隊(duì)尾指針LinkQueue;intInitQueue(LinkQueue&Q)/構(gòu)造空隊(duì)列QQ.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(-2);Q.front-next=NULL;return1;intEnQ

7、ueue(LinkQueue&Q,inte)/插入e為Q的隊(duì)尾元素QueuePtrP=(QueuePtr)malloc(sizeof(QNode);if(!P)exit(-2);P-data=e;P-next=NULL;Q.rear-next=P;Q.rear=P;return1;intDeQueue(LinkQueue&Q,int&e)/銷(xiāo)毀Q的隊(duì)頭元素并用e返回其值if(Q.front=Q.rear)return0;QueuePtrP=Q.front-next;e=P-data;Q.front-next=P-next;if(Q.rear=P)Q.rear=Q.front;free(P);r

8、eturn1;intGetHead(LinkQueueQ,int&e)/用e返回Q的對(duì)頭元素if(Q.front!=Q.rear)e=Q.front-next-data;return1;elsereturn0;voidmain()intn,j,i,t,x,level;/定義變量printf(請(qǐng)輸入所需的楊輝三角級(jí)數(shù):n);scanf(%d,&level);/獲取楊輝三角級(jí)數(shù)LinkQueueQ;InitQueue(Q);EnQueue(Q,1);/插入1為隊(duì)列隊(duì)尾元素printf(n所求楊輝三角如下:n);for(n=1;n=level+1;n+)EnQueue(Q,1);/插入1為隊(duì)列隊(duì)尾元

9、素for(j=1;j=level-n+1;j+)printf();for(i=1;i1)/判斷語(yǔ)句確保首行為空，即去除楊輝三角頂角/輸出行尾的1，完成一行的輸出DeQueue(Q,x);printf(%3d,x);EnQueue(Q,1);printf(n);實(shí)驗(yàn)二約瑟夫環(huán)(JosephusRing)需求分析輸入的形式和輸入值的范圍本程序中，需輸入的系數(shù)n,s,m都是正整數(shù)，由鍵盤(pán)按提示依次輸入，以回車(chē)結(jié)束輸出的形式從屏幕輸出出列順序程序所能達(dá)到的功能用戶由鍵盤(pán)輸入約瑟夫環(huán)的必要數(shù)據(jù)(人數(shù)，起始序號(hào)，出列數(shù))，由屏幕輸出出列順序測(cè)試數(shù)據(jù)輸入：723輸出：4731625概要設(shè)計(jì)以單向循環(huán)鏈表實(shí)現(xiàn)

10、該程序抽象數(shù)據(jù)類(lèi)型的定義ADTListNode數(shù)據(jù)對(duì)象：D=ai|aiCharSet,i=1,2,，n,n0數(shù)據(jù)關(guān)系：R仁|aiD,1=2，n基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個(gè)最大長(zhǎng)度ms內(nèi)容為空的有序表L。ClearList(&L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：將L重置為空表。EmptyList(L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：若L為空表返回TRUE否則返回FALSEListLength(L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù)。GetElem(L,pos,&e)初始條件：線性表L已經(jīng)存在，KiListLength(L)操作結(jié)果：用e

11、返回L中第i個(gè)數(shù)據(jù)元素的值。LocateElem(L,e)初始條件：線性表L已經(jīng)存在。操作結(jié)果：返回L中第1個(gè)與e相同的元素的位序。若不存在返回0。ListInsert(L,i,e)初始條件：線性表L已經(jīng)存在。操作結(jié)果：在L中的第i個(gè)元素的位置之前插入新元素e,L的長(zhǎng)度加1。ListDelete(L,pos,e)初始條件：線性表L已經(jīng)存在，KiListLength(L)操作結(jié)果：刪除L的第i個(gè)數(shù)據(jù)元素，并用e返回其值,L的長(zhǎng)度減1。ListTraverse(L)初始條件：線性表L已經(jīng)存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素進(jìn)行訪問(wèn)。ADTCirLinkedList主程序流程voidmain()初

12、始化；輸入數(shù)據(jù)；執(zhí)行功能；顯示結(jié)果；程序模塊間調(diào)用關(guān)系主程序各功能模塊三、詳細(xì)設(shè)計(jì)抽象數(shù)據(jù)類(lèi)型定義定義數(shù)據(jù)類(lèi)型LNode整形變量num；指針變量*next；定義LNode類(lèi)型NODE各程序模塊算法NODE*createlinklist(intn)/初始化循環(huán)鏈表,并返回頭指針定義指針*head,*p,*q；整形i=1；定義頭指針；賦p值i;令i=2；當(dāng)ip-next；q-p=q；賦p值i;表尾指針指向表頭；返回頭指針；joseph函數(shù)(NODE*p,intn,intm)/約瑟夫函數(shù)，用于輸出約瑟夫環(huán)整形i,j；NODE*q；令i=1；當(dāng)i=n時(shí)循環(huán)，每輪循環(huán)末i+1令j=1；當(dāng)jnext-p；

13、p-next-q；q-next-p-next；輸出q值；釋放q；主函數(shù)算法main()NODE*head;整形n,s,m;整形i;由鍵盤(pán)獲取n；由鍵盤(pán)獲取s；由鍵盤(pán)獲取m；獲取頭指針head；若s=1令i=1；當(dāng)inext-head;else令i=1；當(dāng)inext-head;調(diào)用joseph函數(shù)，輸出序列；函數(shù)調(diào)用關(guān)系圖main函數(shù)調(diào)用createlinklist函數(shù)調(diào)用joseph函數(shù)結(jié)束四、調(diào)試分析程序的編寫(xiě)和調(diào)試基本正常，開(kāi)始編寫(xiě)程序時(shí)忘記考慮s=1時(shí)的情況，導(dǎo)致程序出現(xiàn)bug，經(jīng)過(guò)單步跟蹤調(diào)試后發(fā)現(xiàn)程序的錯(cuò)誤，采用if語(yǔ)句對(duì)s=1的情況單獨(dú)處理將問(wèn)題解決。本實(shí)驗(yàn)采用數(shù)據(jù)抽象的與模塊化程

14、序設(shè)計(jì)方法。這對(duì)于提高我們編寫(xiě)算法的能力是一次很好的鍛煉機(jī)會(huì)。五、用戶使用說(shuō)明根據(jù)提示輸入人數(shù)n起始點(diǎn)s，間隔m示例：圍繞圓桌的人數(shù)為？7從第幾人開(kāi)始？2數(shù)到幾的人出列？3六、測(cè)試結(jié)果FMMicfi&fr&ftVisual叭訓(xùn)匚VisualStudFoVCormcflXMSDevSeXBirtXDebugFfadfsd.l-lJL気繞圓桌的人數(shù)為?7.F:MiciroEO-ftVisualStudi口、Mie口gftVku曲StudijoComnnjcnMSDev9El!BinDebugffadf5d.1nl回國(guó)繞園桌的入鈾加h第幾幵姑r怪繞凰桌的人數(shù)為？乩第幾人開(kāi)嫡？豪到幾的人出列？3-跟繞

15、閱桌的人敵為?*h第幾人開(kāi)始f數(shù)到幾的人岀列？哲歹!|的瞬序如下：4731625Prtstanyktjitocgntlnu引用函數(shù)庫(kù)定義鏈表七、附錄源程序如下：#include#include/structLNodeintnum;structLNode*next;；/typedefstructLNodeNODE;NODE*createlinklist(intn)/初始化循環(huán)鏈表，并返回頭指針NODE*head,*p,*q;inti=1;head=p=(structLNode*)malloc(sizeof(structLNode);p-num=i;for(i=2;inext=q;p=q;p-num=i;p-next=head;/使鏈表尾指向鏈表頭,形成循環(huán)鏈表returnhead;voidjoseph(NODE*p,intn,intm)/約瑟夫函數(shù)，用于輸出約瑟夫環(huán)inti,j;NODE*q;for(i=1;i=n;i+)for(j=1;jnext;/計(jì)算出列者序號(hào)q=p-next;p-next=q-next;printf(%d,q-num);free(q);p-next=NULL;voidmain()N