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

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

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

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

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

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

6、測試結(jié)果操作及輸出流程詳見如下截圖七、附錄源程序如下：#include#include/引用的函數(shù)庫typedefstructQNodeintdata;structQNode*next;QNode,*QueuePtr;typedefstructQueuePtrfront;/隊頭指針QueuePtrrear;/隊尾指針LinkQueue;intInitQueue(LinkQueue&Q)/構(gòu)造空隊列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的隊尾元素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)/銷毀Q的隊頭元素并用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的對頭元素if(Q.front!=Q.rear)e=Q.front-next-data;return1;elsereturn0;voidmain()intn,j,i,t,x,level;/定義變量printf(請輸入所需的楊輝三角級數(shù):n);scanf(%d,&level);/獲取楊輝三角級數(shù)LinkQueueQ;InitQueue(Q);EnQueue(Q,1);/插入1為隊列隊尾元素printf(n所求楊輝三角如下:n);for(n=1;n=level+1;n+)EnQueue(Q,1);/插入1為隊列隊尾元

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

10、該程序抽象數(shù)據(jù)類型的定義ADTListNode數(shù)據(jù)對象：D=ai|aiCharSet,i=1,2,，n,n0數(shù)據(jù)關(guān)系：R仁|aiD,1=2，n基本操作：InitList(&L)操作結(jié)果：構(gòu)造一個最大長度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ù)元素個數(shù)。GetElem(L,pos,&e)初始條件：線性表L已經(jīng)存在，KiListLength(L)操作結(jié)果：用e

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

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

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

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

15、閱桌的人敵為?*h第幾人開始f數(shù)到幾的人岀列？哲歹!|的瞬序如下：4731625Prtstanyktjitocgntlnu引用函數(shù)庫定義鏈表七、附錄源程序如下：#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;/計算出列者序號q=p-next;p-next=q-next;printf(%d,q-num);free(q);p-next=NULL;voidmain()N