數(shù)據(jù)結構課程設計報告 敢死隊問題

1、 課 程 設 計（數(shù)據(jù)結構）班 級計科1003姓 名 學 號1011051093 指導教師 二一一年一月十日課程設計任務書及成績評定課題名稱 敢死隊問題 、題目的目的和要求： 鞏固和加深對數(shù)據(jù)結構的理解，通過上機實驗、調試程序，加深對課本知識的理解，最終使學生能夠熟練應用數(shù)據(jù)結構的知識寫程序。（1）通過本課程的學習，能熟練掌握幾種基本數(shù)據(jù)結構的基本操作。（2）能針對給定題目，選擇相應的數(shù)據(jù)結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。 、設計進度及完成情況日 期內(nèi) 容12.31-1.1選取參考書，查閱有關文獻資料，完成資料搜集和系統(tǒng)分析工作。1.11.2創(chuàng)建相關數(shù)據(jù)結構,錄入

2、源程序。1.21.3調試程序并記錄調試中的問題，初步完成課程設計報告。1.4上交課程設計報告打印版并進行課程設計答辯，要求每個同學針對自己的設計回答指導教師3-4個問題?？己私Y束后將課程設計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。、主要參考文獻及資料1 嚴蔚敏 數(shù)據(jù)結構（c語言版）清華大學出版社 19992 嚴蔚敏 數(shù)據(jù)結構題集（c語言版）清華大學出版社 19993 徐寶文等譯 c語言程序設計 清華大學出版社4 與所用編程環(huán)境相配套的c語言或c+相關的資料、成績評定：設計成績： （教師填寫）指導老師： （簽字）二一一 年 一 月 十 日目 錄第一章 概述1第二章 系統(tǒng)分析2第三章 概要設計3

3、第四章 詳細設計4第五章 運行與測試9第六章 總結與心得13參考文獻14第一章 概述課程設計是實踐性教學中的一個重要環(huán)節(jié)，它以某一課程為基礎，可以涉及和課程相關的各個方面，是一門獨立于課程之外的特殊課程。課程設計是讓同學們對所學的課程更全面的學習和應用，理解和掌握課程的相關知識。數(shù)據(jù)結構是一門重要的專業(yè)基礎課，是計算機理論和應用的核心基礎課程。數(shù)據(jù)結構課程設計，要求學生在數(shù)據(jù)結構的邏輯特性和物理表示、數(shù)據(jù)結構的選擇和應用、算法的設計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設計方法以及上機操作等基本技能和科學作風方面受到比較系統(tǒng)和嚴格的訓練。在這次的課程設計中我選擇的題目是圖書管理

4、。傳統(tǒng)的人工圖書管理，基本業(yè)務活動有對一本書的采編入庫、清除庫存、借閱和歸還等等，但是人工統(tǒng)計操作起來效率相對來說要低，也容易出錯。但是現(xiàn)在這些業(yè)務借助計算機系統(tǒng)完成后，效率可以得到提高，也可以減少出錯的幾率?？梢允箞D書管理的日常業(yè)務更加的方便，迅捷，減少很多勞動量。課程設計的目的意義：加深對循環(huán)隊列和數(shù)組的理解，以及對循環(huán)隊列和數(shù)組的實際應用，加強自己的動手操作能力，增加對課程的興趣，而不是枯燥的看課本。課程設計的問題：敢死隊問題 有m個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一個戰(zhàn)士上去。現(xiàn)給每個戰(zhàn)士編一個

5、號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當數(shù)到5時，對應的戰(zhàn)士就去執(zhí)行任務，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務，再從下一個戰(zhàn)士開始數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務。以此類推，直到任務完成為止。 排長是不愿意去的，假設排長為1號，請你設計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務。第二章 系統(tǒng)分析1 敢死隊問題包括：兩個數(shù)據(jù)的輸入，一個是隊員的數(shù)量，另一個是模擬的形式。由于問題給出的數(shù)數(shù)的數(shù)量為5 ，所以k 值就默認為5 ，不再設置數(shù)據(jù)輸入。故重點是要完成兩種數(shù)據(jù)結構形式的刪除，循環(huán)標記等操作。2 演示程序是以用戶于計算機的對話方式執(zhí)行，這

6、需要調用一個清屏函數(shù)來完成使用者與計算機語言之間界面的處理。3 程序執(zhí)行時的命令：本程序為了使用時的方便，采用阿拉伯數(shù)字的方式來完成程序的等各種選擇輸入，幾乎不用輸入什么特殊的命令。（要注意輸入時必須用數(shù)字，否者可能會引起一些死循環(huán)）5. 測試數(shù)據(jù)。 1 5 13 數(shù)據(jù)運行結果 在第五章有詳細的截圖第三章 概要設計1. 數(shù)據(jù)結構類型： 一種是循環(huán)隊列，另一種是數(shù)組形式 其中循環(huán)隊列操作只需要刪除操作，用數(shù)組形式處理和運算上則較復雜些 因此，循環(huán)隊列占優(yōu)勢2. 程序總體上分為兩大塊，一塊是循環(huán)隊列的模擬，一塊是數(shù)組形式的模擬 這兩種形式功能都是模擬每個開始數(shù)數(shù)的位置對員的死亡順序，其中循環(huán) 隊列

7、的函數(shù)接口為：lianbiao(n) ，數(shù)組的函數(shù)接口為：array(n);兩模塊算法基本一致，數(shù)據(jù)結構形式不同而已算法概述：for(int i=1;i安全的位置； 第四章 詳細設計1：存儲結構形式 struct node int data; node *next;struct nodel int data;sqlistn;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 coutdatan

8、ext; 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; coutnn報數(shù)的位置為kdata=1; head-next=head; int j=1; while(+jdata=j; p-next=t-next; t-next=p; t=t-next; t=head; node *p=head,*q;/ 設置p q 指針 while(p-next!=head) p=p-next; q=head; while(-k) /循環(huán)找開始的位

9、置 p=p-next; q=q-next; if(del(p,q)=1) /判斷位置是否安全 coutendli位置安全n; flag=i; else coutendli位置不安全n; continue ; if(flag) coutnn安全位置是： flagnn; else cout所有的位置都不安全13) key-=13; if(sqkey.data!=0) k-; if(key=1) if(sum=1) return 1; else return 0; else sum-=sqkey.data; sqkey.data=0; coutkey13) key-=13; / coutsqkey.

10、data key13) key-=13; / coutsqkey.data keyendl; while(1);void array(int n) int i,flag=0; for( i=1;i=n;i+)/ 循環(huán)找出安全的開始位置 int k=i; coutnn報數(shù)的位置為k時的排長之前的人員死亡順序:n; int j=1,sum=0; while(j = n) /構造循環(huán)隊列 sqlistj.data=j; sum+=j+; if( delx(sqlist,k,n,sum)=1) coutendli位置安全n; flag=i;/coutflagendl; else coutendlk位置

11、不安全n; /coutflagendl; cout 所有人員情況： 0 表示已死 其它表示幸存者編號nn; for(int xx=1;xx=n;xx+) coutsqlistxx.data ; coutendl; if(flag) cout安全的位置是：flagnnn; else coutnn無安全位置可選nendl;/ 漏洞檢測3 ： 主函數(shù)部分int main() cout-敢死隊之死亡游戲模擬-n; int n,cas; cout作為一名行政長官，報數(shù)開始位置很重要nendl; cout下面將模擬每個開始位置的人員死亡順序-n; /system(cls); do coutcas; if(

12、cas3|cas=0) cout輸入錯誤n;continue; coutn請輸入隊員的數(shù)量n; switch(cas) case 1: lianbiao(n);break; case 2: array(n); break; default : cout輸入錯誤n;break; coutss; if(ss=3) break; else system(cls); while(cas!=3); return 0;第五章 運行與測試1. 調試程序的過程中遇到什么問題 處理過程中經(jīng)常忽視特殊位置的處理 像開始位置為1時，循環(huán)隊列就會出現(xiàn)bugs而數(shù)組形式中刪除操作不容易處理，用0 標記來代替 刪除操作，

13、在循環(huán)數(shù)數(shù)的時候經(jīng)常認為是5 ，但是 循環(huán)只需要進行4 次即可。而刪除操作的判斷則用sum 總和進行判斷，替換循環(huán)判斷，省時！操作方便，在4 層循環(huán)數(shù)數(shù)操作中容易漏 data 為0 的判斷以及 對 key 的變相取余3.測試數(shù)據(jù) 1 5 13 第6章 總結與心得 通過這一課程設計，加深了我對數(shù)據(jù)結構這門課程所學內(nèi)容的進一步的理解與掌握；同時，通過對循環(huán)隊列和數(shù)組的應用，使得我將計算機課程所學知識與實際問題很好地相聯(lián)接在了一起。在這次課程設計中，培養(yǎng)了我開發(fā)一個中小型程序的能力。調程序的時候，要穩(wěn)扎穩(wěn)打，每個子函數(shù)單調試后在和主函數(shù)鏈接，效率較高，不然都最后全在一塊，給調程序會帶來極大的不便！對于每個子函數(shù)都要考慮到一些特殊值。最大的收獲還是感覺到數(shù)據(jù)結構的實用性，不像看課本和考試那樣，總是參生厭煩情緒，離開發(fā)一些東西越來越近了，而不像以前那樣很遙遠?？傊谶@個的課程設計中，我的收獲還是挺大的，不僅對于專業(yè)課有了更好的認識，而且還學到做事要細心、全面