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

1、-作者xxxx-日期xxxx約瑟夫(Josephu)環(huán)C+課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)【精品文檔】目錄1 前言1背景和意義1設(shè)計(jì)的原理、方法和主要內(nèi)容12 正文1設(shè)計(jì)的目的和意義1目標(biāo)與總體方案2設(shè)計(jì)方法和內(nèi)容2鏈表的實(shí)現(xiàn)2設(shè)計(jì)程序3設(shè)計(jì)創(chuàng)新和關(guān)鍵技術(shù)8設(shè)計(jì)創(chuàng)新8關(guān)鍵技術(shù)8結(jié)論83 致謝9參考文獻(xiàn)9附錄A 源程序的清單9 前言數(shù)據(jù)是計(jì)算機(jī)化的信息,它是計(jì)算機(jī)可以直接處理的最基本和最重要的對(duì)象。無(wú)論是進(jìn)行科學(xué)計(jì)算或數(shù)據(jù)處理、過(guò)程控制以及對(duì)文件的存儲(chǔ)和檢索及數(shù)據(jù)庫(kù)技術(shù)應(yīng)用等,都是對(duì)數(shù)據(jù)進(jìn)行加工處理的過(guò)程。因此,要設(shè)計(jì)出一個(gè)結(jié)構(gòu)好效率高的程序,必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對(duì)應(yīng)的存儲(chǔ)表示,并利用這些特

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

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

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

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

6、那個(gè)人出列，他的下一個(gè)人又從1開始數(shù)，報(bào)數(shù)到m的人出列直到所有人都出列為止。給出出列的順序 圖2-2鏈隊(duì)列示意圖 循環(huán)鏈表隊(duì)列的順序表示和實(shí)現(xiàn)和順序棧相似，在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外，尚需附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。為了C語(yǔ)言中描述方便起見，在此我們約定，初始化建空隊(duì)列時(shí)，令front=rear=0,每當(dāng)插入新的隊(duì)列尾元素時(shí)，“尾指針增1”；每當(dāng)刪除隊(duì)列頭元素時(shí)，“頭指針增1”從上述分析可見，在C+中不能用動(dòng)態(tài)分配的一維數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最

7、大隊(duì)列長(zhǎng)度；若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，則宜采用鏈隊(duì)列。2.3.2設(shè)計(jì)程序編寫本實(shí)驗(yàn)設(shè)計(jì)程序采用C語(yǔ)言和C+想結(jié)合的方法，在允許中文環(huán)境下運(yùn)行。本設(shè)計(jì)程序如下：（1）.構(gòu)造Josephu鏈表： 由于是應(yīng)用了類的結(jié)構(gòu)，在main()函數(shù)又有選擇語(yǔ)句，直接構(gòu)造回產(chǎn)生錯(cuò)誤所以我在構(gòu)造最初的Josephu鏈表時(shí)運(yùn)用了兩個(gè)函數(shù)JosephuLink()函數(shù)和putin()函數(shù)。JosephuLink()函數(shù)能構(gòu)造一個(gè)空鏈表而putin()函數(shù)則往其中放入初始值。template <class T>JosephuLink<T>:JosephuLink() /利用頭插法定義構(gòu)造

8、函數(shù) head=new Node<T>template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<1)cout<<"輸入?yún)?shù)錯(cuò)誤!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new Node<T>p->data=i;tail->next=p;tail=p;cout<<"構(gòu)建的Josephu鏈表為:"<<

9、;endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;cout<<endl;如圖2-3所示：圖2-3 程序圖（2）.插入操作 插入操作較為簡(jiǎn)單只是對(duì)以前鏈表的該操作做了一些簡(jiǎn)單的修改就能運(yùn)用于該程序，插入操作用的是Insert()函數(shù)。template <class T>bool JosephuLink<T>:Insert() /插入 int loc;T x;cout<<"輸

10、入要插入位子:"cin>>loc; cout<<"請(qǐng)輸入要插入的數(shù):"cin>>x; if(loc<1) /判斷位置是否合法cout<<"輸入?yún)?shù)錯(cuò)誤，插入失敗!"<<endl;return false;Node<T>*p=head->next;for(int i=1;i<loc-1;i+)p=p->next;Node<T>*m=new Node<T>m->data=x;if(loc-1!=0)m->next=p-

11、>next;p->next=m;elsem->next=head->next;head->next=m;cout<<"新的數(shù)列為:"n+;return true;（3）.刪除操作同插入操作一樣刪除操作也是利用的以前對(duì)鏈表的操作加以簡(jiǎn)單改編而成，在本程序中刪除操作為Delete函數(shù)。template <class T>bool JosephuLink<T>:Delete() /刪除int loc;T x;cout<<"請(qǐng)輸入要?jiǎng)h除的位子:"cin>>loc; if(l

12、oc<1|head=NULL) /判斷位置是否合法return false; Node<T>*p=head;if(loc=1)head=head->next;elseNode<T>*q=head; for(int i=0;i<loc-1;i+)q=q->next;p=q->next;q->next=p->next;x=p->data;delete p;n-;return true;（4）.Josephu操作Josephu操作為本程序的重點(diǎn)，在本程序中我是利用了一個(gè)Josephu函數(shù)來(lái)解決該問(wèn)題的，該函數(shù)是通過(guò)不斷的循環(huán)、淘

13、汰、再循環(huán)、再淘汰直到將Josephu鏈表中的所有元素被刪除。函數(shù)如下：template <class T>int JosephuLink<T>: Josephu()int m, k;int i;cout<<"請(qǐng)輸入執(zhí)行中的每隔幾位數(shù)淘汰一個(gè)元素:"<<endl;cin>>m;cout<<"請(qǐng)輸入從第幾個(gè)數(shù)開始執(zhí)行:"<<endl;cin>>k;p=head;for(i=1;i<k;i+)p=p->next;cout<<"執(zhí)行

14、過(guò)程如下:n"<<endl;while(p!=p->next)for(i=1;i<m;i+)q=p;p=p->next;q->next=p->next;cout<<"本輪刪除元素為:"<<p->data<<endl;delete p;p=q->next; n-; f=p;cout<<"剩下的鏈表為 :"for(i=1;i<=n;i+)cout<<f->data<<" " f=f->n

15、ext;cout<<endl;if(p=p->next)cout<<"最終剩余的元素為:"<<p->data;delete p;head=NULL;return 0;template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<1)cout<<"輸入?yún)?shù)錯(cuò)誤!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new No

16、de<T>p->data=i;tail->next=p;tail=p;cout<<"構(gòu)建的Josephu鏈表為:"<<endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;cout<<endl;（5）.顯示當(dāng)前鏈表操作template <class T>void JosephuLink<T>:show() /遍歷操作 Node<

17、;T> *q;q=head;cout<<q->data;q=head->next;while(q!=head)cout<<" "<<q->data;q=q->next;cout<<endl;（6）.退出操作 退出操作只運(yùn)用了一個(gè)簡(jiǎn)單的返回函數(shù)quit（）。 顯示當(dāng)前鏈表操作直接運(yùn)用了鏈表的一些特性，實(shí)行了簡(jiǎn)單的 遍歷操作。template <class T>int JosephuLink<T>:quit()exit (0); 程序中主要運(yùn)用了C+的類函數(shù)，C語(yǔ)言中的循環(huán)、判

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

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

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

21、十分感謝大家！雖然是講解，。參考文獻(xiàn)1 陳松喬，劉麗華，陳可算法與數(shù)據(jù)結(jié)構(gòu)（C與c+描述）第二版. 北京；清華大學(xué)出版社，2002年；131-1352 嚴(yán)蔚敏，吳偉民.c語(yǔ)言題集（C語(yǔ)言版）.第1版.北京；清華大學(xué)出版社，2005年；96-105.3 李春葆，章啟俊.C+程序設(shè)計(jì).第1版.北京；清華大學(xué)出版社，2007年；56-31.+面對(duì)對(duì)象程序.第1版.北京；清華大學(xué)出版社，2006年；15-32.5 劉振東，劉燕君.c+程序設(shè)計(jì).第一版.北京；機(jī)械工業(yè)出版社，2004年；17-37.6 許卓群C+程序設(shè)計(jì)第一版. 北京；高等教育出版社，1989年；14-18.7 嚴(yán)蔚敏，吳偉民C語(yǔ)言集（

22、C語(yǔ)言版）第一版. 北京；清華大學(xué)出版社，1999；3-10.8 王曉東。數(shù)據(jù)結(jié)構(gòu)（c+語(yǔ)言版） 第一版。北京：科學(xué)出版社。2008年：36-47.9 蔡自經(jīng)，施伯樂(lè)C語(yǔ)言教程第二版. 上海；復(fù)旦大學(xué)出版社，1984年，11-14.附錄A 源程序的清單#inclue <iostream>#include <string>using namespace std;template <class T>class JosephuLink;template <class T>class Node /結(jié)點(diǎn)類friend class JosephuLink&l

23、t;T> /友元類T data; Node<T> *next; ;template <class T>class JosephuLink /鏈表類public:JosephuLink(); /構(gòu)造函數(shù)void putin(); /輸入函數(shù)int Josephu(); /Josephu函數(shù)bool Insert(); /插入bool Delete(); /刪除void show(); /遍歷int quit(); /退出private:Node<T> *head; /頭指針Node<T> *tail; /尾指針Node<T> *p

24、;Node<T> *f;Node<T> *q;int n;template <class T>JosephuLink<T>:JosephuLink() /利用頭插法定義構(gòu)造函數(shù) head=new Node<T>template <class T>int JosephuLink<T>: Josephu()int m, k;int i;cout<<"請(qǐng)輸入執(zhí)行中的每隔幾位數(shù)淘汰一個(gè)元素:"<<endl;cin>>m;cout<<"請(qǐng)輸入從

25、第幾個(gè)數(shù)開始執(zhí)行:"<<endl;cin>>k;p=head;for(i=1;i<k;i+)p=p->next;cout<<"執(zhí)行過(guò)程如下:n"<<endl;while(p!=p->next)for(i=1;i<m;i+)q=p;p=p->next;q->next=p->next;cout<<"本輪刪除元素為:"<<p->data<<endl;delete p;p=q->next; n-; f=p;cout&

26、lt;<"剩下的鏈表為 :"for(i=1;i<=n;i+)cout<<f->data<<" " f=f->next;cout<<endl;if(p=p->next)cout<<"最終剩余的元素為:"<<p->data;delete p;head=NULL;return 0;template <class T>void JosephuLink<T>:putin()int i;cin>>n;if(n<

27、1)cout<<"輸入?yún)?shù)錯(cuò)誤!"<<endl;head->data=1;tail=head;for(i=2;i<=n;i+)p=new Node<T>p->data=i;tail->next=p;tail=p;cout<<"構(gòu)建的Josephu鏈表為:"<<endl;tail->next=head;p=head; for(i=1;i<=n;i+)cout<<p->data<<" " p=p->next;

28、cout<<endl;template <class T>bool JosephuLink<T>:Insert() /插入 int loc;T x;cout<<"輸入要插入位子:"cin>>loc; cout<<"請(qǐng)輸入要插入的數(shù):"cin>>x; if(loc<1) /判斷位置是否合法cout<<"輸入?yún)?shù)錯(cuò)誤，插入失敗!"<<endl;return false;Node<T>*p=head->next

29、;for(int i=1;i<loc-1;i+)p=p->next;Node<T>*m=new Node<T>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 <class T>bool JosephuLink<T>:Delete() /刪除int loc;T x;cout<<"請(qǐng)輸入要?jiǎng)h除的位子:"

30、;cin>>loc; if(loc<1|head=NULL) /判斷位置是否合法return false; Node<T>*p=head;if(loc=1)head=head->next;elseNode<T>*q=head; for(int i=0;i<loc-1;i+)q=q->next;p=q->next;q->next=p->next;x=p->data;delete p;n-;return true;template <class T>void JosephuLink<T>:show() /遍歷操作 Node<T> *q;q=head;cout<<q->data;q=head->next;while(q!=head)cout<<" "<<q->data;q=q->next;cout<<endl;template <class T>int JosephuLink<T>:quit()exit (0); int main() cout<<"*n" <<&qu