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

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

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

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

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

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

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

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

9、對以前鏈表的該操作做了一些簡單的修改就能運用于該程序，插入操作用的是Insert()函數。template bool JosephuLink:Insert() /插入 int loc;T x;coutloc; coutx; if(loc1) /判斷位置是否合法cout輸入參數錯誤，插入失敗!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新的數列

10、為:;n+;return true;（3）.刪除操作同插入操作一樣刪除操作也是利用的以前對鏈表的操作加以簡單改編而成，在本程序中刪除操作為Delete函數。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函數來解決該問題的，該函數是通過不斷的循環、淘汰、再循環、再淘汰直到將Josephu鏈表中的所有元素被刪除。函數如下：template int JosephuLink: Josephu()int m, k;int i;cout請輸入執行中的每隔幾位數淘汰一個元素:m;cout請輸入從第幾個數開始執行:k;p=head;for(i=1;inext;cout執行過程如下: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輸入參數錯誤!data=1;tail=head;for(i=2;i=n;i+)p=new Node;p-data=i;tail-next=p;tail=p;cout構建的Josephu鏈表為:next=head;p=head; for(i=1;i=n;i+)coutdatanext;cout

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

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

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

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

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

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

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

20、int i;cout請輸入執行中的每隔幾位數淘汰一個元素:m;cout請輸入從第幾個數開始執行:k;p=head;for(i=1;inext;cout執行過程如下: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輸入參數

21、錯誤!data=1;tail=head;for(i=2;i=n;i+)p=new Node;p-data=i;tail-next=p;tail=p;cout構建的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輸入參數錯誤，插入失敗!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;