約瑟夫Josephu環(huán)C課程設(shè)計數(shù)據(jù)結(jié)構(gòu)

1、目錄1 前言11.1背景和意義11.2設(shè)計的原理、方法和主要內(nèi)容12 正文12.1設(shè)計的目的和意義12.2目標與總體方案22.3設(shè)計方法和內(nèi)容2鏈表的實現(xiàn)2設(shè)計程序32.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)8設(shè)計創(chuàng)新8關(guān)鍵技術(shù)82.5結(jié)論83 致謝9參考文獻9附錄A 源程序的清單9 前言1.1背景和意義數(shù)據(jù)是計算機化的信息,它是計算機可以直接處理的最基本和最重要的對象。無論是進行科學(xué)計算或數(shù)據(jù)處理、過程控制以及對文件的存儲和檢索及數(shù)據(jù)庫技術(shù)應(yīng)用等,都是對數(shù)據(jù)進行加工處理的過程。因此,要設(shè)計出一個結(jié)構(gòu)好效率高的程序,必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的存儲表示,并利用這些特性結(jié)合相關(guān)編程技術(shù)，運用合適

2、、熟練的方法，才能設(shè)計出符合要求、可操作性強、有利用價值的應(yīng)用程序。1.2設(shè)計的原理、方法和主要內(nèi)容本實驗設(shè)計主要涉及到了隊列的相關(guān)概念、原理、算法和操作等方面內(nèi)容。本實驗設(shè)計主要實現(xiàn)隊列的3個基本功能：建立新的Josephu鏈表、插入一個元素、刪除一個元素。應(yīng)用到的原理是先進先出算法。主要內(nèi)容是使用C語言和C+語言相結(jié)合編寫程序，能夠順利通過鍵盤來操作該程序，完整實現(xiàn)上述要求。約瑟夫（Josephu）問題：已知N個人圍坐在一張圓桌周圍（不妨以1，2，N對每一個人依次編號），現(xiàn)在先從序號為K的人開始報數(shù)，數(shù)到m的那個人出列，他的下一個人又從1開始數(shù)，報數(shù)到m的人出列直到所有人都出列為止。從上述

3、分析可見，在C+中不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊列，則必須為它設(shè)定一個最大隊列長度；若用戶無法預(yù)估所用隊列的最大長度，則宜采用鏈隊列。在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；線性表的容量難以擴充。在程序中有還參照了課外書籍上的一些函數(shù)及程序段完成了Josephu鏈表最主要功能之一的Josephu環(huán)功能。在main函數(shù)中加入了才學(xué)會的Switch，case語句使程序的輸出看上去能比較有可視感。正文2.1設(shè)計的目的和意義課程設(shè)計目的是為學(xué)生提供了一個既動手

4、又動腦，獨立實踐的機會，將課本上的理論知識和實際有機的結(jié)合起來，鍛煉學(xué)生的分析解決實際問題的能力。提高學(xué)生適應(yīng)實際，實踐編程的能力。通過實踐讓學(xué)生理論和實際操作相結(jié)合，更好的理解書面知識，并在鞏固的基礎(chǔ)上融會所學(xué)認識。課程設(shè)計的意思是培養(yǎng)學(xué)生運用所學(xué)課程的知識分析解決實際問題的能力；培養(yǎng)學(xué)生調(diào)查研究、查閱技術(shù)文獻、資料、手冊以及編寫技術(shù)文獻的能力；通過課程設(shè)計，要求學(xué)生在指導(dǎo)教師的指導(dǎo)下，獨立完成設(shè)計課題的全部內(nèi)容，包括：（1）通過調(diào)查研究和上機實習(xí)，收集和調(diào)查有關(guān)技術(shù)資料。（2）掌握課程設(shè)計的基本步驟和方法。（3）根據(jù)課題的要求進行上機實驗調(diào)試。2.2目標與總體方案本實驗設(shè)計的目標是運用循環(huán)

5、鏈表來解決Josephu環(huán)問題，其中運用了許多鏈表中的基本操作使改程序能不只解決一個Josephu的簡單鏈表，其中的Josephu函數(shù)則是用于，運用C+程序（或C語言）編寫程序，實現(xiàn)隊列的建立、插入和刪除基本功能，在程序設(shè)計成功的基礎(chǔ)上，進一步深化理解隊列的作用和實現(xiàn)原理，并獨自撰寫設(shè)計論文。本實驗設(shè)計總體方案如圖2-1所示：圖2-1設(shè)計總體方案圖要求本設(shè)計嚴格按照方案進行，力求省時省力，提高設(shè)計效率，節(jié)約資源。2.3設(shè)計方法和內(nèi)容2.3.1Josphu鏈表的實現(xiàn)Josphu鏈表鏈式表示和實現(xiàn)約瑟夫（Josephu）問題：已知N個人圍坐在一張圓桌周圍（不妨以1，2，N對每一個人依次編號），現(xiàn)在

6、先從序號為K的人開始報數(shù)，數(shù)到m的那個人出列，他的下一個人又從1開始數(shù)，報數(shù)到m的人出列直到所有人都出列為止。給出出列的順序 圖2-2鏈隊列示意圖 循環(huán)鏈表隊列的順序表示和實現(xiàn)和順序棧相似，在隊列的順序存儲結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。為了C語言中描述方便起見，在此我們約定，初始化建空隊列時，令front=rear=0,每當(dāng)插入新的隊列尾元素時，“尾指針增1”；每當(dāng)刪除隊列頭元素時，“頭指針增1”。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位

7、置，如圖2.所示從上述分析可見，在C+中不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊列，則必須為它設(shè)定一個最大隊列長度；若用戶無法預(yù)估所用隊列的最大長度，則宜采用鏈隊列。2.3.2設(shè)計程序編寫本實驗設(shè)計程序采用C語言和C+想結(jié)合的方法，在允許中文環(huán)境下運行。本設(shè)計程序如下：（1）.構(gòu)造Josephu鏈表： 由于是應(yīng)用了類的結(jié)構(gòu)，在main()函數(shù)又有選擇語句，直接構(gòu)造回產(chǎn)生錯誤所以我在構(gòu)造最初的Josephu鏈表時運用了兩個函數(shù)JosephuLink()函數(shù)和putin()函數(shù)。JosephuLink()函數(shù)能構(gòu)造一個空鏈表而putin()函數(shù)則往其中放入初始值。te

8、mplate JosephuLink:JosephuLink() /利用頭插法定義構(gòu)造函數(shù) head=new Node;template void JosephuLink:putin()int i;cinn;if(n1)cout輸入?yún)?shù)錯誤!data=1;tail=head;for(i=2;i=n;i+)p=new Node;p-data=i;tail-next=p;tail=p;cout構(gòu)建的Josephu鏈表為:next=head;p=head; for(i=1;i=n;i+)coutdatanext;coutendl;如圖2-3所示：圖2-3 程序圖（2）.插入操作 插入操作較為簡單只是

9、對以前鏈表的該操作做了一些簡單的修改就能運用于該程序，插入操作用的是Insert()函數(shù)。template bool JosephuLink:Insert() /插入 int loc;T x;coutloc; coutx; if(loc1) /判斷位置是否合法cout輸入?yún)?shù)錯誤，插入失敗!endl;return false;Node*p=head-next;for(int i=1;inext;Node*m=new Node;m-data=x;if(loc-1!=0)m-next=p-next;p-next=m;elsem-next=head-next;head-next=m;cout新的數(shù)列

10、為:;n+;return true;（3）.刪除操作同插入操作一樣刪除操作也是利用的以前對鏈表的操作加以簡單改編而成，在本程序中刪除操作為Delete函數(shù)。template bool JosephuLink:Delete() /刪除int loc;T x;coutloc; if(loc1|head=NULL) /判斷位置是否合法return false; Node*p=head;if(loc=1)head=head-next;elseNode*q=head; for(int i=0;inext;p=q-next;q-next=p-next;x=p-data;delete p;n-;return

11、 true;（4）.Josephu操作Josephu操作為本程序的重點，在本程序中我是利用了一個Josephu函數(shù)來解決該問題的，該函數(shù)是通過不斷的循環(huán)、淘汰、再循環(huán)、再淘汰直到將Josephu鏈表中的所有元素被刪除。函數(shù)如下：template int JosephuLink: Josephu()int m, k;int i;cout請輸入執(zhí)行中的每隔幾位數(shù)淘汰一個元素:m;cout請輸入從第幾個數(shù)開始執(zhí)行:k;p=head;for(i=1;inext;cout執(zhí)行過程如下:nnext)for(i=1;inext;q-next=p-next;cout本輪刪除元素為:datanext; n-;

12、f=p;cout剩下的鏈表為 :;for(i=1;i=n;i+)coutdatanext;coutnext)cout最終剩余的元素為:data;delete p;head=NULL;return 0;template void JosephuLink:putin()int i;cinn;if(n1)cout輸入?yún)?shù)錯誤!data=1;tail=head;for(i=2;i=n;i+)p=new Node;p-data=i;tail-next=p;tail=p;cout構(gòu)建的Josephu鏈表為:next=head;p=head; for(i=1;i=n;i+)coutdatanext;cout

13、endl;（5）.顯示當(dāng)前鏈表操作template void JosephuLink:show() /遍歷操作 Node *q;q=head;coutdata;q=head-next;while(q!=head)cout data;q=q-next;coutendl;（6）.退出操作 退出操作只運用了一個簡單的返回函數(shù)quit（）。 顯示當(dāng)前鏈表操作直接運用了鏈表的一些特性，實行了簡單的 遍歷操作。template int JosephuLink:quit()exit (0); 程序中主要運用了C+的類函數(shù)，C語言中的循環(huán)、判斷和輸入輸出函數(shù)等方法，進行認真仔細的編寫，可以通過Win-tc和V

14、isual C+等語言編譯軟件的運行，其中使用Win-tc必須在中文環(huán)境中方可運行。在Visual C+中運行的情況如圖2-4所示：圖2-42.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)設(shè)計創(chuàng)新算法的設(shè)計取決于數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實現(xiàn)依賴于采用的存儲結(jié)構(gòu)。數(shù)據(jù)的運算是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法，如檢索、插入、刪除、更新的排序等。在本設(shè)計程序中，第一次把算法中的建立、插入、刪除等操作融合在一起，在一個程序中實現(xiàn)各自的功能，從而提高整體的運行效率。關(guān)鍵技術(shù)在本設(shè)計程序中，我們首先定義全體實數(shù)為需要建立新的隊列的有限集，這樣就擴大了新隊列建立所需元素的取值范圍，減少了錯誤的發(fā)生。在本設(shè)計程序中，我們定義隊列為

15、線性的鏈表形式，這樣就更容易操作，方便元素的插入或刪除。其中還借助了指針的作用，使得我們查找某個元素，尤其是方便了刪除或有序插入的操作。使本程序能更加廣泛的運用。2.5結(jié)論通過本次課程設(shè)計的鍛煉，使我對計算方法又有了許多新的深刻認識，更深的理解了數(shù)據(jù)結(jié)構(gòu)的難點，主要有以下新的體會：一方面，在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算。另一方面，在程序設(shè)計過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。一個軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上。一個含抽象數(shù)據(jù)類型的軟件模塊

16、應(yīng)包含定義、表示、實現(xiàn)三個部分。本實驗設(shè)計就是建立在“定義、表示、實現(xiàn)”的基礎(chǔ)上完成的。同時，做好課程設(shè)計更能體現(xiàn)出同學(xué)的學(xué)習(xí)態(tài)度，對于新知識的渴望與追求，能夠反映出同學(xué)對自己負責(zé)任的決心，這點讓我感受頗深。致謝由于本人相關(guān)專業(yè)知識有限，在初始接觸階段遇到了許多的困難，在此特別感謝陳杰老師的幫助，他不是直接告訴我們該怎么做，而是以啟發(fā)的形式鼓勵我們思考，充分的調(diào)動了我們的積極性，更重要的是使我們對不懂的知識點有了深刻的了解。但在指導(dǎo)老師陳杰老師的大力指導(dǎo)下，在各位同學(xué)們的大力幫助與支持下，同時通過本人大量查閱書籍資料，瀏覽相關(guān)網(wǎng)頁論壇之后，才順利編寫完畢，在此十分感謝大家！雖然是講解，。參考文

17、獻1 陳松喬，劉麗華，陳可算法與數(shù)據(jù)結(jié)構(gòu)（C與c+描述）第二版. 北京；清華大學(xué)出版社，2002年；131-1352 嚴蔚敏，吳偉民.c語言題集（C語言版）.第1版.北京；清華大學(xué)出版社，2005年；96-105.3 李春葆，章啟俊.C+程序設(shè)計.第1版.北京；清華大學(xué)出版社，2007年；56-31.4 譚浩強.C+面對對象程序.第1版.北京；清華大學(xué)出版社，2006年；15-32.5 劉振東，劉燕君.c+程序設(shè)計.第一版.北京；機械工業(yè)出版社，2004年；17-37.6 許卓群C+程序設(shè)計第一版. 北京；高等教育出版社，1989年；14-18.7 嚴蔚敏，吳偉民C語言集（C語言版）第一版.

18、北京；清華大學(xué)出版社，1999；3-10.8 王曉東。數(shù)據(jù)結(jié)構(gòu)（c+語言版） 第一版。北京：科學(xué)出版社。2008年：36-47.9 蔡自經(jīng)，施伯樂C語言教程第二版. 上海；復(fù)旦大學(xué)出版社，1984年，11-14.附錄A 源程序的清單#inclue #include using namespace std;template class JosephuLink;template class Node /結(jié)點類friend class JosephuLink; /友元類T data; Node *next; ;template class JosephuLink /鏈表類public:Josephu

19、Link(); /構(gòu)造函數(shù)void putin(); /輸入函數(shù)int Josephu(); /Josephu函數(shù)bool Insert(); /插入bool Delete(); /刪除void show(); /遍歷int quit(); /退出private:Node *head; /頭指針Node *tail; /尾指針Node *p;Node *f;Node *q;int n;template JosephuLink:JosephuLink() /利用頭插法定義構(gòu)造函數(shù) head=new Node;template int JosephuLink: Josephu()int m, k;

20、int i;cout請輸入執(zhí)行中的每隔幾位數(shù)淘汰一個元素:m;cout請輸入從第幾個數(shù)開始執(zhí)行:k;p=head;for(i=1;inext;cout執(zhí)行過程如下:nnext)for(i=1;inext;q-next=p-next;cout本輪刪除元素為:datanext; n-; f=p;cout剩下的鏈表為 :;for(i=1;i=n;i+)coutdatanext;coutnext)cout最終剩余的元素為:data;delete p;head=NULL;return 0;template void JosephuLink:putin()int i;cinn;if(n1)cout輸入?yún)?shù)

21、錯誤!data=1;tail=head;for(i=2;i=n;i+)p=new Node;p-data=i;tail-next=p;tail=p;cout構(gòu)建的Josephu鏈表為:next=head;p=head; for(i=1;i=n;i+)coutdatanext;coutendl;template bool JosephuLink:Insert() /插入 int loc;T x;coutloc; coutx; if(loc1) /判斷位置是否合法cout輸入?yún)?shù)錯誤，插入失敗!endl;return false;Node*p=head-next;for(int i=1;inext

22、;Node*m=new Node;m-data=x;if(loc-1!=0)m-next=p-next;p-next=m;elsem-next=head-next;head-next=m;n+;return true;template bool JosephuLink:Delete() /刪除int loc;T x;coutloc; if(loc1|head=NULL) /判斷位置是否合法return false; Node*p=head;if(loc=1)head=head-next;elseNode*q=head; for(int i=0;inext;p=q-next;q-next=p-next;x=p-data;