1、.數據結構課程設計學院： 信息科學與工程學院 專業班級： 指導老師： 學號： 姓名： 目錄校園導游咨詢系統21.1.題目與要求21.2.設計與實現2基本思路2主要數據結構3程序的算法和主要流程4程序實現過程中的主要難點和解決方法51.3.實驗結果及分析6實驗的準備6實驗結果及分析81.4總結9簡單的職工管理系統102.1.題目與要求102.2.設計與實現10基本思路10主要數據結構11程序的算法和主要流程11程序實現過程中的主要難點和解決方法132.3實驗結果及分析15實驗的準備15實驗結果及分析162.4總結19附件：20校園導游咨詢系統 1.1.題目與要求1） 自己畫一張簡易的校園平面圖，

2、有三個校區和三所附屬醫院，在這些校區和醫院內選10個以上的建筑物、辦公室、宿舍等地名。以圖中頂點表示校園內各地名，存放地名名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。2） 為來訪客人提供圖中任意地名相關信息的查詢。3） 為來訪客人提供任意地名的問路查詢，即查詢任意兩個地名之間的一條最短路徑。實現提示：一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網。頂點和邊均含有相關信息。1.2.設計與實現 基本思路校園導游拓撲圖是由景點和景點之間的路徑組成的，所以這完全可以用數據結構中的圖來模擬。用圖的結點代表景點，用圖的邊代表景點之間的路徑。所以首先應設計一個圖類。結點值

3、代表景點信息，邊的權值代表景點間的距離。結點值及邊的權值用順序表存儲，所以需要設計一個順序表類。本系統需要查詢景點信息和求一個景點到另一個景點的最短路徑長度及路線，為方便操作，所以給每個景點一個代碼，用結構體類型實現。計算路徑長度和最短路線時可用弗洛伊德（Floyd）算法實現。最后用switch選擇語句選擇執行瀏覽景點信息或查詢最短路徑。主要數據結構鏈接矩陣，相關代碼typedef struct arc int adj; /路徑長度arc,adjmatrix4040; /建一個結構體數組保存路徑長度typedef struct scenery /存儲景點信息int num;/景點編號char

4、name20;/景點名稱char introduction200;/景點介紹scenery;typedef struct graph scenery vexs40; /點adjmatrix arcs; /邊int vexnum,arcnum; /點與邊的個數graph;graph b;程序的算法和主要流程用弗洛伊德算法實現最短路徑：void floyd(graph *G) /求有向網G中各對頂點v和w之間的最短路徑pvw int v,u,i,w,k,j,flag=1, /及其帶權長度Dvw，若pvwu為TRUE p101010,D1010; /則u是從v到w當前求得最短路徑上的點 for(v=

5、0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) Dvw=G->arcsvw.adj; /初始路徑賦值 for(u=0;u<G->vexnum;u+)pvwu=0; if(Dvw<9999) /從v到w有直接路徑 pvwv=1;pvww=1; for(u=0;u<G->vexnum;u+) for(v=0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) if(Dvu+Duw<Dvw) Dvw=Dvu+Duw; for(i=0;i<G-

6、>vexnum;i+)pvwi=pvui|puwi; 主要流程： int main() b=initgraph(); /初始化 while(1) Menu(); /界面 int choice; /選擇功能 cin>>choice; switch(choice) case 1: 查看校園景點 showall(&b); system("pause"); system("cls"); break; case 2: 查看景點信息 showselect(&b); system("pause"); system(

7、"cls"); break; case 3: 查找最短旅游路線 floyd(&b); system("pause"); system("cls"); break; case 4: 退出系統 exit(1); break; default:cout<<"請在1-4中選擇操作!"<<endl;system("pause");system("cls");break; return 0;程序實現過程中的主要難點和解決方法程序設計的主要難點就是在對結構體

8、的設計和弗洛伊德算法的具體實現上，通過查詢數據結構的書及相關算法書，我了解到弗洛伊德算法主要運用了動態規劃的相關思想, 通過一個圖的權值矩陣求出它的每兩點間的最短路徑矩陣。從圖的帶權鄰接矩陣A=a(i,j) n×n開始，遞歸地進行n次更新，即由矩陣D(0)=A，按一個公式，構造出矩陣D(1)；又用同樣地公式由D(1)構造出D(2)；最后又用同樣的公式由D(n-1)構造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j號頂點的最短路徑長度，稱D(n)為圖的距離矩陣，同時還可引入一個后繼節點矩陣path來記錄兩點間的最短路徑。1.3.實驗結果及分析實驗的準備圖1.3.1 校園結構

9、拓撲圖首先我們序設計校園導游拓撲結構圖，將相關數據存入相應數據結構中，然后設計實現相關功能的方法。實驗數據如下：strcpy(G.,"升華公寓"); strcpy(G.roduction,"學生宿舍，位于中南大學南校區。"); strcpy(G.,"二食堂"); strcpy(G.roduction,"學生食堂，南校區最大的食堂，四層樓。"); strcpy(G.,"七食堂"); strcpy(G.v

10、roduction,"學生食堂，位于中南大學南校區。"); strcpy(G.,"八食堂"); strcpy(G.roduction,"學生食堂，位于中南大學南校區。"); strcpy(G.,"校醫院"); strcpy(G.roduction,"校內醫院，位于中南大學南校區。"); strcpy(G.,"春之島"); strcpy(G.rodu

11、ction,"校園超市，產品種類齊全，位于中南大學南校區。"); strcpy(G.,"圖書館"); strcpy(G.roduction,"學生自習的好去處，位于中南大學新校區。"); strcpy(G.,"建藝院"); strcpy(G.roduction,"建藝院，位于中南大學新校區。"); strcpy(G.,"外語院"); strcpy(G.roduct

12、ion,"外語院，位于中南大學新校區。"); strcpy(G.,"教學樓"); strcpy(G.roduction,"學生上課場所，位于中南大學新校區。");for(i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)G.arcsij.adj=9999; /初始化，9999為不存在路徑G.arcs01.adj=100;G.arcs03.adj=200;G.arcs12.adj=1100; G.arcs25.adj=1000;G.arcs45.adj=90

13、0;G.arcs34.adj=300;G.arcs47.adj=400;G.arcs67.adj=500;G.arcs69.adj=600;G.arcs78.adj=800;G.arcs89.adj=700;采用這種鏈接矩陣的結構能夠使用floyd算法對后面的最短路徑這一功能進行具體實現。實驗結果及分析將最短路徑計算結果與我們之前所設計的校園拓撲圖的最短路徑進行比較，驗證了實驗結果的正確性。1.4總結 本實驗采用鏈接矩陣來進行數據的存儲，將路徑的權值保存在矩陣中，通過弗洛伊德算法計算兩點之間的最短路徑。實驗代碼能夠實現為來訪客人提供圖中任意地名相關信息的查詢。以及為來訪客人提供任意地名的問路查

14、詢，即查詢任意兩個地名之間的一條最短路徑。 實驗代碼并沒有實現對地圖的增刪等功能，如果要實現該功能，我們需要將鏈接矩陣改為鏈接表的形式進行存儲。這個會在后面進行進一步的學習。在實驗過程中我進一步了解了數據結構中有關圖的存儲，并熟悉了c+的一些使用方法，感到本次實驗收益匪淺。簡單的職工管理系統2.1.題目與要求對單位的職工進行管理，包括插入、刪除、查找、排序等功能。系統要求職工對象包括姓名、性別、出生年月、學歷、電話這幾種屬性。（1）新增一名職工：將新增職工對象按姓名以字典方式存儲。（2）刪除一名職工：從職工信息中刪除一名職工對象。（3）查詢：從職工信息中查詢符合某些條件的職工。（4）修改：檢索

15、某個職工對象，對其某些屬性進行修改。（5）排序：按某種需要對職工信息進行排序。實現提示（1）對職工對象中的"姓名"按字典順序進行排序。（2）對排序后的職工對象進行增、刪、查詢、修改、排序等操作。2.2.設計與實現基本思路該系統利用線性鏈表實現，首先建一個結構體類型，里面用來存放職工相關信息，用鏈表將所有數據關聯起來。從而實現對相應對象的插入、刪除、查找、排序等功能。主要數據結構鏈表：struct Employee /聲明職工的結構作為鏈表節點。 int code; string name; string sex;int birth; string edu;int phone

16、;struct Employee* next; ;typedef struct Employee Node; /別名typedef Node* Link; /指針型別名程序的算法和主要流程冒泡排序算法：Link sort(Link Head) Link p,q; Node *temp; temp=new Node;temp->name="" temp->code=0; temp->birth=0; temp->sex="" temp->edu="" temp->phone=0; temp->n

17、ext=NULL;for(p=Head;p->next!=NULL;p=p->next)for(q=Head->next;q->next!=NULL;q=q->next)if(q->name>q->next->name)temp->name=q->name;q->name=q->next->name;q->next->name=temp->name; 主要流程：int main() Link Head=0; Head=Create(Head); /創建一個空頭節點int menu; while

18、(1) cout<<endl<<"請選擇相應操作菜單項：" cin>>menu; switch(menu) case 0: 退出系統cout<<"成功退出系統！"<<endl; return 0; case 1: 增加員工信息Head=add(Head); break; case 2: 刪除員工信息 Head=del(Head); break; case 3: 員工信息查詢 search(Head); break; case 4: 員工信息修改modify(Head);break; case 5

19、: 信息總表display_list(Head);break; default: cout<<"請選擇正確的菜單項進行操作。多謝合作!"<<endl; Release(Head); return 0; 程序實現過程中的主要難點和解決方法由于采用的是線性鏈表，線性表中的數據元素之間的關系是一對一的關系，即除了第一個和最后一個數據元素外，其他元素都是首尾相連的。當結點刪除時，需要找到所刪元素的前一個結點，用p->next=p->next->next來實現對數據的刪除。我們新建兩個結點來完成對數據的刪除，使ptr_1始終在ptr_2的前面

20、。Link search(Link Head) /返回符合姓名條件的職工信息 Link ptr_1;Link ptr_2;string name;ptr_1=Head->next;ptr_2=Head;while(ptr_1)if(ptr_1->name=name) display_node(ptr_1); /打印滿足條件節點 re(); return ptr_2; else ptr_1=ptr_1->next; /查詢下一節點ptr_2=ptr_2->next; Link del(Link Head) /刪除職工記錄Link ptr;Link ptr_2;ptr_2=

21、search(Head);ptr=ptr_2->next;cout<<ptr->phone;if(ptr) ptr_2->next=ptr->next;free(ptr);elsecout<<"沒找到此職工的記錄,無法刪除。"<<endl; return Head; 2.3實驗結果及分析實驗的準備圖2.3.1 職工管理系統模塊圖首先將職工系統的實現框架圖列出，建立起相應的數據結構，利用注冊職工這一模塊將職工信息輸入，進而實現后續模塊功能。實驗結果及分析在修改界面還有一些不足，比如輸入數據過長會造成數據的溢出，進而影

22、響輸出。2.4總結本次實驗實現了對單位的職工進行管理，包括插入、刪除、查找、排序等功能。最大的收獲是熟悉了對鏈表的使用方式和vc 6.0的debug功能，在這個過程中我發現了調試對程序的重要性。在調試查詢修改功能過程中，查詢的總是不正確，查詢的結果顯示，沒有找到職工信息，最后發現查找的結點不正確，查詢應該與輸入的值和頭結點next比較，而不是頭結點。還有就是查詢結點不知道如何循環，最后又看看了記得筆記和書，才知道如何繼續查找而不出錯誤。 還有就是你新建一個鏈表要對它進行初始化，若沒有初始化，系統不會為它分配空間，從而造成種種錯誤。排序時注意交換的先后順序就可以了，刪除時注意交換結點的順序。本次

23、課程設計是圍繞數據結構進行。根據問題描述可知，需要解決問題并不復雜，整個問題只需要實現一個職工管理系統功能，那就是在這個系統中實現對職工信息的插入、刪除、查詢、排序、修改以及保存。但是，為了實現該功能，卻需要優秀的算法和數據結構以保證實現的時間和空間效率。把職工信息存儲在一個單鏈表中，利用指針實現對職工信息的各項基本操作。 雖然設計的程序完成了題目描述所需要實現的功能，但是仍然存在不如人意的地方。那就是可以排序上面多設計幾個算法。實現多角度排序。在這個系統中沒有職工序號的信息，所以允許職工姓名相同，在很大程度上面，可能使得職工信息重復。 另外刪除時也只能一個個的刪，這些都是還需改進的地方。經過

24、這次數據結構課程設計，我們及時鞏固的了數據結構、算法，另外還懂得了一個好的數據結構的重要性。它能夠幫我們減少代碼量并使程序的性能更加優良。附件：校園導游系統代碼#include<iostream>#include<string>#include<conio.h>using namespace std;typedef struct arc int adj; /路徑長度arc,adjmatrix4040; /建一個結構體數組保存路徑長度typedef struct scenery /存儲景點信息int num;/景點編號char name20;/景點名稱char

25、 introduction200;/景點介紹scenery;typedef struct graph scenery vexs40; /點adjmatrix arcs; /邊int vexnum,arcnum; /點與邊的個數graph;graph b;graph initgraph(void) /初始化 graph G; int i,j; G.vexnum=10; G.arcnum=11; for(i=0;i<G.vexnum;i+)G.vexsi.num=i; /編號 strcpy(G.,"升華公寓"); strcpy(G.r

26、oduction,"學生宿舍，位于中南大學南校區。"); strcpy(G.,"二食堂"); strcpy(G.roduction,"學生食堂，南校區最大的食堂，四層樓。"); strcpy(G.,"七食堂"); strcpy(G.roduction,"學生食堂，位于中南大學南校區。"); strcpy(G.,"八食堂"); strcpy(G.roduction,

27、"學生食堂，位于中南大學南校區。"); strcpy(G.,"校醫院"); strcpy(G.roduction,"校內醫院，位于中南大學南校區。"); strcpy(G.,"春之島"); strcpy(G.roduction,"校園超市，產品種類齊全，位于中南大學南校區。"); strcpy(G.,"圖書館"); strcpy(G.roduction,"

28、;學生自習的好去處，位于中南大學新校區。"); strcpy(G.,"建藝院"); strcpy(G.roduction,"建藝院，位于中南大學新校區。"); strcpy(G.,"外語院"); strcpy(G.roduction,"外語院，位于中南大學新校區。"); strcpy(G.,"教學樓"); strcpy(G.roduction,"學生上課場所，位于

29、中南大學新校區。");for(i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)G.arcsij.adj=9999; /初始化，9999為不存在路徑G.arcs01.adj=100;G.arcs03.adj=200;G.arcs12.adj=1100; G.arcs25.adj=1000;G.arcs45.adj=900;G.arcs34.adj=300;G.arcs47.adj=400;G.arcs67.adj=500;G.arcs69.adj=600;G.arcs78.adj=800;G.arcs89.adj=700;for(i=0;i&

30、lt;G.vexnum;i+)for(j=0;j<G.vexnum;j+) G.arcsji.adj=G.arcsij.adj; /無向圖不分方向return G; void showall(graph* a) int i;for(i=0;i<10;i+)cout<<endl<<a->vexsi.num+1<<" "<<a-><<endl;void showselect(graph* a) /查詢特定景點信息 int i;cout<<"請輸入所要查詢

31、景點編號："cin>>i;cout<<"景點信息："<<endl;cout<<endl<<a-><<" "<<a->roduction<<endl;void floyd(graph *G) /求有向網G中各對頂點v和w之間的最短路徑pvw int v,u,i,w,k,j,flag=1, /及其帶權長度Dvw，若pvwu為TRUE p101010,D1010; /則u是從v到w當前求得最短路徑上的點 f

32、or(v=0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) Dvw=G->arcsvw.adj; /初始路徑賦值 for(u=0;u<G->vexnum;u+)pvwu=0; if(Dvw<9999) /從v到w有直接路徑 pvwv=1;pvww=1; for(u=0;u<G->vexnum;u+) for(v=0;v<G->vexnum;v+) for(w=0;w<G->vexnum;w+) if(Dvu+Duw<Dvw) Dvw=Dvu+Duw; for(i=0;i&

33、lt;G->vexnum;i+)pvwi=pvui|puwi; while(flag) printf("請輸入出發點和目的地的編號:"); scanf("%d%d",&k,&j); if(k<0|k>G->vexnum|j<0|j>G->vexnum) printf("景點編號不存在!請重新輸入出發點和目的地的編號:"); scanf("%d%d",&k,&j); if(k>=0&&k<G->vexnum&a

34、mp;&j>=0&&j<G->vexnum) flag=0; printf("%s",G->); for(u=0;u<G->vexnum;u+) if(pkju&&k!=u&&j!=u) printf("->%s",G->); printf("->%s",G->); printf(" 總路線長%dmn",Dkj); /Floyd endvoi

35、d Menu() /操作界面 printf("n 中南大學校園導游系統nn"); printf(" n"); printf(" n"); printf(" 1.查看校園景點 n"); printf(" 2.查看景點信息 n"); printf(" 3.查找最短旅游路線 n"); printf(" 4.退出系統 n"); printf(" n"); printf(" n"); printf("請按提示進入相應

36、菜單:"); int main() b=initgraph(); while(1) Menu(); int choice; /選擇功能 cin>>choice; switch(choice) case 1: showall(&b); system("pause"); system("cls"); break; case 2: showselect(&b); system("pause"); system("cls"); break; case 3: floyd(&b);

37、 system("pause"); system("cls"); break; case 4: exit(1); break; default:cout<<"請在1-4中選擇操作!"<<endl;system("pause");system("cls");break; return 0;職工管理系統代碼#include <iostream> #include <fstream> #include<string>#include<i

38、omanip>#include<conio.h>#include <vector>#include <algorithm>using namespace std; struct Employee /聲明職工的結構作為鏈表節點。 int code; string name; string sex;int birth; string edu;int phone;struct Employee* next; ;typedef struct Employee Node;typedef Node* Link;Link Create(Link Head);Link

39、 Add(Link Head);Link search(Link Head);Link del(Link Head); void display_list(Link Head); void display_node(Link Head);void Save_ByFile(Link Head,fstream& ofile); Link sort(Link Head);void re(); /清屏Link Create(Link Head) /創建一個帶頭節點的空鏈表Head=(Link)new Node; if(!Head) cout<<"分配內存失敗！"

40、<<endl; return NULL; Head->code=0; Head->name="" Head->birth=0; Head->sex="" Head->edu="" Head->phone=0; Head->next=NULL; return Head; void Release(Link Head) /釋放鏈表。 Link ptr;/聲明一個操作用的指針。 while(Head!=NULL) ptr=Head; Head=Head->next; delete

41、ptr;/釋放節點資源。 Link add(Link Head) /插入數據 Link pNew; int code,birth,phone; string edu,sex; char name20; char again; /控制是否繼續添加數據 do pNew=(Link)new Node; /把Node轉化成指針型賦給pNew，不斷創建新區域 cout<<"請輸入職工代碼: " cin>>code; cout<<"請輸入職工姓名: " cin>>name; cout<<"請輸入職

42、工性別: " cin>>sex; cout<<"請輸入職工出生年月: " cin>>birth; cout<<"請輸入職工學歷: " cin>>edu; cout<<"請輸入職工聯系電話: " cin>>phone; cout<<endl; pNew->code=code; /將數據添加到node中去 pNew->name=name; pNew->sex=sex; pNew->birth=birth; pN

43、ew->edu=edu; pNew->phone=phone; pNew->next=Head->next; /將鏈表next屬性賦給下一個數據 Head->next=pNew; /上一個next的值為pnew cout<<"數據添加成功！是否繼續添加？(Y/N)"<<endl; cin>>again; while(again='Y'|again='y'); system("cls"); return Head; /返回值為head ;Link del(Li

44、nk Head) /刪除職工記錄Link ptr;Link ptr_2;ptr_2=search(Head);ptr=ptr_2->next;cout<<ptr->phone;if(ptr) ptr_2->next=ptr->next;free(ptr);cout<<"已刪除該職工信息"elsecout<<"沒找到此職工的記錄,無法刪除。"<<endl; re(); return Head; Link search(Link Head) /返回符合姓名條件的職工信息 Link ptr

45、_1;Link ptr_2;string name;ptr_1=Head->next;ptr_2=Head;cout<<"請輸入查詢職工姓名：" cin>>name; cout<<"=查詢結果="<<endl; cout<<endl<<"職工代碼 姓名 性別 出生年份 教育程度 聯系方式"while(ptr_1)if(ptr_1->name=name) display_node(ptr_1); /打印滿足條件節點 re(); return ptr_2;

46、 else ptr_1=ptr_1->next; /查詢下一節點ptr_2=ptr_2->next; cout<<endl<<"無此職工信息"<<endl; re(); void re() cout<<"請輸入o返回主界面!" char c=getch(); if(c='o')system("cls");void display_list(Link Head) /查詢所有職工信息 Link ptr,ptr1; ptr=sort(Head); ptr1=ptr-

47、>next; cout<<"=所有職工信息="<<endl; cout<<endl<<"職工代碼 姓名 性別 出生年份 教育程度 聯系方式" while(ptr1) display_node(ptr1); ptr1=ptr1->next; cout<<"請輸入o返回主界面!" char c=getch(); if(c='o') system("cls"); void display_node(Link pNode) /打印數據

48、cout<<setw(10)<<left<<pNode->code <<setw(10)<<left<<pNode->name <<setw(10)<<left<<pNode->sex <<setw(10)<<left<<pNode->birth <<setw(10)<<left<<pNode->edu <<setw(10)<<left<<pNode-

49、>phone<<endl;/setw(10)表示占10個字符位置。 Link modify(Link Head) /修改信息 int code,birth,phone,name; string edu,sex; Link ptr;ptr=search(Head);if(ptr!=NULL) /判斷指針是否為空 cout<<"-你現在可以修改此職工的信息了-"<<endl; cout<<"請輸入職工代碼：" cin>>code; cout<<endl<<"請

50、輸入職工姓名：" cin>>name; cout<<endl<<"請輸入職工性別：" cin>>sex; cout<<endl<<"請輸入職工出生年份：" cin>>birth; cout<<endl<<"請輸入職工教育程度：" cin>>edu; cout<<endl<<"請輸入職工聯系方式：" cin>>phone; cout<<endl; ptr->code=code; ptr-&g