数据结构实验七图

实验六查找

一、实验目的

1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。

2、掌握线性表中顺序查找和折半查找的方法。

3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。

二、实验内容和要求

1. 静态查找表技术

依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：

查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的比较次数：

查找key=35的比较次数：

算法实现代码

#include<stdio.h>

#define N 100

typedef struct {

int data[N];

int length;

}SSTable;

int zbcz(SSTable s,int k, int *p)

{

int n=0;

int low,high,mid;

low=1;

high=s.length;

while(low<=high)

{

n++;

mid=(low+high)/2;

if

图实验 一，邻接矩阵的实现

1. 实验目的

（1） 掌握图的逻辑结构

（2） 掌握图的邻接矩阵的存储结构

（3） 验证图的邻接矩阵存储及其遍历操作的实现 2. 实验内容

（1） 建立无向图的邻接矩阵存储 （2） 进行深度优先遍历 （3） 进行广度优先遍历 3．设计与编码 MGraph.h

#ifndef MGraph_H #define MGraph_H

const int MaxSize = 10;

template class MGraph {

public: MGraph(DataType a[], int n, int e); ~MGraph(){ } void DFSTraverse(int v); void BFSTraverse(int v); private: DataType vertex[MaxSize]; int arc[MaxSize][MaxSize]; int vertexNum, arcNum; };

#endif

MGraph.cpp

#include using namespace std; #include \

extern int visited[MaxSize];

实验七 查找

一、实验目的

1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。

3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。

二、实验内容和要求

1. 静态查找表技术

依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：

查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的比较次数： 查找key=35的比较次数： ? 算法实现代码

1

2、哈希表的构造与查找

/* 采用开放地址法构造哈希表*/ #include #include #define MAXSIZE 25 #define P 13 #define OK 1 #define ERROR 0

#define DUPLICATE -1

2

#define TRUE 1 #define FALSE 0

ty

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

数据结构实验五实验报告

实验名称：图的遍历

姓名：黄州龙 班级：08软件工程A班 学号：0825121022

一、 需求分析

1、 本实验要求要利用图论的一些基本概念和算法来

实现对无向图和有向图的2种遍历，分别是深度优先遍历(DFS)和广度优先遍历(BFS)，通过本实验对图遍历算法的实现来帮助了解图这一特殊(多对多)的数据结构，以便在以后的实际应用中可以以此为基础来进行更好的软件程序开发；

2、 该程序开始时是通过用户输入的图的数据文件

(.txt)所在的路径来读取对应文件中的图的数据，以此来构建，进而调用遍历算法函数来对图进行遍历，如果文件不存在或路径不正确，程序将会报告错误并终止；

3、 本程序读取的文件的格式是.txt文件，其中存储的

数据组成如下:

第一行:M N， M是图中结点的个数，N是图中

弧的条数

第二行:D ，D是1或0, 1表示该图是一个有向图，

0表示该图是一个无向图

第三行:M个互不相同的字符，代表每个结点的字

符数据

接下来的N行，每行有2个字母P1、P2，对于有

向图，表示存在一条从P1到P2的有向边；

对于无向图，表示在P1和P2之间存在一条边；

4、 程序中采用的图

计算机系数据结构实验报告（6）

实验目的：

图是应用极为广泛的数据结构，也是这门课程的重点，继续使学生更了解数据结构加操作的程序设计观点。

问题描述：

给出一张某公园的导游图，游客通过终端询问可知： a)从某一景点到另一个景点的最短路径。

b)游客从公园大门进入，选一条最佳路线，使游客可以不重复的游览各景点，最后回到出口。

实验要求：文法是一个四元

1、将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离，选择适当的数据结构。 2、为游客提供图中任意景点相关信息的查询；

3、为游客提供任意两个景点之间的一条最短的简单路径。 4、为游客选择最佳游览路径。

算法分析：

1、设计公园平面图，选择适当的数据结构；

2、设计图的最短路径算法，如果有几条路径长度相同，选择途径景点较少的路径给游客； 3、设计图的深度优先搜索算法，如果有多种路径可选，则选带权路径最短的路线给游客；

实验内容和过程：

源程序：

#include using namespace std; #include

#define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define VRType

//（一）基础篇

//将一个图采用邻接表存储，并在该存储方法上进行深度优先遍历． //程序构思：

//用户键盘输入结点与各条边，再将边转成邻接链表。 //然后对采用邻接表表示的图进行深度优先遍历。 #include #include

#define vertexnum 100 //定义最大可输入的结点个数 typedef struct node //定义图形的顶点结构 {

int vertex; //图中的顶点信息为数字 struct node *next; }Graph;

Graph head[vertexnum]; //邻接表的表头结点 int Visited[vertexnum]; //遍历记录

void Create_l_Graph(int Vertex1,int Vertex2,int no) { //以邻接链表建立图形 Graph *searchP; //结点声明 Graph *New; //新结点声明

New=(Graph *)malloc(sizeof(

习题七 图

一、单项选择题

1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ）

A．G’为G的子图 B．G’为G的连通分量 C．G’为G的极小连通子图且V’=V D．G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（ ）

A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3．以下说法正确的是（ ）

A．连通分量是无向图中的极小连通子图。 B．强连通分量是有向图中的极大强连通子图。

C．在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 D．对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点，则该图一定是完全图。 4．图中有关路径的定义是（ ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 5．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C

《数据结构》实验报告

◎实验题目: 无向图的建立与遍历

◎实验目的：掌握无向图的邻接链表存储，熟悉无向图的广度与深度优先遍历。 ◎实验内容：对一个无向图以邻接链表存储，分别以深度、广度优先非递归遍历输出。 一、需求分析

1.本演示程序中，输入的形式为无向图的邻接链表形式，首先输入该无向图的顶点数和边数，接着输入顶点信息，再输入每个边的顶点对应序号。 2.该无向图以深度、广度优先遍历输出。

3.本程序可以实现无向图的邻接链表存储，并以深度、广度优先非递归遍历输出。 4.程序执行的命令包括：（1）建立一个无向图的邻接链表存储（2）以深度优先遍历输出 （3）以广度优先遍历输出（4）结束 5.测试数据：

a b c d f e

顶点数和边数：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

一、选择题

1、在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 A．1/2 B 1 C 2 D 4

2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A．1/2 B 1 C 2 D 4

3、已知一个图，如图所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（ ）；按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ）；

① A）a，b，e，c，d，f B）a，c，f，e，b，d

C）a，e，b，c，f，d， D）a，e，d，f，c，b

② A）a，b，c，e，d，f B）a，b，c，e，f，d

C）a，e，b，c，f，d， D）a，c，f，d，e，b

4、采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

5、采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ ）。

A．先序遍历 B．中序遍历 C．后序遍历 D．按层遍历

6、具有n 个结点的连通图至少有（ ）条边。

A． n－1 B． n C． n（n－1）/