課 程 設(shè) 計（數(shù)據(jù)結(jié)構(gòu)）班 級計科1003姓 名 學(xué) 號1011051093 指導(dǎo)教師 二一一年一月十日課程設(shè)計任務(wù)書及成績評定課題名稱 敢死隊問題 、題目的目的和要求： 鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機(jī)實驗、調(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)而給出問題的正確求解過程并編寫代碼實現(xiàn)。 、設(shè)計進(jìn)度及完成情況日 期內(nèi) 容12.31-1.1選取參考書，查閱有關(guān)文獻(xiàn)資料，完成資料搜集和系統(tǒng)分析工作。1.11.2創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu),錄入源程序。1.21.3調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。1.4上交課程設(shè)計報告打印版并進(jìn)行課程設(shè)計答辯，要求每個同學(xué)針對自己的設(shè)計回答指導(dǎo)教師3-4個問題?？己私Y(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。、主要參考文獻(xiàn)及資料1 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（C語言版）清華大學(xué)出版社 19992 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（C語言版）清華大學(xué)出版社 19993 徐寶文等譯 C語言程序設(shè)計 清華大學(xué)出版社4 與所用編程環(huán)境相配套的C語言或C+相關(guān)的資料、成績評定：設(shè)計成績： （教師填寫）指導(dǎo)老師： （簽字）二一一 年 一 月 十 日目 錄第一章 概述1第二章 系統(tǒng)分析2第三章 概要設(shè)計3第四章 詳細(xì)設(shè)計4第五章 運(yùn)行與測試9第六章 總結(jié)與心得13參考文獻(xiàn)14第一章 概述課程設(shè)計是實踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(shè)計是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(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)隊列和數(shù)組的理解，以及對循環(huán)隊列和數(shù)組的實際應(yīng)用，加強(qiáng)自己的動手操作能力，增加對課程的興趣，而不是枯燥的看課本。課程設(shè)計的問題：敢死隊問題 有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(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è)計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務(wù)。第二章 系統(tǒng)分析1 敢死隊問題包括：兩個數(shù)據(jù)的輸入，一個是隊員的數(shù)量，另一個是模擬的形式。由于問題給出的數(shù)數(shù)的數(shù)量為5 ，所以k 值就默認(rèn)為5 ，不再設(shè)置數(shù)據(jù)輸入。故重點是要完成兩種數(shù)據(jù)結(jié)構(gòu)形式的刪除，循環(huán)標(biāo)記等操作。2 演示程序是以用戶于計算機(jī)的對話方式執(zhí)行，這需要調(diào)用一個清屏函數(shù)來完成使用者與計算機(jī)語言之間界面的處理。3 程序執(zhí)行時的命令：本程序為了使用時的方便，采用阿拉伯?dāng)?shù)字的方式來完成程序的等各種選擇輸入，幾乎不用輸入什么特殊的命令。（要注意輸入時必須用數(shù)字，否者可能會引起一些死循環(huán)）5. 測試數(shù)據(jù)。 1 5 13 數(shù)據(jù)運(yùn)行結(jié)果 在第五章有詳細(xì)的截圖第三章 概要設(shè)計1. 數(shù)據(jù)結(jié)構(gòu)類型： 一種是循環(huán)隊列，另一種是數(shù)組形式 其中循環(huán)隊列操作只需要刪除操作，用數(shù)組形式處理和運(yùn)算上則較復(fù)雜些 因此，循環(huán)隊列占優(yōu)勢2. 程序總體上分為兩大塊，一塊是循環(huán)隊列的模擬，一塊是數(shù)組形式的模擬 這兩種形式功能都是模擬每個開始數(shù)數(shù)的位置對員的死亡順序，其中循環(huán) 隊列的函數(shù)接口為：lianbiao(n) ，數(shù)組的函數(shù)接口為：array(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;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 cout<<q->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<<"nn報數(shù)的位置為"<<k<<"時的排長之前的人員死亡順序:n" node *head=new node,*t=head; head->data=1; head->next=head; int j=1; while(+j<=n) /構(gòu)造循環(huán)隊列 node *p=new node; p->data=j; p->next=t->next; t->next=p; t=t->next; 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) /判斷位置是否安全 cout<<endl<<i<<"位置安全n" flag=i; else cout<<endl<<i<<"位置不安全n" continue ; if(flag) cout<<"nn安全位置是： "<<flag<<"nn" else cout<<"所有的位置都不安全"<<endl; /漏洞檢測int delx(nodel sq,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(sqkey.data!=0) k-; if(key=1) if(sum=1) return 1; else return 0; else sum-=sqkey.data; sqkey.data=0; cout<<key<<" " key+;if(key>13) key-=13; / cout<<sqkey.data<<" "<<key<<endl; while(sqkey.data=0) key+; if(key>13) key-=13; / cout<<sqkey.data<<" "<<key<<endl; while(1);void array(int n) int i,flag=0; for( i=1;i<=n;i+)/ 循環(huán)找出安全的開始位置 int k=i; cout<<"nn報數(shù)的位置為"<<k<<"時的排長之前的人員死亡順序:n" int j=1,sum=0; while(j <= n) /構(gòu)造循環(huán)隊列 sqlistj.data=j; sum+=j+; if( delx(sqlist,k,n,sum)=1) cout<<endl<<i<<"位置安全n" flag=i;/cout<<flag<<endl; else cout<<endl<<k<<"位置不安全n" /cout<<flag<<endl; cout<<" 所有人員情況： 0 表示已死 其它表示幸存者編號nn" for(int xx=1;xx<=n;xx+) cout<<sqlistxx.data<<" " cout<<endl; if(flag) cout<<"安全的位置是："<<flag<<"nnn" else cout<<"nn無安全位置可選n"<<endl;/ 漏洞檢測3 ： 主函數(shù)部分int main() cout<<"-敢死隊之死亡游戲模擬-n" int n,cas; cout<<"作為一名行政長官，報數(shù)開始位置很重要n"<<endl; cout<<"下面將模擬每個開始位置的人員死亡順序-n" /system("cls"); do cout<<"請選擇模擬的形式：n 1：鏈表 2：數(shù)組 3: 退出程序n" cin>>cas; if(cas>3|cas<=0) cout<<"輸入錯誤n"continue; cout<<"n請輸入隊員的數(shù)量"<<endl; cin>>n; switch(cas) case 1: 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)試程序的過程中遇到什么問題 處理過程中經(jīng)常忽視特殊位置的處理 像開始位置為1時，循環(huán)隊列就會出現(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)一步的理解與掌握；同時，通過對循環(huán)隊列和數(shù)組的應(yīng)用，使得我將計算機(jī)課程所學(xué)知識與實際問題很好地相聯(lián)接在了一起。在這次課程設(shè)計中，培養(yǎng)了我開發(fā)一個中小型程序的能力。調(diào)程序的時候，要穩(wěn)扎穩(wěn)打，每個子函數(shù)單調(diào)試后在和主函數(shù)鏈接，效率較高，不然都最后全在一塊，給調(diào)程序會帶來極大的不便！對于每個子函數(shù)都要考慮到一些特殊值。最大的收獲還是感覺到數(shù)據(jù)結(jié)構(gòu)的實用性，不像看課本和考試那樣，總是參生厭煩情緒，離開發(fā)一些東西越來越近了，而不像以前那樣很遙遠(yuǎn)?？傊?，在這個的課程設(shè)計中，我的收獲還是挺大的，不僅對于專業(yè)課有了更好的認(rèn)識，而且還學(xué)到做事要細(xì)心、全面周到的重要性。參考文獻(xiàn):1 嚴(yán)蔚敏、吳偉民主編 數(shù)據(jù)結(jié)構(gòu)（C語言版） 清華大學(xué)出版社 20022 殷人昆等著 數(shù)據(jù)結(jié)構(gòu)（C+版） 清華大學(xué)出版社 20013 金遠(yuǎn)平著 數(shù)據(jù)結(jié)構(gòu)（C+描述） 清華大學(xué)出版社 2005 4 許卓群等著 數(shù)據(jù)結(jié)構(gòu)與算法 高等教育出版社 20045 Frank M.Carrano 等著 數(shù)據(jù)結(jié)構(gòu)與+高級教程清華大學(xué)出版社 20046 嚴(yán)蔚敏、吳偉民 數(shù)據(jù)結(jié)構(gòu)習(xí)題集（C語言版）清華大學(xué)出版社 14