C++課程設(shè)計實(shí)驗(yàn)報告

1、目錄前言11.1背景和意義11.2設(shè)計的原理、方法和主要內(nèi)容1正文22.1設(shè)計的目的和意義22.2目標(biāo)與總體方案22.3設(shè)計方法和內(nèi)容22.3.1 線性鏈表的定義22.3.2 josphu鏈表的實(shí)現(xiàn)32.3.3設(shè)計程序42.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)82.5結(jié)論9致謝9參考文獻(xiàn)9附錄a 源程序的清單11 前言1.1背景和意義數(shù)據(jù)結(jié)構(gòu)它支持面向?qū)ο蟮某绦蛟O(shè)計方法，特別適用于中型和大型的軟件開發(fā)項(xiàng)目，從開發(fā)時間、費(fèi)用到軟件的重用性、可擴(kuò)充性、可維護(hù)性和可靠性等方面，數(shù)據(jù)結(jié)構(gòu)均具有很大的優(yōu)越性。數(shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)很多東西。在計算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象（數(shù)據(jù)元素

2、）以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。要設(shè)計出一個結(jié)構(gòu)好效率高的程序,必須研究數(shù)據(jù)的特性及數(shù)據(jù)間的相互關(guān)系及其對應(yīng)的存儲表示,并利用這些特性結(jié)合相關(guān)編程技術(shù)，運(yùn)用合適、熟練的方法，才能設(shè)計出符合要求、可操作性強(qiáng)、有利用價值的應(yīng)用程序。1.2設(shè)計的原理、方法和主要內(nèi)容本實(shí)驗(yàn)設(shè)計主要實(shí)現(xiàn)隊(duì)列的3個基本功能：建立新的josephu鏈表、插入一個元素、刪除一個元素。應(yīng)用到的原理是先進(jìn)先出算法。主要內(nèi)容是使用c語言和c+語言相結(jié)合編寫程序，能夠順利通過鍵盤來操作該程序，完整實(shí)現(xiàn)上述要求。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以

3、不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。兩部分信息組成數(shù)據(jù)元素的存儲映像。它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。暴露的問題.在程序中運(yùn)用了在本學(xué)期中新學(xué)到模版等東西，主要還是運(yùn)用了類相關(guān)內(nèi)容，程序中的josphulink()、insert()、delete()、show()等基本操作函數(shù)都是參照本學(xué)期所學(xué)過的鏈表的相關(guān)內(nèi)容加以運(yùn)用。約瑟夫（josephu）問題：已知n

4、個人圍坐在一張圓桌周圍（不妨以1，2，n對每一個人依次編號），現(xiàn)在先從序號為k的人開始報數(shù)，數(shù)到m的那個人出列，他的下一個人又從1開始數(shù)，報數(shù)到m的人出列直到所有人都出列為止。從上述分析可見，在數(shù)據(jù)結(jié)構(gòu)中不能用動態(tài)分配的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個最大隊(duì)列長度；若用戶無法預(yù)估所用隊(duì)列的最大長度，則宜采用鏈隊(duì)列。在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；線性表的容量難以擴(kuò)充。在程序中有還參照了課外書籍上的一些函數(shù)及程序段完成了josephu鏈表最主

5、要功能之一的josephu環(huán)功能。在main函數(shù)中加入了才學(xué)會的switch，case語句使程序的輸出看上去能比較有可視感。正文2.1設(shè)計的目的和意義課程設(shè)計目的是為學(xué)生提供了一個既動手又動腦，獨(dú)立實(shí)踐的機(jī)會，將課本上的理論知識和實(shí)際有機(jī)的結(jié)合起來，鍛煉學(xué)生的分析解決實(shí)際問題的能力。提高學(xué)生適應(yīng)實(shí)際，實(shí)踐編程的能力。通過實(shí)踐讓學(xué)生理論和實(shí)際操作相結(jié)合，更好的理解書面知識，并在鞏固的基礎(chǔ)上融會所學(xué)認(rèn)識。課程設(shè)計的意思是培養(yǎng)學(xué)生運(yùn)用所學(xué)課程的知識分析解決實(shí)際問題的能力；培養(yǎng)學(xué)生調(diào)查研究、查閱技術(shù)文獻(xiàn)、資料、手冊以及編寫技術(shù)文獻(xiàn)的能力；通過課程設(shè)計，要求學(xué)生在指導(dǎo)教師的指導(dǎo)下，獨(dú)立完成設(shè)計課題的全部

6、內(nèi)容，包括：（1）通過調(diào)查研究和上機(jī)實(shí)習(xí)，收集和調(diào)查有關(guān)技術(shù)資料。（2）掌握課程設(shè)計的基本步驟和方法。（3）根據(jù)課題的要求進(jìn)行上機(jī)實(shí)驗(yàn)調(diào)試。2.2目標(biāo)與總體方案本實(shí)驗(yàn)設(shè)計的目標(biāo)是運(yùn)用循環(huán)鏈表來解決josephu環(huán)問題，其中運(yùn)用了許多鏈表中的基本操作使改程序能不只解決一個josephu的簡單鏈表，其中的josephu函數(shù)則是用于，運(yùn)用c+程序（或c語言）編寫程序，實(shí)現(xiàn)隊(duì)列的建立、插入和刪除基本功能，在程序設(shè)計成功的基礎(chǔ)上，進(jìn)一步深化理解隊(duì)列的作用和實(shí)現(xiàn)原理，并獨(dú)自撰寫設(shè)計論文。本實(shí)驗(yàn)設(shè)計總體方案如圖2. 1所示：圖2.1設(shè)計總體方案圖要求本設(shè)計嚴(yán)格按照方案進(jìn)行，力求省時省力，提高設(shè)計效率，節(jié)約資

7、源。2.3設(shè)計方法和內(nèi)容2.3.1 線性鏈表的定義線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個表示它的直接后繼元素存儲位置的信息。兩部分信息組成數(shù)據(jù)元素的存儲映像。線性表順序存儲結(jié)構(gòu)的特點(diǎn):它是一種簡單、方便的存儲方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲單元中，從而利用數(shù)據(jù)元素的存儲順序表示相應(yīng)的邏輯順序，這種存儲方式屬于靜態(tài)存儲形式。暴露的問題.在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間

8、，但這些空間常常又得不到充分的利用；線性表的容量難以擴(kuò)充。 循環(huán)鏈表是限定插入和刪除操作在表的兩端進(jìn)行的線性表。這兩端分別稱為端點(diǎn)1和端點(diǎn)2也可像棧一樣，可以用一個鐵道轉(zhuǎn)軌網(wǎng)絡(luò)來比喻雙端隊(duì)列。在實(shí)際使用中，還可以有輸出受限的雙端隊(duì)列（即一個端點(diǎn)允許插入和刪除，另一個端點(diǎn)只允許插入的雙端隊(duì)列）和輸入受限的雙端隊(duì)列（即一個端點(diǎn)允許插入和刪除，另一個端點(diǎn)只允許刪除的雙端隊(duì)列）。而如果限定雙端隊(duì)列從某個端點(diǎn)插入的元素只能從該端點(diǎn)刪除，則該雙端隊(duì)列就蛻變?yōu)閮蓚€棧底相鄰接的棧了。 圖2.2循環(huán)鏈表示意圖2.3.2 josphu鏈表的實(shí)現(xiàn)josphu鏈表鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)約瑟夫（josephu）問題：已知n個人

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

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

11、數(shù)能構(gòu)造一個空鏈表而putin()函數(shù)則往其中放入初始值。template 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.4

12、 構(gòu)建（2）.插入操作插入操作較為簡單只是對以前鏈表的該操作做了一些簡單的修改就能運(yùn)用于該程序，插入操作用的是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

13、;head-next=m;cout新的數(shù)列為:;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-da

14、ta;delete p;n-;return true;（4）.josephu操作josephu操作為本程序的重點(diǎn)，在本程序中我是利用了一個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本

15、輪刪除元素為: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ù)錯誤!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

16、;i+)coutdatanext;coutendl;圖 圖2.5 josephu選擇（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）.退出操作退出操作只運(yùn)用了一個簡單的返回函數(shù)quit（）。顯示當(dāng)前鏈表操作直接運(yùn)用了鏈表的一些特性，實(shí)行了簡單的 遍歷操作。template int josephulink:quit()exit (0); 程序中主要運(yùn)用了c+的類函數(shù)，c語言中的循環(huán)、

17、判斷和輸入輸出函數(shù)等方法，進(jìn)行認(rèn)真仔細(xì)的編寫，可以通過win-tc和visual c+等語言編譯軟件的運(yùn)行，其中使用win-tc必須在中文環(huán)境中方可運(yùn)行。在visual c+中運(yùn)行的情況如圖2.6所示：圖2.6 運(yùn)行界面2.4設(shè)計創(chuàng)新和關(guān)鍵技術(shù)c+是最有意義的方面是支持面向?qū)ο蟮奶匦?。c+中不能用動態(tài)分配的一維數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列。如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個最大隊(duì)列長度；若用戶無法預(yù)估所用隊(duì)列的最大長度，則宜采用鏈隊(duì)列。在做插入或刪除元素的操作時，會產(chǎn)生大量的數(shù)據(jù)元素移動；對于長度變化較大的線性表，要一次性地分配足夠的存儲空間，但這些空間常常又得不到充分的利用；線性表的

18、容量難以擴(kuò)充。本程序設(shè)計是利用c+來實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)的特性的。所以在程序的編寫過程中下列操作必不可缺：1. 結(jié)構(gòu)的生成；2. 結(jié)構(gòu)的銷毀；3. 在結(jié)構(gòu)中查找滿足規(guī)定條件的數(shù)據(jù)元素；4. 在結(jié)構(gòu)中插入新的數(shù)據(jù)元素；5. 刪除結(jié)構(gòu)中已經(jīng)存在的數(shù)據(jù)元素；6. 遍歷。在本設(shè)計程序中，充分體現(xiàn)了上述的操作，雖然只是運(yùn)用局部操作，但是仍然起到了關(guān)鍵作用。使用c語言和c+相結(jié)合的方式，使得程序運(yùn)行更靈活，處理更方便，在表現(xiàn)方式方面得到了創(chuàng)新。2.5結(jié)論通過本次課程設(shè)計的鍛煉，使我對c+程序設(shè)計又有了許多新的深刻認(rèn)識，更深的理解了運(yùn)用c+來體現(xiàn)數(shù)據(jù)結(jié)構(gòu)的難點(diǎn)。一個軟件系統(tǒng)框架應(yīng)建立在數(shù)據(jù)之上，而不是建立在操作之上

19、。一個含抽象數(shù)據(jù)類型的軟件模塊應(yīng)包含定義、表示、實(shí)現(xiàn)三個部分。本實(shí)驗(yàn)設(shè)計就是建立在“定義、表示、實(shí)現(xiàn)”的基礎(chǔ)上完成的。同時，做好課程設(shè)計更能體現(xiàn)出同學(xué)的學(xué)習(xí)態(tài)度，對于新知識的渴望與追求，能夠反映出同學(xué)對自己負(fù)責(zé)任的決心，這點(diǎn)讓我感受頗深。致謝為期14天的課程設(shè)計中，朱老師給與我們很大幫助。在同學(xué)遇到疑問時，化老師能夠耐心地講解。雖然是講解，他不是直接告訴我們該怎么做，而是以啟發(fā)的形式鼓勵我們思考，充分的調(diào)動了我們的積極性，更重要的是使我們對不懂的知識點(diǎn)有了深刻的了解。由于本人相關(guān)專業(yè)知識有限，在初始接觸階段遇到了許多的困難，致使程序編寫無法順利進(jìn)行。在指導(dǎo)老師朱賴紅老師的大力指導(dǎo)下，在各位同學(xué)

20、們的大力幫助與支持下，同時通過本人大量查閱書籍資料，瀏覽相關(guān)網(wǎng)頁論壇之后，才順利編寫完畢，在此十分感謝大家！參考文獻(xiàn)1 王曉東。數(shù)據(jù)結(jié)構(gòu)（c+語言版） 第一版。北京：科學(xué)出版社。2008年：36-47.2 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集（c語言版）.第1版.北京；清華大學(xué)出版社，2005年；96-105.3 李春葆，章啟俊.c+程序設(shè)計.第1版.北京；清華大學(xué)出版社，2007年；56-31.4 譚浩強(qiáng).c+面對對象程序.第1版.北京；清華大學(xué)出版社，2006年；15-32.5 劉振東，劉燕君.c+程序設(shè)計.第一版.北京；機(jī)械工業(yè)出版社，2004年；17-37.6 許卓群數(shù)據(jù)結(jié)構(gòu)第一版. 北京；高

21、等教育出版社，1989年；14-18.7 嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)題集（c語言版）第一版. 北京；清華大學(xué)出版社，1999；3-10.8 陳松喬，劉麗華，陳可算法與數(shù)據(jù)結(jié)構(gòu)（c與c+描述）第二版. 北京；清華大學(xué)出版社，2002年；131-135.9 蔡自經(jīng)，施伯樂數(shù)據(jù)結(jié)構(gòu)教程第二版. 上海；復(fù)旦大學(xué)出版社，1984年，11-14.10嚴(yán)華峰.visual c+課程設(shè)計及案例精選.中國水利水電出版社.2004:69-74.11錢能.c+程序設(shè)計教程.北京：清華大學(xué)出版社.1999:201-202.12decoder.c/c+程序設(shè)計.北京：中國鐵道出版社.2002:99-104.13顧仁.高級c

22、+語言程序設(shè)計技巧與實(shí)例.北京：機(jī)械工業(yè)出版社.1995:153-164.14譚浩強(qiáng).c程序設(shè)計(第三版).北京：清華大學(xué)出版社.2005:77-184.15陳松喬，劉麗華，陳可算法與數(shù)據(jù)結(jié)構(gòu)（c與c+描述）第二版. 北京；清華大學(xué)出版社，2002年；131-135.附錄a 源程序的清單#include #include using namespace std;template class josephulink;template class node /結(jié)點(diǎn)類friend class josephulink; /友元類t data; node *next; ;template class j

23、osephulink /鏈表類public:josephulink(); /構(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 jo

24、sephulink: 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-; f=p;cout剩下的鏈表為 :;for(i=1;i=n;i+)coutdatanext;coutnext)cout最終剩余的元素為:data;delete p;head=null;return 0;template void josephulink:put

25、in()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;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;n+;return true;template bool josephulink:delete() /刪除int loc;t x;coutloc; if(loc1|head=null) /判斷位置是否合法r