數(shù)據(jù)結構課程設計

PAGEPAGE2景德鎮(zhèn)陶瓷學院課程設計報告課程名稱：數(shù)據(jù)結構課程設計設計題目：1、通訊錄管理9、撲克牌游戲14、拓撲排序班級：計算機科學與技術1班學生姓名:游君學號:202110510114起止日期:2021年6月23日~2021年6月30日指導教師:李娟徐星題目1、通訊錄管理1、問題描述通訊錄管理是一個比較實用的小型管理系統(tǒng)，該系統(tǒng)用于對通訊人員的姓名、號碼的管理。該設計采用菜單作為應用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語句是實現(xiàn)結構化程序設計的基礎。該設計的任務是利用一個簡單實用的菜單，通過菜單項進行選擇，實現(xiàn)和完成通訊錄管理中常用的幾個不同的功能。2、要求功能要求：建立通訊錄的鏈表；插入通訊錄信息；查詢通訊錄信息；刪除通訊錄信息；輸出通訊錄信息。規(guī)定：輸入通訊錄的信息：編號、姓名、性別、、地址界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。存儲結構：利用單鏈表存儲通訊錄信息，同時要求將通訊信息相關數(shù)據(jù)存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明。系統(tǒng)分析與概要設計根據(jù)問題描述和要求，系統(tǒng)要求能夠按姓名查找、增加、刪除和保存各學生的信息。確定程序應該具備如下功能：“查詢學生信息”、“增加學生信息”、“修改學生信息”“刪除學生信息”、“數(shù)據(jù)存盤”基本模塊。系統(tǒng)可以將學生信息數(shù)據(jù)保存到磁盤文件student.txt，從而可以通過磁盤文件讀出學生數(shù)據(jù)信息，為了便于統(tǒng)計在生成學生信息時同時生成學生編號，這樣每輸入一個學生信息編號順序加1，這樣也方便了管理員查詢學生信息。詳細設計和編碼數(shù)據(jù)類型定義根據(jù)系統(tǒng)要求，可以將姓名和和聯(lián)系通訊地址定義為字符型。各模塊算法描述查詢學生信息：Que_name()輸入要查詢的學生姓名，比較名字與保存的信息是否相同，若相同則查找到，否則，沒查找到。增加學生信息：Add()輸入要添加的學生信息并保存。刪除學生信息：Del()輸入要刪除的學生姓名，若與數(shù)據(jù)相同則刪除，否則輸出查找不到該信息。修改學生信息：Mod()輸入要修改的學生姓名，輸入要修改的信息，并確認。數(shù)據(jù)存盤：Sav()創(chuàng)建文件，將信息寫入文件。程序關鍵算法流程圖主函數(shù)流程（2)某操作算法流程Student::Add()(3)Student::Del()（4)Student::Mod()(5)Student::Que_name()Student::Sav()(7)Student::Load()三、調試結果運行界面錄入信息界面查詢信息界面修改信息界面源代碼：#include<iostream>#include<string.h>#include<windows.h>usingnamespacestd;structstudent{charnum[20];charname[20];charaddress[50];charsex[20];chartelphone[20];}student[2021];//定義學生類結構體voidMenu();//聲明菜單函數(shù)voidInput();//聲明錄入函數(shù)voidSav(int);//聲明保存函數(shù)intLoad();//聲明信息導入函數(shù)voidQue_name();//聲明按姓名查找函數(shù)voidDel();//聲明刪除函數(shù)voidMod();//聲明修改函數(shù)voidScan();//聲明瀏覽函信息數(shù)voidAdd();//聲明添加函數(shù)voidMenu()//菜單函數(shù){cout<<"\t*******歡迎來到景德鎮(zhèn)陶瓷學院學生通訊錄信息管理系統(tǒng)!*******"<<endl;cout<<"\t**請按要求正確錄入學生的通訊錄信息**"<<endl;cout<<"\t**1.錄入相關學生通訊錄信息**"<<endl;cout<<"\t**2.保存相關學生通訊錄信息**"<<endl;cout<<"\t**3.按姓名查找相關學生通訊錄信息**"<<endl;cout<<"\t**4.修改相關學生通訊錄信息**"<<endl;cout<<"\t**5.刪除相關學生通訊錄信息**"<<endl;cout<<"\t**6.添加相關學生通訊錄信息**"<<endl;cout<<"\t**7.退出該學生通訊錄信息系統(tǒng)**"<<endl;cout<<"\t*****************歡迎您的光臨**************************"<<endl;}voidmain()//主函數(shù)的實現(xiàn){intn;loop: Menu();//調用菜單函數(shù) cout<<"請輸入您所要進行的操作過程的序號（1-7）:"; cin>>n; system("cls");switch(n) { case1:cout<<"請輸入相關學生通訊信息:"<<endl;Input();system("cls");gotoloop; case2:cout<<"請保存相關學生通訊信息:"<<endl;Sav(n);gotoloop; case3:cout<<"按姓名查找相關學生通訊信息:"<<endl;Que_name();gotoloop; case4:cout<<"修改相關學生通訊信息:"<<endl;Mod();gotoloop; case5:cout<<"刪除相關學生通訊信息:"<<endl;Del();gotoloop; case6:cout<<"添加相關學生通訊信息:"<<endl;Add();gotoloop;//用goto語句調至指定行 default:break; }cout<<"\t\t\t*********歡迎您的使用!**********"<<endl;}voidInput()//學生通訊信息錄入函數(shù){inti,m;cout<<"請輸入您所要輸入的學生通訊信息的個數(shù)(1-2021):";cin>>m;for(i=0;i<m;i++){ cout<<"請輸入學生的編號："<<endl; cin>>student[i].num; cout<<"請輸入通訊錄中學生的姓名："<<endl; cin>>student[i].name; cout<<"請輸入通訊錄中學生的性別："<<endl; cin>>student[i].sex; cout<<"請輸入通訊錄中學生的號碼："<<endl; cin>>student[i].telphone; cout<<"請輸入通訊錄學生的地址(格式如***省**市**縣**鄉(xiāng))："<<endl; cin>>student[i].address; cout<<"該學生的通訊信息已經(jīng)輸入完畢，請繼續(xù)輸入下一個學生通訊信息!"<<endl;}}voidSav(intm)//如何寫入信息？保存通訊錄文件函數(shù){inti;FILE*fp;if((fp=fopen("E:\\student.dat","wb"))==NULL)//創(chuàng)建文件并判斷是否能打開{cout<<"該文件打開失敗。"<<endl;exit(0);}for(i=0;i<m;i++) //將內存中學生通訊信息輸入到磁盤里去if(fwrite(&student[i],sizeof(structstudent),1,fp)!=1)//申請空間，寫入學生信息，為何有個1???{ cout<<"信息寫入失??！"<<endl;fclose(fp);}}voidQue_name()//按姓名查找函數(shù){charname1[10];inti,m;m=Load();cout<<"請輸入您要查詢學生通訊信息的名字"<<endl;cin>>name1;for(i=0;i<m;i++)if(strcmp(name1,student[i].name)==0) { cout<<"查找到該學生的通訊信息如下："<<endl; Scan(); break; }else{ cout<<"抱歉，查無此人！"<<endl; return;}}voidScan(){inti,m;m=Load();//不明白這個，把函數(shù)賦給m嗎？cout<<"輸出學生通訊信息如下："<<endl;for(i=0;i<m;i++)cout<<"編號:"<<student[i].num<<""<<"姓名："<<student[i].name<<""<<"性別："<<student[i].sex<<""<<"聯(lián)系:"<<student[i].telphone<<""<<"通訊地址："<<student[i].address<<""<<endl;}intLoad()//導入函數(shù){FILE*fp;inti=0;if((fp=fopen("E:\\student.dat","rb"))==NULL){ cout<<"文件打開失??！"<<endl; exit(0);}else{ do { fread(&student[i],sizeof(structstudent),1,fp); i++; }while(feof(fp)==0);} return(i); fclose(fp);}voidDel()//刪除函數(shù){intm;inti,j,n,t,f;charname1[10]; m=Load();cout<<"查看學生的通訊信息如下："<<endl;Scan();//調用瀏覽函數(shù)cout<<"請輸入您想刪除的通訊信息的名字："<<endl; cin>>name1;for(f=1,i=0;f&&i<m;i++){ if(strcmp(student[i].name,name1)==0) { cout<<"查找到該學生的通訊信息如下："<<endl; Scan(); cout<<"如果要刪除該生信息，請按1，否則按0"<<endl; cin>>n; if(n==1)//如果刪除，則其他的信息都向前移一行 { for(j=i;j<m-1;j++) { student[j]=student[j+1]; } f=0; } } }if(!f)m=m-1;//??? elsecout<<"抱歉！未找到該生信息。"<<endl; cout<<"輸出其他學生通訊信息如下："<<endl; Scan();//調用瀏覽函數(shù) Sav(m);//調用保存函數(shù) cout<<"如果您想繼續(xù)刪除通訊信息，請按1，否則按0。"<<endl; cin>>t; switch(t) { case1:Del();break; case0:break; default:break; };}voidMod()//修改函數(shù){ charnum[20],tel[20],sex[20]; charname[20]; charaddress[50]; intb,c,i,n,t,f; intm=Load();//導入文件內的信息 cout<<"該學生先前的通訊信息為："<<endl; Scan();//調用瀏覽函數(shù) cout<<"請輸入您想要修改通訊信息的名字："<<endl; cin>>name; for(f=1,i=0;f&&i<m;i++) { if(strcmp(student[i].name,name)==0) { cout<<"查找到該學生的通訊信息如下："<<endl; Scan(); cout<<"確實要修改該生通訊信息請按1，否則按0"<<endl; cin>>n; if(n==1) { cout<<"請輸入您要修改的項目（1-編號2-姓名3-性別4-聯(lián)系5-通訊地址）:"<<endl; cin>>c; if(c>6||c<1) cout<<"抱歉，您的輸入有誤，請從新輸入。"<<endl; } f=0; } } if(f==1)cout<<"抱歉，未找到此人！"<<endl; do { switch(c)//因為當找到第i個學生時,for語句后i自加了1,所以下面的應該把改后的信息賦值給第i-1個人 { case1:cout<<"將該生的編號改為："; cin>>num; strcpy(student[i].num,num); break; case2:cout<<"將該生的姓名改為："; cin>>name; strcpy(student[i].name,name); break; case3:cout<<"將該生的性別改為："; cin>>sex; strcpy(student[i].sex,sex); break; case4:cout<<"將該生的聯(lián)系改為："; cin>>tel; strcpy(student[i].telphone,tel); break; case5:cout<<"將該生的通訊地址改為："; cin>>address; strcpy(student[i].address,address); break; } cout<<endl; cout<<"確認您所修改的信息請按1，從新修改請按0："<<endl; cin>>b; }while(b==0);Sav(m); cout<<"修改后所有信息如下;"<<endl; Scan(); cout<<"如果您想繼續(xù)修改請按1，否則按0："<<endl; cin>>t; switch(t) { case1:Mod();break; case0:break; default:break; }}voidAdd()//添加函數(shù){ intn=Load(); inti,m; cout<<"請輸入您要添加的學生通訊信息的個數(shù)："<<endl; cin>>m; for(i=n;i<m+n;i++) { cout<<"請輸入該生的編號："; cin>>student[i].num; cout<<endl;; cout<<"請輸入該生的姓名："; cin>>student[i].name; cout<<endl; cout<<"請輸入該生的性別："; cin>>student[i].sex; cout<<endl; cout<<"請輸入該生的聯(lián)系："; cin>>student[i].telphone; cout<<endl; cout<<"請輸入該生的通訊地址："; cin>>student[i].address; cout<<endl; system("cls"); cout<<"該生的通訊信息添加完畢，請輸入您要添加的下一位學生的通訊信息！"<<endl; } Sav(m+n); cout<<"學生通訊信息添加完畢，查看信息如下："<<endl; Scan();}題目9、撲克牌游戲需求分析1.1課程設計題目紙牌游戲：[問題描述]編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的直到以52為基數(shù)的翻過，輸出：這時正面向上的牌有哪些？1.2課程設計目的及其任務1.2.1目的熟練掌握數(shù)據(jù)結構這門課程，掌握經(jīng)性表、棧、隊列、串、數(shù)組、廣義表、樹和二叉樹以及圖等基本類型的數(shù)據(jù)結構及其應用。進一步熟悉抽象數(shù)據(jù)類型的定義和實現(xiàn)、如何利用數(shù)組的動態(tài)分酚實現(xiàn)順序結構、繼承的實現(xiàn)方式。學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構、想念結構及基相應的算法并初步掌握算法的時間分析和空間分析的技術?；菊莆粘绦蛟O計的基本思路和方法。利用所學的基本知識和技能，解決簡單的程序設計問題各算法描述培養(yǎng)我們的數(shù)據(jù)抽象能力。1.2.2任務1、課程設計題目每組一題，每個學生必須獨立完成；2、對課題進行功能分析，選擇合適的數(shù)據(jù)結構，并定義數(shù)據(jù)結構的結構體；3、根據(jù)程序所要完成的基本要求，設計出完整的算法；4、編程簡練，程序功能齊全，能夠正確的運行；5、每人提交一份報告，并按照報告有固定的模板和要求書寫報告。在課程設計過程中要求重視課程設計環(huán)節(jié)，用嚴謹、科學、踏實的工作態(tài)度對待課程設計的每一項任務，按照課程設計的題目要求，獨立的完成各項任務，按時到機房上機，認真編寫課程設計報告。1.3課程設計思想首先必須確定實現(xiàn)這個課程設計的主算法是使用鏈式存儲結構還是棧又或是數(shù)組和廣義表。根據(jù)題目要求需要實現(xiàn)的功能有：1、數(shù)據(jù)錄入：輸入各種數(shù)據(jù)；此處即創(chuàng)建鏈表的過程，調用一個成員函數(shù)負值。在此處還有一個方法實現(xiàn)，即先輸入數(shù)據(jù)，然后再調用構造實現(xiàn)。2、數(shù)據(jù)統(tǒng)計：存儲方式的選擇，是使用鏈式存儲結構還是棧又或是數(shù)組和廣義表；遵守先定義后調用的原則；數(shù)組定義時注意下標的起始值和上限；鏈表定義時注意結點中的項；準確運用結點。3、數(shù)據(jù)輸出：按要求的格式打印調用do循環(huán)和for循環(huán)4、查找,修改,刪除：這三個功能的核心是尋找成員，先遍歷鏈表，然后尋找對應的ID號來找到結點，然后再對結點實行刪除，修改操作。1.4軟件運行環(huán)境及開發(fā)工具軟件運行的環(huán)境是WindowsXP開發(fā)工具是MicrosoftVisualC++6.0概要設計2.所用方法及其原理說明1.當每個號碼每次遇到是某個數(shù)的倍數(shù)時，都會相應的翻一次，這樣，每張牌會翻的次數(shù)就各不一樣，可能很多次，也可能只有一兩次，結果就只是要輸出在經(jīng)過各個不同次數(shù)的翻牌后，正面向上的牌都有哪幾個。將所有的牌建立一個數(shù)組，運用for的循環(huán)嵌套執(zhí)行以下操作：把52張牌初始化成正面朝上、控制基數(shù)和翻牌次數(shù)，判斷最終的紙牌朝向并打印出結果，具體實現(xiàn)算法參看詳細設計。詳細設計3.詳細設計方案源代碼：#include<stdio.h>voidmain(){ inti,j,a[52]; for(i=2;i<=52;i++) for(j=i-1;j<52;j+=i) a[j]=!a[j];printf("正面向上的牌有:"); for(i=0;i<52;i++) if(a[i]) printf("%4d",i+1);}第四章調試和操作說明4.調試運行后的菜單展示圖2調試圖第五章總結與體會5.1本文的主要工作1．這題的時間復雜度是T（n）=O（n2）。2．雖然本次程序的題目難度與其他問題相比不是很高，但仍有很多問題我們是很容易忽視的，其一：在理解題目的要求時，注意翻牌的次數(shù)可能有多次；其二：for循環(huán)的嵌套使用在書寫時很容易漏掉大括弧。3．運用更多的基礎算法，使得程序和算法思想得到更好的表現(xiàn)。5.2心得體會這個學期是我第一次接觸“課程設計”，在完成設計的過程中，我遇到了一系列的問題，能明顯感覺到自己在很多方面的不足，但另一方面，問題是要分析解決的，找出問題以便為完善學習計劃，改變學習內容與方法提供實踐依據(jù)。通過這次課程設計，加強了我們的動手、思考和解決問題的能力。在設計過程中，經(jīng)常會遇到這樣那樣的情況，總覺得思路對著，可是就是行不通，所以耗費時間比較多。在做課程設計的同時，我對課本知識也得到了鞏固和加強，由于課本上的東西太多，平時課間的學習并不能很好的理解和運用各個知識點的功能，而且考試內容有限，所以在這次課程設計過程中，我們了解了很多知識點的功能，并且對數(shù)據(jù)結構有了更多的了解。在平時看課本的過程中，有些問題老是弄不明白，做完課程設計，有些問題就迎刃而解了。而且還可以記住很多東西。通過動手實踐讓我們映象深刻，知識來源于實踐。實踐是認識的動力和最終目的，也是檢驗真理的唯一標準。所以這次課程設計對我們的幫助很大。題目14拓撲排序1、問題描述拓撲排序可判斷AOV網(wǎng)絡中是否存在回路，使的所有活動可排成一個線性序列，使用每個活動的所有前驅活動都排在該活動的前面。2、要求（1）在有向圖中選一個沒有前驅的頂點，輸出；（2）從有向圖中刪除該頂點及其該頂點出發(fā)的所有邊；（3）重復以上兩個步驟，直至全部頂點輸出；注：輸出所有拓撲排序可加分。3、實驗內容：拓撲排序。任意給定一個有向圖，設計一個算法，對它進行拓撲排序。拓撲排序算法思想：a.在有向圖中任選一個沒有前趨的頂點輸出；b.從圖中刪除該頂點和所有以它為尾的弧；c.重復上述a、b，直到全部頂點都已輸出，此時，頂點輸出序列即為一個拓樸有序序列；或者直到圖中沒有無前趨的頂點為止，此情形表明有向圖中存在環(huán)。試驗分析：在拓撲排序的過程之中，輸入入度為零（即沒有前趨）的頂點，同時將該頂點的直接后繼的入度減1。、查鄰接表中入度為零的頂點，并進棧。（2）、當棧為空時，進行拓撲排序。（a）、退棧，輸出棧頂元素V。（b）、在鄰接表中查找Vj的直接后繼Vk，將Vk的入度減一，并令入度減至零的頂點進棧。、若?？諘r輸出的頂點數(shù)不是N個則說明有向回路，否則拓撲排序結束。為建立存放入度為零的頂點的棧，不需要另分配存儲單元，即可借入入度為零的數(shù)據(jù)域。一方面，入度為零的頂點序號即為表頭結點的序號，另一方面，借用入度為零的數(shù)據(jù)域存放帶鏈棧的指針域（下一個入度的頂點號）。源程序：#include<iostream>#include<stack>usingnamespacestd;#defineMAXV50stack<int>mystack;intindegree[MAXV];structnode{intadjvex;node*next;}AdjList[MAXV];voidCreate(nodeAdjList[],intn,intm)//鄰接表建表函數(shù)，n代表頂點數(shù)，m代表邊數(shù){inti;node*p;for(i=0;i<=n-1;i++){AdjList[i].adjvex=i;AdjList[i].next=NULL;}for(i=0;i<=m-1;i++){cout<<"請輸入第"<<i<<"條邊:";intu,v;cin>>u>>v;p=newnode;p->adjvex=v;p->next=AdjList[u].next;AdjList[u].next=p;}}voidprint(intn)//鄰接表打印函數(shù){inti;node*p;for(i=0;i<=n-1;i++){p=&AdjList[i];while(p!=NULL){cout<<p->adjvex<<'';p=p->next;}cout<<endl;}}voidTopSort(nodeAdjList[],intn){inti;node*p;memset(indegree,0,sizeof(indegree));for(i=0;i<=n-1;i++){p=AdjList[i].next;while(p!=NULL){indegree[p->adjvex]++;p=p->next;}}for(i=0;i<=n-1;i++){if(indegree[i]==0)mystack.push(i);}intcount=0;while(mystack.size()!=0){i=mystack.top();mystack.pop();cout<<i<<'';count++;for