计算机科学与工程系
实验（四） 实验名称 图的深度优先与广度优先遍历
软件环境
Windows98/2000, VC++6.0或turbo C
硬件环境
PⅡ以上微型计算机
实验目的
理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。
实验内容（应包括实验题目、实验要求、实验任务等）
图的遍历
利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。
计算机科学与工程系
2 实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）
实验步骤及算法描述和流程：
1. 无向图的邻接矩阵存储结构
1.1 创建无向图的边的结构，由该边的信息指针和组成该边的两个顶点的位置以及指向与两个顶点相连的下一条边构成
1.2 创建无向图的顶点结构，由顶点所存储的信息和指向依附该顶点的边的指针构成
1.3 创建无向图的结构，由顶点结构数组和无向图当前的顶点数和边数构成
1.4 利用单链队列作为无向图的邻接表存储结构
2. 采用邻接表存储结构，构造无向图
2.1 输入无向图的相关信息：顶点数，边数，再输入顶点信息构造表节点链表
2.2 输入顶点间的关系，构造出无向图的邻接表
3. 深度优先遍历无向图
3.1 编写函数DFS，从顶点v出发，对v所在的连通分量进行深度优先搜索，
并利用递归，输出结点信息并对未访问的结点调用DFS函数
3.2 编写函数DFSTraverse对无向图做深度优先搜索，对已访问的结点标记，对尚未访问过得结点调用DFS
4. 广度优先遍历无向图
使用辅助队列Q和访问标志数组visite对无向图进行非递归广度优先搜索
4.1 用for循环给顶点访问标志数组置初值0
少年易学老难成，一寸光阴不可轻 - 百度文库
1 数据结构实验报告
姓名： 班级：
学号：
日期：2015年9月27日
上机环境：win7系统，mircosoft visual++
1．实验名称：线性表
2． 实验题目
编写一个程序algo2-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char）并在此基础上设计一个主程序完成如下功能：
(1) 初始化顺序表L；
(2) 依次采用尾插入法插入a,b,c,d,e元素；
(3) 输出顺序表L；
(4) 输出顺序表L的长度；
(5) 判断顺序表L是否为空；
(6) 输出顺序表L的第3个元素；
(7) 输出元素a的位置；
(8) 在第4个元素位置上插入f元素；
(9) 输出顺序表L；
(10) 删除L的第3个元素；
(11) 输出顺序表L；
(12) 释放顺序表。
3． 实验程序
#include
#include
#define MaxSize 50 少年易学老难成，一寸光阴不可轻 - 百度文库
2 typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList *&L)
{
L= (SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L->length=0; //置空线性表长度为0
}
void DestroyList(SqList *L)
{
free(L);
}
bool ListEmpty(SqList *L)
{
return(L->length==0);
}
int ListLength(SqList *L)
{
return(L->length);
} 少年易学老难成，一寸光阴不可轻 - 百度文库
本科实验报告
课程名称： 数据结构
实验项目： 树形结构
实验地点： 迎西校区逸夫楼302
专业班级：软件1109 学号： 2011004872
学生姓名： 栗永春
指导教师： 牛之贤
年 月 日
树形结构
一、实验目的和要求
目的与要求
二、实验内容和原理
三、主要仪器设备
四、操作方法与实验步骤
列出调试通过的源程序。
习题1：
/*********************************************************************
*1． 编写递归算法，计算二叉树中叶子结点的数目。 *
*********************************************************************/
#include
#include
int count = 0;
struct node{
char info;
struct node *llink,*rlink;
};
typedef struct node NODE;
NODE *creat(){
char x;
NODE *p;
scanf("%c",&x);
printf("%c",x);
if(x!='.'){
p=(NODE *)malloc(sizeof(NODE));
p->info=x;
p->llink=creat();
p->rlink=creat();
}
else
p=NULL;
return p;
}
void run(NODE *t){
if(t){
数学与计算科学学院
实 验 报 告
实验项目名称 线性表的链式表示
所属课程名称 数据结构（C语言版）
实 验 类 型 验证型实验
实 验 日 期 2011年10月28日
班 级 信计1001班
学 号 201053100127
姓 名 徐超
成 绩
1
一、实验概述：
【实验目的】
1.掌握线性链表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素以外，每个元素总存在唯一一个直接前驱元素；除最后一个元素以外，每个元素总存在唯一一个直接后继元素。
2.线性链表的特点：逻辑结构上相邻物理结构上不相邻；是一种随机的存储结构。
3.通过上机实验验证顺序表的算法正确性，了解算法与程序的区别。
【实验原理】
线性链表的存储结构：用一组任意的存储单元存储线性表的数据元素.
【实验环境】
VC++6.0
2 二、实验内容：
【实验方案】
首先建立一个带表头节点的单链线性表，然后调用输入函数给每个节点赋值，然后调用插入和删除函数插入和删除元素。
【实验过程】（实验步骤、记录、数据、分析）
在输入窗口输入：
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
Status GetElem_L(LinkList L,int i,ElemType&e)
