數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 敢死隊(duì)問題

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 敢死隊(duì)問題》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 敢死隊(duì)問題（18頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 課 程 設(shè) 計 （數(shù)據(jù)結(jié)構(gòu)） 班 級 計科1003 姓 名 學(xué) 號 1011051093 指導(dǎo)教師 二○一一年一月十日 課程設(shè)計任務(wù)書及成績評定 課題名稱 敢死隊(duì)問題 Ⅰ、題目的目的和要求： 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)實(shí)驗(yàn)、調(diào)試程序，加深對課本知識的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。 （1）通過本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。 （2）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進(jìn)而

2、給出問題的正確求解過程并編寫代碼實(shí)現(xiàn)。 Ⅱ、設(shè)計進(jìn)度及完成情況 日 期 內(nèi) 容 12.31-1.1 選取參考書，查閱有關(guān)文獻(xiàn)資料，完成資料搜集和系統(tǒng)分析工作。 1.1~1.2 創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu),錄入源程序。 1.2~1.3 調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。 1.4 上交課程設(shè)計報告打印版并進(jìn)行課程設(shè)計答辯，要求每個同學(xué)針對自己的設(shè)計回答指導(dǎo)教師3-4個問題。 考核結(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。 Ⅲ、主要參考文獻(xiàn)及資料 [1] 嚴(yán)蔚敏

3、數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社 1999 [2] 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社 1999 [3] 徐寶文等譯 C語言程序設(shè)計 清華大學(xué)出版社 [4] 與所用編程環(huán)境相配套的C語言或C++相關(guān)的資料 Ⅳ、成績評定： 設(shè)計成績： （教師填寫） 指導(dǎo)老師： （簽字） 二○一一 年 一 月 十 日 目 錄 第一章 概述……………………………………………………………1 第二章 系統(tǒng)分析………………………………

4、………………………2 第三章 概要設(shè)計………………………………………………………3 第四章 詳細(xì)設(shè)計………………………………………………………4 第五章 運(yùn)行與測試……………………………………………………9 第六章 總結(jié)與心得……………………………………………………13 參考文獻(xiàn)………………………………………………………………14 第一章 概述 課程設(shè)計是實(shí)踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識?！稊?shù)據(jù)結(jié)構(gòu)》是一門重要的專業(yè)基礎(chǔ)課，是

5、計算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實(shí)現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。 在這次的課程設(shè)計中我選擇的題目是圖書管理。傳統(tǒng)的人工圖書管理，基本業(yè)務(wù)活動有對一本書的采編入庫、清除庫存、借閱和歸還等等，但是人工統(tǒng)計操作起來效率相對來說要低，也容易出錯。但是現(xiàn)在這些業(yè)務(wù)借助計算機(jī)系統(tǒng)完成后，效率可以得到提高，也可以減少出錯的幾率。可以使圖書管理的日常業(yè)務(wù)更加的方便，迅捷，減少很多勞動量。 課程設(shè)計的目的意義：加深對循環(huán)

6、隊(duì)列和數(shù)組的理解，以及對循環(huán)隊(duì)列和數(shù)組的實(shí)際應(yīng)用，加強(qiáng)自己的動手操作能力，增加對課程的興趣，而不是枯燥的看課本。 課程設(shè)計的問題：敢死隊(duì)問題 有M個敢死隊(duì)員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)行任務(wù)。如果前一個戰(zhàn)士沒完成任務(wù)，則要再派一個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當(dāng)數(shù)到5時，對應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。 排長是不愿意去的，假設(shè)排長為1號，請你設(shè)計一程序，求

7、出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。 第二章 系統(tǒng)分析 1． 敢死隊(duì)問題包括：兩個數(shù)據(jù)的輸入，一個是隊(duì)員的數(shù)量，另一個是模擬的形式。由于問題給出的數(shù)數(shù)的數(shù)量為5 ，所以k 值就默認(rèn)為5 ，不再設(shè)置數(shù)據(jù)輸入。故重點(diǎn)是要完成兩種數(shù)據(jù)結(jié)構(gòu)形式的刪除，循環(huán)標(biāo)記等操作。 2． 演示程序是以用戶于計算機(jī)的對話方式執(zhí)行，這需要調(diào)用一個清屏函數(shù)來完成使用者與計算機(jī)語言之間界面的處理。 3． 程序執(zhí)行時的命令： 本程序?yàn)榱耸褂脮r的方便，采用阿拉伯?dāng)?shù)字的方式來完成程序的等各種選擇輸入，幾乎不用輸入什么特殊的命令。（要注意輸入時必須用數(shù)字，否者

8、可能會引起一些死循環(huán)） 5. 測試數(shù)據(jù)。 1 5 13 數(shù)據(jù)運(yùn)行結(jié)果 在第五章有詳細(xì)的截圖 第三章 概要設(shè)計 1. 數(shù)據(jù)結(jié)構(gòu)類型： 一種是循環(huán)隊(duì)列，另一種是數(shù)組形式 其中循環(huán)隊(duì)列操作只需要刪除操作，用數(shù)組形式處理和運(yùn)算上則較復(fù)雜些 因此，循環(huán)隊(duì)列占優(yōu)勢 2. 程序總體上分為兩大塊，一塊是循環(huán)隊(duì)列的模擬，一塊是數(shù)組形式的模擬 這兩種形式功能都是模擬每個開始數(shù)數(shù)的位置對員的死亡順序，其中循環(huán) 隊(duì)列的函數(shù)接口為：lianbiao(n) ，數(shù)組的函數(shù)接口為：ar

9、ray(n); 兩模塊算法基本一致，數(shù)據(jù)結(jié)構(gòu)形式不同而已 算法概述： For(int i=1;i<=n;i++) { 初始化數(shù)據(jù) 對每個位置進(jìn)行模擬/調(diào)用del /delx 函數(shù)進(jìn)行模擬 判斷是否安全 } Printf->安全的位置； 第四章 詳細(xì)設(shè)計 1：存儲結(jié)構(gòu)形式 struct node { int data; node *next; }; struct nodel { int data; }sqlist[N]

10、; 2：成員函數(shù)部分 int del(node *p,node *q) // 鏈表的刪除操作 { while(q->next!=q) { int k=4; while(k--) { p=p->next; q=q->next; } if(q->data==1) { return 0; } else

11、 { cout<data<<" "; q=q->next; p->next=q; } } if(q->next==q) { return 1; } } void lianbiao(int n) { int i,flag=0; for( i=1;i<=n;i++)// 循環(huán)找出安全的開始位置 { int k=i; cout<<"\n\n報數(shù)的位置為"<

12、<<"時的排長之前的人員死亡順序:\n"; node *head=new node,*t=head; head->data=1; head->next=head; int j=1; while(++j<=n) //構(gòu)造循環(huán)隊(duì)列 { node *p=new node; p->data=j; p->next=t->next; t->next=p; t=t->next;

13、 } t=head; node *p=head,*q;// 設(shè)置p q 指針 while(p->next!=head) p=p->next; q=head; while(--k) //循環(huán)找開始的位置 { p=p->next; q=q->next; } if(del(p,q)==1) //判斷位置是否安全

14、 { cout<

15、],int key,int n,int sum) //數(shù)組的偽刪除操作 { // printf("第%d個位置開始數(shù)數(shù)的死亡的順序號\n",key); do { int k=4; while(k) { key++; if(key>13) key-=13; if(sq[key].data!=0) k--; } if(key==1) {

16、 if(sum==1) return 1; else return 0; } else { sum-=sq[key].data; sq[key].data=0; cout<13) key-=13; // cout<

17、.data==0) { key++; if(key>13) key-=13; } // cout<

18、 int k=i; cout<<"\n\n報數(shù)的位置為"<

19、\n"; flag=i;//cout<

20、 cout<

21、員死亡順序-----------------\n"; //system("cls"); do{ cout<<"請選擇模擬的形式：\n 1：鏈表 2：數(shù)組 3: 退出程序\n"; cin>>cas; if(cas>3||cas<=0) { cout<<"輸入錯誤\n";continue; } cout<<"\n請輸入隊(duì)員的數(shù)量~~~~"<>n; switch(cas) { case 1:

22、 lianbiao(n);break; case 2: array(n); break; default : cout<<"輸入錯誤\n";break; } cout<<"還要繼續(xù)嗎？ 按3 退出程序,其他輸入繼續(xù)\n"; int ss;cin>>ss; if(ss==3) break; else system("cls"); }while(cas!=3); return 0; } 第五章 運(yùn)行與測試 1. 調(diào)試

23、程序的過程中遇到什么問題 處理過程中經(jīng)常忽視特殊位置的處理 像開始位置為1時，循環(huán)隊(duì)列就會出現(xiàn)bugs 而數(shù)組形式中刪除操作不容易處理，用0 標(biāo)記來代替 刪除操作，在循環(huán)數(shù)數(shù)的時候 經(jīng)常認(rèn)為是5 ，但是 循環(huán)只需要進(jìn)行4 次即可。而刪除操作的判斷則用sum 總和進(jìn)行判斷，替換循環(huán)判斷，省時！操作方便，在4 層循環(huán)數(shù)數(shù)操作中容易漏 data 為0 的判斷以及 對 key 的變相取余 3.測試數(shù)據(jù) 1 5 13 第6章 總結(jié)與心得 通過這一課程設(shè)計，加深了我對《數(shù)據(jù)結(jié)構(gòu)》這門課程所學(xué)內(nèi)容的進(jìn)一步的

24、理解與掌握；同時，通過對循環(huán)隊(duì)列和數(shù)組的應(yīng)用，使得我將計算機(jī)課程所學(xué)知識與實(shí)際問題很好地相聯(lián)接在了一起。在這次課程設(shè)計中，培養(yǎng)了我開發(fā)一個中小型程序的能力。 調(diào)程序的時候，要穩(wěn)扎穩(wěn)打，每個子函數(shù)單調(diào)試后在和主函數(shù)鏈接，效率較高，不然都最后全在一塊，給調(diào)程序會帶來極大的不便?。?！對于每個子函數(shù)都要考慮到一些特殊值。 最大的收獲還是感覺到數(shù)據(jù)結(jié)構(gòu)的實(shí)用性，不像看課本和考試那樣，總是參生厭煩情緒，離開發(fā)一些東西越來越近了，而不像以前那樣很遙遠(yuǎn)。。。 總之，在這個的課程設(shè)計中，我的收獲還是挺大的，不僅對于專業(yè)課有了更好的認(rèn)識，而且還學(xué)到做事要細(xì)心、全面周到的重要性。

25、 參考文獻(xiàn): [1] 嚴(yán)蔚敏、吳偉民主編 《數(shù)據(jù)結(jié)構(gòu)》（C語言版） 清華大學(xué)出版社 2002 [2] 殷人昆等著 《數(shù)據(jù)結(jié)構(gòu)》（C++版） 清華大學(xué)出版社 2001 [3] 金遠(yuǎn)平著 《數(shù)據(jù)結(jié)構(gòu)》（C++描述） 清華大學(xué)出版社 2005 [4] 許卓群等著 《數(shù)據(jù)結(jié)構(gòu)與算法》 高等教育出版社 2004 [5] Frank M.Carrano 等著 《數(shù)據(jù)結(jié)構(gòu)與Ｃ++高級教程》清華大學(xué)出版社 2004 [6] 嚴(yán)蔚敏、吳偉民 《數(shù)據(jù)結(jié)構(gòu)習(xí)題集》（C語言版）清華大學(xué)出版社 14