中南大学数据结构课程设计.doc

数据结构课程设计学院： 信息科学与工程学院 专业班级： 指导老师： 学号： 姓名： 目录校园导游咨询系统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） 自己画一张简易的校园平面图，有三个校区和三所附属医院，在这些校区和医院内选10个以上的建筑物、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2） 为来访客人提供图中任意地名相关信息的查询。3） 为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。1.2.设计与实现 基本思路校园导游拓扑图是由景点和景点之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点，用图的边代表景点之间的路径。所以首先应设计一个图类。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度和最短路线时可用弗洛伊德（Floyd）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径。主要数据结构链接矩阵，相关代码typedef struct arc int adj; /路径长度arc,adjmatrix4040; /建一个结构体数组保存路径长度typedef struct scenery /存储景点信息int num;/景点编号char 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=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; /初始路径赋值 for(u=0;uvexnum;u+)pvwu=0; if(Dvw9999) /从v到w有直接路径 pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+)pvwi=pvui|puwi; 主要流程： int main() b=initgraph(); /初始化 while(1) Menu(); /界面 int choice; /选择功能 cinchoice; switch(choice) case 1: 查看校园景点 showall(&b); system(pause); system(cls); break; case 2: 查看景点信息 showselect(&b); system(pause); system(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;程序实现过程中的主要难点和解决方法程序设计的主要难点就是在对结构体的设计和弗洛伊德算法的具体实现上，通过查询数据结构的书及相关算法书，我了解到弗洛伊德算法主要运用了动态规划的相关思想, 通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵A=a(i,j) nn开始，递归地进行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 校园结构拓扑图首先我们序设计校园导游拓扑结构图，将相关数据存入相应数据结构中，然后设计实现相关功能的方法。实验数据如下：strcpy(G.,升华公寓); strcpy(G.roduction,学生宿舍，位于中南大学南校区。); strcpy(G.,二食堂); strcpy(G.roduction,学生食堂，南校区最大的食堂，四层楼。); strcpy(G.,七食堂); strcpy(G.roduction,学生食堂，位于中南大学南校区。); strcpy(G.,八食堂); strcpy(G.roduction,学生食堂，位于中南大学南校区。); strcpy(G.,校医院); strcpy(G.roduction,校内医院，位于中南大学南校区。); strcpy(G.,春之岛); strcpy(G.roduction,校园超市，产品种类齐全，位于中南大学南校区。); strcpy(G.,图书馆); strcpy(G.roduction,学生自习的好去处，位于中南大学新校区。); strcpy(G.,建艺院); strcpy(G.roduction,建艺院，位于中南大学新校区。); strcpy(G.,外语院); strcpy(G.roduction,外语院，位于中南大学新校区。); strcpy(G.,教学楼); strcpy(G.roduction,学生上课场所，位于中南大学新校区。);for(i=0;iG.vexnum;i+)for(j=0;jname=; temp-code=0; temp-birth=0; temp-sex=; temp-edu=; temp-phone=0; temp-next=NULL;for(p=Head;p-next!=NULL;p=p-next)for(q=Head-next;q-next!=NULL;q=q-next)if(q-nameq-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(1) coutendlmenu; 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: 信息总表display_list(Head);break; default: cout请选择正确的菜单项进行操作。多谢合作!next=p-next-next来实现对数据的删除。我们新建两个结点来完成对数据的删除，使ptr_1始终在ptr_2的前面。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=search(Head);ptr=ptr_2-next;coutphone;if(ptr) ptr_2-next=ptr-next;free(ptr);elsecout没找到此职工的记录,无法删除。endl; return Head; 2.3实验结果及分析实验的准备图2.3.1 职工管理系统模块图首先将职工系统的实现框架图列出，建立起相应的数据结构，利用注册职工这一模块将职工信息输入，进而实现后续模块功能。实验结果及分析在修改界面还有一些不足，比如输入数据过长会造成数据的溢出，进而影响输出。2.4总结本次实验实现了对单位的职工进行管理，包括插入、删除、查找、排序等功能。最大的收获是熟悉了对链表的使用方式和vc 6.0的debug功能，在这个过程中我发现了调试对程序的重要性。在调试查询修改功能过程中，查询的总是不正确，查询的结果显示，没有找到职工信息，最后发现查找的结点不正确，查询应该与输入的值和头结点next比较，而不是头结点。还有就是查询结点不知道如何循环，最后又看看了记得笔记和书，才知道如何继续查找而不出错误。 还有就是你新建一个链表要对它进行初始化，若没有初始化，系统不会为它分配空间，从而造成种种错误。排序时注意交换的先后顺序就可以了，删除时注意交换结点的顺序。本次课程设计是围绕数据结构进行。根据问题描述可知，需要解决问题并不复杂，整个问题只需要实现一个职工管理系统功能，那就是在这个系统中实现对职工信息的插入、删除、查询、排序、修改以及保存。但是，为了实现该功能，却需要优秀的算法和数据结构以保证实现的时间和空间效率。把职工信息存储在一个单链表中，利用指针实现对职工信息的各项基本操作。 虽然设计的程序完成了题目描述所需要实现的功能，但是仍然存在不如人意的地方。那就是可以排序上面多设计几个算法。实现多角度排序。在这个系统中没有职工序号的信息，所以允许职工姓名相同，在很大程度上面，可能使得职工信息重复。 另外删除时也只能一个个的删，这些都是还需改进的地方。经过这次数据结构课程设计，我们及时巩固的了数据结构、算法，另外还懂得了一个好的数据结构的重要性。它能够帮我们减少代码量并使程序的性能更加优良。附件：校园导游系统代码#include#include#includeusing namespace std;typedef struct arc int adj; /路径长度arc,adjmatrix4040; /建一个结构体数组保存路径长度typedef struct scenery /存储景点信息int num;/景点编号char name20;/景点名称char 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;iG.vexnum;i+)G.vexsi.num=i; /编号 strcpy(G.,升华公寓); strcpy(G.roduction,学生宿舍，位于中南大学南校区。); strcpy(G.,二食堂); strcpy(G.roduction,学生食堂，南校区最大的食堂，四层楼。); strcpy(G.,七食堂); strcpy(G.roduction,学生食堂，位于中南大学南校区。); strcpy(G.,八食堂); strcpy(G.roduction,学生食堂，位于中南大学南校区。); strcpy(G.,校医院); strcpy(G.roduction,校内医院，位于中南大学南校区。); strcpy(G.,春之岛); strcpy(G.roduction,校园超市，产品种类齐全，位于中南大学南校区。); strcpy(G.,图书馆); strcpy(G.roduction,学生自习的好去处，位于中南大学新校区。); strcpy(G.,建艺院); strcpy(G.roduction,建艺院，位于中南大学新校区。); strcpy(G.,外语院); strcpy(G.roduction,外语院，位于中南大学新校区。); strcpy(G.,教学楼); strcpy(G.roduction,学生上课场所，位于中南大学新校区。);for(i=0;iG.vexnum;i+)for(j=0;jG.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;iG.vexnum;i+)for(j=0;jG.vexnum;j+) G.arcsji.adj=G.arcsij.adj; /无向图不分方向return G; void showall(graph* a) int i;for(i=0;i10;i+)coutendlvexsi.num+1 endl;void showselect(graph* a) /查询特定景点信息 int i;couti;cout景点信息：endl; roductionendl;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=0;vvexnum;v+) for(w=0;wvexnum;w+) Dvw=G-arcsvw.adj; /初始路径赋值 for(u=0;uvexnum;u+)pvwu=0; if(Dvw9999) /从v到w有直接路径 pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(Dvu+DuwDvw) Dvw=Dvu+Duw; for(i=0;ivexnum;i+)pvwi=pvui|puwi; while(flag) printf(请输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(kG-vexnum|jG-vexnum) printf(景点编号不存在!请重新输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; printf(%s,G-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) printf(-%s,G-); printf(-%s,G-); printf( 总路线长%dmn,Dkj); /Floyd endvoid 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(请按提示进入相应菜单:); int main() b=initgraph(); while(1) Menu(); int choice; /选择功能 cinchoice; switch(choice) case 1: showall(&b); system(pause); system(cls); break; case 2: showselect(&b); system(pause); system(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;职工管理系统代码#include #include #include#include#include#include #include 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 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分配内存失败！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 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，不断创建新区域 coutcode; coutname; coutsex; coutbirth; coutedu; coutphone; coutcode=code; /将数据添加到node中去 pNew-name=name; pNew-sex=sex; pNew-birth=birth; pNew-edu=edu; pNew-phone=phone; pNew-next=Head-next; /将链表next属性赋给下一个数据 Head-next=pNew; /上一个next的值为pnew cout数据添加成功！是否继续添加？(Y/N)again; while(again=Y|again=y); system(cls); return Head; /返回值为head ;Link del(Link Head) /删除职工记录Link ptr;Link ptr_2;ptr_2=search(Head);ptr=ptr_2-next;coutphone;if(ptr) ptr_2-next=ptr-next;free(ptr);cout已删除该职工信息;elsecout没找到此职工的记录,无法删除。next;ptr_2=Head;coutname; cout=查询结果=endl; coutendlname=name) display_node(ptr_1); /打印满足条件节点 re(); return ptr_2; else ptr_1=ptr_1-next; /查询下一节点ptr_2=ptr_2-next; coutendl无此职工信息endl; re(); void re() coutnext; cout=所有职工信息=endl; coutendlnext; cout请输入o返回主界面!; char c=getch(); if(c=o) system(cls); void display_node(Link pNode) /打印数据 coutsetw(10)leftcode setw(10)leftname setw(10)leftsex setw(10)leftbirth setw(10)leftedu setw(10)leftphoneendl;/setw(10)表示占10个字符位置。 Link modify(Link Head) /修改信息 int code,birth,phone,name; s