数据结构
实
验
报
告
目的要求
1.掌握图的存储思想及其存储实现。
2.掌握图的深度、广度优先遍历算法思想及其程序实现。
3.掌握图的常见应用算法的思想及其程序实现。
实验容
1.键盘输入数据,建立一个有向图的邻接表。
2.输出该邻接表。
3.在有向图的邻接表的基础上计算各顶点的度,并输出。
4.以有向图的邻接表为基础实现输出它的拓扑排序序列。
5.采用邻接表存储实现无向图的深度优先递归遍历。
6.采用邻接表存储实现无向图的广度优先遍历。
7.在主函数中设计一个简单的菜单,分别调试上述算法。源程序:
主程序的头文件:队列
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemT ype;
typedef struct QNode{ //队的操作
QElemT ype data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q){ //初始化队列
Q.front =Q.rear =(QueuePtr)malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW); //存储分配失败
Q.front ->next =NULL;
}
int EnQueue(LinkQueue &Q,QElemT ype e) //插入元素e为Q的新的队尾元素
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p) exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear =p;
return OK;
}
int DeQueue(LinkQueue &Q,QElemT ype &e) //删除Q的队头元素,用e返回其值
{ if(Q.front ==Q.rear ) return ERROR;
QueuePtr p;
p=Q.front ->next;
e=p->data;
Q.front->next=p->next ;
if(Q.rear==p) Q.rear =Q.front ;
free(p);
return OK;
}
主程序:
#include
#include
#include"duilie.h"
#define TRUE 1
#define FALSE 0
#define Status int
#define MAX_VERTEX_NUM 8 /*顶点最大个数*/
#define VertexType char /*顶点元素类型*/
enum BOOlean {False,True};
BOOlean visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组typedef struct ArcNode
{int adjvex;
struct ArcNode *nextarc;
int weight; /*边的权*/
}ArcNode; /*表结点*/
typedef struct VNode
{ int degree,indegree;/*顶点的度,入度*/
VertexType data;
ArcNode *firstarc;
}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM];
typedef struct
{ AdjList vertices;
int vexnum,arcnum;/*顶点的实际数,边的实际数*/
}ALGraph;
//建立图的邻接表
void creat_link(ALGraph *G)
{ int i,j;
ArcNode *s;
printf("请依次输入顶点数、边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i=0;i
{ G->vertices[i].data='A'+i;
G->vertices[i].firstarc=NULL;
}
for (i=0;i
{ printf("请输入顶点的数组坐标(若退出,请输入-1):");
scanf("%d",&i);
if(i==-1) break;
printf("请输入顶点所指向下一个顶点的数组坐标:");
scanf("%d",&j);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=j;
s->nextarc=G->vertices[i].firstarc;
G->vertices[i].firstarc=s;
}
}
// 输出邻接表
void visit(ALGraph G)
{ int i;
ArcNode *p;
printf("%4s%6s%18s\n","NO","data","adjvexs of arcs");
for (i=0;i { printf("%4d%5c ",i,G.vertices[i].data); for(p=G.vertices[i].firstarc;p;p=p->nextarc) printf("%3d",p->adjvex); printf("\n"); } } // 计算各顶点的度及入度 void cacu(ALGraph *G) { ArcNode *p; int i; for (i=0;i {G->vertices[i].degree=0;G->vertices[i].indegree=0;}//度与初度初始化为零for (i=0;i for(p=G->vertices[i].firstarc;p;p=p->nextarc) {G->vertices[i].degree++; G->vertices[p->adjvex].degree++; G->vertices[p->adjvex].indegree++; } } void print_degree(ALGraph G) { int i; printf("\n Nom data degree indegree\n"); for (i=0;i printf("\n%4d%5c%7d%8d",i,G.vertices[i].data, G.vertices[i].degree,G.vertices[i].indegree); printf("\n"); } // 拓扑排序 Status T opologiSort(ALGraph G) {int i,count,top=0,stack[50]; ArcNode *p; cacu(&G); print_degree(G); printf("\nT opologiSort is \n"); for(i=0;i if(!G.vertices[i].indegree) stack[top++]=i; count=0; while(top!=0) { i=stack[--top]; if (count==0) printf("%c",G.vertices[i].data); else printf("-->%c",G.vertices[i].data); count++; for(p=G.vertices[i].firstarc;p;p=p->nextarc) if (!--G.vertices[p->adjvex].indegree)stack[top++]=p->adjvex; } if (count } //在图G中寻找第v个顶点的第一个邻接顶点 int FirstAdjVex(ALGraph G,int v) { if(!G.vertices[v].firstarc) return 0; else return(G.vertices[v].firstarc->adjvex); } //在图G中寻找第v个顶点的相对于u的下一个邻接顶点 int NextAdjVex(ALGraph G,int v,int u) { ArcNode *p; p=G.vertices[v].firstarc; while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u if(p->nextarc==NULL) return 0; //若已是最后一个顶点,返回0 else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号} //采用邻接表存储实现无向图的深度优先递归遍历 void DFS(ALGraph G,int i) { int w; visited[i]=True; //访问第i个顶点 printf("%d->",i); for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w)) if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS } void DFSTraverse(ALGraph G) { int i; printf("DFSTraverse:"); for(i=0;i if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS } //按广度优先非递归的遍历图G,使用辅助队列Q和访问标志数组visited void BFSTraverse(ALGraph G) { int i,u,w; LinkQueue Q; printf("BFSTreverse:"); for(i=0;i InitQueue(Q); //初始化队列 for(i=0;i if(!visited[i]) {visited[i]=True; //访问顶点i printf("%d->",i); EnQueue(Q,i); //将序号i入队列 while(!(Q.front ==Q.rear)) //若队列不空,继续 {DeQueue(Q,u); //将队头元素出队列并置为u for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w)) if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列 { visited[w]=True; printf("%d->",w); EnQueue(Q,w); } } } } void main() { ALGraph G; int select; printf(" 图的有关操作实验\n "); do{ printf("\n1 创建一个有向图的邻接表 2 输出该邻接表\n"); printf("3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列\n"); printf("5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\n"); printf("7.广度优先遍历该无向图0.退出\n"); printf("请输入选择:"); scanf("%d",&select); switch(select){ case 1: printf("\n创建一个有向图的邻接表:\n"); creat_link(&G); break; case 2: printf("\n输出该邻接表:\n"); visit(G); break; case 3: printf("\n输出该有向图的度和入度:\n"); cacu(&G); print_degree(G); break; case 4: printf("\n输出该有向图拓扑排序序列:\n"); if(!T opologiSort(G))printf("T oposort is not success!"); break; case 5: printf("\n创建一个无向图的邻接表: \n"); creat_link(&G); break; case 6: printf("\n深度优先递归遍历该无向图: \n"); DFSTraverse(G); break; case 7: printf("\n广度优先遍历该无向图:\n"); BFSTraverse(G); break; case 0: break; default: printf("输入选项错误!重新输入!\n"); } }while(select); } 运行结果截图: 1.主菜单界面: 2.创建一个有向图的领接表 一,实验题目 实验十一:图实验 采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径。 二,问题分析 本程序要求采用邻接表存储有向图,设计算法判断任意两个顶点间手否存在路径,完成这些操作需要解决的关键问题是:用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1,数据的输入形式和输入值的范围:输入的图的结点均为整型。 2,结果的输出形式:输出的是两结点间是否存在路径的情况。 3,测试数据:输入的图的结点个数为:4 输入的图的边得个数为:3 边的信息为:1 2,2 3,3 1 三,概要设计 (1)为了实现上述程序的功能,需要: A,用邻接表的方式构建图 B,深度优先遍历该图的结点 C,判断任意两结点间是否存在路径 (2)本程序包含6个函数: a,主函数main() b,用邻接表建立图函数create_adjlistgraph() c,深度优先搜索遍历函数dfs() d,初始化遍历数组并判断有无通路函数dfs_trave() e,输出邻接表函数print() f,释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示: 四,详细设计 (1)邻接表中的结点类型定义: typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; (2)邻接表中头结点的类型定义: typedef struct{ char vexdata; arcnode *firstarc; }adjlist; (3)邻接表类型定义: typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; (4)深度优先搜索遍历函数伪代码: int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } (5)初始化遍历数组并判断有无通路函数伪代码: void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五,源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 软件工程实验报告 课题:人事管理系统学生姓名: 学号: 专业班级: 指导教师: 同组成员: 需求分析 一、实验目的 掌握软件需求的结构化分析方法。 二、实验任务与实验要求 导出系统详细的逻辑模型,这里用数据流图来表示。 三、实验内容 (1)功能分析 经过初步分析“人事管理系统”应该具备以下主要功能。 1、职员个人信息资料的增加、修改和删除; 2、职员的考勤录入和查询; 3、职员工资结算和查询; 4、人事管理人员的变化和操作授权; 由于是使用计算机管理,就带来了新的功能:用户登陆、操作人员的管理、基本数据的维护、由数据安全产生的数据备份与恢复。 (2)、关系模式 在满足函数依赖和无损连接的基础上,使数据的设计更加合理。在本系统中只有3个实体,那就是普通员工、管理员、超级管理员,他们权限的不听通过角色来区分。在整个系统中超级管理员只有一人,管理员二人。一个人只可以在普通员工、管理员、超级管理员中处于一个角色,而不可以兼任。其具体的关系模式如下: 普通员工(员工号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 管理员(管理员号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 超级管理员(超级管理员号,密码,姓名,性别,出生年月,身份证号,联系电话,就职时间) 工资(员工号,时间,基本工资,提成,奖金) 考勤(员工号,时间,迟到,早退,管理员号) 注意:“”表示主码,“”表示既是主码又是外码。 E-R图如下所示 数据字典设计: 为了方便数据库的管理和维护,本系统只设计一个数据库workers.mdb,其中包含worker(员工信息表)、manager(考勤信息表)、booklist(工资信息表) 表1-1 worker(员工信息表)各字段设计 表1-2 monit (考勤信息表)各字段设计 数据结构实验报告全集 实验一线性表基本操作和简单程序 1 .实验目的 (1 )掌握使用Visual C++ 6.0 上机调试程序的基本方法; (2 )掌握线性表的基本操作:初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2 .实验要求 (1 )认真阅读和掌握和本实验相关的教材内容。 (2 )认真阅读和掌握本章相关内容的程序。 (3 )上机运行程序。 (4 )保存和打印出程序的运行结果,并结合程序进行分析。 (5 )按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果 实验代码: 1)头文件模块 #include iostream.h>// 头文件 #include nodetype *create()// 建立单链表,由用户输入各结点data 域之值, // 以0 表示输入结束 { elemtype d;// 定义数据元素d nodetype *h=NULL,*s,*t;// 定义结点指针 int i=1; cout<<" 建立一个单链表"< 图实验一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template #include 实验报告格式范文 实验一撰写可行性研究报告 一、实验目的 1、掌握可行性研究步骤; 2、学习编制可行性研究报告。 二、实验要求 硬件:Intel Pentium 120 或以上级别的CPU,大于16MB的内存。 软件:Win dows 95/98/2000 操作系统,Office 97/2000 软件 学时:2学时 写岀此项实验报告 三、实验内容 1、可行性研究(结构化分析)方法; 2、绘制数据流图,使用Word写实验报告。 四、实验步骤 1 ?引言 1.1 编写目的 可行性研究的目的是为了对问题进行研究,以最小的代价在最短的时间内确定问题是否可解。 经过对此项目进行详细调查研究,初拟系统实现报告,对软件开发中将要面临的问题及其解决方案进行初步设计及合理安排。明确开发风险及其所带来的经济效益。本报告经审核后,交软件经理审查。 1 . 2 项目背景 (1 )待开发的软件产品名称:旅行社机票预定系统。 (2)本项目的提岀者:冯剑。开发者:李翀。用户:旅行社 (3)本软件产品将用于旅行社的机票预定和费用的记录。 1 . 3术语说明 DFD (数据流图):一种描述书记变换的图形工具,是结构化分析方法最普遍采用的表示手段,但数据流图并不是结构化分析模型的全部,数据字典和小说明为数据流图提供了补充,并用以验证图形表示的正确性、一致性和完整性,三者共同构成了被建系统的模型。 1 . 4.系统参考文献 参考文献见附录 2?可行性研究的前提 2.1基本要求 ⑴功能 本软件实现的功能有:为游客提供机票预定服务,提高旅游局的服务质量和服务效率。 对航班数据库的查询和修改,对机票费用记帐数据库的查询和修改,记录旅客信息(姓名、性别、年龄、身份证号、单位、旅行时间、目的地)、航班时间和班次,打印机票和帐单。 (2) 性能 时间:提供的信息必须及时的反映在工作平台上。售票系统的定单必须无差错的存 储在机场的主服务器上。对服务器上的数据必须进行及时正确的刷新。一笔业务在一分钟内完成。空间:运行空间 2M。 (3) 系统的输入和输岀 输入:旅行社定票单。数据完整,详实。 输岀:机票、帐单。简捷,快速,实时。 (4) 处理流程 旅行社将定票信息输入定票系统,系统输岀机票和帐单给旅客。 5 )安全保密要求 华北电力大学 实验报告| | 实验名称数据结构实验 课程名称数据结构 | | 专业班级:学生姓名: 学号:成绩: 指导教师:实验日期:2015/7/3 实验报告说明: 本次实验报告共包含六个实验,分别为:简易停车场管理、约瑟夫环(基于链表和数组)、二叉树的建立和三种遍历、图的建立和两种遍历、hash-telbook和公司招工系统。 编译环境:visual studio 2010 使用语言:C++ 所有程序经调试均能正常运行 实验目录 实验一约瑟夫环(基于链表和数组) 实验二简易停车场管理 实验三二叉树的建立和三种遍历 实验四图的建立和两种遍历 实验五哈希表的设计 实验一:约瑟夫环 一、实验目的 1.熟悉循环链表的定义和有关操作。 二、实验要求 1.认真阅读和掌握实验内容。 2.用循环链表解决约瑟夫问题。 3.输入和运行编出的相关操作的程序。 4.保存程序运行结果 , 并结合输入数据进行分析。 三、所用仪器设备 1.PC机。 2.Microsoft Visual C++运行环境。 四、实验原理 1.约瑟夫问题解决方案: 用两个指针分别指向链表开头和下一个,两指针依次挪动,符合题意就输出结点数据,在调整指针,删掉该结点。 五、代码 1、基于链表 #include 邻接矩阵的实现 1. 实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历3.设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 数据流图实验报告 篇一:软件工程实验报告 篇二:需求分析实验报告 软件工程实践报告 计科12—1班 杨光敏 08123234 (一)软件需求分析 1.实验目的 学习图形工具软件VISIO,掌握结构化需求分析方法,熟练绘制数据流图;学习快速原型工具的使用。 2.基本要求 (1)针对银行ATM系统进行需求分析工作,了解银行ATM系统的功能、流程;(2)安装VISIOXX以上版本软件,熟练应用Visio绘制DFD图,绘制银行ATM系统数据流图,完成系统的软件逻辑模型; (3)安装Axure RP Pro 或者Balsamiq Mockups快速原型软件,学习绘制软件原型,完成银行ATM系统的软件原型。 3.系统概述 (1)ATM系统为银行提供一套高效稳定可靠的终端服务平台,为储户登录, 存款,取款,查询,打印凭条,转账,修改密码等操作提供便利。 图1 ATM工作流程 (2).用户特点 本软件的用户主要是银行的广大持卡人,大多都具有使用ATM经验。另外,我们的系统要实现的一个重要目标就是当储户取钱出现故障时能在下笔业务进行之前自动恢复。以此来方便用户和保障用户的利益。本系统还为用户提供了足够的界面友好性和易操作性。即使是一个对ATM系统完全陌生的客户,也可以在交易界面的提示下顺利完成交易。 另外一部分的用户是银行工作人员,本系统不予考虑。 4需求说明 (1) 基本描述 ATM终端可以接受一张可识别的银行储蓄卡,通过储户身份验证后,同储户进行各种交互,例如:查询、存款、取款、打印凭条等;处理储户相应的要求,执行对应操作,为储户服务。该系统要求须保持一定时间内的交易记录,系统应每天自动汇总各种交易数据与服务器进行对账。同时,在通讯失败或其他交易结果不确定的情况下,ATM要自动发起冲正交易,以保证账务的完整性。 本系统的实现需要记录一些相关信息,其中包括的信息有:用户信息和交易信息。 实验项目名称:图的遍历 一、实验目的 应用所学的知识分析问题、解决问题,学会用建立图并对其进行遍历,提高实际编程能力及程序调试能力。 二、实验容 问题描述:建立有向图,并用深度优先搜索和广度优先搜素。输入图中节点的个数和边的个数,能够打印出用邻接表或邻接矩阵表示的图的储存结构。 三、实验仪器与设备 计算机,Code::Blocks。 四、实验原理 用邻接表存储一个图,递归方法深度搜索和用队列进行广度搜索,并输出遍历的结果。 五、实验程序及结果 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include typedef struct ArCell{ int adj; }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char name[20]; }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,char* v) { int c = -1,i; for(i=0;i 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列,要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 实验报告课程名称_软件工程导论__________ 学院____计算机工程学院_________班级14软件1班 学号2014144141 姓名秦川 2016年11月8日 批阅教师时间实验成绩 课程名称软件工程 学号2014144141姓名秦川实验日期2016.11.8实验名称实验2分析数据流和绘制数据流图 实验目的: 1、掌握数据流的分析方法 2、掌握数据流图的绘制 实验内容: 任务一绘制数据流图 任务二分析数据流和绘制数据流图 案例一:总务办公管理系统 案例二:火车票预订系统 实验原理: 数据流图(DFD)是软件系统系统的逻辑模型,仅仅描绘数据在软件中流动(从输入移动到输出)的过程中所经受的变换(即加工处理)。 数据流图的绘制方法:根据数据流图的四种成分:源点或终点,处理,数据存储和数据流,从问题描述中提取数据流图的四种成分;然后依据“自顶向下、从左到右、由粗到细、逐步求精”的基本原则进行绘制。 基本符号如下: 实验过程与结果: 1.运行Microsoft Office Visio2007 运行Microsoft Office Visio2007 2.选择“软件和数据库”中的“数据流模型图”模板 选中数据流模型图模板 3.用鼠标选拉图标进行绘图 任务一绘制数据流图 试绘制工资管理系统的数据流图,根据数据流图的符号说明仔细理解下图含义: 这是学校教职工工资管理系统,教师根据课时表,职工根据任务表来确定个人工资情况,数据按以下方向传递: 首先,对课时表或任务表进行审核,审核后的数据经排序形成专用表格; 再进行一系列额外计算,包括个人所得说、住房公积金、保险费得出具体所发工资,并将工资表发给银行; 然后,向教职工展示工资所得明细; 最后,形成编制报表,更新分类表后,交于会计。 其中,人事科负责人事数据,教师与职工的工资由银行发放,会计做好报表的统计。 附录A 实验报告 课程:数据结构(c语言)实验名称:图的建立、基本操作以及遍历系别:数字媒体技术实验日期: 12月13号 12月20号 专业班级:媒体161 组别:无 姓名:学号: 实验报告内容 验证性实验 一、预习准备: 实验目的: 1、熟练掌握图的结构特性,熟悉图的各种存储结构的特点及适用范围; 2、熟练掌握几种常见图的遍历方法及遍历算法; 实验环境:Widows操作系统、VC6.0 实验原理: 1.定义: 基本定义和术语 图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E),其中:V(G)是顶点(V ertex)的非空有限集E(G)是边(Edge)的有限集合,边是顶点的无序对(即:无方向的,(v0,v2))或有序对(即:有方向的, 无向图中顶点V i的度TD(V i)是邻接矩阵A中第i行元素之和有向图中, 顶点V i的出度是A中第i行元素之和 顶点V i的入度是A中第i列元素之和 邻接表 实现:为图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧) 特点: 无向图中顶点Vi的度为第i个单链表中的结点数有向图中 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 逆邻接表:有向图中对每个结点建立以Vi为头的弧的单链表。 图的遍历 从图中某个顶点出发访遍图中其余顶点,并且使图中的每个顶点仅被访问一次过程.。遍历图的过程实质上是通过边或弧对每个顶点查找其邻接点的过程,其耗费的时间取决于所采用的存储结构。图的遍历有两条路径:深度优先搜索和广度优先搜索。当用邻接矩阵作图的存储结构时,查找每个顶点的邻接点所需要时间为O(n2),n为图中顶点数;而当以邻接表作图的存储结构时,找邻接点所需时间为O(e),e 为无向图中边的数或有向图中弧的数。 实验内容和要求: 选用任一种图的存储结构,建立如下图所示的带权有向图: 要求:1、建立边的条数为零的图; 软 件 工 程 实 验 报 告 班级:计算机科学与技术1102班 学号:1108030209 姓名:蒙雨茹 实验一:使用Microsoft Visio 1.1实验目的: (1)熟悉Visio的工作环境及组成。 (2)掌握Visio软件绘制图表的基本操作。 (3)掌握基本流程图的设计方法。 1.2实验内容: 绘制基本流程图 1.3实验步骤: (1)打开一个模板,,在主菜单中依次选择【文件】->【新建】->【选 择绘图类型】,出现“选择绘图类型”窗口,在【类别】下,单击 【流程图】,在【模板】下,单击【基本流程图】。 (2)添加形状,将【形状】窗口中模具上的自己需要的形状拖到绘图页 面中合适的位置。并添加文本、连接不同形状,使流程图完整的显 现出来。 1.4实验结果: 实验二:数据流图 2.1 实验目的 (1)熟悉Visio的工作环境及组成。 ⑵掌握Visio软件绘制图表的基本操作。 ⑶掌握数据流图的设计方法。 2.2 实验内容 习题3-3,3-4,3-5 2.3 实验步骤 (1)打开模板 ①在主菜单中,依次选择【文件】——【新建】——【选择绘图类型】,出现“选择绘图类型”窗口。 ②在左侧【类别】下,单击【软件】。 ③在右侧【模板】下,单击【数据流模型图】。 (2)绘制顶层图 ①在顶层进程页面中添加、移动图形元素并调整其大小。将所需要元素用鼠标拖动到模板里,添加所需的元素符号。 接口:输入源点或输出终点,其中注明源点或终点的名称。 进程:即处理,输入数据在此进行变换产生输出数据,其中注明进程的名称。数据存储:用于代表系统中存储的信息,其中注明信息的名称。 数据流:被加工的数据及其流向。流线上注明数据名称,箭头代表数据流动方向。 ②向图形元素中添加文本,并修改数据流图中的文字和格式。 连接图形元素。 ③使用“数据流”连接线将“接口”、“进程”和“数据存储”等形状互相连接起来。 逻辑连接:将数据流起点、终点拖拽到进程或接口中央位置,进程或接口被红色框包围时松开鼠标,这时可看到数据流符号相应端点为红色方框。拖动进程或接口,可看到流据流的端点随着进程或接口的移动而移动。 《数据结构》实验报告 ◎实验题目: 无向图的建立与遍历 ◎实验目的:掌握无向图的邻接链表存储,熟悉无向图的广度与深度优先遍历。 ◎实验内容:对一个无向图以邻接链表存储,分别以深度、广度优先非递归遍历输出。 一、需求分析 1.本演示程序中,输入的形式为无向图的邻接链表形式,首先输入该无向图的顶点数和边数,接着输入顶点信息,再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。 3.本程序可以实现无向图的邻接链表存储,并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括:(1)建立一个无向图的邻接链表存储(2)以深度优先遍历输出(3)以广度优先遍历输出(4)结束 5.测试数据: 顶点数和边数:6,5 顶点信息:a b c d e f 边的顶点对应序号: 0,1 0,2 0,3 2,4 3,4 深度优先遍历输出: a d e c b f 广度优先遍历输出: a d c b e f 二概要设计 为了实现上述操作,应以邻接链表为存储结构。 1.基本操作: void createalgraph(algraph &g) 创建无向图的邻接链表存储 void dfstraverseal(algraph &g,int v) 以深度优先遍历输出 void bfstraverseal(algraph &g,int v) 以广度优先遍历输出 2.本程序包含四个模块: (1)主程序模块 (2)无向图的邻接链表存储模块 (3)深度优先遍历输出模块 (4)广度优先遍历输出模块 3.模块调用图: 三详细设计 1.元素类型,结点类型和指针类型:typedef struct node { int adjvex; struct node *next; }edgenode; typedef struct vnode { char vertex; edgenode *firstedge; }vertxnode; typedef vertxnode Adjlist[maxvernum]; typedef struct { Adjlist adjlist; int n,e; }algraph; edgenode *s; edgenode *stack[maxvernum],*p; 2.每个模块的分析: (1)主程序模块 int main() 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的: 1.了解熟知图的定义和图的基本术语,掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点,并通过实例解析掌握邻接矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用,并掌握图的遍历方法及其基本思想。 二、实验内容: 1.建立无向图的邻接矩阵 2.图的xx优先搜索 3.图的xx优先搜索 三、实验步骤及结果: 1.建立无向图的邻接矩阵: 1)源代码: #include "stdio.h" #include "stdlib.h" #define MAXSIZE 30 typedefstruct{charvertex[MAXSIZE];//顶点为字符型且顶点表的长度小于MAXSIZE intedges[MAXSIZE][MAXSIZE];//边为整形且edges为邻近矩阵 }MGraph;//MGraph为采用邻近矩阵存储的图类型 voidCreatMGraph(MGraph *g,inte,int n) {//建立无向图的邻近矩阵g->egdes,n为顶点个数,e为边数inti,j,k; printf("Input data of vertexs(0~n-1): \n"); for(i=0;i 软件工程实验报告 学生成绩管理系统的设计与实现 学生姓名 学号 班级 成绩 指导教师 年月日 目录 1 课题描述 (3) 2 可行性研究 (4) 2.1 编写目的 (4) 2.2 项目背景 (4) 2.3 定义(术语) (4) 2.4 数据流程和处理流程 (4) 2.5 可行性分析的前提 (5) 2.6 可行性分析 (5) 3 需求分析 (7) 3.1 学生成绩管理系统功能需求 (7) 3.2 学生成绩管理系统性能要求 (8) 3.3 数据流图 (8) 3.4 数据字典 (9) 3.5 学生信息管理系统逻辑结构图 (12) 3.6 用户信息实体关系图 (12) 4 概要设计 (13) 4.1 编写目的 (13) 4.2 项目背景 (13) 4.3 任务概述 (13) 4.4 总体设计 (13) 4.5接口设计 (17) 4.6数据结构设计 (17) 5 详细设计 (19) 5.1 系统程序流程图 (19) 5.2 界面设计 (21) 5.3 程序界面截图 (22) 5.4 程序源代码 (27) 6 软件测试 (58) 7 总结 (62) 1 课题描述 随着互联网的发展,利用INTERNET 技术来实现“无纸办公”这个概念已经深入人心,校园网作为学校信息化建设的一个平台在完成资源共享、互联网访问、教务管理、电子备课等方面发挥了重要作用。服务教学、提高教学水平和效果是校园网建设的核心目标和核心价值,本系统立足于校园实际,着眼于未来发展,建成符合标准化协议、通用性较强、实用的系统,以提高高校的现代化管理水平,实现信息资源的共享。该项目主要是服务于教学方面,进一步方便教师的工作和学生的学习,从而从侧面达到提高学校的教学方面‘软件’质量。可以说它适用于每一所高校,因此很有开发价值。我们不敢说该产品是所有该系列产品中最好的,但是我们这里要强调的是它具有使用范围广,实用性强,使用简单,所花经费少等优点。我们可以肯定的说它将在高校的使用过程中其优点将得到最充分的体现。 主要功能有三方面: 管理员,登陆,进入系统,可以进行管理员操作,进行学生信息、教师信息、课程信息的编辑、查询、删除、修改、添加、打印等操作。 学生,登陆,进入系统,可以进行查询、修改、打印等操作。 教师,登陆,进入系统,可以进行查询、学生成绩录入、修改、打印等操作。 软件系统目标: (1)本系统具有很强的可靠行,可以对录入的学生信息进行效验,对数据进行修改、删除,规定各种权限。 (2)本系统中的模块具有很强的可续性,可以方便管理人员的修改与维护。 (3)本系统操作方便、灵活、简单。 (4)本系统可高效、快速的查询到学生的基本信息。 图实验 一,邻接矩阵的实现 1.实验目的 (1)掌握图的逻辑结构 (2)掌握图的邻接矩阵的存储结构 (3)验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 (1)建立无向图的邻接矩阵存储 (2)进行深度优先遍历 (3)进行广度优先遍历 3.设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 精品文档数据结构 实 验 报 告 目的要求 1.掌握图的存储思想及其存储实现。 2.掌握图的深度、广度优先遍历算法思想及其程序实现。 3.掌握图的常见应用算法的思想及其程序实现。 实验内容 1.键盘输入数据,建立一个有向图的邻接表。 2.输出该邻接表。 3.在有向图的邻接表的基础上计算各顶点的度,并输出。 4.以有向图的邻接表为基础实现输出它的拓扑排序序列。 5.采用邻接表存储实现无向图的深度优先递归遍历。 6.采用邻接表存储实现无向图的广度优先遍历。 7.在主函数中设计一个简单的菜单,分别调试上述算法。 源程序: 主程序的头文件:队列 #include 实验一软件结构化分析 实验目的: 1) 熟练使用Visio的图形模板绘制出专业图表 2)掌握系统的功能描述、性能描述方法; 3) 掌握需求分析工具数据流图、数据字典等; 4) 掌握系统需求分析的步骤和方法。 实验要求: 要求做到使用结构化数据流分析技术分析课题需求,写出详细的数据流图和数据字典,编写 实验内容: 用结构化数据流分析技术进行软件系统需求分析,得出系统得数据流图和数据字典。实验步骤: 1) 到相关单位进行需求分析。 2) 综合利用Internet网和相关书籍整理并完善需求分析。 3) 画出系统数据流图。 4) 得出系统数据字典。 1.软件系统需求描述:(从功能,性能上进行描述) 本系统可细化为两个子系统:销售系统和采购系统。 销售系统的主要工作过程为:首先由教师及学生提交购书单,经教材发行人员审核是有效购书单后,开发票,登记并返还给教师和学生领书单,教师和学生即可去书库领书。 采购系统的主要工作过程为:若是脱销教材,则登记缺书单给书库采购人员,一旦新书入库后,即发进书通知给教材发行人员。 本系统是学校教材订购系统,希望通过计算机能实现对教材采购自动化管理,达到节省人力和提高工作效率的目的。凡书库中的书的数量发生变化(包括领书或进书)时,都应修改相关的书库记录,例如库存表或进/出库表 所以在本次实验中我们应注意教师(学生)与教材发行人员与书库采购员之间的联系;两个子系统:销售系统与采购系统之间的联系,两个子系统合为一个教材订购系统,而与销售系统和采购系统都有关系的是教材发行人员,教师(学生)、图书采购员都需要与教材发行人员联系凡书库中的书的数量发生变化(包括领书或进书)时,都应修改相关的书库记录,例如库存表或进/出库表。 2.软件系统数据流图(由加工、数据流、文件、源点和终点四种元素组成): 3.软件系统数据字典: 1.数据流条目 2.加工条目 3.文件条目 4. 实验小结 本次实验我主要思考了两个子系统之间的关系,以及它们的基本实现方法,教师发书单给教材发行人员后,教材发行人员通过审核销售系统的库存表如教材充足,则返回书单去领书,如缺书书库采购人员进书后将教材的数量输入采购系统库存表反馈给教材发行人员。 本科实验报告 课程名称:数据结构(C语言版) 实验项目:线性表、树、图、查找、内排序实验地点:明向校区实验楼208 专业班级:学号: 学生姓名: 指导教师:杨永强 2019 年 1 月10日 #include 数据结构实验十一:图实验
人事管理系统-软件工程实验报告
(完整版)数据结构实验报告全集
数据结构实验报告图实验
实验报告格式范文
数据结构实验报告完整
数据结构实验报告图实验
数据流图实验报告
数据结构图的遍历实验报告
数据结构实验
实验分析数据流和绘制数据流图
数据结构实验报告(图)
软件工程实验报告
数据结构实验报告无向图
数据结构图实验报告
软件工程实验报告_学生成绩管理系统
数据结构实验报告图实验
数据结构实验—图实验报告
实验一 软件结构化分析实验报告
数据结构实验报告