___《数据结构》课程实验报告(实验5——图的存储方式和应用)参考答案

数据结构实验报告实验五图子系统实验题目：图的遍历问题专业班级：网络工程 1002班组长：王星（30）组员：郭坤铭（43）张磊（44）2012年 5月 18日实验报告实验类型__综合__实验室_软件实验室二__一、实验题目图的遍历问题二、实验目的和要求1、掌握图的存储思想及其存储实现2、掌握图的深度、广度优先遍历算法思想及其程序实现3、掌握图的常见应用算法的思想及其程序实现三、需求分析本演示程序用c++6.0编写，完成用户用键盘输入以下结点数据：太原、成都、北京、上海、天津、大连、河北。

（1）建立一个有向图或无向图（自定）的邻接表并输出该邻接表。

（2）在图的邻接表的基础上计算各顶点的度，并输出。

（3）以有向图的邻接表为基础实现输出它的拓扑排序序列。

（4）采用邻接表存储实现无向图的深度优先遍历。

（5）采用邻接表存储实现无向图的广度优先遍历。

（6）采用邻接矩阵存储实现无向图的最小生成树的 PRIM 算法。

最后，在主函数中设计一个简单的菜单，分别调试上述算法。

四、概要设计为了实现上述程序功能，需要定义如下内容基本数据类型定义如下：typedef struct node{ //边表结点int adj; //边表结点数据域struct node *next;}node;typedef struct vnode //顶点表结点{ char name[20];node *fnext;}vnode,AList[20];typedef struct{ AList List; //邻接表int v,e; //顶点树和边数}*Graph;Graph CreatDG(){ } //建立无向邻接表Graph CreatAG(){ } //有向邻接图void Print(Graph G){} //输出图的邻接表void CreateAN(AGraph *G1){} //构造邻接矩阵结构的图G void Du(Graph G){} //输出各顶点的度数void DFSTravel(Graph G){} //深度优先遍历void BFSTravel(Graph G){} //广度优先遍历五、详细设计#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct node{//边表结点int adj;//边表结点数据域struct node *next;}node;typedef struct vnode{//顶点表结点char name[20];node *fnext;}vnode,AList[20];typedef struct{AList List;//邻接表int v,e;//顶点树和边数}*Graph;//建立无向邻接表Graph CreatDG(){Graph G;int i,j,k;node *s;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数(空格隔开)：");scanf("%d%d",&G->v,&G->e);//读入顶点数和边数for(i=0;i<G->v;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",G->List[i].name);//读入顶点信息G->List[i].fnext=NULL;//边表置为空表}for(k=0;k<G->e;k++){printf("请请输入第%d条边的两顶点序号(空格隔开)：",k+1);scanf("%d%d",&i,&j);//读入边（Vi,Vj）的顶点对序号;s=(node *)malloc(sizeof(node));//生成边表结点s->adj=j;s->next=G->List[i].fnext;G->List[i].fnext=s;//将新结点*s插入顶点Vi的边表头部s=(node *)malloc(sizeof(node));s->adj=i;//邻接点序号为is->next=G->List[j].fnext;G->List[j].fnext=s;// 将新结点*s插入顶点Vj的边表头部}return G;}//有向邻接图Graph CreatAG(){Graph G;int i,j,k;node *q;G=malloc(20*sizeof(vnode));printf("请输入图的顶点数和边数【空格隔开】：");scanf("%d%d",&G->v,&G->e);for (i=0;i<G->v;i++){printf("请输入图中第%d元素：",i+1);scanf("%s",&G->List[i].name); //读入顶点信息G->List[i].fnext=NULL;}for (k=0;k<G->e;k++){printf("请请输入第%d边的两顶点序号【空格隔开】：",k+1);scanf("%d%d",&i,&j);q=(node *)malloc(sizeof(node)); //生成新边表结点sq->adj=j; //邻接点序号为jq->next=G->List[i].fnext;G->List[i].fnext=q;}return G;}//输出图的邻接表void Print(Graph G){int i;node *p;printf("\t=======邻接表========\n");for(i=0;i<G->v;i++){p=G->List[i].fnext;printf("%d | %3s",i,G->List[i].name);while(p){printf("->%3s",G->List[p->adj].name);printf("->%d",p->adj);p=p->next;}printf("\n");}}typedef struct {char vex[20];}Lists[20];typedef struct{Lists l;int edge[20][20];//邻接矩阵int v1,e1;//顶点数和弧数}AGraph;typedef struct{int data; /* 某顶点与已构造好的部分生成树的顶点之间权值最小的顶点 */int lowcost; /* 某顶点与已构造好的部分生成树的顶点之间的最小权值 */}ClosEdge[20]; /* 用普里姆算法求最小生成树时的辅助数组 */ void CreateAN(AGraph *G1){/* 构造邻接矩阵结构的图G */int i,j,k,w;printf("请输入图的顶点数和边数（空格隔开）：");scanf("%d%d",&G1->v1,&G1->e1);//读入顶点数和边数for(i=1;i<=G1->v1;i++){printf("请输入图%d号元素：",i);scanf("%s",&G1->l[i].vex);//读入顶点信息}for(i=1;i<=G1->v1;i++)//初始化邻接矩阵for(j=1;j<=G1->v1;j++)G1->edge[i][j] = 9;for(k=1;k<=G1->e1;k++){printf("请输入两顶点及边的权值（空格隔开）：");scanf("%d%d%d",&i,&j,&w);G1->edge[i][j]=w;G1->edge[j][i]=w;}}void PrintAN(AGraph *G1){int i,j;printf("\t=======邻接矩阵========\n");for(i=1;i<=G1->v1;i++){for(j=1;j<=G1->v1;j++)printf("%3d",G1->edge[i][j]);printf("\n");}}//输出各顶点的度数void Du(Graph G){int i,j;printf("\n<----各点度数---->\n");for(i=0;i<G->v;i++){p=G->List[i].fnext;printf("顶点%2s的度为：",G->List[i].name);j=0;while(p){j++;p=p->next;}printf("%d\n",j);}}//栈typedef struct stack{int x;struct stack *next;}stack;int push(stack *s,int i){stack *p;p=(stack *)malloc(sizeof(stack));p->x=i;p->next=s->next;s->next=p;return 1;}int pop(stack *s,int j){stack *p=s->next;//保存栈顶指针j=p->x;s->next=p->next; //将栈顶元素摘下free(p);//释放栈顶空间return j;}//拓扑排序void Topo(Graph G,stack *s){int i,k, count;int j=0;int indegree[20]={0};for(i=0;i<G->v;i++){p=G->List[i].fnext;;while(p!=NULL){indegree[p->adj]++;p=p->next;}}for(i=0;i<G->v;i++)if(indegree[i]==0)push(s,i);count=0;while(s->next!=NULL){i=pop(s,j);printf("%2s ",G->List[i].name);++count;for(p=G->List[i].fnext;p!=NULL;p=p->next){ k=p->adj;if(!(--indegree[k]))push(s,k);}}if(count<G->v) printf("有回路!");}void DFS(Graph G,int i,int flag[]){node *p;printf("%2s ",G->List[i].name);flag[i]=1;p=G->List[i].fnext;while(p){if(!flag[p->adj])DFS(G,p->adj,flag);p=p->next;}}//深度优先遍历void DFSTravel(Graph G){int i;int flag[20];//标志数组for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(!flag[i])DFS(G,i,flag);}//建立队列typedef struct{int *elem;int front, rear;}*Queue;//队列初始化void InitQueue(Queue Q){Q->elem=(int *)malloc(20*sizeof(int));if(!Q->elem)exit(0);Q->front=Q->rear=0;}//入队void Enter(Queue Q, int e){if((Q->rear + 1)%20!= Q->front)Q->elem[Q->rear ]=e;elseprintf("队列满!\n");Q->rear=(Q->rear+1)%20;}//出队void Leave(Queue Q, int e){if(Q->rear != Q->front)e=Q->elem[Q->front];elseprintf("队列空!\n");Q->front=(Q->front+1)%20;}//广度优先遍历void BFSTravel(Graph G){Queue Q;node *p;int i,j=0;int flag[20];//标志数组Q=malloc(sizeof(20));InitQueue(Q);for(i=0;i<G->v;i++)flag[i]=0;for(i=0;i<G->v;i++)if(flag[i]==0){flag[i]=1;printf("%2s",G->List[i].name);Enter(Q,i);while(Q->front!=Q->rear){Leave(Q,j);//队头元素出队并置为jp=G->List[j].fnext;while(p!=NULL){if(flag[p->adj]==0){printf("%2s ",G->List[p->adj].name);flag[p->adj]=1;Enter(Q,p->adj);}p=p->next;}}}}int minimum(ClosEdge cl,int vnum){int i;int w,p;w=1000;for(i=1;i<=vnum;i++)if(cl[i].lowcost!=0&&cl[i].lowcost<w){w=cl[i].lowcost;p=i;}return p;}void Prim(AGraph *G1,int u){ClosEdge closedge;int i,j,k;for(j=1;j<=G1->v1;j++) /* 辅助数组初始化 */if(j!=u){closedge[j].data=u;closedge[j].lowcost=G1->edge[u][j];}closedge[u].lowcost=0; /* 初始，U={u} */for(i=1;i<G1->v1;i++){k=minimum(closedge,G1->v1); /* 求出生成树的下一个顶点*/printf("%d-----%d\n",closedge[k].data,k); /* 输出生成树的边 */closedge[k].lowcost=0; /* 第k顶点并入U集 */for(j=1;j<=G1->v1;j++) /* 新顶点并入U后，修改辅助数组*/if(G1->edge[k][j]<closedge[j].lowcost){closedge[j].data=k;closedge[j].lowcost=G1->edge[k][j];}}}//菜单列表void menu(){printf("\t**********************图的遍历问题**********************\n");printf("\t\t------- 1.建立无向邻接图---------\n");printf("\t\t------- 2.建立有向邻接图---------\n");printf("\t\t------- 3.建立无向邻接矩阵---------\n");printf("\t\t------- 4.输出各顶点的度---------\n");printf("\t\t------- 5.拓扑排序---------\n");printf("\t\t------- 6.深度优先遍历---------\n");printf("\t\t------- 7.广度优先遍历---------\n");printf("\t\t------- 8.prim算法生成最小生成树---------\n");printf("\t\t------- 9-退出---------\n");printf("\t********************************************** **********\n");}//主函数void main(){Graph G;AGraph G1;int choice,u;stack *s=(stack *)malloc(sizeof(stack));s->next =NULL;while(1){menu();printf("请输入选择:");scanf("%d",&choice);switch(choice){case1:G=CreatDG();Print(G);printf("\n\n");break;case2:G=CreatAG();Print(G);printf("\n\n");break;case3:CreateAN(&G1);PrintAN(&G1);printf("\n\n");break; case4:Du(G);printf("\n\n");break;case5:printf("拓扑排序:");Topo(G,s);printf("\n\n");break;case6:printf("深度优先遍历:");DFSTravel(G);printf("\n\n");break;case7:printf("广度优先遍历:");BFSTravel(G);printf("\n\n");break;case 8:printf("请输入起点序号:");scanf("%d",&u);printf("Prim算法:\n");Prim(&G1,u);printf("\n");break;case 9: exit(0);default: printf("输入错误,请重新输入：\n\n ");}}}六、使用说明1、程序名为实验5.exe，运行坏境为DOS.程序执行后显示如图所示：2、建立无向邻接图3、输出各顶点的度4、进行深度优先遍历5、进行广度优先遍历6、建立有向邻接图7、拓扑排序8、建立无向邻接矩阵9、prim算法生成最小生成树七、实验总结本次实验对我们来说有不小的难度，花费了很长的时间，在大家的商量讨论和共同努力下，最终完成了实验的内容，组长在此过程中很认真负责，使组员一步一步前进。

实验报告
开课学院及实验室: 年月日
五实验方法
1 对问题进展需求分析, 选取详细城市结点, 通过调研获取城市间的交通网络, 选取主要的通行道路抽象为图的无向带权边。

2 进展概要设计和详细设计, 形成模块间的调用构造图和模块的算法。

3 编写程序, 设计测试用例进展测试。

4 完成开发文档。

六实验结果
1需求分析: 在中国城市, 电子地图的认知度和使用率正在飞快递增, 随着用户量不断增加, 纸质地图逐渐被电子地图取而代之。

在大中型城市, 电子地图已经成为绝大多数用户出行前首选的参照工具和查询途径。

电子地图强调准确性、简单易用以及查询速度。

电子地图的另外一个特点是使用方便, 无论是通过互联网还是手机都可以方便接触到并使用。

出行前用电脑通过互联网地图规划道路、查找目的地, 路上那么可以用手机连接无线网络, 通过手机地图随时修正道路和辨识方向。

2概要设计:
3详细设计:
4编程遇到的问题和调试分析:
5用户手册:
概述: 简单的交通咨询系统
功能:
1.珠三角地区交通查询；
2.珠三角地区各城市信息查询。

使用说明:
1.翻开方法: 翻开命令行窗口, 进入map.exe文件所在目录〔如: cd e:/map〕, 输入map, 进入程序。

2.构造地图信息, 按提示输入map.txt.
3.交通查询功能的使用: 输入1进入查询, 按要求输入起点城市编号和终点城市编号, 回车即可。

4.城市信息查询功能的使用：输入2进入查询, 按要求输入城市编号, 回车即可。

6 测试结果:
7 附录〔源程序清单〕。

数据结构实验报告实验5一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构，如链表、栈、队列、树和图等，并通过实际编程实现，提高对数据结构的操作和应用能力。

同时，培养解决实际问题的思维和编程能力，提高代码的可读性、可维护性和效率。

二、实验环境本次实验使用的编程语言为C+＋，开发环境为Visual Studio 2019。

三、实验内容1、链表的基本操作创建链表插入节点删除节点遍历链表2、栈的实现与应用用数组实现栈用链表实现栈栈的应用：括号匹配3、队列的实现与应用用数组实现队列用链表实现队列队列的应用：排队模拟4、二叉树的遍历前序遍历中序遍历后序遍历5、图的表示与遍历邻接矩阵表示法邻接表表示法深度优先遍历广度优先遍历四、实验步骤1、链表的基本操作创建链表：首先定义一个链表节点结构体，包含数据域和指向下一个节点的指针域。

然后通过动态内存分配创建链表节点，并将节点逐个连接起来，形成链表。

插入节点：根据插入位置的不同，分为在表头插入、在表尾插入和在指定位置插入。

在指定位置插入时，需要先找到插入位置的前一个节点，然后进行节点的连接操作。

删除节点：同样需要根据删除位置的不同进行处理。

删除表头节点时，直接将头指针指向下一个节点；删除表尾节点时，找到倒数第二个节点，将其指针置为空；删除指定位置节点时，找到要删除节点的前一个节点，然后调整指针。

遍历链表：通过从链表头开始，依次访问每个节点，输出节点的数据。

2、栈的实现与应用用数组实现栈：定义一个固定大小的数组作为栈的存储空间，同时用一个变量记录栈顶位置。

入栈操作时，先判断栈是否已满，如果未满则将元素放入栈顶位置，并更新栈顶位置；出栈操作时，先判断栈是否为空，如果不空则取出栈顶元素，并更新栈顶位置。

用链表实现栈：与链表的操作类似，将新元素添加在链表头部作为栈顶。

括号匹配：输入一个包含括号的字符串，使用栈来判断括号是否匹配。

遇到左括号入栈，遇到右括号时与栈顶的左括号进行匹配，如果匹配成功则出栈，否则括号不匹配。

《数据结构》实验报告实验一一、实验目的及要求理解线性表的顺序存储结构；熟练掌握顺序表结构及其有关算法的设计；理解线性表的链式存储结构；熟练掌握动态链表结构及其有关算法的设计；根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法；深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时巩固对这两种结构的构造方法的理解。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以顺序表作存储结构，实现线性表的插入、删除；2.以单链表作存储结构，实现有序表的合并；3.利用栈（以顺序栈作存储结构）实现进制转换，并用队列（以链队列作存储结构）计算并打印杨辉三角。

四、源程序清单五、实验结果六、总结实验二一、实验目的及要求掌握二叉树的动态存储结构--二叉链表，掌握二叉树的三种遍历方法，会运用三种遍历的方法求解有关问题。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以二叉链表作存储结构，建立一棵二叉树；2.输出其先序、中序、后序遍历序列；3.求出它的深度；4.统计其叶子结点数四、源程序清单五、实验结果六、总结实验三一、实验目的及要求掌握图的存储结构及其建立算法，熟练掌握图的两种遍历算法及其应用。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.以邻接矩阵法作存储结构，建立一个无向图；2.输出该图的深度优先搜索序列；3.输出该图的广度优先搜索序列；4. 设计算法求出该图的连通分量个数及边的数目。

四、源程序清单五、实验结果六、总结实验四一、实验目的及要求掌握顺序表的查找方法，尤其是折半查找方法。

掌握二叉排序树的查找算法。

二、实验环境硬件：计算机软件：Microsoft Visual C++三、实验内容1.建立一个顺序表，用顺序查找的方法对其实施查找；2.建立一个有序表，用折半查找的方法对其实施查找；3.建立一个二叉排序树，根据给定值对其实施查找；4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。

2、熟练掌握图的存储结构。

3、熟练掌握图的两种遍历算法。

二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。

[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。

以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。

【测试数据】由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握图的相关概念。

2、掌握图的逻辑结构和存储结构。

3、掌握图的两种遍历算法的实现。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。

实验五图的存储与遍历1、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(dfs)和广度优先遍历（BFS）操作的实现。

2、实验预备知识（1）图的存储结构：邻接矩阵表示法和邻接表表示法。

邻接矩阵表示法除了要用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外还有图的顶点数和边数。

邻接表表示法类似于树的孩子链表表示法。

（2）图的遍历方法有深度优先遍历（Depth－First Traersal）和广度优先遍历（Breadth－First Traversal），简称 DFS和BFS。

DFS对图遍历时尽可能先对纵深方向进行搜索；BFS是类似于树的按层次遍历。

3、实验内容题目1对以邻接矩阵为存储结构的图进行 DFS和 BFS遍历(1) 问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4．18所示。

(4) 实现提示：图的DFS遍历可通过递归调用或用栈来实现。

其思想是：只要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结点，然后从这个结点继续进行DFS遍历。

在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。

若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。

BFS遍历可利用队列来帮助实现，也可以用栈。

实现方法与二叉树的层次遍历类似。

题目2对以邻接表为存储结构的图进行DFS和BFS遍历(1) 问题描述：以邻接表为存储结构，实现图的DFS和BFS遍历。

(2) 基本要求：建立一个图的邻接表存储，输出顶点的一种DFS和BFS序列。

(3) 测试数据：如图4.19所示：(4) 实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。

实验五：图的操作及应用实验学时：4实验类型：综合型一、实验目的1.理解图的逻辑结构和物理结构；2.掌握图的邻接矩阵和邻接表存储表示的实现方法;3.掌握图的深度优先和广度优先遍历算法的实现;4.掌握拓扑排序算法的实现方法。

二、实验条件Visual C++ 6.0三、实验原理及相关知识1.图的邻接矩阵和邻接表存储结构的描述；2.图的邻接矩阵和邻接表存储表示的算法；3.图的深度优先和广度优先遍历算法；4.拓扑排序算法。

四、实验步骤1. 实现图的邻接矩阵的存储表示。

2. 实现图的邻接表存储表示。

3. 实现图的深度优先和广度优先遍历算法。

4. 实现拓扑排序算法。

5. 调用以上函数实现以下操作：(1) 建立图。

(2) 输出基于邻接表存储的深度优先和广度优先遍历序列。

(3) 输出有向图的拓扑排序序列。

参考代码：要求：补充完整以下代码使其能够运行通过。

#include "stdio.h"#include "malloc.h"#include "string.h"#define INFINITY 10000// 用整型最大值代替∞#define MAX_VERTEX_NUM 20 // 最大顶点个数#define OK 1#define ERROR 0#define FALSE 0#define TRUE 1#define MAXQSIZE100typedef int QElemType;typedef float VRType;typedef float InfoType;typedef char VertexType;typedef char VexType;//============邻接矩阵的定义============typedef struct {VRType adj;InfoType info; // 该弧相关信息的指针(可无)}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedef struct {VertexType vexs[MAX_VERTEX_NUM][100]; // 顶点向量AdjMatrix arcs; // 邻接矩阵int vexnum,arcnum; // 图的当前顶点数和弧数} MGraph ;//=======================邻接矩阵的定义========//=================================邻接表的定义========= typedef struct ArcNode{ // 表结点int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc; // 指向下一条弧的指针float info; // 网的权值指针} ArcNode;typedef struct{ // 头结点VertexType data[100]; // 顶点信息ArcNode *firstarc; // 第一个表结点的地址} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum,arcnum; // 图的当前顶点数和弧数}ALGraph;int visited[MAX_VERTEX_NUM];//=================邻接表的定义=========================//=========队列定义和基本操作=============== typedef struct QNode1{QElemType data;struct QNode1 *next;}QNode, *QueuePtr;typedef struct { //链队列的定义QElemType *base;int front;int rear;} SqQueue;typedef struct{QueuePtr front;QueuePtr rear;}LinkQueue;LinkQueue InitQueue(LinkQueue Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(1);Q.front->next=NULL;return Q;}int EnQueue(LinkQueue* Q, QElemType e){QueuePtr p;if( !(p=(QueuePtr)malloc(sizeof(QNode))) )return ERROR;p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;return OK;}int DeQueue(LinkQueue *Q, QElemType *e) {QueuePtr p;if( Q->front == Q->rear )return ERROR;p = Q->front->next;*e = p->data;Q->front->next = p->next;if(Q->rear == p) Q->rear = Q->front;free(p);return OK;}int QueueEmpty(LinkQueue *Q) {if(Q->front ==Q->rear) return 1;else return 0;}int DestroyQueue( LinkQueue *Q ){while(Q->front) {Q->rear=Q->front->next;free(Q->front);Q->front=Q->rear;}return OK;}//===================队列定义和基本操作===============int LocateVex(MGraph G,char *vert){ int i;for(i=0; i<G.vexnum; i++)if(strcmp(G.vexs[i],vert)==0)return i;return -1;}int LocateVex1(ALGraph G,char *vert){ int i;for(i=0; i<G.vexnum; i++)if(strcmp(G.vertices[i].data,vert)==0)return i;return -1;}MGraph CreateGraph_UDN( MGraph G ){//建立无向网G的邻接矩阵int i, j,k;float w;VexType v1[100], v2[100];printf("输入顶点数,数边数：");scanf("%d %d", &G.vexnum, &G.arcnum);for(i=0; i<G.vexnum; i++) // 读入所有的顶点{ printf("输入第%d个顶点的信息：",i+1);scanf("%s", &G.vexs[i]);}for(i=0; i <G.vexnum; i++) //初始化邻接矩阵for(j=0; j<G.vexnum; j++)G.arcs[i][j].adj=INFINITY;for(k=0; k<G.arcnum; k++) { // 输入所有的边printf("输入第%d条边依附的两个顶点和边上的权值:",k+1);scanf("%s %s %f", &v1, &v2, &w);// 查询两个顶点在图中存储的位置i = LocateVex(G, v1);j = LocateVex(G, v2);if (i==-1 || j==-1){printf("输入的边不正确\n"); return;}G.arcs[i][j].adj = w;G.arcs[j][i].adj = G.arcs[i][j].adj;}return G;}ALGraph CreateALGraph_UDN(ALGraph G )//建立无向网G的邻接表{int i,j,k;float w;ArcNode * p;VexType v1[100], v2[100];printf("输入顶点数,数边数：");scanf("%d %d",&(G.vexnum),&(G.arcnum)); /* 读入顶点数和边数*/for(i=0;i<G.vexnum;i++) /* 建立有n个顶点的顶点表*/{printf("输入第%d个顶点的信息：",i+1);scanf("%s",&(G.vertices[i].data)) ; /* 读入顶点信息*/G.vertices[i].firstarc=NULL; /* 顶点的边表头指针设为空*/}for(k=0;k<G.arcnum;k++ ) /* 建立边表*/{printf("输入一条边依附的两个顶点和边上的权值:");scanf("%s %s %f",&v1,&v2,&w) ; /* 读入边<Vi，Vj>的顶点对应序号*/i = LocateVex1(G, v1);j = LocateVex1(G, v2);if (i==-1 || j==-1){printf("输入的边不正确\n"); return;}p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生成新边表结点p */p->adjvex=j; /* 邻接点序号为j */p->info =w;p->nextarc=G.vertices[i].firstarc; /* 将新边表结点p插入到顶点Vi的链表头部*/G.vertices[i].firstarc=p;p=(ArcNode*)malloc(sizeof(ArcNode) ); /* 生成新边表结点p */p->adjvex=i; /* 邻接点序号为i */p->info =w;p->nextarc=G.vertices[j].firstarc; /* 将新边表结点p插入到顶点Vj的链表头部*/G.vertices[j].firstarc=p;}return G;} /*CreateALGraph*/VisitFunc(char *ch)//输出顶点的信息{printf("%s ",ch);}void DFS(ALGraph G, int v ) {int j;ArcNode *p;VisitFunc(G.vertices[v].data); // 访问第v个顶点visited[v]=TRUE; // 设置访问标志为TRUE(已访问)for(p=G.vertices[v].firstarc; p;p=p->nextarc){j=p->adjvex;if( !visited[j] ) DFS(G, j);}}void DFSTraverse( ALGraph G){//图的深度优先遍历算法int v;for(v=0; v<G.vexnum; v++)visited[v]=FALSE; // 访问标志数组初始化(未被访问) for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v); // 对尚未访问的顶点调用DFS }void BFSTraverse(ALGraph G) //图的广度优先遍历算法{int v,j,u ;ArcNode *p;LinkQueue Q;Q=InitQueue(Q); // 置空的辅助队列Qfor(v=0; v<G.vexnum; v++)visited[v]=FALSE; // 置初值for(v=0; v<G.vexnum; v++)if(!visited[v]){visited[v]=TRUE; // 设置访问标志为TRUE(已访问)VisitFunc(G.vertices[v].data);EnQueue( &Q, v ); // v入队列while(!QueueEmpty(&Q)){DeQueue(&Q,&u); // 队头元素出队并置为ufor(p=G.vertices[u].firstarc; p;p=p->nextarc){j=p->adjvex;if( !visited[j] ){visited[j]=TRUE;VisitFunc(G.vertices[j].data);EnQueue(&Q, j);}}}}DestroyQueue( &Q );}//实现建立有向网的邻接矩阵和邻接表的函数MGraph CreateGraph_DN( MGraph G ){//建立有向网G的邻接矩阵{}ALGraph CreateALGraph_DN(ALGraph G )//建立有向网G的邻接表{}Print_MGraph(MGraph G)//输出图的邻接矩阵表示{int i,j;for(i=0;i<G.vexnum;i++){ for(j=0;j<G.vexnum;j++)printf("%f ",G.arcs[i][j].adj ); /*邻接矩阵*/printf("\n");}}Print_ALGraph(ALGraph G) //输出图的邻接表表示{int i,j;ArcNode *p;for(i=0;i<G.vexnum;i++){printf("%s",G.vertices[i].data ); /* 顶点信息*/p=G.vertices[i].firstarc ;while(p!=NULL) /* 表节点信息*/{printf("->%s",G.vertices[p->adjvex ].data);p=p->nextarc ;} /* 顶点的边表头指针设为空*/printf("\n");}}void FindInDegree(ALGraph G, int *indegree){int i,k;ArcNode *p;for (i=0; i<G.vexnum; ++i){for (p=G.vertices[i].firstarc; p; p=p->nextarc) {{k = p->adjvex;indegree[k]++; }}}}//===================拓扑排序==============================int TopologicalSort(ALGraph G) {// 有向图G采用邻接表存储结构。

数据结构实验报告数据结构实验报告一、引言数据结构是计算机科学中非常重要的一门课程，它涉及到数据的存储、组织和管理等方面。

通过实验学习，我们可以更好地理解和掌握不同的数据结构，提升我们在编程中解决实际问题的能力。

二、实验目的本次实验的主要目的是通过实际操作，加深对数据结构的理解，学习并掌握不同数据结构的特点和应用场景，提高编程能力。

三、实验内容1. 实验环境的搭建在开始实验之前，我们需要搭建相应的实验环境。

首先，我们选择合适的集成开发环境（IDE），如Eclipse或IntelliJ IDEA，并安装好Java Development Kit（JDK）。

然后，根据实验要求，下载并安装相应的数据结构库或框架。

2. 实验一：线性表线性表是最基本且最常用的数据结构之一，它可以用于存储一系列具有相同数据类型的元素。

实验中，我们需要实现一个线性表的基本操作，包括插入、删除、查找、修改等。

3. 实验二：栈和队列栈和队列是两种常用的数据结构，它们都是线性表的衍生结构，但在操作上有一些特殊的限制。

实验中，我们需要实现栈和队列的基本操作，并比较它们在不同场景下的优劣。

4. 实验三：树和二叉树树是一种非线性的数据结构，它以分层的方式存储数据。

二叉树是树的一种特殊情况，其中每个节点最多只有两个子节点。

实验中，我们需要实现树和二叉树的构建和遍历算法，并掌握它们在实际问题中的应用。

5. 实验四：图图是一种非线性的数据结构，由节点和边组成。

实验中，我们需要实现图的构建和遍历算法，并应用它们解决实际的图相关问题。

四、实验结果与分析通过实验，我们得到了以下结果和分析：1. 在线性表实验中，我们成功实现了插入、删除、查找和修改等基本操作，并验证了其正确性和效率。

2. 在栈和队列实验中，我们对比了它们在不同场景下的应用，发现栈适用于后进先出（LIFO）的情况，而队列适用于先进先出（FIFO）的情况。

3. 在树和二叉树实验中，我们掌握了树和二叉树的构建和遍历算法，并应用它们解决了一些实际问题，如树形结构的存储和搜索。

数据结构实验报告图的存储数据结构图实验报告一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。

（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。

（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。

（4）掌握图的其他运算，包括最小生成树，最短路径，拓扑排序和关键路径等算法。

（5）灵活运用图这种数据结构解决一些综合应用问题。

二、实验内容和方法(1)实验内容：1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：①建立如图1所示的有向图G的邻接矩阵，并输出；②由有向图G的邻接矩阵产生邻接表，并输出；③再由②的邻接表产生对应的邻接矩阵，并输出。

图12、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）；②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）；③输出图1所示的有向图G从顶点0开始的广度优先遍历序列。

3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。

(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。

2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。

3、根据实验内容，编译程序。

三、实验环境：Windows 7，Visual C++6.0三、实验过程描述文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。

其代码如下：#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDEDtypedef int InfoType;#define MAXV 100 //最大顶点个数#define INF 32767 //INF表示无限大//以下定义邻接矩阵类型typedef struct{int no;InfoType info;}VertexType;typedef struct{int edges[MAXV][MAXV];int n,e;VertexType vexs[MAXV];}MGraph;//以下定义邻接表类型typedef struct ANode{int adjvex;struct ANode* nextarc;InfoType info;}ArcNode;typedef int Vertex;typedef struct VNode{Vertex data;实验①源程序。

数据结构课程实验报告一、实验目的本次数据结构课程实验的主要目的是通过实践掌握常见数据结构的基本操作，包括线性结构、树形结构和图形结构。

同时，也要求学生能够熟练运用C++语言编写程序，并且能够正确地使用各种算法和数据结构解决具体问题。

二、实验内容本次实验涉及到以下几个方面：1. 线性表：设计一个线性表类，并且实现线性表中元素的插入、删除、查找等基本操作。

2. 栈和队列：设计一个栈类和队列类，并且分别利用这两种数据结构解决具体问题。

3. 二叉树：设计一个二叉树类，并且实现二叉树的遍历（前序遍历、中序遍历和后序遍历）。

4. 图论：设计一个图类，并且利用图论算法解决具体问题（如最短路径问题）。

三、实验过程1. 线性表首先，我们需要设计一个线性表类。

在这个类中，我们需要定义一些成员变量（如线性表大小、元素类型等），并且定义一些成员函数（如插入元素函数、删除元素函数等）。

在编写代码时，我们需要注意一些细节问题，如边界条件、异常处理等。

2. 栈和队列接下来，我们需要设计一个栈类和队列类。

在这两个类中，我们需要定义一些成员变量（如栈顶指针、队头指针等），并且定义一些成员函数（如入栈函数、出栈函数、入队函数、出队函数等）。

在编写代码时，我们需要注意一些细节问题，如空间不足的情况、空栈或空队列的情况等。

3. 二叉树然后，我们需要设计一个二叉树类，并且实现二叉树的遍历。

在这个类中，我们需要定义一个节点结构体，并且定义一些成员变量（如根节点指针、节点数量等），并且定义一些成员函数（如插入节点函数、删除节点函数、遍历函数等）。

在编写代码时，我们需要注意一些细节问题，如递归调用的情况、空节点的情况等。

4. 图论最后，我们需要设计一个图类，并且利用图论算法解决具体问题。

在这个类中，我们需要定义一个邻接矩阵或邻接表来表示图形结构，并且定义一些成员变量（如顶点数量、边的数量等），并且定义一些成员函数（如添加边函数、删除边函数、最短路径算法等）。

数据结构课程实验报告数据结构课程实验报告引言：数据结构是计算机科学中非常重要的一门课程，它研究了数据的组织、存储和管理方法。

在数据结构课程中，我们学习了各种数据结构的原理和应用，并通过实验来加深对这些概念的理解。

本文将对我在数据结构课程中的实验进行总结和分析。

实验一：线性表的实现与应用在这个实验中，我们学习了线性表这种基本的数据结构，并实现了线性表的顺序存储和链式存储两种方式。

通过实验，我深刻理解了线性表的插入、删除和查找等操作的实现原理，并掌握了如何根据具体应用场景选择合适的存储方式。

实验二：栈和队列的实现与应用栈和队列是两种常见的数据结构，它们分别具有后进先出和先进先出的特点。

在这个实验中，我们通过实现栈和队列的操作，加深了对它们的理解。

同时，我们还学习了如何利用栈和队列解决实际问题，比如迷宫求解和中缀表达式转后缀表达式等。

实验三：树的实现与应用树是一种重要的非线性数据结构，它具有层次结构和递归定义的特点。

在这个实验中，我们学习了二叉树和二叉搜索树的实现和应用。

通过实验，我掌握了二叉树的遍历方法，了解了二叉搜索树的特性，并学会了如何利用二叉搜索树实现排序算法。

实验四：图的实现与应用图是一种复杂的非线性数据结构，它由节点和边组成，用于表示事物之间的关系。

在这个实验中，我们学习了图的邻接矩阵和邻接表两种存储方式，并实现了图的深度优先搜索和广度优先搜索算法。

通过实验，我深入理解了图的遍历方法和最短路径算法，并学会了如何利用图解决实际问题，比如社交网络分析和地图导航等。

实验五：排序算法的实现与比较排序算法是数据结构中非常重要的一部分，它用于将一组无序的数据按照某种规则进行排列。

在这个实验中，我们实现了常见的排序算法，比如冒泡排序、插入排序、选择排序和快速排序等，并通过实验比较了它们的性能差异。

通过实验，我深入理解了排序算法的原理和实现细节，并了解了如何根据具体情况选择合适的排序算法。

结论：通过这些实验，我对数据结构的原理和应用有了更深入的理解。

（前面可加目录页）一. 实验目的1.理解图的概念并熟悉有关术语。

2.熟练掌握邻接矩阵表示法和邻接表表示法。

3.掌握连通图遍历的基本思想和算法。

4.掌握最小生成树的有关概念和算法实现。

5.掌握最短路径有关概念和算法。

6.掌握拓扑排序的概念及实现。

二. 实验内容1.对给定的图，用邻接矩阵实现该图的深度优先搜索遍历。

2.对给定的图，用邻接矩阵实现该图的广度优先搜索遍历。

3.对给定的图，用邻接表实现该图的深度优先搜索遍历。

4.对给定的图，用邻接表实现该图的广度优先搜索遍历。

三. 文献综述数据结构（C语言版）习题解答及实训指导------------李根强、谢月娥四. 实验思路和技术路线（数据结构及算法）（1，2）算法设计：首先定义图的类型为结构型，包含图中的顶点信息和邻接矩阵两项信息，然后将输入边的信息建立邻接矩阵，再将深度搜索优先遍历和广度优先搜索遍历写成子函数的形式，在主函数中调用他们；（3，4）算法设计：首先定义图的邻接表数据类型，建立该图的邻接表，然后再用子函数写出深度优先搜索遍历和广度优先搜索遍历的算法，在主函数中调用它；五. 实验结果分析及心得（1）对给定的图，用邻接矩阵实现该图的深度优先和广度优先搜索遍历：<1 给定的图如下：< 2 广度优先和深度优先遍历程序如下：#include<stdio.h>#define n 8 //图中顶点数#define e 15 //图中边数#define elemtype intint visited[n+1]; //访问标志数组，为false表示未访问，为true表示已访问struct graph //定义图的数据类型{elemtype v[n+1]; //存放顶点信息 v1,v2,...,vn,不使用v[0]存储空间int arcs[n+1][n+1]; //邻接矩阵}g;void creatadj() //建立邻接矩阵{int i,j,k;printf("请输入%d个顶点信息\n",n);for(k=1;k<=n;k++)scanf("%d",&g.v[k]); //输入顶点信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)g.arcs[i][j]=0;for(k=1;k<=e;k++){printf("请输入第%d条边，共%d条边",k,e);scanf("%d%d",&i,&j); //输入一条边（i,j)g.arcs[i][j]=1;g.arcs[j][i]=1;}}void dfs(int i) //从顶点i出发进行深度优先搜索遍历 {int j;printf("%d",g.v[i]); //输出访问顶点visited[i]=1; //全局数组访问标记置1表示已访问for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j]))dfs(j);}void bfs(int i) //从顶点i出发进行广度优先搜索遍历{int q[n+1]; //q为队列int f,r,j; //f,r分别为队列头指针、尾指针f=r=0; //设置空队列printf("%d",g.v[i]); //输出访问顶点visited[i]=1; //全局数组标记置1表示已访问r++;q[r]=i; //入队列while(f<r){f++;i=q[f]; //出队列for(j=1;j<=n;j++)if((g.arcs[i][j]==1)&&(!visited[j])){printf("%d",g.v[j]);visited[j]=1;r++;q[r]=j; //入队列}}}main(){int i,j;int yn=1;creatadj(); //建立邻接矩阵for(i=1;i<=n;i++) //输出邻接矩阵{for(j=1;j<=n;j++)printf("%d",g.arcs[i][j]);printf("\n");}while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入深度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的深度优先搜素遍历序列为\n",i);dfs(i);printf("\n继续进行深度优先搜索吗（1/2）？");scanf("%d",&yn);}yn=1;while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入广度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的广度优先搜索遍历序列为\n",i);bfs(i);printf("\n继续进行广度优先搜索吗 (1/2) ？");scanf("%d",&yn);}}运行结果：#define e 15 //图中边数#define elemtype intint visited[n+1];istruct link{elemtype data;struct link *next;};struct graph{struct link a[n+1];}g;void creatlink(){int i,j,k;struct link *s;for(i=1;i<=n;i++){g.a[i].data=i;g.a[i].next=NULL;}for(k=1;k<=e;k++){printf("请输入一条边");scanf("%d%d",&i,&j);s=(struct link *)malloc(sizeof(struct link));s->data=j;s->next=g.a[i].next;g.a[i].next=s;s=(struct link *)malloc(sizeof(struct link));s->data=i;s->next=g.a[j].next;g.a[j].next=s;}}void dfs1(int i){struct link *p;printf("%d",g.a[i].data);visited[i]=1;p=g.a[i].next;while(p!=NULL){if(!visited[p->data])dfs1(p->data);p=p->next;}}void bfs1(int i){int q[n+1];int f,r;struct link *p;f=r=0;printf("%d",g.a[i].data);visited[i]=1;r++;q[r]=i;while(f<r){f++;i=q[f];p=g.a[i].next;while(p!=NULL){if(!visited[p->data]){printf("%d",g.a[p->data].data);visited[p->data]=1;r++;q[r]=p->data;}p=p->next;}}}main(){struct link *p;int yn=1,i;creatlink();while(yn==1){for(i=1;i<=n;i++){p=g.a[i].next;printf("%d->",g.a[i].data);while(p->next!=NULL){printf("%d->",p->data);p=p->next;}printf("%d\n",p->data);}while(yn==1){for(i=1;i<=n;i++)visited[i]=0;printf("请输入深度优先搜索开始访问的顶点");scanf("%d",&i);printf("\n");printf("从%d出发的深度优先搜索遍历序列为\n",i);dfs1(i);printf("\n继续进行深度优先搜索吗（1/2）？");scanf("%d",&yn);}yn=1;while(yn==1){for(i=1;i<=n;i++)。

数据结构实验报告(实验)数据结构实验报告(实验)1. 实验目的1.1 理解数据结构的基本概念和操作1.2 学会使用数据结构解决实际问题1.3 掌握常用数据结构的实现和应用2. 实验环境2.1 操作系统：Windows 102.2 编程语言：C++2.3 开发工具：Visual Studio3. 实验内容3.1 实验一：线性表的实现和应用3.1.1 设计并实现线性表的基本操作函数3.1.2 实现线性表的插入、删除、查找等功能 3.1.3 实现线性表的排序算法3.1.4 应用线性表解决实际问题3.2 实验二：栈和队列的实现和应用3.2.1 设计并实现栈的基本操作函数3.2.2 设计并实现队列的基本操作函数3.2.3 实现栈和队列的应用场景3.2.4 比较栈和队列的优缺点3.3 实验三：树的实现和应用3.3.1 设计并实现二叉树的基本操作函数3.3.2 实现二叉树的创建、遍历和查找等功能3.3.3 实现树的遍历算法（前序、中序、后序遍历）3.3.4 应用树解决实际问题4. 数据结构实验结果4.1 实验一的结果4.1.1 线性表的基本操作函数实现情况4.1.2 线性表的插入、删除、查找功能测试结果4.1.3 线性表的排序算法测试结果4.1.4 线性表解决实际问题的应用效果4.2 实验二的结果4.2.1 栈的基本操作函数实现情况4.2.2 队列的基本操作函数实现情况4.2.3 栈和队列的应用场景测试结果4.2.4 栈和队列优缺点的比较结果4.3 实验三的结果4.3.1 二叉树的基本操作函数实现情况4.3.2 二叉树的创建、遍历和查找功能测试结果 4.3.3 树的遍历算法测试结果4.3.4 树解决实际问题的应用效果5. 实验分析与总结5.1 实验问题与解决方案5.2 实验结果分析5.3 实验总结与心得体会6. 附件附件一：实验源代码附件二：实验数据7. 法律名词及注释7.1 版权：著作权法规定的对原创作品享有的权利7.2 专利：国家授予的在一定时间内对新型发明享有独占权利的证书7.3 商标：作为标识企业商品和服务来源的标志的名称、符号、图案等7.4 许可协议：指允许他人在一定条件下使用自己的知识产权的协议。

国开数据结构(本)数据结构课程实验报告1. 实验目的本次实验的主要目的是通过实际操作，掌握数据结构的基本概念、操作和应用。

通过对实验内容的了解和实际操作，达到对数据结构相关知识的深入理解和掌握。

2. 实验工具与环境本次实验主要使用C++语言进行编程，需要搭建相应的开发环境。

实验所需的工具和环境包括：C++编译器、集成开发环境(IDE)等。

3. 实验内容本次实验主要包括以下内容：3.1. 实现顺序存储结构的线性表3.2. 实现链式存储结构的线性表3.3. 实现栈和队列的顺序存储结构和链式存储结构3.4. 实现二叉树的顺序存储结构和链式存储结构3.5. 实现图的邻接矩阵和邻接表表示4. 实验步骤实验进行的具体步骤如下：4.1. 实现顺序存储结构的线性表- 定义数据结构- 实现插入、删除、查找等操作4.2. 实现链式存储结构的线性表- 定义数据结构- 实现插入、删除、查找等操作4.3. 实现栈和队列的顺序存储结构和链式存储结构- 定义数据结构- 实现入栈、出栈、入队、出队操作4.4. 实现二叉树的顺序存储结构和链式存储结构- 定义数据结构- 实现插入、删除、查找等操作4.5. 实现图的邻接矩阵和邻接表表示- 定义数据结构- 实现插入、删除、查找等操作5. 实验结果与分析通过对以上实验内容的实现和操作，得到了以下实验结果与分析： 5.1. 顺序存储结构的线性表- 实现了线性表的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.2. 链式存储结构的线性表- 实现了线性表的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.3. 栈和队列的顺序存储结构和链式存储结构- 实现了栈和队列的入栈、出栈、入队、出队操作- 通过实验数据进行性能分析，得出了相应的性能指标5.4. 二叉树的顺序存储结构和链式存储结构- 实现了二叉树的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标5.5. 图的邻接矩阵和邻接表表示- 实现了图的插入、删除、查找等操作- 通过实验数据进行性能分析，得出了相应的性能指标6. 总结与展望通过本次数据结构课程的实验，我们深入了解并掌握了数据结构的基本概念、操作和应用。

《数据结构》实验报告班级学号：姓名：《数据结构》实验报告学院：信息科学与技术学院专业：学期：班级：学号：姓名：易网返利网——淘宝购物返现逐新时尚-品牌服装-提供：目录实验1 函数、指针、结构体复习 (1)1.1 实验目的 (1)1.2 实验准备 (1)1.3 实验任务 (1)实验2 线性表 (4)2.1 实验目的 (4)2.2 实验准备 (4)2.3 实验任务 (4)实验3 栈和队列 (19)3.1 实验目的 (19)3.2 实验准备 (19)3.3 实验任务 (19)实验4 线性表的综合应用 (27)4.1 实验目的 (27)4.2 实验准备 (27)4.3 实验任务 (27)实验5 树和二叉树 (32)5.1 实验目的 (32)5.2 实验准备 (32)5.3 实验任务 (32)实验6 图 (42)6.1 实验目的 (42)6.2 实验准备 (42)6.3 实验任务 (42)实验7 查找 (46)7.1 实验目的 (46)7.2 实验准备 (46)7.3 实验任务 (46)实验8 排序 (55)8.1 实验目的 (55)8.2 实验准备 (55)8.3 实验任务 (55)实验9 综合实验 (58)9.1 实验目的 (60)9.2 实验预习 (60)9.3 实验任务 (60)实验1 函数、指针、结构体复习院（系）：信息科学与技术学院课程名称：数据结构教师签名：1.1 实验目的1．掌握C语言的语法并由算法形成相应的程序。

2．熟练掌握C语言函数调用的相关知识点。

3．熟练掌握C语言的指针和结构体相关知识点。

4．理解数据结构的基本概念。

1.2 实验准备1．复习C语言的函数调用、指针、结构体的相关知识点。

2．算法的概念和算法分析等知识。

3．C语言程序设计有关函数及数组等的知识及编程环境的使用方法。

4．复习课堂讲解的理论内容。

1.3 实验任务1．在提示/**********blank**********/下面填写合适的内容完成程序设计。

数据结构实验五图子系统实验五实验题目:图子系统指导老师:王春红专业班级:计算机科学与技术系1105班姓名:李慧2011100521杜丽20111005122白莹2011100523王媛20111005292013年 5月23日实验类型综合实验室_软件实验室一__一、实验题目1图子系统二、实验目的和要求,(掌握图的存储思想及其存储实现,(掌握图的深度、广度优先遍历算法思想及其程序实现,(掌握图的常见应用算法的思想及其程序实现。

三、实验内容实验内容二:所有顶点对的最短路径1(设置4个村庄之间的交通，村庄之间的距离用各边上的权值来表示。

现在要求从这4个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院最近。

2(设计分析用有向加权图表示的交通图中，有向边<vi,vj>表示第i个村庄和第j个村庄之间有道路，边上的权表示这条道路的长度。

该问题的实质是求解任意两顶点间的最短路径问题。

即求出每个顶点到其他顶点的最短路径的最大值，最大值最小的顶点作为医院所在村庄。

3(结构类型定义typedef char vextype;/*顶点数据类型*/typedef int edgetype;/*边数据类型*/typedef struct{vextype vex[maxsize];edgetype arc[maxsize][maxsize];int vexnum,arcnum;}Mgraph;小组分工:组长:王媛定义结构体和主函数组员:李慧 void juzhen(Mgraph *G)白莹、杜丽void panduan(Mgraph *G)四、实验步骤程序如下:#include <stdio.h>#include <malloc.h>#define max 100#define min 0typedef int edgetype;typedef char vextype;typedef struct2{vextype ver[4];edgetype edge[4][4];int edgenum,vernum; }Mgraph;void juzhen(Mgraph *G) {int i,j;printf("四个村庄的邻接矩阵为:\n"); for(i=0;i<4;i++)for(j=0;j<4;j++)scanf("%d",&G->edge[i][j]);}void panduan(Mgraph *G) {int a[4],b[4],c[4];int i,j,t,t2,p,q,n,k;for(i=0;i<4;i++){a[0]=0;a[1]=0;a[2]=0;a[3]=0;a[i]=1;for(j=0;j<4;j++){b[j]=G->edge[i][j];}t=max;for(k=0;k<4;k++){if(b[k]<t&&a[k]==0){t=b[k];p=k;}}a[p]=1;printf("%d到%d的最短路径为:%d\n",i,p,t); q=2;while(q>0){for(k=0;k<4;k++){if(a[k]==0)if(b[k]>(b[p]+G->edge[p][k]))b[k]=b[p]+G->edge[p][k];3}t=max;for(k=0;k<4;k++){if(b[k]<t&&a[k]==0){t=b[k];p=k;}}a[p]=1;--; qprintf("%d到%d的最短路径为:%d\n",i,p,b[p]); }t2=min;for(k=0;k<4;k++){if(t2<b[k]&&(k!=i)){t2=b[k];}c[i]=t2;}}//i的循环结束t=max;for(k=0;k<4;k++){if(t>c[k]){t=c[k];n=k;}}switch(n){case 0:printf("医院设在0村庄!");printf("0到最远村庄的最近距离为:%d\n",t); break;case 1:printf("医院设在1村庄!");printf("1到最远村庄的最近距离为:%d\n",t); break;case 2:4printf("医院设在2村庄!");printf("2到最远村庄的最近距离为:%d\n",t); break;case 3:printf("医院设在3村庄!");printf("3到最远村庄的最近距离为:%d\n",t);break;}}main(){Mgraph *G;G=(Mgraph*)malloc(sizeof(Mgraph));juzhen(G);panduan(G);}实验结果如下:五、实验总结这次实验和之前的实验相比有一定的难度，需要对实验的思路特别清晰，在其中设定的变量有些多，要特别注意，其中遇到了很多的问题，通过请教同学老师最终得出了结果～5。

数据结构实验报告实验5一、实验目的本次实验的主要目的是深入理解和掌握常见的数据结构，通过实际编程实现和操作，提高对数据结构的应用能力和编程技巧。

二、实验环境本次实验使用的编程语言为C+＋，开发工具为Visual Studio 2019。

三、实验内容1、线性表的基本操作实现线性表的创建、插入、删除、查找等基本操作。

对不同操作的时间复杂度进行分析和比较。

2、栈和队列的应用利用栈实现表达式求值。

使用队列模拟银行排队系统。

3、二叉树的遍历实现二叉树的先序、中序、后序遍历算法。

分析不同遍历算法的特点和应用场景。

4、图的表示和遍历采用邻接矩阵和邻接表两种方式表示图。

实现图的深度优先遍历和广度优先遍历算法。

四、实验步骤及结果1、线性表的基本操作首先，定义了一个线性表的结构体，包含数据域和指针域。

创建线性表时，动态分配内存空间，并初始化表头和表尾指针。

插入操作分为表头插入、表尾插入和指定位置插入。

在指定位置插入时，需要先找到插入点的前一个节点，然后进行插入操作。

删除操作同样需要找到要删除节点的前一个节点，然后释放删除节点的内存空间，并调整指针。

查找操作通过遍历线性表，逐个比较数据值来实现。

经过测试，不同操作的时间复杂度如下：创建操作的时间复杂度为 O(1)。

插入操作在表头和表尾插入的时间复杂度为 O(1)，在指定位置插入的时间复杂度为 O(n)。

删除操作的时间复杂度为 O(n)。

查找操作的平均时间复杂度为 O(n)。

2、栈和队列的应用表达式求值：将表达式转换为后缀表达式，然后利用栈进行计算。

遇到操作数则入栈，遇到操作符则从栈中弹出两个操作数进行计算，并将结果入栈。

最后栈顶元素即为表达式的结果。

银行排队系统：使用队列模拟客户的排队过程。

客户到达时入队，服务窗口空闲时从队列头部取出客户进行服务。

实验结果表明，栈和队列能够有效地解决相关问题，提高程序的效率和可读性。

3、二叉树的遍历先序遍历：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。

数据结构形成性考核册实验名称：实验一线性表线性表的链式存储结构【问题描述】某项比赛中，评委们给某参赛者的评分信息存储在一个带头结点的单向链表中，编写程序：（1）显示在评分中给出最高分和最低分的评委的有关信息（姓名、年龄、所给分数等）。

（2）在链表中删除一个最高分和一个最低分的结点。

（3）计算该参赛者去掉一个最高分和一个最低分后的平均成绩。

【基本要求】（1）建立一个评委打分的单向链表；（2）显示删除相关结点后的链表信息。

（3）显示要求的结果。

【实验步骤】（1）运行PC中的Microsoft Visual C++ 6.0程序，（2）点击“文件”→“新建”→对话窗口中“文件”→“c++ Source File”→在“文件名”中输入“X1.cpp”→在“位置”中选择储存路径为“桌面”→“确定”，（3）输入程序代码，程序代码如下:#include <stdio.h>#include <stdlib.h>#include <malloc.h>#include <iostream.h>#include <conio.h>#define NULL 0#define PWRS 5 //定义评委人数struct pw //定义评委信息{ char name[6];float score;int age;};typedef struct pw PW;struct node //定义链表结点{struct pw data;struct node * next;};typedef struct node NODE;NODE *create(int m); //创建单链表int calc(NODE *h); //计算、数据处理void print(NODE *h); //输出所有评委打分数据void input(NODE *s);//输入评委打分数据void output(NODE *s);//输出评委打分数据void main(){NODE *head;float ave=0;float sum=0;head=create(PWRS);printf("所有评委打分信息如下:\n");print(head);//显示当前评委打分calc(head);//计算成绩printf("该选手去掉1 最高分和1 最低分后的有效评委成绩:\n");print(head);//显示去掉极限分后的评委打分}void input(NODE *s){printf("请输入评委的姓名: ");scanf("%S",&s->);printf("年龄: ");scanf("%d",&s->data.age);printf("打分: ");scanf("%f",&s->data.score);printf("\n");}void output(NODE *s){printf("评委姓名: %8s ,年龄: %d,打分: %2.2f\n",s->,s->data.age,s->data.score); }NODE *create(int m){NODE *head,*p,*q;int i;p=(NODE*)malloc(sizeof(NODE));head=p;q=p;p->next=NULL;for(i=1;i<=m;i++){p=(NODE*)malloc(sizeof(NODE));input(p);p->next=NULL;q->next=p;q=p;}return (head);}void print(NODE *h){ for(int i=1;((i<=PWRS)&&(h->next!=NULL));i++){h=h->next;output(h); }printf("\n");}int calc(NODE *h){NODE *q,*p,*pmin,*pmax;float sum=0;float ave=0;p=h->next; //指向首元结点pmin=pmax=p; //设置初始值sum+=p->data.score;p=p->next;for(;p!=NULL;p=p->next){if(p->data.score>pmax->data.score) pmax=p;if(p->data.score<pmin->data.score) pmin=p;sum+=p->data.score;}cout<<"给出最高分的评委姓名："<<pmax-><<"年龄："<<pmax->data.age<<"分值："<<pmax->data.score<<endl;cout<<"给出最低分的评委姓名："<<pmin-><<"年龄："<<pmin->data.age<<"分值："<<pmin->data.score<<endl;printf("\n");sum-=pmin->data.score;sum-=pmax->data.score;for (q=h,p=h->next;p!=NULL;q=p,p=p->next){if(p==pmin){q->next=p->next; p=q;}//删除最低分结点if(p==pmax) {q->next=p->next; p=q;}//删除最高分结点}ave=sum/(PWRS-2);cout<<"该选手的最后得分是："<<ave<<endl;return 1;}程序运行结果如下:线性表的顺序存储结构【问题描述】用顺序表A记录学生的信息，编写程序：（1）将A表分解成两个顺序表B和C，使C表中含原A表中性别为男性的学生，B表中含原表中性别为女性的学生，要求学生的次序与原A表中相同。