数据结构实验五图子系统

数据结构实验五矩阵的压缩存储与运算第五章矩阵的压缩存储与运算【实验目的】1. 熟练掌握稀疏矩阵的两种存储结构(三元组表和十字链表)的实现；2. 掌握稀疏矩阵的加法、转置、乘法等基本运算；3. 加深对线性表的顺序存储和链式结构的理解。

第一节知识准备矩阵是由两个关系（行关系和列关系）组成的二维数组，因此对每一个关系上都可以用线性表进行处理；考虑到两个关系的先后，在存储上就有按行优先和按列优先两种存储方式，所谓按行优先，是指将矩阵的每一行看成一个元素进行存储；所谓按列优先，是指将矩阵的每一列看成一个元素进行存储；这是矩阵在计算机中用一个连续存储区域存放的一般情形，对特殊矩阵还有特殊的存储方式。

一、特殊矩阵的压缩存储1. 对称矩阵和上、下三角阵若n阶矩阵A中的元素满足= （0≤i，j≤n-1 ）则称为n阶对称矩阵。

对n阶对称矩阵，我们只需要存储下三角元素就可以了。

事实上对上三角矩阵（下三角部分为零）和下三角矩阵（上三角部分为零），都可以用一维数组ma[0.. ]来存储A的下三角元素（对上三角矩阵做转置存储），称ma为矩阵A的压缩存储结构，现在我们来分析以下，A和ma之间的元素对应放置关系。

问题已经转化为：已知二维矩阵A[i，j]，如图5-1，我们将A用一个一维数组ma[k]来存储，它们之间存在着如图5-2所示的一一对应关系。

任意一组下标(i,j)都可在ma中的位置k中找到元素m[k]= ；这里：k=i(i+1)/2+j (i≥j)图5-1 下三角矩阵a00 a10 a11 a20 … an-1,0 … an-1,n-1k= 0 1 2 3 …n(n-1)/2 …n(n+1)/2-1图5-2下三角矩阵的压缩存储反之，对所有的k=0,1，2,…,n(n+1)/2-1，都能确定ma[k]中的元素在矩阵A中的位置（i,j）。

这里，i=d-1，（d是使sum= > k的最小整数），j= 。

2. 三对角矩阵在三对角矩阵中，所有的非零元素集中在以主对角线为中心的带内状区域中，除了主对角线上和直接在对角线上、下方对角线上的元素之外，所有其它的元素皆为零，见图5-3。

实验一线性表操作一、实验目的1熟悉并掌握线性表的逻辑结构、物理结构。

2熟悉并掌握顺序表的存储结构、基本操作和具体的函数定义。

3熟悉VC++程序的基本结构，掌握程序中的用户头文件、实现文件和主文件之间的相互关系及各自的作用。

4熟悉VC++操作环境的使用以及多文件的输入、编辑、调试和运行的全过程。

二、实验要求1实验之前认真准备，编写好源程序。

2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。

3不断积累程序的调试方法。

三、实验内容基本题:1对元素类型为整型的顺序存储的线性表进行插入、删除和查找操作。

加强、提高题：2、编写一个求解Josephus问题的函数。

用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人。

然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。

最后分析所完成算法的时间复杂度。

定义JosephusCircle类，其中含完成初始化、报数出圈成员函数、输出显示等方法。

（可以选做其中之一）加强题：（1）采用数组作为求解过程中使用的数据结构。

提高题：（2）采用循环链表作为求解过程中使用的数据结构。

运行时允许指定任意n、s、m数值，直至输入n = 0退出程序。

实验二栈、队列、递归应用一、实验目的1熟悉栈、队列这种特殊线性结构的特性2熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。

二、实验要求1实验之前认真准备，编写好源程序。

2实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。

3不断积累程序的调试方法。

三、实验内容基本题（必做）：1分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。

2、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。

加强题：3设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。

《数据结构和算法》实验指导书实验及学时数分配序号实验名称学时数（小时）1 实验一线性表 42 实验二树和二叉树 23 实验三图 24 实验四查找 25 实验五内部排序 2合计12几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科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.实现图的存储结构;2.通过图的相关算法实现，掌握其算法思想。

二、实验内容及要求1.无向带权图的存储结构(邻接矩阵、邻接表等自选)2.实现图的相关算法(1)计算指定顶点的度(2)图的深度优先遍历和广度优先遍历算法(3)分别使用Kruskal和Prim算法求解该图的最小生成树三、系统分析（1）数据方面：定义图的模板基类，在模板类定义中的数据类型参数表<class T,class E>中，T是定点数据的类型，E是边上所附数据的类型。

这个模板基类是按照带权无向图来定义的。

在该实验中定点的数据的类型为char型，边上所附数据的类型为int型。

且图的创建为无向图。

（2）功能方面：1.能够实现图的创建以及图的输出。

2.能够返回顶点在图中位置以及图中位置对应顶点的值。

3.返回当前图中的边数与顶点数。

4.返回输入边的权值。

5.能够插入一个顶点或插入顶点与之相关联的边。

6.删除边或删除顶点与之相关联的边。

7.计算顶点的度。

8.实现深度优先搜索、广度优先搜索遍历。

9.Kruskal算法、Prim算法生成最小生成树。

四、系统设计（1）设计的主要思路根据实验要求，首先确定图的存储结构，在根据存储结构编写模板类，并将需要实现的功能代码完善，再写出实现各个功能的菜单并进行调试。

由于在编写由图生成最小生成树中采用了最小堆以及并查集的算法，故需要将这两个个类的代码完成并进行调试。

最后将此次实验所涉及的类全部整理完全后，通过之前编写的菜单对功能进行依次调试，完成此次实验。

（2）数据结构的设计图是非线性结构，它的每一个顶点可以与多个其他顶点相关联，各顶点之间的关系是任意的。

可以用很多方法来存储图结构。

在此采用邻接矩阵来存储图结构。

首先将所有顶点的信息组织成一个顶点表，然后利用一个矩阵来表示各顶点之间的邻接关系，称为邻接矩阵。

下面针对带权无向图的邻接矩阵作出说明。

其中有一个类型为顺序表的顶点表向量VerticesList，用以存储顶点的信息，还有一个作为邻接矩阵使用的二维数组Edge，用以存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关。

《数据结构与算法》实验指导书实验及学时数分配几点要求：一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。

上机时签到；下机时验收签字。

三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一线性表【实验目的】1、掌握用Turbo c上机调试线性表的基本方法；2、掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、运用线性表解决线性结构问题。

【实验学时】4 学时【实验类型】设计型【实验内容】1、顺序表的插入、删除操作的实现；2、单链表的插入、删除操作的实现；3、两个线性表合并算法的实现。

(选做)【实验原理】1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。

若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。

若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；3、详细原理请参考教材。

【实验步骤】一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i，和要插入的元素值；实现插入；显示插入后的线性表）3、指定一个元素，删除此元素。

（从键盘接受删除元素位置i，实现删除；显示删除后的线性表）二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。

数据结构实验报告图数据结构实验报告图问题描述：;四则运算表达式求值，将四则运算表达式用中缀表达式;一、需求分析：;1、本程序是利用二叉树后序遍历来实现表达式的转换;2、输入输出格式：;输入格式：在字符界面上输入一个中缀表达式，回车表;请输入表达式：;输入一个中缀表达式;输出格式：如果该中缀表达式正确，那么在字符界面上;式，其中后缀表达式中两相邻操作数之间利用空格隔开;果不正确，在字符界面上输出问题描述：四则运算表达式求值，将四则运算表达式用中缀表达式，然后转换为后缀表达式，并计算结果。

一、需求分析：1、本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。

2、输入输出格式：输入格式：在字符界面上输入一个中缀表达式，回车表示结束。

请输入表达式：输入一个中缀表达式输出格式：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开;如果不正确，在字符界面上输出表达式错误提示。

逆波兰表达式为：3、测试用例输入：21+23*(12-6)输出：21 23 12 6 -*+ 输出逆波兰表达式运算结果为：输出运算后的结果二、概要设计：抽象数据类型二叉树类BiTree算法的基本思想根据题目要求，利用栈计算，和二叉树存储，来计算表达式该算法的基本思想是：先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值程序的流程程序由三个模块组成：(1) 输入模块：输入一个运算式(2) 计算模块：利用栈进行表达式的计算，二叉树来存储。

(3 ) 输出模块：屏幕上显示出后缀表达式和运算结果。

三、详细设计物理数据类型程序含有两个类，其中栈不再赘述，另一个类为二叉树class BiTree包含私有成员struct BiTreeNode，根节点BiTreeNode *T;索引index; int number_of_point 优先级比较函数compare(char a,char b);生成树的函数void InorderCreate(BiTreeNode *&T,char str,int start,int end);判断数字函数bool IsNumber(char a);求值函数double Operate(BiTreeNode *T);还有显示后缀表达式的函数void display(BiTreeNode *T) ;而公有成员函数则是对私有函数的重载，为方便使用，因为函数中普遍使用了递归的算法。

数据结构实验报告图的存储数据结构图实验报告一、实验目的和要求（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;实验①源程序。

/**题目：编写按键盘输入的数据建立图的邻接矩阵存储*编写图的深度优先遍历程序*编写图的广度优先遍历程序*设计一个选择式菜单形式如下：*图子系统**************************************1------更新邻接矩阵***2------深度优先遍历***3------广度优先遍历***0------返回**************************************请选择菜单号（ 0--3）：*/#include <stdio.h>#include <stdlib.h>#define GRAPHMAX 30#define QUEUEMAX 30typedef struct// 图的邻接表的结构体{char value[GRAPHMAX];// 记录图中的点值int data[GRAPHMAX][GRAPHMAX];// 记录图中的边的关系int n, e;// 记录图中的点的个数及边的个数}pGraph;typedef struct// 队列结构体{int queueData[QUEUEMAX];int front, rear, count;// 队头，队尾，数目}grQueue;void createCraph(pGraph *G);void DFSTraverse(pGraph *G);void BFSTraverse(pGraph *G);void DFS(pGraph *G, int i);void BFS(pGraph *G, int i);void initQueue(grQueue *Q);int queueEmpty(grQueue *Q);int queueFull(grQueue *Q);int outQueue(grQueue *Q);void inQueue(grQueue *Q, int i);int visited[GRAPHMAX];// 用于标志性的数组（全局变量）void main(){pGraph G;int choice, i, j, k = 1;printf(" 建立一个有向图的邻接矩阵表示createCraph(&G);\n");printf("已建立一个图的邻接矩阵存储\n\n");for (i = 0; i<G.n; i++){for(j = 0; j<G.n; j++){printf("%5d", G.data[i][j]);}printf("\n");}while (k){printf("\n图子系统 \n");printf("***********************************\n");printf("* printf("* printf("* printf("*1------ 更新邻接矩阵2------ 深度优先遍历3------ 广度优先遍历0------返回*\n");*\n");*\n");*\n");printf("***********************************\n");printf(" 请选择菜单号（ fflush(stdin);scanf("%d", &choice);0--3）： ");switch(choice){case 1:createCraph(&G);printf(" 图的邻接矩阵存储成功break;case 2:\n\n");DFSTraverse(&G);break;case 3:BFSTraverse(&G);break;case 0:k = 0;break;default:printf(" 输入错误，请重新输入。

.数据结构实验报告图一、实验目的1、熟悉图的结构和相关算法。

二、实验内容及要求1、编写创建图的算法。

2、编写图的广度优先遍历、深度优先遍历、及求两点的简单路径和最短路径的算法。

三、算法描述1、图的邻接表存储表示：对图的每个顶点建立一个单链表，第i个单链表表示所有依附于第i个点的边（对于有向图表示以该顶点为尾的弧）；链表的每个节点存储两个信息，该弧指向的顶点在图中的位置（adjvex）和指向下一条弧的指针（nextarc）。

每个连表的头结点存储顶点的数据：顶点信息（data）和指向依附于它的弧的链表域。

存储表示如下：typedef struct ArcNode {int adjvex; // 该弧所指向的顶点的位置struct ArcNode *nextarc;// 指向下一条弧的指针// InfoType *info; // 该弧相关信息的指针} ArcNode;typedef struct VNode {char data; // 顶点信息int data2;int sngle;ArcNode *firstarc;// 指向第一条依附该顶点的弧} VNode, AdjList[MAX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum;int kind; // 图的种类标志} ALGraph;2、深度优先搜索：假设初始态是图中所有定点未被访问，从图中的某个顶点v开始，访问此顶点，然后依次从v的未访问的邻接点出发深度优先遍历，直至途中所有和v有相同路径的点都被访问到；若图中仍有点未被访问，则从图中另选一个未被访问的点作为起点重复上述过程，直到图中所有点都被访问到。

为了便于区分途中定点是否被访问过，需要附设一个访问标致数组visited [0..n-1]，将其初值均设为false，一旦某个顶点被访问，将对应的访问标志赋值为true。

2、广度优先搜索：假设初始态是图中所有顶点未被访问，从图中的某个顶点v开始依次访问v的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。

数据结构实验报告图一、实验目的本次实验的主要目的是深入理解和掌握图这种数据结构的基本概念、存储结构和相关算法，并通过实际编程实现来提高对图的操作和应用能力。

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

三、实验内容（一）图的存储结构1、邻接矩阵邻接矩阵是用一个二维数组来表示图中顶点之间的关系。

如果顶点i 和顶点 j 之间有边相连，则数组中对应的元素值为 1；否则为 0。

这种存储结构简单直观，适用于顶点数较少且边数较多的稠密图。

2、邻接表邻接表是为图的每个顶点建立一个单链表，链表中存储的是与该顶点相邻的顶点信息。

这种存储结构在存储空间上比较节省，适用于顶点数较多且边数较少的稀疏图。

（二）图的遍历算法1、深度优先遍历（DepthFirst Search，简称 DFS）从图中的某个顶点出发，沿着一条路径尽可能深地访问顶点，直到无法继续前进，然后回溯到上一个未完全访问的顶点，继续进行深度优先搜索。

2、广度优先遍历（BreadthFirst Search，简称 BFS）从图中的某个顶点出发，先访问其所有相邻的顶点，然后再依次访问这些相邻顶点的相邻顶点，以此类推，逐层向外扩展。

（三）图的最短路径算法1、迪杰斯特拉（Dijkstra）算法用于求解单源最短路径问题，即从一个给定的源顶点到图中其他所有顶点的最短路径。

2、弗洛伊德（Floyd）算法用于求解任意两个顶点之间的最短路径。

四、实验步骤（一）邻接矩阵的实现｀｀｀cppinclude ＜iostream>using namespace std;const int MAX_VERTEX_NUM ＝ 100;class Graph ｛private:int vertexNum;int edgeNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;edgeNum ＝ 0;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ 0;｝｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ 1;adjMatrixji ＝ 1;edgeNum+＋；｝｝void printGraph(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛cout ＜＜ adjMatrixij ＜＜＂＂；｝cout ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gprintGraph(）；return 0;｝｀｀｀（二）邻接表的实现｀｀｀cppinclude ＜iostream>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void printGraph(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛cout ＜＜ i ＜＜＂：＂；for （int j ＝ 0; j ＜ adjListisize(）； j+＋）｛cout ＜＜ adjListij ＜＜＂＂；｝cout ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gprintGraph(）；return 0;｝｀｀｀（三）深度优先遍历的实现｀｀｀cppinclude ＜iostream>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100;class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛visitedi ＝ false;｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void DFS(int v) ｛visitedv ＝ true;cout ＜＜ v ＜＜＂＂；for （int i ＝ 0; i ＜ adjListvsize(）； i+＋）｛int u ＝ adjListvi;if （！visitedu) ｛DFS(u)；｝｝｝void DFSTraversal(）｛for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv) ｛DFS(v)；｝｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gDFSTraversal(）；return 0;｝｀｀｀（四）广度优先遍历的实现｀｀｀cppinclude ＜iostream>include ＜queue>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; class Graph ｛private:int vertexNum;vector<int> adjListMAX_VERTEX_NUM; bool visitedMAX_VERTEX_NUM; public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛visitedi ＝ false;｝｝void addEdge(int i, int j) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjListipush_back(j)；adjListjpush_back(i)；｝｝void BFS(int v) ｛queue<int> q;visitedv ＝ true;qpush(v)；while （！qempty(））｛int u ＝ qfront(）；qpop(）；cout ＜＜ u ＜＜＂＂；for （int i ＝ 0; i ＜ adjListusize(）； i+＋）｛int w ＝ adjListui;if （！visitedw) ｛visitedw ＝ true;qpush(w)；｝｝｝｝void BFSTraversal(）｛for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv) ｛BFS(v)；｝｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1)；gaddEdge(0, 2)；gaddEdge(1, 2)；gaddEdge(2, 3)；gaddEdge(3, 4)；gBFSTraversal(）；return 0;｝｀｀｀（五）迪杰斯特拉算法的实现｀｀｀cppinclude ＜iostream>include ＜climits>include ＜vector>using namespace std;const int MAX_VERTEX_NUM ＝ 100; const int INFINITY ＝ INT_MAX; class Graph ｛private:int vertexNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;int distanceMAX_VERTEX_NUM;bool visitedMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ INFINITY;｝distancei ＝ INFINITY;visitedi ＝ false;｝｝void addEdge(int i, int j, int weight) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ weight;adjMatrixji ＝ weight;｝｝int minDistance(）｛int min ＝ INFINITY;int minIndex ＝－1;for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv ＆＆ distancev ＜＝ min) ｛min ＝ distancev;minIndex ＝ v;｝｝return minIndex;｝void dijkstra(int src) ｛distancesrc ＝ 0;for （int count ＝ 0; count ＜ vertexNum 1; count+＋）｛int u ＝ minDistance(）；visitedu ＝ true;for （int v ＝ 0; v ＜ vertexNum; v+＋）｛if （！visitedv ＆＆ adjMatrixuv!＝ INFINITY ＆＆ distanceu!＝INFINITY ＆＆ distanceu ＋ adjMatrixuv ＜ distancev) ｛distancev ＝ distanceu ＋ adjMatrixuv;｝｝｝for （int i ＝ 0; i ＜ vertexNum; i+＋）｛cout ＜＜＂源点＂＜＜ src ＜＜＂到顶点＂＜＜ i ＜＜＂的最短距离为: ＂＜＜ distancei ＜＜ endl;｝｝｝；int main(）｛Graph g(5)；gaddEdge(0, 1, 2)；gaddEdge(0, 2, 4)；gaddEdge(1, 2, 1)；gaddEdge(1, 3, 7)；gaddEdge(2, 3, 3)；gaddEdge(3, 4, 5)；gdijkstra(0)；return 0;｝｀｀｀（六）弗洛伊德算法的实现｀｀｀cppinclude ＜iostream>include ＜climits>using namespace std;const int MAX_VERTEX_NUM ＝ 100; const int INFINITY ＝ INT_MAX; class Graph ｛private:int vertexNum;int adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;int distanceMAX_VERTEX_NUMMAX_VERTEX_NUM;public:Graph(int vNum) ｛vertexNum ＝ vNum;for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛adjMatrixij ＝ INFINITY;｝｝｝void addEdge(int i, int j, int weight) ｛if （i ＞＝ 0 ＆＆ i ＜ vertexNum ＆＆ j ＞＝ 0 ＆＆ j ＜ vertexNum) ｛adjMatrixij ＝ weight;｝｝void floyd(）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛distanceij ＝ adjMatrixij;｝｝for （int k ＝ 0; k ＜ vertexNum; k+＋）｛for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛if （distanceik!＝ INFINITY ＆＆ distancekj!＝ INFINITY ＆＆distanceik ＋ distancekj ＜ distanceij) ｛distanceij ＝ distanceik ＋ distancekj;｝｝｝｝for （int i ＝ 0; i ＜ vertexNum; i+＋）｛for （int j ＝ 0; j ＜ vertexNum; j+＋）｛if （distanceij ＝＝ INFINITY) ｛cout ＜＜＂顶点＂＜＜ i ＜＜＂到顶点＂＜＜ j ＜＜＂的距离为: 无穷大" ＜＜ endl;｝ else ｛cout ＜＜＂顶点＂＜＜ i ＜＜＂到顶点＂＜＜ j ＜＜＂的距离为: ＂＜＜ distanceij ＜＜ endl;｝｝｝｝｝；int main(）｛Graph g(4)；gaddEdge(0, 1, 5)；gaddEdge(0, 3, 10)；gaddEdge(1, 2, 3)；gaddEdge(2, 3, 1)；gfloyd(）；return 0;｝｀｀｀五、实验结果分析（一）邻接矩阵和邻接表的比较邻接矩阵的优点是可以快速判断两个顶点之间是否有边相连，时间复杂度为O(1)。

数据结构实验五图子系统实验五实验题目:图子系统指导老师:王春红专业班级:计算机科学与技术系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。

数据结构图实验报告一、实验目的本次实验的主要目的是深入理解和掌握数据结构图的基本概念、原理和操作方法，通过实际编程和操作，提高对数据结构的应用能力和解决问题的能力。

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

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

分析顺序表在不同操作下的时间复杂度。

2、链表实现单链表、双向链表的创建、插入、删除、查找等基本操作。

比较单链表和双向链表在操作上的优缺点。

（二）栈和队列1、栈实现顺序栈和链式栈。

用栈解决表达式求值问题。

2、队列实现顺序队列和链式队列。

用队列模拟银行排队问题。

（三）树1、二叉树实现二叉树的创建、遍历（前序、中序、后序）。

计算二叉树的深度和节点数。

2、二叉搜索树实现二叉搜索树的插入、删除、查找操作。

分析二叉搜索树的性能。

（四）图1、图的存储实现邻接矩阵和邻接表两种图的存储方式。

比较两种存储方式的优缺点。

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

用图的遍历解决最短路径问题。

四、实验步骤（一）线性表1、顺序表定义一个数组来存储顺序表的元素，并使用一个变量记录当前表的长度。

插入操作时，需要判断插入位置是否合法，如果合法则将插入位置后的元素依次向后移动一位，然后将新元素插入指定位置。

删除操作时，先判断删除位置是否合法，合法则将删除位置后的元素依次向前移动一位，并更新表的长度。

查找操作通过遍历数组来实现。

分析不同操作的时间复杂度，插入和删除操作在最坏情况下为O(n)，查找操作在平均情况下为 O(n/2)。

2、链表对于单链表，定义一个节点结构体，包含数据域和指向下一个节点的指针域。

通过操作指针来实现插入、删除和查找操作。

双向链表则在节点结构体中增加指向前一个节点的指针，使得操作更加灵活，但也增加了空间复杂度。

比较单链表和双向链表在插入、删除操作中指针的调整过程，得出双向链表在某些情况下更方便，但空间开销较大的结论。

上机实验要求及规范《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。

一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。

对于一名大学生必须严格训练分析总结能力、书面表达能力。

需要逐步培养书写科学实验报告以及科技论文的能力。

拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。

具体步骤如下：1.问题分析与系统结构设计充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。

按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。

在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。

最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。

2.详细设计和编码详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。

编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。

尽量多设一些注释语句，清晰易懂。

尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。

3.上机准备熟悉高级语言用法，如C语言。

熟悉机器（即操作系统），基本的常用命令。

静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。

如果程序中逻辑概念清楚，后者将比前者有效。

4.上机调试程序调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。

上机实验五图(一)一．任务图的定义及其相关操作。

二．训练目的（1）进一步掌握指针变量的用途和程序设计方法。

（2）掌握图的结构特征，以及图的两种常用的存储结构。

（3）掌握建立图的基本方法。

（4）掌握图遍历算法的设计方法。

（5）掌握图的其它常见操作的算法实现。

三．任务描述图结构是一种重要的数据结构结构，常采用邻接矩阵和邻接表作为存储结构，基本的操作有图的建立和两种遍历等。

四．任务要求任务分“基本要求”与“拓展要求”两部分，“基本要求”部分为必做题，“拓展要求”部分为选做题。

1．基本要求（1）定义图的两种存储结构。

（2）编写建立无向图（邻接矩阵存储形式）的函数。

（3）编写建立无向图（邻接表存储形式）的的函数。

（4）编写深度优先搜索遍历（邻接矩阵存储形式）的函数。

（5）编写输出图的函数。

（6）编写带菜单的测试主函数并上机运行。

打印出运行结果，并结合程序运行结果进行分析。

2．拓展要求（1）编写建立有向图（邻接矩阵存储形式）的函数。

（2）编写建立网络图（邻接矩阵存储形式）的函数。

（3）编写建立有向图（邻接表存储形式）的的函数。

（4）编写建立网络图（邻接表存储形式）的的函数。

（5）编写深度优先搜索遍历（邻接表存储形式）的函数。

（6）编写广度优先搜索遍历（邻接表存储形式）的函数。

（7）编写广度优先搜索遍历（邻接矩阵存储形式）的函数。

五．工作过程1．数据结构设计（1）采用邻接矩阵存储图，顶点的数据类型为int。

如下是其定义，请在下划线处填上相应代码，使其完整。

typedef-------VexType;typedef struct{------ vexs[MAX];int edges[MAX][MAX];int n,e;}Mgraph;(2) 采用邻接表存储图，顶点的数据类型为int。

如下是其定义，请在下划线处填上相应代码，使其完整。

typedef int VexType;typedef struct node //边表结点类型{int adjvex;struct node *next;}EdgeNode;typedef struct Vnode //顶点表结点类型{VexType vertex;EdgeNode *firstedge;}Vnode; /* Vnode是顶点的结点结构 */typedef Vnode AdjList[MAX]; /* 邻接表类型 */typedef struct{-------- adjlist;int n,e;}Lgraph ; /* Lgraph是以邻接表方式存储的图类型 */2. 程序的模块结构本次实验的程序模块结构如下图所示。

验证性实验5：串子系统班级学号 012301114114 姓名胡德文1．实验目的（1）掌握串的特点及顺序定长存储的方式。

（2）掌握串的创建、连接、插入、删除、显示等操作。

（3）掌握串的查找、取子字符串、比较串大小的操作（4）掌握模式匹配的基本思想及其算法。

2．实验内容（1）由用户通过键盘输入建立一个字符串。

（2）编写插入、删除、查找、比较、取子字符串、连接字符串、显示、模式匹配等程序。

（3）设计一个选择式菜单，以菜单方式选择上述操作。

串子系统********************************************* 1------输入字串** 2------连接字串** 3------取出子串** 4------删除子串** 5------插入子串** 6------查找子串** 7------比较串大小** 8------显示字串** 0------返回*********************************************请输入菜单选项（0--8）：3．实验程序#include <stdio.h>#define STRINGMAX 100typedef struct{ char vec [STRINGMAX];int len;}str;void ConcatStr(str *r1,str *r2){ int i;printf("\n\t\tr1=%s r2=%s\n",r1->vec,r2->vec);if (r1->len+r2->len>STRINGMAX)printf("\n\n\t 两个串太长，溢出!\n");else{ for (i=0;i<r2->len;i++)r1->vec[r1->len+i]=r2->vec[i];r1->vec[r1->len+i]='0';r1->len=r1->len+r2->len;}}void SubStr(str *r,int i,int j){ int k;str a;str *r1=&a;if (i+j-1>r->len){ printf ("\n\t\t子串超界!\n");return;}else{for (k=0;k<j;k++)r1->vec[k]=r->vec[i+k-1];r1->len=j;r1->vec[r1->len]='\0';}printf("\n\t\t取出字符为:");puts(r1->vec);}void DelStr(str *r,int i,int j){int k;if(i+j-1>r->len)printf("\n\t\t所要删除的子串超界!\n"); else{for (k=i+j;k<r->len;k++,i++)r->vec[i]=r->vec[k];r->len=r->len-j;r->vec[r->len]='\0';}}str *InsStr(str *r,str *r1,int i){int k;if(i>=r->len||r->len+r1->len>STRINGMAX) printf("\n\t\t不能插入!\n");else{ for(k=r->len-1;k>=i;k--)r->vec[r1->len+k]=r->vec[k];for(k=0;k<r1->len;k++)r->vec[i+k]=r1->vec[k];r->len=r->len+r1->len;r->vec[r->len]='\0';}return r;}int IndexStr(str *r,str *r1){int i,j,k;for(i=0;r->vec[i];i++)for(j=i,k=0;r->vec[j]==r1->vec[k];j++,k++)if(!r1->vec[k+1])return i;return -1;}int LenStr(str *r){int i=0;while(r->vec[i]!='\0')i++;return i;}str*CreateStr(str *r){ gets(r->vec);r->len=LenStr(r);return r;}int EqualStr(str *r1,str *r2){for(int i=0;r1->vec[i]&&r2->vec[i]&&r1->vec[i]==r2->vec[i];i++); return r1->vec[i]-r2->vec[i];}void main(){str a,b,c,d;str *r=&a,*r1;r->vec[0]='\0';char choice,p;int i,j,ch=1;while(ch!=0){printf("\n");printf("\n\t\t 串子系统 ");printf("\n\t\t*********************************************");printf("\n\t\t* 1------输入字串 *");printf("\n\t\t* 2------连接字串 *");printf("\n\t\t* 3------取出子串 *");printf("\n\t\t* 4------删除子串 *");printf("\n\t\t* 5------插入子串 *");printf("\n\t\t* 6------查找子串 *");printf("\n\t\t* 7------比较串大小 *");printf("\n\t\t* 8------显示字串 *");printf("\n\t\t* 0------返回 *");printf("\n\t\t*********************************************");printf("\n\t\t 请选择菜单号(0--8): "); scanf("%c",&choice);getchar();if(choice=='1'){printf("\n\t\t请输入一个字符串:");gets(r->vec);r->len=LenStr(r);}else if(choice=='2'){printf("\n\t\t请输入所要连接的串:");r1=CreateStr(&b);ConcatStr(r,r1);printf("\n\t\t连接以后的新串值为:");puts(r->vec);}else if(choice=='3'){printf("\n\t\t请输入从第几个字符开始:");scanf("%d",&i);getchar();printf("\n\t\t请输入取出的连续字符数:");scanf("%d",&j);getchar();SubStr(r,i,j);}else if(choice=='4'){printf("\n\t\t请输入从第几个字符开始:");scanf("%d",&i);getchar();printf("\n\t\t请输入删除的连续字符数:");scanf("%d",&j);getchar();DelStr(r,i-1,j);}else if(choice=='5'){printf("\n\t\t 请输入在第几个字符前插入: ");scanf("%d",&i);getchar();printf("\n\t\t 请输入所要插入的字符串: ");r1=CreateStr(&b);InsStr(r,r1,i-1);}else if(choice=='6'){printf("\n\t\t 请输入所要查找的字符串: ");r1=CreateStr(&b);i=IndexStr(r,r1);if(i!=-1)printf("\n\t\t 第一次出现的位置是第%d个.\n",i+1);elseprintf("\n\t\t 该字串不在其中! \n");}else if(choice=='7'){printf("\n\t\t 请输入第一个串: ");gets(c.vec);printf("\n\t\t 请输入第二个串: ");gets(d.vec);int k=EqualStr(&c,&d);if(k>0)printf("\n\t\t第一个串大！\n");else if(k<0)printf("\n\t\t第二个串大！\n");elseprintf("\n\t\t两个串一样大！\n");}else if(choice=='8'){printf("\n\t\t该串值为：");if(r->vec[0]=='\0')printf("空！\n");elseputs(r->vec);}else if(choice=='0')break;elseprintf("\n\t\t 请注意：输入有误！\n");if(choice!='X'&&choice!='X'){printf("\n\t\t按【Enter】键继续，按任意键返回主菜单."); p=getchar();if(p!='\xA'){getchar();break;}}}}4．程序运行5．实验小结本章要求我们掌握的是字符串的创建、连接、删除、显示、查找、取子串和比较字符串大小。

实验五图一、实验目的1. 掌握图的基本存储方法；2. 掌握有关图的操作算法并用高级语言实现；3. 熟练掌握图的两种搜索路径的遍历方法。

二、实验内容假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。

三、实验步骤1. 定义结点结构，定义图结构。

2.存储图信息；3. 定义求任意两点最短路径函数；4. 写出主函数。

四、实现提示typedef struct node{ int no;float wgt;struct node *next;}edgenode;typedef struct{ char vtx;edgenode *link;}vexnode;typedef vexnode Graph[n];void Floyd(Graph G, float A[n][n], int p[n][n]){int i, j, k;for (i=0; i<n; i++)for(j=0;j<n;j++){A[i][j]=G[i][j];P[i][j]=-1;}for (k=0; k<n; k++)for (i=0; i<n; i++)for (j=0; j<n; j++)if(A[i][k] +A[k][j]<A[i][j]){P[i][j]=k;A[i][j]=A[i][k]+A[k][j];}}五、思考与提高（直接将答案写在小题后面）1. 判断两点是否可达。

2.如何对程序进行修改，找一条人最少的公交线路？3.练习图的拓扑排序六、调试以下参考程序代码，并将运行效果截图1.图的建立与遍历#include <conio.h>#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_VERTEX_NUM 20 //图的最大顶点数#define MAXQSIZE 30 //队列的最大容量enum BOOL {False,True};typedefstructArcNode{intadjvex; //该弧所指向的顶点的位置structArcNode *nextarc; //指向下一条弧的指针}ArcNode; //弧结点typedefstruct{ArcNode* AdjList[MAX_VERTEX_NUM]; //指向第一条依附该顶点的弧的指针intvexnum,arcnum; //图的当前顶点和弧数intGraphKind; //图的种类，0---无向图，1---有向图}Graph;typedefstruct //队列结构{intelem[MAXQSIZE]; //数据域int front; //队头指针int rear; //队尾指针}SqQueue;BOOL visited[MAX_VERTEX_NUM]; //全局变量——访问标志数组void CreateGraph(Graph &); //生成图的邻接表void DFSTraverse(Graph); //深度优先搜索遍历图void DFS(Graph,int);void BFSTraverse(Graph); //广度优先搜索遍历图void Initial(SqQueue&); //初始化一个队列BOOL QueueEmpty(SqQueue); //判断队列是否空BOOL EnQueue(SqQueue&,int); //将一个元素入队列BOOL DeQueue(SqQueue&,int&); //将一个元素出队列intFirstAdjVex(Graph,int); //求图中某一顶点的第一个邻接顶点intNextAdjVex(Graph,int,int); //求某一顶点的下一个邻接顶点void main(){Graph G; //采用邻接表结构的图char j='y';printf("本程序将演示生成一个图，并对它进行遍历.\n");printf("首先输入要生成的图的种类.\n");printf("0---无向图, 1--有向图\n");printf("之后输入图的顶点数和弧数。

实验五图操作实现实验日期：2017 年 4 月27 日实验目的及要求1. 熟练掌握图的邻接矩阵和邻接表的存储方式；2. 实现图的一些基本运算，特别是深度优先遍历和广度优先遍历；实验内容用邻接矩阵法建一个无向连通图（顶点信息为顺序字母A，B，C，D...，而非键盘输入），分别用dfs（深度优先搜索）和bfs(广度优先搜索)遍历，输出图中顶点信息并验证。

邻接矩阵图类型定义：#define MAX 40typedef char vexType; /*顶点类型*/typedef struct{vexType vex[MAX];int arcs[MAX][MAX];int vn,en;} MGraph;访问标记数组定义：int visited[MAX]; /*值为0时对应顶点未被访问，值为1时对应顶点已被访问*/顺序存储的循环队列类型定义：typedef int datatype; /*队列元素为图的顶点下标,int型*/typedef struct node{datatype data[MAX];int front, rear;} SeqQueue; /*顺序存储的循环队列类型*/任务1．自定义函数库文件Queue.h，完成队列的相关操作。

2．创建一个程序文件sy15.cpp，自定义相应函数完成以下操作：（1）void createGraph(MGraph *g) /*建邻接矩阵存储的无向图*/（2）void visit(MGraph *g,int v) /*访问v号顶点*/（3）void dfs(MGraph *g,int v) /*邻接矩阵存储的图的深度优先搜索*/ （4）void bfs(MGraph *g,int v) /*邻接矩阵存储的图的广度优先搜索*/3．回答下列问题（1）现有定义：MGraph *g，并且g指针指向的无向图已创建完成，请写出该图遍历前需初始化visited数组的C程序语句。