第一篇：校园导游实验报告——数据结构
数据结构实验报告
——实验六 简单校园导游程序的设计与实现
本实验的目的是通过对校园导游程序的设计与实现来熟练掌握图型结构在实际问题中的应用。
一、【问题描述】
当人们到一个陌生的地方去旅游的时候可能会找一个导游为自己在游玩的过程中提供方便。导游可以提供很多服务，比如介绍参观景点的历史背景等相关信息，推荐到下一个景点的最佳路径，以及解答旅游者所提出的关于旅游经典的相关问询等等。对于新生刚刚来到校园，对校园环境不熟悉的情况也如此，一般都是高年级的学生充当了“校园导游员”的角色，如果能够提供一个程序让新生或来访的客人自主的通过与机器的“对话”来获得相关的信息的话，将会节省大量的人力和时间。而且所提供的信息也能够做到尽可能的准确、详尽。一个成功的校园导游程序可以替代现实生活中这些“校园导游员”，更方便了大家查询校园相关的信息。
本次实验需要开发一个简单的校园导游程序，程序的主体功能为：
1、显示校园平面图，方便用户直观的看到校园的全景示意图，并确定自己的位置。
2、为用户提供对平面图中任意场所的相关信息的查询。
3、为用户提供对平面图中任意场所的问路查询。
二、【数据结构设计】
由于各个场所通过校园中的道路相连，各个场所和连接它们的道路构成了整个校园的地理环境，所以使用图这种数据结构对他们去进行描述。以图中的顶点表示校园内各个场所，应包含场所名称、代号、简介等信息；以边表示连接各个场所的道路，应包含道路的代号、路径的长度等信息。顶点和边均使用结构体定义，整个图的数据结构可以采用教材中介绍的各种表示方法，例如带权的邻接矩阵。
三、【功能（函数）设计】
1、显示校园平面图的功能模块。
通过读文件的方式将各个地点的信息读入程序中.平面图中应醒目的标识出场所的准确名称以备用户查询。河北大学校园导游的基本地点信息。
***************欢迎进入河北大学校园导游系统!**************-----------------------景点名称---------------------------
主楼 多功能馆 毓秀园 图书馆
操场
留学生楼
七教 八教
九教 成教 南大门 北大门
一教 逸夫楼 博物馆 物理楼
电信楼 化学楼 生科楼 建工楼
北院食堂
南院食堂
竹园 梅园
桂园 菊园 易百超市 北院生活园区
---------------------------地点的存储
typedef struct Vertex//顶点结构体 { int No;//地点编号
char name[20];//地点名称
char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex];int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵
int vnum,anum;//顶点和边的个数 }Graph;
2、查询任意场所的相关信息查询的功能模块。
此模块接收用户所输入的场所名称，并将场所的简介信息反馈给用户。查找出查询的场所将其信息输出,信息通过文本文件读入 函数void introduction(Graph &G)实现
先通过strcpy进行查找，再讲找到顶点v1 G.view[v1].info输出
3、任意场所的问路查询的功能模块。
void shortpath(Graph &G,int v0,int v1)；此函数运用克鲁斯卡尔算法计算两点间最短路径。
void dispath(Graph &G)//查询最短路径 { „shortpath(G, v0, v1)； } 此模块接收用户所输入的场所名称，并在调用shortpath(G, v0, v1)；计算出最短路径相关项的信息反馈给用户。
4、求单源点到其他各点的最短路径的功能模块。
此模块计算并记录从校园门口到各个场所的最短路径。for(i=0;i 四、【界面设计】 本程序为方便用户所设计，由于使用的最终用户大多对校园的情况并不熟悉，所以在图中给出的任何提示信息一定要准确，尽量的避免歧义。 五、【编码实现】 #include char name[20];//地点名称 char info[1000];//地点简介 }Vertex;typedef struct //无向图结构体 { Vertex view[Max_Vertex]; int edges[Max_Vertex][Max_Vertex];//边的邻接矩阵 int vnum,anum;//顶点和边的个数 }Graph;void Creat(Graph &G){ ifstream infile(“view.txt”,ios::in); if(!infile) { cout<<“文件打开错误”< abort(); } int i,j,k,w; infile>>G.vnum; infile>>G.anum; //cout< for(i=0;i { infile>>G.view[i].No>>G.view[i].name>>G.view[i].info; } for(i=0;i { for(j=0;j G.edges[i][j]=Maxnum; } ifstream weight_file(“weight.txt”,ios::in); if(!weight_file) { cout<<“文件打开错误”< abort(); } for(k=0;k { weight_file>>i>>j>>w; i--; j--; G.edges[i][j]=w; G.edges[j][i]=G.edges[i][j]; } } void introduction(Graph &G){ char temp[20];cout<<“请输入要查询的景点名称”< if(strcmp(G.view[i].name,temp)==0) { v1=i; count++; } } if(count!=1){ cout<<“输入的名称不存在”< return;} else { cout<<“该景点简介为”< cout< return;} } void shortpath(Graph &G,int v0,int v1){ int P[100];float D[100];int i,j,w;int v,pre;float min; int final[Max_Vertex];for(v=0;v { final[v]=0; D[v]=G.edges[v0][v]; if(D[v] P[v]=v0; if(D[v]==Maxnum) P[v]=-2; } D[v0]=0;final[v0]=1;P[v0]=-1; for(i=1;i min=Maxnum; //min为当前所知离源点的最近距离 for(w=0;w if(!final[w]) if(D[w] { j=w; //记忆此点 min=D[w]; } final[j]=1; //离源点最近的j加入S集合 for(w=0;w //更新其它点地当前最短路径 if(!final[w] &&(min+G.edges[j][w] { D[w]=min+G.edges[j][w]; P[w]=j; //将w的前驱结点改为j } } if(P[v1]==-2) cout<<“max”< else { pre=P[v1]; cout< cout< cout< while(pre>0) { cout<<“←”< pre=P[pre]; } if(v0==0) cout<<“←”< else cout< cout< } } void dispath(Graph &G)//查询最短路径 { int v1,v0,i;int count=0;char temp1[20],temp2[20];cout<<“请输入要查询的两个景点名称”< for(i=0;i if(strcmp(G.view[i].name,temp1)==0) { v0=i; count++; } if(strcmp(G.view[i].name,temp2)==0) { v1=i; count++; } } if(count!=2){ cout<<“输入的名称不存在”< return;} else { shortpath(G,v0,v1); return;} } void main(){ Graph G;Creat(G);int i;char ch1; cout<<“t***************欢迎进入河北大学校园导游系统!**************”< cout<<“t-----------------------景点名称---------------------------”< for(i=0;i { if(i%4==0) { cout< cout< } else { cout< } } cout< cout<<“t---------------------------”< cout<<“t__________________________________________________________”< cout<<“tt 请选择要进行的操作”< cout<<“ tt 1.查询景点信息”< cout<<“ tt 2:显示大门到各个地点的最短路径”< cout<<“ tt 3:查询两个景点之间的最短路径”< cout<<“ tt 0:退出”< cout<<“t__________________________________________________________”< cout<<“请选择(0~2):”; cin>>ch1; while(!(ch1<='3'&&ch1>='0')) { cout<<“数据输入错误，请重新选择(0~2):”; cin>>ch1; } switch(ch1) { case '1': introduction(G);break; case '2' : for(i=0;i shortpath(G,10,i); break; case '3' : dispath(G); break; } }while(ch1!=0);} 六、【运行与测试】 ***************欢迎进入河北大学校园导游系统!************** -----------------------景点名称--------------------------- 主楼 多功能馆 毓秀园 图书馆 操场 留学生楼 七教 八教 九教 成教 南大门 北大门 一教 逸夫楼 博物馆 物理楼 电信楼 化学楼 生科楼 建工楼 北院食堂 南院食堂 竹园 梅园 桂园 菊园 易百超市 北院生活园区 --------------------------- __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 主楼 该景点简介为 是河北大学本部标志性建筑，这H型高大的建筑，正对着河北大学校本部南院黑 校门，此楼于2001年建成。主要为教学、科研、办公服务。 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):1 请输入要查询的景点名称 哈哈 输入的名称不存在 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):2 南大门到主楼最短路径为50米 主楼←南大门 南大门到多功能馆最短路径为60米 多功能馆←南大门 南大门到毓秀园最短路径为60米 毓秀园←图书馆←南大门 南大门到图书馆最短路径为40米 图书馆←南大门 南大门到操场最短路径为160米 操场←毓秀园←图书馆←南大门 南大门到留学生楼最短路径为180米 留学生楼←操场←毓秀园←图书馆←南大门 南大门到七教最短路径为115米 七教←桂园←毓秀园←图书馆←南大门 南大门到八教最短路径为65米 八教←图书馆←南大门 南大门到九教最短路径为70米 九教←图书馆←南大门 南大门到成教最短路径为75米 成教←八教←图书馆←南大门 南大门到南大门最短路径为0米 南大门 南大门到北大门最短路径为25米 北大门←南大门 南大门到一教最短路径为35米 一教←北大门←南大门 南大门到逸夫楼最短路径为60米 逸夫楼←博物馆←物理楼←北大门←南大门 南大门到博物馆最短路径为45米 博物馆←物理楼←北大门←南大门 南大门到物理楼最短路径为35米 物理楼←北大门←南大门 南大门到电信楼最短路径为60米 电信楼←一教←北大门←南大门 南大门到化学楼最短路径为50米 化学楼←物理楼←北大门←南大门 南大门到生科楼最短路径为145米 生科楼←建工楼←化学楼←物理楼←北大门←南大门 南大门到建工楼最短路径为100米 建工楼←化学楼←物理楼←北大门←南大门 南大门到北院食堂最短路径为115米 北院食堂←化学楼←物理楼←北大门←南大门 南大门到南院食堂最短路径为80米 南院食堂←八教←图书馆←南大门 南大门到竹园最短路径为135米 竹园←七教←桂园←毓秀园←图书馆←南大门 南大门到梅园最短路径为145米 梅园←七教←桂园←毓秀园←图书馆←南大门 南大门到桂园最短路径为95米 桂园←毓秀园←图书馆←南大门 南大门到菊园最短路径为125米 菊园←八教←图书馆←南大门 南大门到易百超市最短路径为145米 易百超市←七教←桂园←毓秀园←图书馆←南大门 南大门到北院生活园区最短路径为159米 北院生活园区←北院食堂←化学楼←物理楼←北大门←南大门 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2): 请输入要查询的两个景点名称 主楼 七教 主楼到七教最短路径为75米 七教←桂园←毓秀园←主楼 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2):3 请输入要查询的两个景点名称 桌喽 菊园 输入的名称不存在 __________________________________________________________ 请选择要进行的操作 1.查询景点信息 2:显示大门到各个地点的最短路径 3:查询两个景点之间的最短路径 0:退出 __________________________________________________________ 请选择(0~2): 校园导游实验报告 学号：200930457018 姓名：熊博 班级：09计科1班 完成日期：2010-12-21 1、问题描述 制作陶瓷学院的校园导游图，游客通过终端可询问：（1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线3，使游客可以不重复地游览各景点，最后回到出口（出口就在入口处旁边） 2、要求 （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。 3、实现提示 （1）第一实际是最短路径问题，如果有几条路径长度相同，可选择途径景点较少的路径提供给游客。 （2）第二问可采用深度优先搜索，如果有多种路径可选择，则选择带权路径最小的路线提供给游客。 2.概要设计： typedef struct ArCell { int adj; //路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct //图中顶点表示主要景点，存放景点的信息 { char name[30];int num;int x;int y;char introduction[500];//简介 }infotype;typedef struct { infotype vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;}MGraph;MGraph b; void dij(MGraph *);计算出起点到其他各个顶点之间的最短路径 void floyd(MGraph *);计算任意两个景点之间的最短路径 void Search(MGraph *G);查看景点信息 void jdbrowser();查看主要景点布局图 3.详细设计： main函数： void main(){ int k;system(“color cf”);system(“mode con: cols=140 lines=130”);b=InitGraph();system(“cls”);printf(“ 欢迎您进入景德镇陶瓷学院学校园导游咨询系统n”);printf(“ttn”);Sleep(1000);do { while(1) { printf(“ n”); printf(“ 主要景点列表 n”); printf(“ n”); printf(“ <1> 操场 <2> 游泳馆 n”); printf(“ <3> 3教 <4> 体育馆 n”); printf(“ <5> 2教 <6> 1教 n”); printf(“ <7> 图书馆 <8> 2实验楼 n”); printf(“ <9> 9实验楼 <10> 医院 n”); printf(“ <11> 东西办 <12> 9#宿舍楼 n”); printf(“ <13> 综合食堂 <14> 二三食堂 n”); printf(“ <15> 80广场 <16>大门 n”); printf(“ n”); printf(“ttn”); printf(“ ┏━━━━━━━━━━━━━━━━━━━━━━━┓n”); printf(“ ┃ 1.查看主要景点布局图 ┃n”); printf(“ ┃ 2.查看景点信息 ┃n”); printf(“ ┃ 3.查看某一景点到其他景点的最短路径 ┃n”); printf(“ ┃ 4.查看任意两个景点之间的最短路径 ┃n”); printf(“ ┃ 0.退出系统 ┃n”); printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━┛n”); printf(“请输入您的选择选择，按回车键结束:”); scanf(“%d”,&k); if(k<0||k>5) { printf(“输入有误请重新输入，按回车键结束!n”); scanf(“%d”,&k); } else break;} switch(k){ case 1:jdbrowser();system(“cls”);break;case 2:Search(&b);system(“cls”);break;case 3:dij(&b);system(“cls”);break;case 4:floyd(&b);system(“cls”);break;case 0:exit(0); } }while(1);} 图形初始化函数： MGraph InitGraph(){ MGraph G;int i,j;G.vexnum=17;G.arcnum=19;for(i=0;i G.vexs[i].num=i;strcpy(G.vexs[1].name,“操场”);strcpy(G.vexs[1].introduction,“足球场，现代化塑胶跑道,人造草坪,锻炼身体的场所”);strcpy(G.vexs[2].name,“游泳馆”);strcpy(G.vexs[2].introduction,“一般只是暑假期间开放，水不是很干净”);strcpy(G.vexs[3].name,“3教”);strcpy(G.vexs[3].introduction,“多媒体教学场所,设施先进,环境良好”);strcpy(G.vexs[4].name,“体育馆”);strcpy(G.vexs[4].introduction,“里面有篮球场还有羽毛球场，平时用作羽毛球场地”);strcpy(G.vexs[5].name,“2教”);strcpy(G.vexs[5].introduction,“学院第二大教学楼,环境较差”);strcpy(G.vexs[6].name,“1教”);strcpy(G.vexs[6].introduction,“学院最大的教学楼,共5层，环形建筑,适宜学习”);strcpy(G.vexs[7].name,“图书馆”);strcpy(G.vexs[7].introduction,“藏书60万册,设施良好，2楼为电子阅览室，环境幽雅”);strcpy(G.vexs[8].name,“2实验楼”);strcpy(G.vexs[8].introduction,“信息科学与技术学院所在地”);strcpy(G.vexs[9].name,“9实验楼”);strcpy(G.vexs[9].introduction,“学校机房所在地”);strcpy(G.vexs[10].name,“医院”);strcpy(G.vexs[10].introduction,“校医院,设施不是很齐全，收费较贵”);strcpy(G.vexs[11].name,“春晖楼”);strcpy(G.vexs[11].introduction,“全体教师办公场所，楼高12层，各种设施齐全”);strcpy(G.vexs[12].name,“9#宿舍楼”);strcpy(G.vexs[12].introduction,“装饰古朴，设施还算齐全，就是挤了点”);strcpy(G.vexs[13].name,“综合食堂”);strcpy(G.vexs[13].introduction,“新建标准化食堂，食物种类多，但是价格比较贵。”);strcpy(G.vexs[14].name,“二三食堂”);strcpy(G.vexs[14].introduction,“收费比较便宜的食堂，二楼的套餐还可以，主要是便宜，不过菜有点难吃”);strcpy(G.vexs[15].name,“80广场 ”);strcpy(G.vexs[15].introduction,“新建的广场，据说由80界校友捐赠。”);strcpy(G.vexs[16].name,“大门”);strcpy(G.vexs[16].introduction,“我们学校的大门，车辆进出的地方。设有保安。”);G.vexs[1].x=1;G.vexs[1].y=3;G.vexs[2].x=2;G.vexs[2].y=3;G.vexs[3].x=1;G.vexs[3].y=2;G.vexs[4].x=2;G.vexs[4].y=2;G.vexs[5].x=2;G.vexs[5].y=1;G.vexs[6].x=3;G.vexs[6].y=1;G.vexs[7].x=3;G.vexs[7].y=2;G.vexs[8].x=3;G.vexs[8].y=3;G.vexs[9].x=3;G.vexs[9].y=4;G.vexs[10].x=4;G.vexs[10].y=1;G.vexs[11].x=5;G.vexs[11].y=1;G.vexs[12].x=5;G.vexs[12].y=4;G.vexs[13].x=6;G.vexs[13].y=1;G.vexs[14].x=6;G.vexs[14].y=3;G.vexs[15].x=5;G.vexs[15].y=3;for(i=0;i for(j=0;j G.arcs[i][j].adj=INFINITY;G.arcs[1][2].adj=40;G.arcs[2][8].adj=80; G.arcs[2][4].adj=50;G.arcs[3][4].adj=10; G.arcs[4][7].adj=42; G.arcs[4][5].adj=50;G.arcs[5][6].adj=40; G.arcs[6][7].adj=50; G.arcs[6][16].adj=20;G.arcs[6][10].adj=100;G.arcs[7][8].adj=50;G.arcs[8][9].adj=100;G.arcs[8][15].adj=200;G.arcs[10][11].adj=100;G.arcs[11][13].adj=50; G.arcs[15][14].adj=80;G.arcs[13][14].adj=100;G.arcs[11][15].adj=100;G.arcs[12][15].adj=10;for(i=1;i for(j=1;j G.arcs[i][j].adj=G.arcs[j][i].adj; return G;}//InitGraph end 迪杰斯特拉算法求一点到任意其他景点的最短路径： void dij(MGraph * G){ int v,w,w1,i,j,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20];while(flag){ printf(“请您输入一个起始景点编号，按回车键结束:”); scanf(“%d”,&v0); if(v0<0||v0>G->vexnum) { printf(“景点编号不存在!请重新输入景点编号,按回车键结束:”); scanf(“%d”,&v0); } if(v0>=0&&v0 flag=0;} for(v=1;v final[v]=0; D[v]=G->arcs[v0][v].adj;for(w=1;w p[v][w]=0;if(D[v] { p[v][v0]=1;p[v][v]=1; } } D[v0]=1;final[v0]=1;for(i=1;i min=INFINITY; for(w=1;w if(!final[w]) if(D[w] final[v]=1; for(w=1;w if(!final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } } for(v=1;v flag=0;min=INFINITY; for(w=1;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].x printf(“向东走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].x>G->vexs[j].x) printf(“向西走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y printf(“向北走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y>G->vexs[j].y) printf(“向南走%dm”,G->arcs[w1][j].adj); printf(“-->%s”,G->vexs[j].name); w1=j; p[v][j]=0; } else break; }while(1); printf(“n 总路线长%dmnn”,D[v]);} printf(“完毕，按任意键继续!n”);getch();Floyd算法求任意两点间的最短距离： void floyd(MGraph * G) // 计算任意两个景点之间的最短路径 { int v,w,w1,i,j,v1,min,t=0,x,flag=1,v0; int final[20], D[20], p[20][20];while(flag){ printf(“请您输入一个起始景点编号，按回车键结束:”); scanf(“%d”,&v0); if(v0<0||v0>G->vexnum) { printf(“景点编号不存在!请重新输入景点编号:”); scanf(“%d”,&v0); } if(v0>=0&&v0 flag=0;} flag=1;while(flag){ printf(“请您输入一个目的地景点编号，按回车键结束:”); scanf(“%d”,&v1); if(v1<0||v1>G->vexnum) { printf(“景点编号不存在!请重新输入景点编号:”); scanf(“%d”,&v1); } if(v1>=0&&v1 flag=0;} for(v=0;v final[v]=0; D[v]=G->arcs[v0][v].adj; for(w=0;w p[v][w]=0; if(D[v] { p[v][v0]=1;p[v][v]=1; } } D[v0]=0;final[v0]=1;for(i=1;i min=INFINITY; for(w=0;w if(!final[w]) if(D[w] final[v]=1; for(w=0;w if(!final[w]&&(min+G->arcs[v][w].adj { D[w]=min+G->arcs[v][w].adj; for(x=0;x p[w][x]=p[v][x]; p[w][w]=1; } } v=v1; w1=v0; printf(“%s”,G->vexs[v0].name);do { flag=0;min=INFINITY; for(w=0;w { if(p[v][w]&&w!=v0) { flag=1; if(D[w] } } if(flag) { if(G->vexs[w1].x printf(“向东走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].x>G->vexs[j].x) printf(“向西走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y printf(“向北走%dm”,G->arcs[w1][j].adj); if(G->vexs[w1].y>G->vexs[j].y) printf(“向南走%dm”,G->arcs[w1][j].adj); printf(“-->%s”,G->vexs[j].name); w1=j; p[v][j]=0; } else break; }while(1);printf(“n 总路线长%dmnn”,D[v]);printf(“完毕，按任意键继续!n”);getch();} 查询景点信息函数： void Search(MGraph *G){ int k,flag=1;while(flag){ printf(“请您输入要查询的景点编号，按回车键结束:”); scanf(“%d”,&k); if(k<0||k>=G->vexnum) { printf(“景点编号不存在!请重新输入景点编号:”); scanf(“%d”,&k); } if(k>=0&&k flag=0;} printf(“┏━━┳━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“┃编号┃景点名称 ┃简介 ┃n”);printf(“┃%-4d┃%-16s┃%-96s┃n”,G->vexs[k].num,G->vexs[k].name,G->vexs[k].introduction);printf(“┗━━┻━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);printf(“完毕，按任意键继续!n”);getch();} 主要的景点显示函数： void jdbrowser(){ printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“● ●n”); printf(“● (9)九实验楼 (12)九栋 ●n”); printf(“● ┃ ┃ ●n”); printf(“● ┃ ┃ ●n”); printf(“● (1)操场━━(2)游泳馆━━━━(8)二实验楼━━━━━━━━━━━━━━━━━(15)80广场━━━━(14)二三食堂 ●n”);printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● (3)三教━━(4)体育馆━━━━━(7)图书馆 ┃ ┃ ●n”);printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● ┃ ┃ ┃ ┃ ●n”); printf(“● (5)二教━━━━━━(6)一教━━━━━━━━━━━━(10)医院━━━━━(11)东西办━━━━(13)综合食堂 ●n”);printf(“● ┃ ●n”); printf(“● (16)大门 ●n”); printf(“● ●n”); printf(“●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●n”);printf(“输出完毕，按任意键返回!n”);getch();} 4.使用说明： （1）.查看主要景点布局图（2）.查看景点信息 （3）.查看某一景点到其他景点的最短路径（4）.查看任意两个景点之间的最短路径 （0）.退出系统 5.测试结果： 主界面 景点图 景点信息 从某点到其他点的最短路径 任意两点的最短路径 退出系统 6.参考资料： 1、《数据结构（C语言版）》 严蔚敏，吴伟民 清华大学出版社 2、《数据结构—C语言描述》 耿国华等 西安电子科技大学出版社 3、Data Structure &Program Design in C Robert L.Kruse 清华大学出版社 4、《数据结构（用面向对象方法与C++描述）》 殷人昆 清华大学出版社 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高 南京信息工程大学实验（实习）报告 实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍 系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700 3实验一顺序表的基本操作及C语言实现 【实验目的】 1、顺序表的基本操作及 C 语言实现 【实验要求】 1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。 2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。 【实验内容】 1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作； 2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重 复的元素），并求这样的两个集合的并。 【实验结果】 [实验数据、结果、遇到的问题及解决] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 数据结构实验报告 一． 题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二． 解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include typedefintElemType; //数据类型 typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ ElemType data; structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;intInsertBST(BiTree&T,int key){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->data=key; T->lChild=T->rChild=NULL; return 1;} else if(key InsertBST(T->rChild,key);} else return 0;} BiTreeCreateBST(int a[],int n){//创建二叉树函数 BiTreebst=NULL;inti=0;while(i //数据域 InsertBST(bst,a[i]); i++;} returnbst;} int Delete(BiTree&T) { BiTreeq,s; } if(!(T)->rChild){ //右子树为空重接它的左子树 q=T;T=(T)->lChild;free(q);}else{ if(!(T)->lChild){ //若左子树空则重新接它的右子树 q=T;T=(T)->rChild;}else{ q=T;s=(T)->lChild;while(s->rChild){ q=s;s=s->rChild;} (T)->data=s->data;//s指向被删除结点的前驱 if(q!=T) q->rChild=s->lChild; else q->lChild=s->lChild; free(s);} } return 1; //删除函数，在T中删除key元素 intDeleteBST(BiTree&T,int key){ if(!T)return 0;else{ if(key==(T)->data)return Delete(T); else{ if(key<(T)->data) returnDeleteBST(T->lChild,key); else returnDeleteBST(T->rChild,key); } } } intPosttreeDepth(BiTree T){//求深度 inthr,hl,max;if(!T==NULL){ hl=PosttreeDepth(T->lChild);hr=PosttreeDepth(T->rChild);max=hl>hr?hl:hr;return max+1;} else return 0; } void printtree(BiTreeT,intnlayer){//打印二叉树 if(T==NULL)return;printtree(T->rChild,nlayer+1);for(inti=0;i ”);} printf(“%dn”,T->data);printtree(T->lChild,nlayer+1);} void PreOrderNoRec(BiTree root)//先序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;while(NULL!=p||num>0){ while(NULL!=p) { printf(“%d ”,p->data); stack[num++]=p; p=p->lChild; } num--; p=stack[num]; p=p->rChild;} printf(“n”);} void InOrderNoRec(BiTree root)//中序非递归遍历 { BiTree p=root; } intnum=0;BiTreestack[50];while(NULL!=p||num>0){ while(NULL!=p){ stack[num++]=p; p=p->lChild;} num--;p=stack[num];printf(“%d ”,p->data);p=p->rChild;} printf(“n”);void PostOrderNoRec(BiTree root)//后序非递归遍历 { BiTree p=root;BiTreestack[50];intnum=0;BiTreehave_visited=NULL; while(NULL!=p||num>0){ while(NULL!=p) { stack[num++]=p; p=p->lChild; } p=stack[num-1]; if(NULL==p->rChild||have_visited==p->rChild) { printf(“%d ”,p->data); num--; have_visited=p; p=NULL; } else { p=p->rChild; } } printf(“n”);} int main(){//主函数 printf(“ ---------------------二叉排序树的实现-------------------”);printf(“n”);int layer;inti;intnum;printf(“输入节点个数:”);scanf(“%d”,&num);printf(“依次输入这些整数（要不相等）”);int *arr=(int*)malloc(num*sizeof(int));for(i=0;i scanf(“%d”,arr+i);} BiTreebst=CreateBST(arr,num);printf(“n”);printf(“二叉树创建成功!”);printf(“n”);layer=PosttreeDepth(bst);printf(“树状图为:n”);printtree(bst,layer);int j;int T;int K;for(;;){ loop: printf(“n”);printf(“ ***********************按提示输入操作符************************:”);printf(“n”);printf(“ 1:插入节点 2:删除节点 3:打印二叉树 4:非递归遍历二叉树 5:退出”);scanf(“%d”,&j); switch(j){ case 1: printf(“输入要插入的节点:”); scanf(“%d”,&T); InsertBST(bst,T); printf(“插入成功!”);printf(“树状图为:n”); printtree(bst,layer); break; case 2: } printf(“输入要删除的节点”);scanf(“%d”,&K);DeleteBST(bst,K);printf(“删除成功!”);printf(“树状图为:n”);printtree(bst,layer);break;case 3: layer=PosttreeDepth(bst);printtree(bst,layer);break;case 4: printf(“非递归遍历二叉树”);printf(“先序遍历:n”);PreOrderNoRec(bst);printf(“中序遍历:n”);InOrderNoRec(bst); printf(“后序遍历:n”); PostOrderNoRec(bst); printf(“树状图为:n”); printtree(bst,layer); break;case 5: printf(“程序执行完毕!”); return 0;} goto loop;} return 0;对于第四小问，要储存学生的三个信息，需要把上面程序修改一下，二叉树结构变为 typedefintElemType; //数据类型 typedefstring SlemType; typedefint Status; //返回值类型 //定义二叉树结构 typedefstructBiTNode{ SlemType name;ElemType score;ElemType no; //数据域 structBiTNode *lChild, *rChild;//左右子树域 }BiTNode, *BiTree;参数不是key,而是另外三个 intInsertBST(BiTree&T,intno,intscore,string name){//插入二叉树函数 if(T==NULL){ T =(BiTree)malloc(sizeof(BiTNode)); T->no=no;T->name=name;T->score=score; T->lChild=T->rChild=NULL; return 1;} else if(no InsertBST(T->rChild,no,score,name);} else return 0;} 其他含参函数也类似 即可完成50个信息存储 用数组存储50个信息，查看以往代码 #include int main(){ cout<<“ 欢迎来到学生管理系统”< cout<<“该学号信息已经存在，添加失败”< break;} cout<<“重新输入添加的学号”< for(int n=m+1;n<20;n++){ if(ptr[m].average() student a; a=ptr[m]; ptr[m]=ptr[n]; ptr[n]=a; }} ptr[m].show();} break;case 4: cout<<“谢谢使用”< 二叉排序树储存数据界面（储存学生信息略） 创建二叉树： 插入节点： 删除节点： 非递归遍历： 退出： 数组储存学生信息界面 分析查找效率： 因为二叉树查找要创建二叉树，而数组查找只创建一个数组，二叉树的创建时间比较长，所以对于数据量较少的情况下数组的查找效率比较高。但当数据量增加时，二叉树的查找优势就显现出来。所以数据量越大的时候，二叉树的查找效率越高。 四． 总结与改进 这个实验工作量还是很大的，做了很久。树状图形输出还是不美观，还需要改进。 一开始打算用栈实现非递归，但是根据书里面的伪代码发现部分是在C++编译器里运行不了的（即使补充了头文件和数据的定义），所以之后参考了网上的数组非递归，发现其功能和栈相似。 递归遍历的实现比非递归的遍历真的简单很多。 开始时只看到前三问，所以没有写到储存学生数据的代码，里面还可以用clock（）函数加一个计算查找所要数据时间的代码，让二叉树查找与数组查找到效率比较更加直观。第二篇：校园导游实验报告
第三篇：数据结构实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
![下载校园导游实验报告——数据结构[范文大全]word格式文档](http://static.xiexiebang.com/skin/default/images/icon_word.png){kind=icon}
点击咨询 