校園導游咨詢?yōu)閬碓L的客人提供各種信息服務完結版

CENTRALSOUTHUNIVERSITY數據結構課程設計報告學生姓名學號專業(yè)班級指導老師學院完成時間目錄實驗一課程設計的題目和要求·························1設計與實現···································1基本思路主要數據結構程序的算法和主要流程(4)程序實現過程中的主要難點和解決方法實驗結果及分析·······························1實驗的準備(2)實驗結果及分析總結·····································1實驗二一．課程設計的題目和要求·························1二．設計與實現···································1(1)基本思路(2)主要數據結構(3)程序的算法和主要流程(4)程序實現過程中的主要難點和解決方法三．實驗結果及分析·······························1(1)實驗的準備(2)實驗結果及分析四．總結·····································1第第頁實驗一課程設計的題目和要求：題目：校園導游咨詢（為來訪的客人提供各種信息服務）基本要求：設計中南大學校園平面圖，有三個校區(qū)和三所附屬醫(yī)院，在這些校區(qū)和醫(yī)院內選10個以上的建筑物、辦公室、宿舍等地名。以圖中頂點表示校園內各地名，存放地名名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。為來訪客人提供圖中任意地名相關信息的查詢。為來訪客人提供任意地名的問路查詢，即查詢任意兩個地名之間的一條最短路徑。實現提示一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網。頂點和邊均含有相關信息。設計與實現：(1)基本思路=1\*GB3①從中南大學校園平面圖中選取10個有代表性的景點，抽象成一個無向帶權圖，以圖中頂點表示景點，邊上的權表示兩地的之間的距離。=2\*GB3②本程序的目的是為用戶提供路徑查詢。根據用戶指定的始點和終點輸出相應路徑，或者根據用戶指定的景點輸出景點的信息。=3\*GB3③用鄰接表建立圖，圖的每一個頂點代表相應的景點。然后再用深度優(yōu)先遍歷進行搜索，查找所需的路徑。然后再用弗洛伊德算法求出要查詢的出發(fā)點到目的地的最短路徑。(2)主要數據結構typedefstructEdge//對邊的定義{intadj;//路徑長度}Edge,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct//圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，{charname[30];intnum;charintroduction[100];//簡介}infotype;//數據域typedefstruct{infotypevexs[MAX_VERTEX_NUM];//頂點的數據域AdjMatrixedge;//鄰接矩陣intvexnum,edgenum;//圖的當前頂點數和邊數}MGraph;(3)程序的算法和主要流程<1>Floyd算法算法思想：從vi到vj的所有存在的路徑中，選出一條長度最短的路徑，即每一對頂點之間的最短路徑。voidFloyd(MGraph*G)//用Floyd算法求圖中各對頂點v和w之間的最短路徑P[v][w]及其//帶權長度D[v][w]。若P[v][w][u]為1，則u是從v到w當前求得最短//路徑上的頂點。{intv,u,i,w,k,j,flag=1,p[10][10][10],D[10][10];for(v=0;v<G->vexnum;v++)//各對結點之間初始已知路徑及距離for(w=0;w<G->vexnum;w++){D[v][w]=G->edge[v][w].adj;for(u=0;u<G->vexnum;u++)p[v][w][u]=0;if(D[v][w]<INFINITY){p[v][w][v]=1;p[v][w][w]=1;}}for(u=0;u<G->vexnum;u++)for(v=0;v<G->vexnum;v++)for(w=0;w<G->vexnum;w++)if(D[v][u]+D[u][w]<D[v][w])//從v經u到w的一條路徑更短{D[v][w]=D[v][u]+D[u][w];//修改權值for(i=0;i<G->vexnum;i++)p[v][w][i]=p[v][u][i]||p[u][w][i];}while(flag){printf("請輸入出發(fā)點和目的地的編號:");scanf("%d%d",&k,&j);if(k<0||k>G->vexnum||j<0||j>G->vexnum){printf("景點編號不存在!請重新輸入出發(fā)點和目的地的編號:");scanf("%d%d",&k,&j);}if(k>=0&&k<G->vexnum&&j>=0&&j<G->vexnum)flag=0;}printf("%s",G->vexs[k].name);for(u=0;u<G->vexnum;u++)if(p[k][j][u]&&k!=u&&j!=u)printf("-->%s",G->vexs[u].name);printf("-->%s",G->vexs[j].name);printf("總路線長%dm\n",D[k][j]);}//Floydend<2>主函數主函數調用函數調用函數<3>結束查看各景點游覽路線結束查看各景點游覽路線開始開始定義變量VVoidMenu()進入菜單Switch()選擇功能退出系統瀏覽校園全景顯示此圖的鄰接矩陣查看景點信息選擇出發(fā)點和目的地退出系統瀏覽校園全景顯示此圖的鄰接矩陣查看景點信息選擇出發(fā)點和目的地（4）程序實現過程中的主要難點和解決方法<1>這個程序的關鍵代碼就利用Floyd算法求最短路徑并將路徑存放起來。Floyd算法的算法思想：設矩陣用來存放帶權無向圖G的權值，即矩陣元素D[i][j]中存放著序號為i的結點到序號為j的結點之間的權值，可以通過遞推構造一個矩陣序列A0，A1，A2，…，AN來求每對結點之間的最短路徑。其中，Ak[i][j]表示從結點Vi到結點Vj的路徑上所經過的結點序號不大于k的最短路徑長度。初始時有A0[i][j]=cost[i][j]。當已經求出Ak，要遞推求解Ak+1時，可分為兩種情況來考慮：一種清楚是該結點序號為k+1的結點，此時該路徑長度與從結點Vi到結點Vj的路徑上所經過的結點序號不大于k的最短路徑長度相同；另一種情況是該路徑經過結點序號k+1的結點，此時該路徑可分為兩段，一段是從結點Vi到結點Vk+1的最短路徑，另一段是從結點Vk+1到結點Vj的最短路徑，此時的最短路徑長度等于這兩段最短路徑長度之和。這兩種情況的路徑長度較小者，就是要求的從結點Vi到結點Vj的路徑上所經過的結點序號不大于k+1的最短路徑長度。Floyd具體算法設計voidfloyed(){inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){ shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}<2>由于導游程序在實際執(zhí)行時，需要根據用戶的臨時輸入求最短路徑。因此。雖然迪杰斯特拉算法的時間復雜度比佛洛依德算法低，但每求一條最短路徑都必須重新搜索一遍，在頻繁查詢時會導致查詢效率降低，而佛洛依德算法只要計算一次，即可求得每一對頂點間的最短路徑，雖然時間復雜度為o(n^3)，但以后每次查詢都只查表即可，極大地提高了查詢效率，而且，佛洛依德算法還支持帶負權的圖的最短路徑的計算。由此可見，在選用算法時，不能單純的只考慮算法的漸近時間復雜度，有時還必須綜合考慮各種因素。實驗結果與分析：實驗的準備用鄰接表建立圖，圖的每一個頂點代表相應的景點。然后再用深度優(yōu)先遍歷進行搜索，查找所需的路徑。然后再用弗洛伊德算法求出要查詢的出發(fā)點到目的地的最短路徑。（1）主菜單（Menu）：存放著所有的選擇供用戶查詢。用戶可通過輸入編號來查詢自己想要獲得的信息。（2）瀏覽校園全景（Browser）：采用深度遍歷遍歷圖進行所有景點瀏覽，將遍歷景點信息輸出。（3）選擇出發(fā)點和目的地(Floyd)：用戶輸入一個出發(fā)點和一個目的地編號，采用弗洛伊德算法求出發(fā)點到目的地的最短路徑。（4）查看景點信息(Search)：直接輸入編號進行單個景點查詢。（5）顯示圖的鄰接矩陣(print)（6）退出系統(exit)(2)實驗結果及分析<1>開始界面實現了底為湖藍色，字體為白色的整體要求，以及選項明確，直觀易懂。<2>瀏覽校園全景，中南大學10個景點的名稱以及簡介。<3>選擇出發(fā)點和目的地，輸入兩地編號，輸出用弗洛伊德算法計算出的兩點之間的最短距離以及最短線路。<4>查看景點信息，輸入景點編號，輸出景點名稱和簡介<5>顯示此圖的鄰接矩陣四．總結：為期一周的課程設計快結束了，通過這次數據結構課程設計，我感受最深的就是對于循環(huán)鏈表的使用，可以說對循環(huán)鏈表有了比以前更進一步的認識，以前只是一知半解的，如果只給個題目自己根本不能把程序完整地編寫出來，所以這次課程設計最大的收獲就在于對循環(huán)鏈表有了一定的理解，包括其中的一系列操作，如建立一個循環(huán)鏈表，刪除鏈表中的一個結點，增加一個結點等。在這次課程設計過程中需要我們一邊設計一邊探索，這這個過程當中我發(fā)現自己在數據結構方面知識掌握不夠深入，對一些基本概念不能很好的理解，對一些數據結構不能夠熟練的進行上機實現，這是自己比較薄弱的。學好基礎知識是理論付諸實踐的前提，這樣理論和實踐才能充分地結合起來。在以后的學習中，我還要努力改正，充分利用上機實驗的機會提高自己。在程序的輸入的時候，因為自己對鍵盤的不熟練，代碼又很多很繁瑣，常常會產生放棄的念頭，從中我也感受到只有堅持到底，勝利才會出現。本次程序設計是對全學期數據結構課程學習的一次實踐，通過親自編寫編譯調試程序，逐步掌握了編程方法。也說明了一個深刻道理，知識只有在實踐中才能充分理解并運用。從傳統的被動接受變?yōu)橹鲃犹剿?，起初不是很適應，什么也不懂，茫然無措。漸漸地開始自己編寫時候，發(fā)現了其中之樂趣。我相信，這樣的學習堅持到底，必將有所成就。數據結構課程設計有別于大學考試的類型，要求我們創(chuàng)新自己的新程序，從已有的教材模板中推陳出新，總結教材上的例題和基本結構，發(fā)散思維來設計命題程序，對我們提出了很高的要求，是我們不僅要把課本讀透，還要求我們有所創(chuàng)造，這是一個很大的挑戰(zhàn)。當毫無頭緒時，一個人的力量是微薄的，所以這就要求我們和同學一起討論，一起研究，在激烈的爭論中有所收獲，也提高了我們思維的縝密度和拓展了思想的深度及廣度。揚長避短，通過討論和對書本的進一步深究理解，以及上網查詢有關注意事項并上機調試，是我們加深了對程序設計的理解與探尋，使我們在設計的過程中加強了編程邏輯，深喑耐心細致十分重要，更懂得了編程不能求快，急于求成，只能穩(wěn)扎穩(wěn)打，步步推進。而我們從中所收獲的，不僅如此，更為以后我們的編程學習和工作獲得了一些初級經驗，我明天積累下重要財富。雖然通過自己的努力，解決了很多從前沒有遇到的問題，但依舊有無數的難題擺在我面前，重重疊疊的大山阻礙著我前進的道路。山高人為峰，我一定不會懼怕擺在前面的困難，不斷努力奮斗，爭取看到更多的陽光。目前的程序漏洞確實還是很多，但編成之后的成就感還是會油然而生，成為我向程序設計之路成功邁出的第一步，同時，對于我的VC++的應用水平也有很大的提高，用起來會更加嫻熟、得心應手。從易到難這是一個準則，總之，數據結構的研究會對增長程序閱讀能力、程序編寫能力等起到了意想不到的作用。在以后漫漫的研究學習道路上，我還有很遠的路要走，迎接我的是又一個嚴峻的挑戰(zhàn)!實驗二課程設計的題目和要求：題目：停車場管理問題問題描述設有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內有車開走，則排在便道上的第一輛車就進入停車場。停車場內如有某輛車要開走，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應根據它在停車場內停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理。實現要求要求程序輸出每輛車到達后的停車位置(停車場或便道上)，以及某輛車離開停車場時應交納的費用和它在停車場內停留的時間。實現提示汽車的模擬輸入信息格式可以是：(到達／離去，汽車牌照號碼，到達／離去的時刻)。例如，(‘A’，，1，5)表示1號牌照車在5這個時刻到達，而(‘D’，，5，20)表示5號牌照車在20這個時刻離去。整個程序可以在輸入信息為(‘E’，0，0)時結束。本題可用棧和隊列來實現。二．設計與實現：(1)基本思路此停車場管理系統是在一個狹長的通道上的，而且只有一個大門可以供車輛進出，并且要實現停車場內某輛車要離開時，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場的功能，就可以設計兩個堆棧，其中一個堆棧用來模擬停車場，另一個堆棧用來模擬臨時停車場，該臨時停車場用來存放當有車輛離開時，原來停車場內為其讓路的車輛。至于當停車場已滿時，需要停放車輛的通道可以用一個鏈隊列來實現。當停車場內開走一輛車時，通道上便有一輛車進入停車場，此時只需要改變通道上車輛結點的連接方式就可以了，使通道上第一輛車進入停車場這個堆棧，并且使通道上原來的第二輛車成為通道上的第一輛車，此時只需將模擬通道的鏈隊列的頭結點連到原來的第二輛車上就可以了。對于此停車場管理系統的實現，就是用兩個堆棧來分別模擬停車場以及停車場內車輛為其它車輛讓路時退出停車的臨時停放地點。至于通道上車輛的停放則用一個鏈隊列來實現，此時，通道上車輛的離開或者進入停車場只需改變此鏈隊列上的結點而已。對于要對停車場內的車輛根據其停放時間收取相應的停車費用，可以記錄下車輛進入以及離開停車場的時間，再用時間差乘以相應的單價并且打印出最后的費用就可以實現了。主要數據結構typedefstructnode{intnum;intreachtime;intleavetime;}CarNode;/*車輛信息結點*/typedefstructNODE{CarNode*stack[MAX+1];inttop;}SeqStackCar;/*模擬車站*/typedefstructcar{CarNode*data;structcar*next;}QueueNode;typedefstructNode{QueueNode*head;QueueNode*rear;}LinkQueueCar;/*鏈隊列模擬通道*/程序的算法和主要流程intArrival(SeqStackCar*Enter,LinkQueueCar*W)/*車輛到達*/{CarNode*p;QueueNode*t;p=(CarNode*)malloc(sizeof(CarNode));printf("\t\t\t請輸入到達車輛車牌號:");scanf("%d",&(p->num));if(Enter->top<MAX)/*車場未滿，車進車場*/{Enter->top++;printf("\n\t\t\t該車輛在停車場的位置是:%d\n",Enter->top);printf("\n\t\t\t請輸入該車輛到達的時間:");scanf("%d",&(p->reachtime));Enter->stack[Enter->top]=p;return(1);}else/*車場已滿，車進便道*/{printf("\n\t\t\t停車場已滿該車輛需在便道上等待！");t=(QueueNode*)malloc(sizeof(QueueNode));t->data=p;t->next=NULL;W->rear->next=t;W->rear=t;return(1);}}voidLeave(SeqStackCar*Enter,SeqStackCar*Temp,LinkQueueCar*W)/*車輛離開*/{introom;CarNode*p,*t;QueueNode*q;/*判斷車場內是否有車*/if(Enter->top>0)/*有車*/{while(1)/*輸入離開車輛的信息*/{printf("\t\t\t停車場里停放的車輛總數:%d",Enter->top);printf("\n\n\t\t\t請輸入要離開車輛的位置:");scanf("%d",&room);if(room>=1&&room<=Enter->top)break;}while(Enter->top>room)/*車輛離開*/{Temp->top++;Temp->stack[Temp->top]=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;}p=Enter->stack[Enter->top];Enter->stack[Enter->top]=NULL;Enter->top--;while(Temp->top>=1){Enter->top++;Enter->stack[Enter->top]=Temp->stack[Temp->top];Temp->stack[Temp->top]=NULL;Temp->top--;}PRINT(p);/*判斷通道上是否有車及車站是否已滿*/if((W->head!=W->rear)&&Enter->top<MAX)/*便道的車輛進入車場*/{q=W->head->next;t=q->data;Enter->top++;printf("\n\n\t\t\t便道的%d號車進入車場第%d位置.",t->num,Enter->top);printf("\n\n\t\t\t請輸入現在的時間:");scanf("%d",&(t->reachtime));W->head->next=q->next;if(q==W->rear)W->rear=W->head;Enter->stack[Enter->top]=t;free(q);}elseprintf("\n\n\t\t\t便道里沒有車.\n");}elseprintf("\n\n\t\t\t車場里沒有車.");/*沒車*/}程序實現過程中的主要難點和解決方法<1>在剛開始進行停車場管理系統分析時，我始終沒有解決如何在一輛車要離開停車場時，它后面的車要為它讓路這件事，如果是堆棧的增加減少，整個程序顯得過于麻煩，所以經過查找資料，我發(fā)現建立一個臨時停車場來存放一輛車在離開時它后面的車是最簡單的解決方法，編入程序也簡潔明了，瞬間降低了程序的復雜度，我覺得很開心。<2>在剛開始程序執(zhí)行程序時，選擇執(zhí)行一個任務后就會跳轉到一個全新的界面，之前的選項不復存在，所以只能進行單一的選擇，不能連貫執(zhí)行形成一個動態(tài)存取過程，因此我想到由于此停車場管理系統是分模塊設計的，而且在程序的實現過程中又使用了清屏函數，那么，運行時用戶選擇任務并且執(zhí)行完任務后，又會回到供用戶選擇功能的主界面，因此整個程序從整體上來講結構清晰，使用方便。三．實驗結果與分析：（1）實驗的準備首先定義用來模擬停車場的堆棧以及用來模擬通道的鏈隊列為全局變量，然后編寫主函數，在此主函數中實現對其它各個模塊的調用。在主函數中首先調用option()函數，出現歡迎用戶使用的主界面，然后提示用戶進入此停車場管理系統后，再出現一個供用戶選擇的界面，在用戶的選擇過程中，程序又分別調用車輛的到達、車輛的離開、停車場內停放車輛的信息以及退出程序這四個函數模塊。其中，在車輛的離開那個模塊函數中又調用了打印離開車輛信息的函數，在停車場內停放車輛信息的那個模塊函數中，又分別調用了顯示停車場上車輛信息的函數以及顯示便道上車輛信息的函數。最后，從調用的這四個函數中回到主函數結束整個程序的運行。(2)實驗結果及分析<1>開始界面，界面清晰簡潔，一目了然<2>車輛到達，輸入到達車輛的車牌號，該車輛在停車場存放的位置以及車輛到達的時間，則這些信息就會存儲在存車信息中。<3>我暫時將整個停車場的最大容車輛定在了兩輛，就是為了檢測一下通道是否正常運行。第二輛車可以正常存放在停車場的二號位置，但是第三輛車進入就會顯示停車場已滿，該車輛需要停在便道上等待，程序運行符合預期要求。<4>查看存車信息。依次顯示車場，便道的車輛信息，顯示車輛的位置，到達時間以及車牌