C語言課程設計報告約瑟夫環(huán)胡存夫.doc

《C語言課程設計報告約瑟夫環(huán)胡存夫.doc》由會員分享，可在線閱讀，更多相關《C語言課程設計報告約瑟夫環(huán)胡存夫.doc（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 沈陽航空航天大學 課課 程程 設設 計計 報報 告告 課程設計名稱：課程設計名稱：C 語言課程設計語言課程設計 課程設計題目：約瑟夫環(huán)課程設計題目：約瑟夫環(huán) 院（系）：計算機學院 專 業(yè)：計算機科學與技術 班 級：3410301 學 號：2013040103023 姓 名： 胡存夫 指導教師： 丁一軍 沈陽航空航天大學課程設計報告 I 目目 錄錄 1 課程設計介紹課程設計介紹.1 1.1 課程設計內(nèi)容及要求.1 1.2 系統(tǒng)需求.1 2 課程設計原理課程設計原理.3 2.1 課設題目粗略分析.3 2.2.1 功能模塊圖5 2.2.2 流程圖分析5 3 調(diào)試與分析調(diào)試與分析.10 3.1 調(diào)試

2、過程.10 參考文獻參考文獻.16 附附 錄（關鍵部分程序清單）錄（關鍵部分程序清單）.16 沈陽航空航天大學課程設計報告 1 1 課程設計介紹 1.1 課程設計內(nèi)容及要求課程設計內(nèi)容及要求 設計程序，實現(xiàn)算術表達式求值，系統(tǒng)主要功能如下： 1.問題描述 約瑟夫環(huán)問題的一種描述是：編號為 1,2,n 的 n 個人按順時針方向圍坐 一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限 值 m，從第一個人開始按順時針方向自 1 開始順序報數(shù)，報到 m 時停止報數(shù)。 報 m 的人出列，將他的密碼作為新的 m 值，從他在順時針方向上的下一個人 開始重新從 1 報數(shù)，如此下去，直至所有人全

3、部出列為止。試設計一個程序 求出出列順序。 2.分析約瑟夫問題： n 個人圍成圈，每人各持一個密碼，任選一個正整數(shù)作為報數(shù)上限值 m， 從第一個人開始，數(shù)到第 m 個人，刪除并以出列者密碼作為新的 m 值，從下 一個人開始進行第二輪操作，直到所有人都出列。 設計 1.2 系統(tǒng)需求系統(tǒng)需求 1.需求 此程序最終目的是要求出所有人的出列順序 沈陽航空航天大學課程設計報告 2 2.功能描述 1 2 3 4 5 6 7 8 9 0 這是第一個人， 他的密碼是 “1” ，個他輸 一個 m 值，如 果 m=3,則從他 開始向下走 3 個 這就是第二步的 位置，這時他的 密碼作為新的 m 值，即 m=4,

4、同時得到的第一 個密碼為 4；4 號出去向下走 4，到 9 這兒； （這這一步完了 剩余的為： 1,2,3,5,6， ，7,8,9, 0， ） 這就是第三步的 位置，這時他的 密碼作為新的 m 值，即 m=9，同 時得到的第二個 密碼為 9；9 號出 去向下走 9，到 0 這兒；繼續(xù)走就 行了（這兒剩余 的就是： 1，2，3，5，6,7, 8,0） 圖 1.1 約瑟夫環(huán)功能示圖 沈陽航空航天大學課程設計報告 3 2 課程設計原理 2.1 課設題目粗略分析課設題目粗略分析 根據(jù)課設題目要求，擬將整體程序分為四大模塊。此四個模塊相互獨立，沒有嵌 套調(diào)用的情況，以下是五個模塊： （1）創(chuàng)建鏈表模塊

5、void createList(LNode *ppHead,int n) （2）出隊處理模塊 void jose(LNode *ppHead,int m_pwd) （3）約瑟夫環(huán)說明輸出模塊 void instruction() （4）菜單模塊 void menu() （5）主函數(shù)模塊 int main（） 沈陽航空航天大學課程設計報告 4 原理圖介紹原理圖介紹 3271484 約瑟夫環(huán)原理演示圖 1 234567 第二部：第一次停下 的位置，此時 6 號出 列，并將他的值作為 新的 m 值，即：新 的 m=8；從 7 好開 始繼續(xù)向下走 8 次， 到 1 號的位置 最后排序后的密 碼序列：

6、（本圖只演示前 兩步） 8 第三步： 第二次，1 號出列 第四步：第三 次，4 號出列 3 第一步：給第 一個人賦初始 密碼為：20 則從它開始向 下走 20 次， 到 6 號位置 24 174 6147235 圖 2.1 約瑟夫環(huán)原理演 示圖 沈陽航空航天大學課程設計報告 5 2.2.1 功能模塊圖功能模塊圖 Case 2:建立的約瑟夫環(huán),并輸 出已建立的約瑟夫環(huán)： createList(LNode *ppHead,int n) 輸出該約瑟夫環(huán)的每個人的 出列順序: jose(LNode *ppHead,int m_pwd) 圖 2.2 約瑟夫環(huán)函數(shù)調(diào)用關 系圖 菜單函數(shù)； void men

7、u() 主函數(shù)調(diào)用函 數(shù)； main() Case 1：一個簡單的輸出函 數(shù)，用于說明約瑟夫環(huán)； void instruction() Case 0:default : 輸入 0，退 出 exit(0)； 2.2.2 流程圖分析流程圖分析 沈陽航空航天大學課程設計報告 6 1. 否 是 createList（）; 從主函數(shù)中獲取 玩家信息 n 如果 n0 創(chuàng)建循環(huán)單鏈表， 儲存各個玩家密 碼 退出 創(chuàng)建鏈表完成返 回主函數(shù) main() 創(chuàng)建儲存玩家密 碼的循環(huán)單鏈表 的方法 Main()函 數(shù) 圖 2.3 創(chuàng)建鏈表函數(shù)的數(shù)據(jù)流 程圖 2. 沈陽航空航天大學課程設計報告 7 Main()函 數(shù)

8、 從循環(huán)鏈表中按初 始密碼依次掃描， 找出對應的玩家序 列 輸出其持有的密碼 i=ppHead-pwd; j=ppHead-num; 移動浮標指針 m_pwd=ppHead- pwd; 輸出密碼后，刪除相應的 結(jié)點，并釋放所占的儲存 空間 free(ppHead); ppHead=p-next; 執(zhí)行完后返 回主函數(shù) jose()；出隊函 數(shù)出隊處理 的方法 圖 2.4 出隊函數(shù)的數(shù)據(jù)流 程圖 3. void instruction() printf(“* n“); printf(“約瑟夫環(huán):n“); printf(“ 編號為 1,2,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個

9、 密n“); printf(“碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值 m,從第一個人開 沈陽航空航天大學課程設計報告 8 始n“); printf(“按順時針方向自 1 開始順序報數(shù),報到時停止.報 m 的人出列，將他的 密碼n“); printf(“m 作為新的 m 值,從他在順時針方向上的下一人開始重新從 1 報數(shù),如 此下去,n“); printf(“直到所有人全部出列為止.編程打印出列順序.n“); printf(“*n“); return 0; 4 菜單模塊 void menu() printf(“*約瑟夫環(huán) *n“); printf(“ n“); printf(“ 1約

10、瑟夫環(huán)問題的闡述 n“); printf(“ 2按要求求解約瑟夫環(huán) n“); printf(“ 0退出 n“); printf(“* 歡迎使用！ *n“); 沈陽航空航天大學課程設計報告 9 5. 沈陽航空航天大學課程設計報告 10 Main()開始 Menu()功能菜單 功能 1：約瑟 夫環(huán)說明 功能 2：按要 求求解約瑟 夫環(huán) 功能 3：退出 系統(tǒng) 輸入總?cè)藬?shù) n 輸入開始上線數(shù)： m 輸入每個玩家的密碼 調(diào)用： createList( jose(ppHead,m);函數(shù)求解所 需的密碼序列 選擇要執(zhí) 行的操作 程序運行完， 自動返回到功 能菜單 圖 2.5 主函數(shù)數(shù)據(jù)流程 圖 3 調(diào)試與

11、分析 3.1 調(diào)試過程調(diào)試過程 在調(diào)試程序是主要遇到一下幾類問題： 這是一個使用循環(huán)鏈表的經(jīng)典問題。本程序開始運行界面如下： 沈陽航空航天大學課程設計報告 11 選擇 1 進入約瑟夫環(huán)問題闡述。 圖 3.1 約瑟夫環(huán)開始運行 界面 圖 3.2 約瑟夫環(huán)問題闡述 沈陽航空航天大學課程設計報告 12 選擇 2，輸入下列數(shù)據(jù)測試： 請輸入總?cè)藬?shù) n：7 請輸入開始上限數(shù) m：20； 請依次輸入每個人的密碼：3 1 7 2 4 8 4 出隊順序：6 1 4 7 2 3 5 圖 3.3 約瑟夫環(huán)測試 1 沈陽航空航天大學課程設計報告 13 繼續(xù)選擇 2，輸入下列數(shù)據(jù)測試： 請輸入總?cè)藬?shù) n：5 請輸入開

12、始上限數(shù) m：30 請依次輸入每個人的密碼：3 4 5 6 7 出隊順序：5 3 1 2 4 圖 3.4 約瑟夫環(huán)測試 2 沈陽航空航天大學課程設計報告 14 繼續(xù)選擇 2，輸入下列數(shù)據(jù)測試： 請輸入總?cè)藬?shù) n：8 請輸入開始上限數(shù) m：14 請依次輸入每個人的密碼：3 4 5 6 7 8 9 10 出隊順序：6 7 2 8 3 5 1 4 沈陽航空航天大學課程設計報告 15 測試完成，選擇 0 退出。. 圖 3.5 約瑟夫環(huán)測試 3 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 16 參考文獻 1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)M.北京：清華大學出版社，2007. 2 張長海，陳

13、娟.C 程序設計M.北京：高等教育出版社，2004. 3 譚浩強.C 程序設計M.北京：清華大學出版社，2005 4嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（C 語言版） .清華大學出版社. 5DATA STRUCTURE WITH C+. William Ford,William Topp .清華大學出 版社（影印版）. 附 錄（關鍵部分程序清單） 程序代碼 #include /輸入輸出函數(shù)頭文件 #include /字符串轉(zhuǎn)短整形函數(shù)的頭文件 10140219 / typedef struct LNode/定義單循環(huán)鏈表中節(jié)點的結(jié)構(gòu) int num;/編號 int pwd;/password stru

14、ct LNode *next;/指向下一結(jié)點的指針 LNode; /*構(gòu)造結(jié)點*/ LNode *createNode(int m_num,int m_pwd) LNode *p; 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 17 p=(LNode *)malloc(sizeof(LNode);/生成一個結(jié)點 p-num=m_num;/把實參賦給相應的數(shù)據(jù)域 p-pwd=m_pwd; p-next=NULL;/指針域為空 return p; /*創(chuàng)建循環(huán)鏈表*/ void createList(LNode *ppHead,int n) /*創(chuàng)建單向循環(huán)鏈表 ppHead，人

15、數(shù)個數(shù)為 n，并輸入每個人的密碼值，若 建立失敗則生成頭結(jié)點，讓 cur 指向他，若建立成功則插入結(jié)點 P，cur 指 向的數(shù)據(jù)元素為 p,后續(xù)為“空“的節(jié)點，再把 P 插入循環(huán)鏈表 ppHead 中*/ int i,m_pwd; LNode *p,*cur;/cur:浮標指針 for(i=1;inext=*ppHead;/cur 的指針域指向自身 else/如果不為空，則插入結(jié)點 p-next = cur-next; cur-next = p; 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 18 cur= p;/cur 指向新插入結(jié)點 printf(“完成創(chuàng)建！n“); /

16、提示鏈表創(chuàng)建完成 /*出隊處理*/ void jose(LNode *ppHead,int m_pwd) /*p 指向要刪除節(jié)點的前一個節(jié)點，ppHead 指向要刪除的節(jié)點，使 p=ppHead，ppHead 再指向要刪除節(jié)點的下一個節(jié)點，使 p 和 ppHead 鏈接，輸出 p 指向節(jié)點的編號和密碼值，釋 放 ppHead，如此循環(huán)，直至把所有節(jié)點都打印和刪除為止！*/ int i,j; LNode *p,*p_del;/定義指針變量 for(i=1;p!=ppHead;i+) for(j=1;jnext;/ppHead 指向下一個元素 p-next = ppHead-next;/p 結(jié)點與

17、頭結(jié)點鏈接 i=ppHead-pwd;/i 賦值為 ppHead-pwd j=ppHead-num;/j 賦值為 ppHead-num，j 為要刪除的密碼值 printf(“第%d 個人出列，密碼：%dn“,j,i); m_pwd=ppHead-pwd;/m_pwd 賦值為 ppHead-pwd free(ppHead);/釋放頭結(jié)點 ppHead=p-next;/ppHead 重新賦值給 p-next,即釋放前的 ppHead-pwd 指 針/刪除報數(shù)結(jié)點 i=ppHead-pwd;/i 賦值為 ppHead-pwd 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 19 j=

18、ppHead-num;/j 賦值為 ppHead-num printf(“最后一個出列是%d 號，密碼是:%dn“,j,i); free(ppHead);/釋放頭結(jié)點 void instruction() printf(“* n“); printf(“約瑟夫環(huán):n“); printf(“ 編號為 1,2,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個 密n“); printf(“碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值 m,從第一個人開 始n“); printf(“按順時針方向自 1 開始順序報數(shù),報到時停止.報 m 的人出列，將他的 密碼n“); printf(“m 作

19、為新的 m 值,從他在順時針方向上的下一人開始重新從 1 報數(shù),如 此下去,n“); printf(“直到所有人全部出列為止.編程打印出列順序.n“); printf(“*n“); return 0; void menu() printf(“*約瑟夫環(huán) *n“); printf(“ n“); printf(“ 1約瑟夫環(huán)問題的闡述 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 20 n“); printf(“ 2按要求求解約瑟夫環(huán) n“); printf(“ 0退出 n“); printf(“* 歡迎使用！ *n“); /*主函數(shù)模塊*/ int main() int n,m

20、,x; LNode *ppHead=NULL; menu(); printf(“n 請選擇要執(zhí)行的操作：“); scanf(“%d“, system(“cls“); switch(x) case 1: printf(“* n“); printf(“約瑟夫環(huán):n“); printf(“ 編號為 1,2,3,4,n 的 n 個人按順時針方向圍坐一圈,每人持有一個密n“); printf(“碼(正整數(shù)).一開始任選一個正整數(shù)作為報數(shù)的上限值 m,從第一個人開始n“); printf(“按順時針方向自 1 開始順序報數(shù),報到 m 時停止.報 m 的人出列，將他的密 沈陽航空航天大學課程設計報告 T1T

21、JmEdtgTYWOA0I 21 碼n“); printf(“m 作為新的 m 值,從他在順時針方向上的下一人開始重新從 1 報數(shù),如此下 去,n“); printf(“直到所有人全部出列為止.編程打印出列順序.n“); printf(“* n“); main(); break; case 2: printf(“n 請輸入總?cè)藬?shù) n：“); scanf(“%d“, printf(“請輸入開始上限數(shù) m：“); scanf(“%d“, createList( printf(“n“); printf(“出隊順序：n“); jose(ppHead,m); printf(“n 約瑟夫環(huán)游戲結(jié)束!n“)

22、; main(); break; case 0: exit(0); default: system(“cls“); printf(“n 您選擇的操作有誤，請重新選擇.nnn“); main(); 沈陽航空航天大學課程設計報告 T1TJmEdtgTYWOA0I 22 return 0; 沈陽航空航天大學課程設計報告 23 課程設計總結(jié)： 本次課程設計涉及到的范圍很廣，讓本人能夠比較系統(tǒng)的對 C 語言和數(shù)據(jù)結(jié)構(gòu) 進行一次整理和復習。同時有了很多的體會和經(jīng)驗。 鞏固了以前學過的 C 語言的知識，在這次課程設計中我體會到 C 語言超強的邏 輯性，能夠熟練使用 VC+的編譯環(huán)境，也對這兩門課程有了新的認

23、識，他們 既有聯(lián)系，又相互區(qū)別，在編寫程序過程中要靈活應用 對數(shù)據(jù)結(jié)構(gòu)的理解有待加強，算法的知識面也有待于提高。不同的人會選擇不 同的算法，所以即使同樣的程序，不同的人必然會設計出不同的方案，所以以 后的學習生活中，一定要廣泛涉獵，掌握更多更好的解決問題的方法。 此次設計讓我意識到程序設計是腦力勞動和體力勞動相結(jié)合的，沒有平時基礎 的訓練是不會寫出高效的算法。 此次課程設計時間雖短，但卻課設的過程是短暫的，但我所收獲的是永恒的。 它讓我嘗到了學習的快樂，成功的喜悅，更讓我懂得了不少做人的道理。要完 成一項任務或把東西學好就必須有足夠的信心，持久的耐心，有面對困難無所 畏懼的精神，這對我日后的學習和生活產(chǎn)生了深遠一個影響。 指導教師評語： 指導教師(簽字)： 年 月 日 課程設計成績