实验报告七图及图的操作实验班级： 2010XXX 姓名： HoogLe 学号： 2010XXXX 专业： XXXX
2858505197@https://www.doczj.com/doc/dc4766299.html,
一、实验目的：
1、掌握图的基本概念和术语
2、掌握图的存储结构及创建算法。
3、掌握图的遍历算法（递归算法）。
二、实验内容：
1、图邻接矩阵存储结构表示及基本操作算法实现
[实现提示] （同时可参见教材及ppt上的算法）函数、类名称等可自定义，部分变量请
加上学号后3位。也可自行对类中所定义的操作进行扩展。
所加载的库函数或常量定义及类的定义：
（1）邻接矩阵存储结构类定义：
自定义如下：
#include
using namespace std;
const int MaxSize=12;
const int INFINITY=65535;
template
class Mgraph{
public:
Mgraph(T a[],int n,int e);//构造函数，a[]表示节点数组，n表示顶点个数，e表示边数
void printGraph(); //输出
void BFS(int v,int visited[]); //广度优先搜索
private:
T vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum,arcNum;
void createUG(T a[],int n,int e); //无向图
void createUW(T a[],int n,int e); //无向网
void createHG(T a[],int n,int e); //有向图
void createHW(T a[],int n,int e); //有向网
};
template
Mgraph
int kind;
cout<<"请输入所需创建的图的类型:"< cout<<"1.无向图"< cout<<"2.无向网"< cout<<"3.有向图"< cout<<"4.有向网"< cin>>kind; switch(kind){ case 1:createUG(a,n,e);break; case 2:createUW(a,n,e);break; case 3:createHG(a,n,e);break; case 4:createHW(a,n,e);break; default:cout<<"输入错误！"< } } （2）创建邻接矩阵算法 创建无向图邻接矩阵算法： template void Mgraph {//创建无向图 vertexNum=n; //顶点数 arcNum=e; //边数 int i,j,k; for (i=0; i vertex[i]=a[i]; for (i=0; i for (j=0; j arc[i][j]=0; for (k=0; k //依次输入每一条边，并修改邻接矩阵的相应元素{ cout<<"请输入第"< cin>>i>>j; //边依附的两个顶点的序号 arc[i-1][j-1]=1; //置有边标志 arc[j-1][i-1]=1; } } 创建无向网邻接矩阵算法： 无向网的创建： template void Mgraph {//创建无向网 int w;//权值 vertexNum=n; //顶点数 arcNum=e; //边数 int i,j,k; for (i=0; i vertex[i]=a[i]; for (i=0; i for (j=0; j arc[i][j]=INFINITY; for (k=0; k //依次输入每一条边，并修改邻接矩阵的相应元素 {cout<<"请输入第"< cin>>i>>j>>w; //边依附的两个顶点的序号 arc[i-1][j-1]=w; //置有边标志 arc[j-1][i-1]=w; } } 创建有向图邻接矩阵算法： template void Mgraph {//创建无向图 vertexNum=n; //顶点数 arcNum=e; //边数 int i,j,k; for (i=0; i vertex[i]=a[i]; for (i=0; i for (j=0; j arc[i][j]=0; for (k=0; k //依次输入每一条边，并修改邻接矩阵的相应元素 { cout<<"请输入第"< cin>>i>>j; //边依附的两个顶点的序号 arc[i-1][j-1]=1; //置有边标志 } } 创建有向网邻接矩阵算法： template void Mgraph {//创建无向图 vertexNum=n; //顶点数 arcNum=e; //边数 int i,j,k; int w; for (i=0; i vertex[i]=a[i]; for (i=0; i for (j=0; j arc[i][j]=0; for (k=0; k { cout<<"请输入第"< cin>>i>>j>>w; //边依附的两个顶点的序号 arc[i-1][j-1]=w; //置有边标志 } } （3）输出邻接矩阵结果算法 template void Mgraph {//输出邻接矩阵 int i,j; for(i=0;i { for(j=0;j cout< cout< } } 测试结果粘贴如下： void main() { int a[6]={1,2,3,4,5,6}; Graph graph1.printGraph(); } 2、图邻接表存储结构表示及基本操作算法实现 [实现提示]函数、类名称等可自定义，部分变量请加上学号后3位。也可自行 对类中所定义的操作进行扩展。 所加载的库函数或常量定义及类的定义： （1）邻接表存储结构类定义： 自定义如下： #include using namespace std; const int MaxSize=12; class Edge //边 { public: int adjvertex; //当前结点的下标 Edge *nextarc; //下一条边 int value; //边的权值 }; template template class VertexNode{ //节点 friend class Mgraph T vex; //结点名 Edge *firstarc; //第一个边 }; template class Mgraph{ public: Mgraph(T a[],int n,int e);//构造一个有E条边N个结点的图，A[]为结点矩阵 ~Mgraph(); //析构函数 void printGraph(); //输出 void DFS(int v,int visited[]); //深度优先遍历 private: VertexNode int vertexNum,arcNum; //顶点数和边数 void creatGraphU(T a[],int n,int e); //无向图 void creatGraphH(T a[],int n,int e); //有向图 }; template Mgraph for(int i=0;i { Edge *E,*q; E=adjlist[i].firstarc; while(E) { q=E; E=E->nextarc; delete q; } } } template Mgraph int kind; cout<<"请输入所需创建的图类型："< cout<<"1.无向图"< cout<<"2.有向图"< cin>>kind; switch(kind){ case 1:creatGraphU(a,n,e);break; case 2:creatGraphH(a,n,e);break; default:cout<<"输入错误！"< } } （2）创建邻接表算法 创建无向网邻接表算法： template void Mgraph Edge *E; vertexNum=n; arcNum=e; for (int i=0;i { adjlist[i].vex=a[i]; adjlist[i].firstarc=NULL; } int j,w; for (int k=0;k { cout<<"请输入第"< cin>>i>>j>>w; E=new Edge; E->value=w; E->adjvertex=j-1; E->nextarc=adjlist[i-1].firstarc; adjlist[i-1].firstarc=E; E=new Edge; E->value=w; E->adjvertex=i-1; E->nextarc=adjlist[j-1].firstarc; adjlist[j-1].firstarc=E; } } 创建有向网邻接表算法： template void Mgraph Edge *E; vertexNum=n; arcNum=e; for (int i=0;i { adjlist[i].vex=a[i]; adjlist[i].firstarc=NULL; } int j,w; for (int k=0;k { cout<<"请输入第"< cin>>i>>j>>w; E=new Edge; E->value=w; E->adjvertex=j-1; E->nextarc=adjlist[i-1].firstarc; adjlist[i-1].firstarc=E; } } （3）输出邻接表结果算法 template void Mgraph for (int i=0;i { Edge *p; cout< p=adjlist[i].firstarc; while(p) { cout< p=p->nextarc; } cout< } } 测试结果粘贴如下： void main() { int a[5]={1,2,3,4,5}; Mgraph graph1.printGraph(); int visited[5]={0}; graph1.DFS(2,visited); } 3、图的遍历递归算法 （1）（存储结构为邻接表）深度优先遍历算法 递归算法： template void Mgraph if(v>vertexNum){ cout<<"顶点数处错误"< int j; cout< visited[v]=1; p=adjlist[v].firstarc; while (p!=NULL) //依次搜索顶点v的邻接点j { j=p->adjvertex; if (visited[j]==0) DFS(j,visited); p=p->nextarc; } } 测试结果粘贴如下：有向网的测试结果： 无向网的测试结果： （2）广度优先遍历算法 非递归算法 template void Graph if (v>vertexNum){ cout<<"元素不存在！"< int front=-1; int rear=-1; int Queue[MaxSize]; ////////////////// cout< visited[v]=1; Queue[++rear]=v; while (front!=rear) { v=Queue[++front]; //将队头元素出队并送到v中 for (int j=0; j if (arc[v][j]==1 && visited[j]==0 ){ cout< visited[j]=1; Queue[++rear]=j;//进队 } } } 测试结果粘贴如下： void main(){ int a[5]={1,2,3,4,5}; Mgraph graph1.printGraph(); int visited[5]={0}; graph1.BFS(2,visited); } 有向网的测试结果： 无向网的测试结果： 三、实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新 点及编程的心得） 实验七查找 一、实验目的 1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤 1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序（课后自己做）。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t; while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key 数据结构实验指导书 实验一线性表的顺序存储结构 一、实验学时 4学时 二、背景知识:顺序表的插入、删除及应用。 三、目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 四、实验内容 1．从键盘随机输入一组整型元素序列，建立顺序表。（注意：不可将元素个数和元素值写死在程序中） 2．实现该顺序表的遍历（也即依次打印出每个数据元素的值）。 3．在该顺序表中顺序查找某一元素,如果查找成功返回1,否则返回0。 4．实现把该表中某个数据元素删除。 5．实现在该表中插入某个数据元素。 6．实现两个线性表的归并（仿照课本上P26 算法2.7）。 7. 编写一个主函数,调试上述6个算法。 五、实现提示 1.存储定义 #include typedef int ElemType；//元素类型 typedef struct list{ ElemType *elem;//静态线性表 int length; //表的实际长度 int listsize; //表的存储容量 }SqList;//顺序表的类型名 2.建立顺序表时可利用随机函数自动产生数据。 3.为每个算法功能建立相应的函数分别调试，最后在主函数中调用它们。 六、注意问题 插入、删除元素时对于元素合法位置的判断。 七、测试过程 1.先从键盘输入元素个数，假设为6。 2.从键盘依次输入6个元素的值（注意：最好给出输入每个元素的提示，否则除了你自己知道之外，别人只见光标在闪却不知道要干什么），假设是：10,3,8,39,48，2。 3．遍历该顺序表。 4.输入待查元素的值例如39（而不是待查元素的位置）进行查找，因为它在表中所以返回1。假如要查找15,因为它不存在，所以返回0。 5.输入待删元素的位置将其从表中删掉。此处需要注意判断删位置是否合法，若表中有n个元素，则合法的删除位 实验2 查找算法的实现和应用?实验目的 1. 熟练掌握静态查找表的查找方法； 2. 熟练掌握动态查找表的查找方法; 3. 掌握hash表的技术. ?实验内容 1.用二分查找法对查找表进行查找； 2.建立二叉排序树并对该树进行查找； 3.确定hash函数及冲突处理方法，建立一个hash表并实现查找。 程序代码 #include cout<<"Not present!"; } return 0; } 结果 二叉排序树 #include 暨南大学本科实验报告专用纸 课程名称数据结构实验成绩评定 实验项目名称习题6.51 指导教师孙世良 实验项目编号实验7 实验项目类型实验地点实验楼三楼机房学生姓名林炜哲学号2013053005 学院电气信息学院系专业软件工程 实验时间年月日午～月日午温度℃湿度(一)实验目的 熟悉和理解二叉树的结构特性； 熟悉二叉树的各种存储结构的特点及适用范围； 掌握遍历二叉树的各种操作及其实现方式。 (二)实验内容和要求 编写一个算法，输出以二叉树表示的算术表达式，若该表达式中含有括号，则应该在输出时添上。 (三)主要仪器设备 实验环境：Microsoft Visual Studio 2012 (四)源程序 #include if(t==' ') T=NULL; else{ if( !( T=(bitnode*)malloc(sizeof(bitnode)) ) ) exit(0); T->data=t; create(T->lchild); create(T->rchild); } } void middle_order(bitree &Node){ if(Node != NULL){ if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf("( "); middle_order(Node->lchild); if((Node->data=='*'||Node->data=='/')&&(Node->lchild->data=='+'|| Node->lchild->data=='-')) printf(") "); printf("%c ", Node->data); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf("( "); middle_order(Node->rchild); if((Node->data=='*'||Node->data=='/')&&(Node->rchild->data=='+'|| Node->rchild->data=='-')) printf(") "); } } int main() { bitree y; printf("以先序遍历的方式输入二叉树："); create(y); printf("输出表达式："); middle_order(y); return 0; } (五)数据调试 实验报告 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网 的类型定义和基本操作,完成上述功能。 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 【题目五】连通OR 不连通 描述：给定一个无向图，一共n个点，请编写一个程序实现两种操作： D x y 从原图中删除连接x，y节点的边。 Q x y 询问x，y节点是否连通 输入 第一行两个数n,m（5<=n<=40000,1<=m<=100000） 接下来m行，每行一对整数 x y （x,y<=n）,表示x,y之间有边相连。保证没有重复的边。 接下来一行一个整数 q（q<=100000） 以下q行每行一种操作，保证不会有非法删除。 输出 按询问次序输出所有Q操作的回答，连通的回答C，不连通的回答D 样例输入 3 3 1 2 1 3 2 3 5 Q 1 2 D 1 2 Q 1 2 D 3 2 Q 1 2 样例输出 C C D 【题目六】 Sort Problem An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not. 【Input】 Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n<= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. 1 <= m <= 100. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input. 【Output】 For each problem instance, output consists of one line. This line should be one of the following three: Sorted sequence determined: y y y… y. Sorted sequence cannot be determined. Inconsistency found. 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日 云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。） （下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include 实验八内部排序 一、实验目的 1、掌握内部排序的基本算法； 2、分析比较内部排序算法的效率。 二、实验内容和要求 1. 运行下面程序： #include 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 实验七图的创建与遍历 实验目的： 通过上机实验进一步掌握图的存储结构及基本操作的实现。 实验内容与要求： 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。算法设计： #include . } void EnQueue(int e) { base[rear]=e; rear=(rear+1)%QUEUE_SIZE; } void DeQueue(int &e) { e=base[front]; front=(front+1)%QUEUE_SIZE; } public: int *base; int front; int rear; }; //图G中查找元素c的位置 int Locate(Graph G,char c) { for(int i=0;i #include 长春大学计算机学院网络工程专业 数据结构实验报告 实验名称：实验二栈和队列的操作与应用 班级：网络14406 姓名：李奎学号：041440624 实验地点：日期： 一、实验目的： 1．熟练掌握栈和队列的特点。 2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。 3．掌握链队的入队和出队等基本操作。 4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。 二、实验内容、要求和环境： 注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.doczj.com/doc/dc4766299.html,。提交时限：本次实验后24小时之内。 阅读程序，完成填空，并上机运行调试。 1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 (1)文件SqStackDef. h 中实现了栈的顺序存储表示 #define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/ #define STACKINCREMENT 2 /* 存储空间分配增量*/ typedef struct SqStack { SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */ SElemType *top; /* 栈顶指针*/ int stacksize; /* 当前已分配的存储空间，以元素为单位*/ }SqStack; /* 顺序栈*/ (2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义） Status InitStack(SqStack &S) { /* 构造一个空栈S */ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); /* 存储分配失败*/ S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } int StackLength(SqStack S) { // 返回S 的元素个数，即栈的长度, 编写此函数 云南大学 数据结构实验报告 第三次实验 学号： 姓名： 一、实验目的 1、复习结构体、指针； 2、掌握链表的创建、遍历等操作； 3、了解函数指针。 二、实验内容 1、（必做题）每个学生的成绩信息包括：学号、语文、数学、英语、总分、加权平均分；采用链表存储若干学生的成绩信息；输入学生的学号、语文、数学、英语成绩；计算学生的总分和加权平均分（语文占30%，数学占50%，英语占20%）；输出学生的成绩信息。 三、算法描述 （采用自然语言描述） 首先创建链表存储n个学生的成绩信息，再通过键盘输入学生的信息，创建指针p所指结点存储学生的成绩信息，从键盘读入学生人数，求出学生的总分和加权平均分，输出结果。 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #include 实验六图的应用及其实现 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOE网在邻接表上的实现及解决简单的应用问题。 二、实验内容 [题目]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 三、实验步骤 （一）、数据结构与核心算法的设计描述 本实验题目是基于图的基本操作以及邻接表的存储结构之上，着重拓扑排序算法的应用，做好本实验的关键在于理解拓扑排序算法的实质及其代码的实现。 （二）、函数调用及主函数设计 以下是头文件中数据结构的设计和相关函数的声明： typedef struct ArcNode // 弧结点 { int adjvex; struct ArcNode *nextarc; InfoType info; }ArcNode; typedef struct VNode //表头结点 { VertexType vexdata; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct //图的定义 { AdjList vertices; int vexnum,arcnum; int kind; }MGraph; typedef struct SqStack //栈的定义 { SElemType *base; SElemType *top; int stacksize; }SqStack; int CreateGraph(MGraph &G);//AOE网的创建 int CriticalPath(MGraph &G);//输出关键路径 （三）、程序调试及运行结果分析 （四）、实验总结 在做本实验的过程中，拓扑排具体代码的实现起着很重要的作用，反复的调试和测试占据着实验大量的时间，每次对错误的修改都加深了对实验和具体算法的理解，自己的查错能力以及其他各方面的能力也都得到了很好的提高。最终实验结果也符合实验的预期效果。 四、主要算法流程图及程序清单 1、主要算法流程图： 2、程序清单： 创建AOE网模块： int CreateGraph(MGraph &G) //创建有向网 { int i,j,k,Vi,Vj; ArcNode *p; cout<<"\n请输入顶点的数目、边的数目"< 邻接矩阵的实现 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 数据结构实验 实验四、图遍历的演示。 【实验学时】5学时 【实验目的】 （1）掌握图的基本存储方法。 （2）熟练掌握图的两种搜索路径的遍历方法。 【问题描述】 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示连通的无向图上，遍历全部结点的操作。 【基本要求】 以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 教科书图7.33。暂时忽略里程，起点为北京。 【实现提示】 设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1，2，…，n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。 【选作内容】 （1）借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。 （3）正如习题7。8提示中分析的那样，图的路径遍历要比结点遍历具有更为广泛的应用。再写一个路径遍历算法，求出从北京到广州中途不过郑州的所有简单路径及其里程。 【源程序】 #include 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 课程实验报告课程名称：数据结构 专业班级：信安 学号： 姓名： 指导教师： 报告日期：2015.4.5 计算机科学与技术学院 目录 1 课程实验概述 (1) 2 实验一基于顺序结构的线性表实现 2.1 问题描述 (2) 2.2 系统设计 (2) 2.3 系统实现 (7) 2.4 效率分析 (11) 3 实验二基于链式结构的线性表实现 3.1 问题描述 (12) 3.2 系统设计 (12) 3.3 系统实现 (14) 3.4 效率分析 (22) 4 实验三基于二叉链表的二叉树实现 4.1 问题描述 (23) 4.2 系统设计 (23) 4.3 系统实现 (32) 4.4 效率分析 (43) 5 实验总结与评价 (45) 1 课程实验概述 上机实验是对学生的一种全面综合训练，是与课堂听课、自学和练习相辅相成的必不可少的一个教学环节。实验目的着眼于原理与应用的结合，使学生学会如何把书上的知识用语解决实际问题，能够理解和运用常用的数据结构，如线性表、栈、队列、树、图、查找表等，并在此基础上建立相应的算法；通过上机实验使学生了解算法和程序的区别，培养学生把算法转换为程序的能力，提高学生解决实际问题的能力；学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。 2 实验一基于顺序结构的线性表实现 2.1 问题描述 编写一个程序，实现顺序表的各种基本运算，并在此基础上完成以下功能: 1) 初始化顺序表； 2) 释放顺序表； 3) 判断顺序表L是否为空； 4) 输出顺序表L的长度； 5) 输出顺序表L的第i个元素； 6) 输出元素e的位置； 7) 输出元素e的前一个元素； 8) 输出元素e的后一个元素； 9) 在第i个元素位置上插入f元素； 10) 删除L的第i个元素； 11) 输出顺序表L； 12) 保存顺序表L的数据。 2.2 系统设计 1、数据类型 顺序表：typedef struct { ElemType * elem; //线性表首地址 int length; //线性表当前长度 int listsize; //线性表最大长度 }SqList; 数据类型：int（可以在头文件中更改数据类型） 输入形式：文件读取、键盘输入 输入范围：-2^15~2^16 2、函数返回状态 判断为真：TRUE 0 判断为假：FALSE -1 函数正确执行：OK -2 函数执行错误：ERROR -3 元素不存在：NOTEXIST -4 内存分配溢出：OVERFLOW -5 天津科技大学 2015—2016学年第2学期数据结构实验任务书 课程名称：数据结构实验学时： 2 实验题目：线性表的基本操作 实验环境： Visual C++ 实验目的： 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 实验内容： 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 实验提示： 学生信息的定义： typedef struct { char no[8]; //8位学号 char name[20]; //姓名 int score; //成绩 }Student; 顺序表的定义 typedef struct { Student *elem; //指向数据元素的基地址 int length; //线性表的当前长度 }SqList； 链表的定义： typedef struct LNode{ Student data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; 实验要求： (1) 程序要添加适当的注释，程序的书写要采用缩进格式。 (2) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。 (3) 程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。 (4) 根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。 (5) 以班为单位实验周周五上传源程序和实验报告。顺序表的源程序保存为SqList.cpp，链表的源程序保存为LinkList.cpp，实验报告命名为：实验报告1.doc。源程序和实验报告压缩为一个文件（如果定义了头文件则一起压缩），按以下方式命名：学号姓名.rar，如07081211薛力.rar。数据结构实验七 查找
数据结构实验
数据结构实验
数据结构实验7实验报告
数据结构_实验六_报告
数据结构实验报告
数据结构实验报告七查找、
数据结构实验八内部排序
数据结构实验报告
数据结构实验七图的创建与遍历
数据结构第六章实验
数据结构实验
数据结构实验报告[3]
数据结构实验六 图的应用及其实现
数据结构实验报告图实验
数据结构实验四五六
数据结构实验报告及心得体会
数据结构课程实验报告(7)
数据结构实验1
相关主题
文本预览