C++數(shù)據(jù)結構 大作業(yè)課程設計正文

《C++數(shù)據(jù)結構 大作業(yè)課程設計正文》由會員分享，可在線閱讀，更多相關《C++數(shù)據(jù)結構 大作業(yè)課程設計正文（60頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、C++數(shù)據(jù)結構 大作業(yè)課程設計正文 第一篇：C++數(shù)據(jù)結構 大作業(yè)課程設計 C++/數(shù)據(jù)結構 大作業(yè)/課程設計——【校園導游咨詢】【停車場管理】娃娃們可以收著以后用 絕對純手工打造 內(nèi)含類模塊/一維指針數(shù)組（謹以此程序供大家參考。運行結果后面有貼圖） 目錄 【1】校園導游咨詢 程序設計源代碼 及 截圖 【2】停車場管理——方案一 程序設計源代碼 及 截圖 【3】停車場管理——方案二 程序設計源代碼 及 截圖 【1】【【校園導游咨詢】】 ###### (ps:該校園導游咨詢系統(tǒng)沒有輸入值，所有信息是都在class MGraph的構造函數(shù)中傳輸?shù)模倚@景點信息皆為【【上海電力學院】

2、】景點信息。請大家注意，直接從文章copy到visual stutio中會出現(xiàn)中文字符，注意刪除，推薦大家在一行語句的分號后面，點出光標，按一下delete鍵，然后按一下enter鍵，完成visual stutio的自動對齊，這樣程序看起來一目了然，更易于操作和更改) 【問題描述】 設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。 【基本要求】 (1)設計你所在學校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。 (2)為來訪客人提供圖中任意景點相關信息的查詢。 (3)為來訪客人提供圖中任意景點的

3、問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑。 【選作內(nèi)容】 (6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結果能提供詳盡的導向信息。 **************************【以下為類的定義】******************************** #include #include using namespace std; const int MaxSize=18; const int INFINITY=65535;//最大值無窮 class direction; template class MGraph; template class Verte

4、xNode//定義頭結點 { friend class MGraph; public: int vex;//頂點名稱 T vexname;//頂點名稱 T vexinf;//頂點信息 direction dir;//存放頂點方位信息的direction類的dir。 }; class direction { public: int ln;//存放在方向圖中的橫坐標，表示東西 int col;//存放在方向圖中的縱坐標，表示南北 }; template class MGraph//定義無向圖的鄰接矩陣 { public: MGraph(); //構造函數(shù)，初始化具有n個頂點的圖 voi

5、d printvexname();//顯示所有景點及景點代號 void printvexinf(int i);//顯示代號為i景點的名稱及信息 void printroad(int i,int j);//顯示景點i~j的最短路徑方案信息 void printdir(int i,int j);//顯示景點i到j的方向信息，如“向東100m，向南2021” VertexNode adjlist[MaxSize]; //存放景點全部信息的 景點類數(shù)組 int vertexNum,arcNum; //圖的頂點數(shù)和邊數(shù) void Root(int p,int q);//遞歸尋找pq間的最短路徑

6、 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//創(chuàng)建Path和Dist分別存放兩點間最短路徑的前驅(qū)節(jié)點，兩點間最短路徑長度 int Line[MaxSize];//Line存放路徑 int kkk;//Line[]數(shù)組的標記 private: T vertex[MaxSize]; //存放圖中頂點的數(shù)組 int arc[MaxSize][MaxSize];//存放圖中邊的數(shù)組 }; *************************【以下為類的實現(xiàn) 即類函數(shù)的定義】*********************************

7、** template MGraph::MGraph()//a[]為景點代號，b[]為景點名稱，c[]為景點信息，d[]為景點方位信息的橫坐標，e[]為景點方位信息的縱坐標 //s[]為存放景點鄰接矩陣信息的一維數(shù)組，根據(jù)其對稱性可以用公式賦值給二維數(shù)組arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,

8、0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0}; int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}; char* b[]={"南門","實驗樓","南圖","大活","睿思樓"

9、,"大禮堂", "南4教","知行樓","國交樓","南3教","南2教","南1教", "北圖","北3教","北4教","北2教","北1教","北門"}; char* c[]={"南校區(qū)正門","物理實驗樓","南校區(qū)圖書館","大學生活動中心", "教師辦公樓、醫(yī)務室及留學生公寓","大禮堂，用于舉辦各種文藝演出","南校區(qū)第4教學樓","實習基地，計算機房等", "國際交流中心，教職工餐廳","南校區(qū)第3教學樓","南校區(qū)第2教學樓","南校區(qū)第1教學樓", "北校區(qū)圖書館","北校區(qū)第3教學樓","北校區(qū)第4教學樓","北校區(qū)第2教學樓", "北校區(qū)第1教學樓","北校區(qū)正門"};

10、 int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8}; int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2}; int i,j; vertexNum=18; arcNum=30; for(i=0;i for (j=0; j void MGraph::printvexname() { int i; for(i=0;i template void MGraph::printvexinf(int i) { cout0)//即j在i的東邊 cout0) { Root(p,Path[p][q]); Root(Pa

11、th[p][q],q); } else { Line[kkk]=q; kkk++; } } template void MGraph::printroad(int i,int j) { int p,q,m,k,item1,item2; for(p=0;p0) for(q=0;q0) if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)) { Dist[p][q]=Dist[p][k]+Dist[k][q]; Path[p][q]=k; } cout""choice; return choice; } voi

12、d main() { MGraph mg; int funcchoice(); int fc; while(1) { fc=funcchoice(); if(fc==1) { int i; for(i=0;i>i; mg.printvexinf(i); } else if(fc==3) { int i,j; mg.printvexname(); cout>i>>j; mg.printroad(i,j); } else if(fc==4) break; else couti) stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出棧的元素數(shù)組逐個賦給臨時棧 pop

13、stacknumber=p.number;//將這個車牌號信息傳給int popstacknumber() popstacktime=p.time;//將該車的時間信息傳給double popstacktime() cs.top--;//棧頂指針回到原來位置 while(stemp.top>=0) cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//臨時棧出棧的元素逐個賦給原棧，完成先退再進的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入隊,隊內(nèi)進行調(diào)整，

14、返回隊內(nèi)位置 { car *p,*countp; int count(1);//count用于記錄車在過道上的位置信息，因隊列為鏈式的，所以進行循環(huán)累加 p=new car;//創(chuàng)建一個car類型的指針 p->number=cnum; p->time=ctime; p->next=NULL;//首先將指向存放car類型元素的數(shù)組初始地址置空 if (cq.front==NULL)//第一次入隊要判斷頭結點是否為空 { cq.front=cq.rear=p; } else {//尾插法插入元素 p->next=(cq.rear)->next; (cq.rear)->next=p; cq.re

15、ar=(cq.rear)->next; } countp=(cq.front)->next; while(countp!=NULL) { count++; countp=countp->next; }//count即車在過道上的位置，【從1開始計?。?！】 return count; } int parkingmanagement::popqueue(carqueue &cq)//出隊,隊內(nèi)進行調(diào)整，返回汽車車牌號 { car p; p.number=((cq.front)->next)->number;//cq隊里，從cq.front開始指向下一個元素的車牌號賦給car類型的車信息 p.ti

16、me=((cq.front)->next)->time;//cq隊里，從cq.front開始指向下一個元素的時刻 //賦給car類型的車信息 p.next=((cq.front)->next)->next;//cq隊里，從cq.front開始指向下一個元素的指針 //賦給car類型的車信息的下一個元素的指針 return p.number; cq.front=(cq.front)->next; } void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime) //車輛到達，根據(jù)輸入的車牌號、到

17、達時間，變更函數(shù)參數(shù)；并cout車位信息 { int pos; if(!(cs.full()))//如果棧未滿，車輛停入停車場 { int fl(0),i;//定義一個從0開始的標記fl for(i=0;inext; if(p->number==cnum)//在過道中找到要出去的車，則在隊列中刪除該car。 //后面的車輛依然順序排列，補足空位 { deletequeue(cq,count); if(count>Max) { coutnext) coutnext; p->next=q->next; delete q; } } *******************************【以

18、下是主程序】************************************ void print() { coutacc>>carnum>>cartime; if(acc=='A') park.arrival(cars,carq,carnum,cartime); else if(acc=='D') park.leave(cars,carq,carnum,cartime); else if(acc=='E') break; else coutcarnum=cnum; s->next=NULL; if(front==NULL)//空隊列，【【【新結點既是隊頭，又是隊尾】】】關鍵是！fro

19、nt指向第一個結點 { front=rear=s; } else { rear->next=s;//將結點s插入到隊尾 rear=s; } p=front; while(p!=NULL) { i++; p=p->next; }//i即車在過道上的位置，【從1開始計?。?！】 return i; } template T carQueue::DeQueue() { Node *p; if (front==NULL) coutnext;//將隊頭元素所在結點摘鏈 } return p->carnum; delete p;//將出隊進棧的車從隊列里刪除 } template bool carQ

20、ueue::Empty()//判斷是否為空，為空則返回1，不為空則返回0 { return front==NULL; } template carStack::carStack()//構造棧算法 :top(-1) {//建立一個最大尺寸為size的空棧 S=new carinfo[MaxSize];//創(chuàng)建存儲棧的數(shù)組 if(S==NULL) //分配不成功 { cerri) Stemp.S[++Stop]=S[top--]; hour=outctime-S[top].cartime; return hour; top--; while(Stop>=0) S[++top]=Stemp.

21、S[Stop--]; } template bool carStack::full() { return top==MaxSize-1; } template void carQueue::deletequeue(int i) { Node *p,*q; int j(1); p=front; while(p && jnext; j++; }//找到第i-1個結點(結點位置從1開始) if(!p||!p->next) coutnext=q->next; delete q; } } ******************************【以下為主函數(shù)】********************

22、******************* void outputpark()//系統(tǒng)功能選擇頁面，輸入泊車信息 { cout>arrive>>carnum>>cartime; if(arrive=='A') { if(cs.top!=MaxSize-1)//停車場內(nèi)有空位可以駛入 { cs.Pushcar(carnum,cartime); coutcarnum==carnum) { flagde=1; break; } pos++; p=p->next; } if(flagde) { coutdata);//輸出學生信息和成績信息 pNodeScore=pNodeScore->next;

23、 } } void Add() { p_node_score pNodeScore; // 定義一個節(jié)點 pNodeScore=(p_node_score)malloc(sizeof(node_score));//為節(jié)點分配存儲空間 printf("請輸入學號："); scanf("%s",pNodeScore->data.Number); printf("請輸入姓名："); scanf("%s",pNodeScore->data.Name); printf("請輸入語文成績："); scanf("%s",pNodeScore->data.Chinese); printf("請輸入英語成

24、績："); scanf("%s",pNodeScore->data.English); printf("請輸入高數(shù)成績："); scanf("%s",pNodeScore->data.Math); if(headScore==NULL) { //如果頭結點為空 headScore=pNodeScore; pNodeScore->next=NULL; } else { //如果頭結點不為空 pNodeScore->next=headScore; headScore=pNodeScore;//將頭結點新結點 } } void Input() { int n,i; printf("輸入幾

25、個學生的數(shù)據(jù)："); scanf("%d",&n); for(i=0;i Add(); printf("輸入成功！"); } int Delete() { p_node_score pNodeScore,p1; //p1為pNodeScore的前驅(qū) p1=headScore; if(p1==NULL) { printf("成績表中沒有數(shù)據(jù)！請先添加數(shù)據(jù)！\n"); return 0; } char DeleteNumber[2021 printf("請數(shù)入要刪除的學生學號:"); scanf("%s",DeleteNumber); if(strcmp(p1->data.Number,

26、DeleteNumber)==0) { //如果要刪除的結點在第一個 headScore=p1->next; pNodeScore=p1; printf("學號為%s的學生信息已經(jīng)刪除！\n",DeleteNumber); return 0; } else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf("學號為%s的學生信息已經(jīng)刪除！\n",D

27、eleteNumber); return 0; } else { //否則，結點向下一個，p1仍為pNodeScore的前驅(qū) p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf("沒有此學號的學生！"); } int Change() { p_node_score pNodeScore; pNodeScore=headScore; if(pNodeScore==NULL) { printf("成績表中沒有數(shù)據(jù)！請先添加數(shù)據(jù)！\n"); return 0; } char EditNumber[2021 prin

28、tf("請輸入你要修改的學生學號："); scanf("%s",EditNumber); while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比較兩字符串是否相等，相等則返回0 printf("原來的學生成績信息如下：\n"); //輸出原來的成績信息 printf(" 學號 | 姓名 | 語文成績 | 英語成績| 高數(shù)成績\n"); PrintScore(pNodeScore->data); printf("語文新成績:"); scanf("%s"

29、,pNodeScore->data.Chinese); printf("英語新成績:"); scanf("%s",pNodeScore->data.English); printf("高數(shù)新成績:"); scanf("%s",pNodeScore->data.Math); printf("成績已經(jīng)修改！"); return 0; } pNodeScore=pNodeScore->next; //如果不相等，pNodeScore則指向下一個結點 } printf("沒有此學號的學生！\n"); //如果找到最后都沒有，則輸出沒有此學號的學生 } int Find() { p

30、_node_score pNodeScore; pNodeScore=headScore; if(pNodeScore==NULL) { printf("成績表中沒有數(shù)據(jù)！請先添加數(shù)據(jù)！\n"); return 0; } char FindNumber[2021 printf("請輸入你要查找的學生學號："); scanf("%s",FindNumber); while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf("你要查找的學生成績信息如下：\n"); printf

31、(" 學號 | 姓名 | 語文成績 | 英語成績| 高數(shù)成績\n"); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next; } printf("沒有此學號的學生！\n"); } int main() //主函數(shù) { int choice=0; headScore=NULL; int c; do { system("color 2f"); //運行環(huán)境背景顏色. printf("\n\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\n\t

32、\t"); printf("\n\t\t\t 學生成績管理系統(tǒng) \t\t\t"); printf("\n\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\n\t\t"); printf("\n\t\t\t1.輸入成績信息\n\t\t\t2.輸出成績信息\n\t\t\t3.添加成績信息\n\t\t\t"); printf("4.修改成績信息\n\t\t\t5.刪除成績信息\n\t\t\t6.查詢成績信息\n\t\t\t7.退出"); printf("\n\n\t\t\t請選擇:"); scanf("%d",&c); switch(c)

33、{ case 1:system("cls");Input();break; case 2:system("cls");View();break; case 3:system("cls");Add();break; case 4:system("cls");Change();break; case 5:system("cls");Delete();break; case 6:system("cls");Find();break; case 7:system("cls");exit(0); } }while(1); return 0; } 運行界面如下： 第三篇：數(shù)據(jù)結構課程

34、設計 二○一三 ～二○一四 學年第 二 學期 信息科學與工程學院 綜合設計報告書 課程名稱： 數(shù)據(jù)結構課程設計 班 級： 學 號： 姓 名： 指導教師： 二○一四 年 六 月 一、實驗內(nèi)容 (一)、單鏈表：將若干城市的信息存入一個帶頭的單鏈表中，結點中城市信息包括城市的位置坐標，要求：給定一個城市名，返回其位置坐標；給定一個位置坐標P和一個距離D，返回所有與P的距離小于等于D的城市。 （二）、回文判斷：試寫出一個算法，判斷依次讀入的一個以@為結束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含有字符“&”，且序列2是序列1的逆序列。例如，“a+

35、b&b+a”是屬于該模式的字符序列。 （三）、樹和二叉樹：建立一棵用二叉鏈表方式存儲的二叉樹，并對其進行遍歷（先序，中序，后序）。打印輸出遍歷結果。 二、實驗過程 （一）、城市信息 1、根據(jù)題目，我們認為我們所編的程序需要實現(xiàn)以下功能： （1）、創(chuàng)建一個城市鏈表，能夠輸入城市信息，即城市名和城市位置坐標； （2）、能夠根據(jù)城市名查詢其位置坐標； （3）、根據(jù)離中心坐標距離查詢城市名； （4）、能夠插入城市信息； （5）、能夠刪除城市信息； （6）、能夠更新城市信息； （7）、執(zhí)行完畢，退出程序。 2、演示程序以用戶和計算機的對話方式執(zhí)行，即在在計算機終端上顯示“提示信息”之后，由用戶

36、在鍵盤上輸入演示程序中規(guī)定的運算命令；輸入相應的數(shù)據(jù)（濾去輸入中非法字符），運算結果顯示在其后。`測試數(shù)據(jù) 1）、輸入”1”調(diào)用函數(shù) Create()； 新建城市信息: fujian(1.1,2.2) beijing(3.3,4.4) shanghai(5,6) tianjing(7,8) nanjing(910，910) hangzhou(11,12) 輸入END鍵,退出. 2）、輸入”2”,調(diào)用函數(shù)FindCity()； 當鍵入城市名時,返回其城市坐標: 如：鍵入城市名”fujian”，返回坐標：1.10.2.2021）、輸入“3”調(diào)用函數(shù) FindCityDistance()

37、; 如：當給定坐標P（3.3，4.4）時,距離5時,就輸出所有與P的距離小于等于5的城市信息。 4）、輸入”4”,調(diào)用函數(shù)Insert().進行插入新城市信息操作； 如:插入城市信息:hainan(5,8)，當進行查找時,能看到插入城市的信息.證明插入成功. 5）、輸入”5”,調(diào)用函數(shù)Delete(),進行刪除操作： 6）、輸入”6”,調(diào)用函數(shù)UpdateCity(Store),進行更新操作； 7）、輸入”7”,退出. 3、源程序代碼： void Init(CityList *LHead) { LHead->Next = NULL; } //建立一個帶頭結點的單鏈線性表，LHead指向

38、頭結點。 void Insert(CityList *LHead) { CityList* newNode; //定義指針結構為cityList型 char m; newNode = (CityList*)malloc(sizeof(CityList)); //生成新結點 if(newNode == NULL) //驗證空間申請是否成功 { printf("內(nèi)存分配失敗\n"); return; //若分配內(nèi)存不成功，則返回繼續(xù)分配。 } printf("請輸入城市名\n"); scanf("%s",newNode->CityName);//指針的數(shù)據(jù)域 printf("請輸入城

39、市坐標x,y\n"); scanf("%f%c%f",&newNode->X,&m,&newNode->Y); //將城市信息填入新節(jié)點中 while(LHead->Next != NULL) { LHead = LHead->Next; }//如果非空，HLead指針的位置向后移 newNode->Next = LHead->Next; LHead->Next = newNode; } //將新節(jié)點插入鏈表 void Delete(CityList *LHead) { char delCity[10]; printf("請輸入要刪除的城市名\n"); scanf("%s",delCit

40、y); while(strcmp(LHead->Next->CityName,delCity ))//從LHead指向得頭結點的下一個結點開判斷結點中的城市名與輸入城市名是否相等。 { LHead = LHead->Next; //不相等則指針LHead下移，繼續(xù)查找 } LHead ->Next = LHead->Next->Next; //相等則刪除此節(jié)點 } void Create(CityList *LHead) { char sign[2021 //定義輸入信息類型及長度 printf("輸入END退出,輸入其余值繼續(xù)\n"); //當輸入END時，在任意輸入，則退出此操作

41、 scanf("%s",sign); while(strcmp(sign,"END")) ////當輸入END時，再任意輸入，則退出此操作 { Insert(LHead); printf("輸入END退出,輸入其余值繼續(xù)\n"); scanf("%s",sign); } } void FindCity(CityList* LHead) { char CityName[30]; int j=0; printf("請輸入您要搜索的城市名\n"); scanf("%s",CityName); while(LHead->Next != NULL && strcmp(LHead->Next-

42、>CityName,CityName)) { LHead = LHead->Next; } if(LHead->Next == NULL) { printf("您要搜索的城市不存在\n"); return; } printf("城市坐標為%.2f,%.2f\n",LHead->Next->X,LHead->Next->Y); } void UpdateCity(CityList* LHead) { char CityName[10]; printf("請輸入您要更新的城市名\n"); scanf("%s",CityName); while(strcmp(LHead->Next->Cit

43、yName,CityName)) //從LHead指向得頭結點的下一個結點開判斷結點中的城市名與輸入城市名是否相等。 { LHead = LHead->Next; // 當不相等則指針LHead下移，繼續(xù)查找 } printf("請輸入城市新信息:\n"); printf("請輸入城市新名\n"); scanf("%s",LHead->Next->CityName); printf("請輸入城市新坐標\n"); scanf("%f",&LHead->Next->X); scanf("%f",&LHead->Next->Y); } //輸入城市新信息 void FindCityDista

44、nce(CityList* LHead) { char m; float x; float y; float distance; printf("請輸入中心坐標x,y\n"); scanf("%f%c%f",&x,&m,&y); printf("請輸入距離:"); scanf("%f",&distance); LHead = LHead->Next; while(LHead != NULL) { if((x-LHead->X)*(x-LHead->X) + (y-LHead->Y)*(y-LHead->Y)CityName); printf("城市坐標為%.2f,%.2f\n",LHead

45、->X,LHead->Y); } LHead = LHead->Next; }} void main() { CityList* LHead; CityList* Store; char choice[3] = {1,2,3}; LHead = (CityList*)malloc(sizeof(CityList)); Init(LHead);//建立空表 Store = LHead; while(strcmp(choice,"7")){ //當所選擇等于7時，進行以下操作 printf("***************************\n"); printf("*******

46、********************\n"); printf(" 歡迎使用本系統(tǒng) \n"); printf("***************************\n"); printf("***************************\n"); printf("1.創(chuàng)建城市鏈表\n"); printf("2.根據(jù)城市名查詢城市\(zhòng)n"); printf("3.根據(jù)離中心坐標距離查詢城市\(zhòng)n"); printf("4.插入新城市信息\n"); printf("5.刪除城市信息\n"); printf("6.更新城市信息\n"); printf("7.退出\n"); //以上相當于

47、一個選擇菜單，皆為提示信息 printf("==========================\n"); printf("請輸入:"); scanf("%s",&choice); switch(choice[0]){ case '1': //相當于選擇1 Create(Store); //構造并創(chuàng)建城市信息鏈表 break; case '2': FindCity(Store);//根據(jù)城市名查找城市位置 break; case '3': FindCityDistance(Store);//根據(jù)所給中心坐標和距離值，返回小于等于所給距離值得節(jié)點信息。 break; ca

48、se '4': Insert(Store);//插入新結點 break; case '5': Delete(Store);//刪除結點 break; case '6': UpdateCity(Store);//更新結點信息 break; case '7'://退出 break; default: printf("輸入錯誤,請重新輸入\n"); break; } } system("PAUSE"); return ; } （二）、回文判斷 1、需求分析： （1）輸入測試數(shù)據(jù)組數(shù)，接著分組輸入字符串，以@結尾。 （2）輸入序列總長不超過 (MAX_N = 1000

49、5)/2 個。將序列1先入棧，接著處理序列2，同時出棧判斷。 （3）將序列1全部入棧，接著輸入序列2，同時出棧判斷。 （4）如果序列滿足題目要求，則輸出“回文序列”；否則，輸出“非回文序列”。 12 a+b&b+a@ a&b@ a&a@ 2、（1）數(shù)據(jù)結構： typedef struct Stack{ int top,size; char str[MAX_N>>1]; }; 使用結構體，內(nèi)部定義數(shù)組模擬棧。top為棧頂指針，指向當前元素的下一個位置，size表示棧內(nèi)的元素個數(shù)。 （2）函數(shù)介紹： void st_init(Stack *st); //棧的初始化 bool s

50、t_push(Stack *st,const char *temp); //入棧 bool st_top(Stack *st,char *temp); //出棧 3、源程序代碼： #include #include #include const int MAX_N = 10005; typedef struct Stack{ int top,size; char str[MAX_N>>1]; }; void st_init(Stack *st) { st->size=MAX_N>>1; st->top=0; } bool st_push(Stack *st,const char *t

51、emp) { if( st->top>st->size ) return false; st->str[st->top++] = *temp; return true; } bool st_pop(Stack *st) { if( st->top==0 ) return false; st->top--; return true; } bool st_top(Stack *st,char *temp) { if( st->top==0 ) return false; *temp = st->str[st->top-1]; return true; } int main() { char

52、str[MAX_N],c; int i,j,cas,len; Stack st; bool flag; // freopen("pal.txt","r",stdin); printf("請輸入測試組數(shù)：\n"); scanf("%d",&cas); getchar(); j=0; while( cas-- ) { ++j; printf("\n第 %d 組數(shù)據(jù)??\n",j); printf("\n請輸入數(shù)據(jù)（字符串1&字符串2@）：\n"); for( i=0; 1; i++ ) { str[i]=getchar(); if( str[i]=='@' ) { str[i]='\0';

53、 break; } } getchar(); flag = true; len = strlen(str); st_init(&st); if( !len&1 ) flag = false; else { for( i=0; i if( str[i]=='&' ) break; st_push(&st,&str[i]); } for( ++i; i st_top(&st,&c); flag = st_pop(&st); if( c!=str[i] || !flag) { flag = false; break; } } if( st.top>0 ) flag = fals

54、e; } printf("\nCase : %d\n",j); if( flag ) printf("回文序列。\n"); else printf("非回文序列。\n"); printf("\n"); } printf("輸入結束。By changning.huang"); // while( true ); return 0; } （三）、二叉樹 1、算法思想： 定義二叉樹結構體類型時，也定義了一個順序棧結構體類型，用以輔助完成二叉樹的非遞歸遍歷。 由鍵盤輸入二叉樹先序序列，用擴展線序序列函數(shù)接受并創(chuàng)建二叉鏈表。 遍歷前先判斷二叉樹是否為空，若為空，執(zhí)行空操作；否則依次執(zhí)行各

55、遍歷函數(shù)相應操作。 先序遍歷，先訪問根節(jié)點，然后按先序遍歷左子樹，再按先序遍歷右子樹。 中序遍歷，先按中序遍歷左子樹，再訪問根節(jié)點，然后按中序訪問右子樹。 后序遍歷，先按后序遍歷左子樹，接著按中序遍歷右子樹，然后訪問根節(jié)點。 2、測試數(shù)據(jù)： ABCффDEфGффFффф（其中ф表示空格字符） 輸出結果為： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 3、源程序代碼： #include #include typedef struct tnode { char data; struct tnode *lchild; struct tnode *rchild;

56、}tnode; tnode *Tree_creat(tnode *t) { char ch; ch=getchar(); if(ch==' ') t=NULL; else { if(!(t=(tnode *)malloc(sizeof(tnode)))) printf("Error!"); t->data=ch;//printf("[%c]",t->data); t->lchild=Tree_creat(t->lchild); t->rchild=Tree_creat(t->rchild); } return t; } void preorder(tnode *t) { if(t!=NULL

57、) { printf("%c ",t->data); preorder(t->lchild); preorder(t->rchild); } } void main() { tnode *t=NULL; t=Tree_creat(t); preorder(t); } 三、心得體會： 數(shù)據(jù)結構實驗是大一學過c語言實驗的深化，難度增加了很多。但本次實驗三個部分主要涉及單鏈表、棧、隊列的知識。我覺得這些計算機中的線性存儲結構原理比較好理解，但是當自己來編寫程序的時候難度大大增加了，這其中涉及到一些指針、結構體等c語言基礎的東西。開始做實驗的時候，由于對上述知識不太熟悉，感覺很困難，后來通過復

58、習c語言相關內(nèi)容和上網(wǎng)查閱資料，逐步理解代碼，一點點掌握了技巧。 總之，這次實驗自己感覺對用c語言寫程序的掌握又進一步強化了，實驗中遇到的困難也都解決了，能力得到了鍛煉。 第四篇：數(shù)據(jù)結構課程設計 課 程 設 計 任 務 書 信息 學院 信息管理與信息系統(tǒng) 專業(yè) 09級1班 班 孫鵬 一、 二、 課程設計題目： 迷宮求解、一元多項式 課程設計主要參考資料： 數(shù)據(jù)結構（C語言版） 嚴蔚敏、吳偉民 編著 數(shù)據(jù)結構題集（C語言版） 嚴蔚敏、吳偉民、米寧 編著 數(shù)據(jù)結構課件 三、 設計應解決下列各主要問題： 1.實現(xiàn)迷宮的路徑求解，并輸出最終路徑，標記走過卻未選擇的路徑和最終選擇

59、的路徑 2.對一元多項式實現(xiàn)加法，減法，乘法，求導的計算，并按指數(shù)由大到小排序輸出 四、 課程設計相關附件（如：圖紙、軟件等）： 五、命題發(fā)出日期：2021-3-15 設計應完成日期： 2021-6-2021 設計指導教師（簽章）： 系主任（簽章）： 指導教師對課程設計的評語 指導教師（簽章）： 年 月 日 山東科技大學學生課程設計 課程設計1 迷宮問題 一、 需求分析： 1. 2. 3. 4. 以二維數(shù)組Maze[][]表示迷宮 用戶輸入迷宮的數(shù)據(jù)：構建迷宮，行數(shù)m，列數(shù)n 迷宮的入口位置和出口位置可由用戶隨時設定 若設定的迷宮存在通路，則以長方陣形式將迷宮及其通

60、路輸出到標準輸出文件（即終端）上，其中，字符“#”表示障礙，字符“*”表示路徑上的位置，字符“@”表示“死胡同”，即曾經(jīng)途徑然而不能到達出口的位置，余者用空格符印出。若設定的迷宮不存在通路，則報告相應信息。 5. 本程序只求出一條成功的通路。然而，只需要對迷宮求解的函數(shù)做小量修改，便可求得全部路徑。 二、 概要設計： 抽象數(shù)據(jù)類型線性表的定義如下： ⒈ 設計棧的抽象數(shù)據(jù)類型定義： ADT Stack { 數(shù)據(jù)對象：D={ai:|ai∈PositionSet,i=1?n,n≥0} 數(shù)據(jù)關系：R1={|ai-1,ai∈d,i=2,?n} 基本操作： 的初始化S GetTop(S,&e)

61、素 Push(&S,e) Pop(&S,e) 返回其值 }ADT Stack； ⒉ 迷宮的抽象數(shù)據(jù)類型定義： ADT Maze{ 數(shù)據(jù)對象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0} 數(shù)據(jù)關系：R={ROW.COL} Row={|ai-1,aij∈D i=1,?,m+2,j=1,?,n+2} 第1頁 操作結果 構造一個空棧，完成棧用e返回棧S的棧頂元將新的元素e壓入棧頂 刪除棧頂元素，并用eInitStack(&S) 山東科技大學學生課程設計 Col={|aijaij-1∈D} 基本操作: masepa

62、th (int i,int j,int m,int n,sqstack &s) 初始條件：已知目前迷宮狀態(tài), 傳過起始位置，和終止位置 操作結果：搜索迷宮，用sqstack s返回搜索所得路徑。如不存在，返回2 }ADT MAZE 三、 詳細設計： #include #include #include #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 //存儲空間初始量 #define STACK_INCREMENT 10//

63、存儲空間初始增量 typedef int Status; typedef struct { int r; int c; }PostType;//坐標位置 迷宮的r行c列 typedef struct { int ord;//通道塊在路徑上的序號 PostType seat;//通道塊的當前坐標位置 int di;//通道塊指向下一通道塊的方向 }SElemType;//棧元素的類型 typedef struct { SElemType *base;//棧底指針 SElemType *top;//棧頂指針 int stacksize;//棧的最大容量 }Stack;//棧的類型

64、第2頁 山東科技大學學生課程設計 Status InitStack(Stack &S)//初始化棧 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW);//存儲分配失敗; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack Status StackEmpty(Stack S) //判斷棧是否為空,如果為空返回TRUE,否則返回FALSE { if(S.top==S.base)

65、 return TRUE; return FALSE; }//StackEmpty Status Push(Stack &S,SElemType e) //插入元素為e的棧頂元素 { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT; }

66、 *S.top++=e; return OK; }//Push Status Pop(Stack &S,SElemType &e) //刪除棧頂元素存入e { if(S.top==S.base) return ERROR; e=*--S.top; 第3頁 山東科技大學學生課程設計 return OK; }//Pop Status DestroyStack(Stack &S) //銷毀棧 { free(S.base); S.top=S.base; return OK; }//DestroyStack //maze.cpp #define MAXLEN 2021迷宮包括外墻最大行列數(shù)目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType; //迷宮類型 Status InitMaze(MazeType &maze){ //初始化迷宮若成功返回TRUE,否則返回FALSE int m,n,i,j,k=1; printf("輸入迷口的行數(shù)和列數(shù): ");