数据结构实验报告
学 生 实 验 报 告 书
20## — 20## 学年 第 1 学期
第二篇：数据结构实验报告--图
数据结构实验报告
一、实验目的
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的各个未被访问的邻接点，然后分别从这些邻接点出发以此访问他们的邻接点，并使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，直至图中所有已被访问过的顶点的邻接顶点都被访问。若图中仍有未被访问的顶点，选择另一个未被访问的顶点开始，重复上述操作，直到图中所有顶点都被访问。为了使“先被访问的邻接顶点”先于“后被访问的邻接顶点”被访问，在次算法中加入一个队列，queue暂时存储被访问的顶点。
3、搜索简单路径：
利用深度优先搜索，以一个要搜索的起点v顶点为起始点，搜索到要找的终点s结束。为了方便记录路径，此算法中加入栈。访问第v个顶点时将v入栈，以v为顶点进行深度优先搜索，分别将其邻接点vi入栈，若找到s，将s入栈，若没有找到，将vi出栈；对vi+1深度优先搜索，直到找到s，或者图中所有顶点都被访问。
4、搜索最短路径：
搜索最短路径时，要记录被访问的顶点的上一个顶点在图中的位置，所以添加一个上一个顶点的标识single；访问v时将其标识置为-1；搜索从v到s的最短路径，从v开始进行广度优先搜索，直到找到s，将s以及它的之前的顶点依次入栈，直到将v入栈，然后将栈内元素输出。
四、程序代码：
#include
#include
#include
#define MAX_NUM 20
bool visited[MAX_NUM];//访问标致数组
bool found;
int fomer=0;
char v1,v2;
int tfind;
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;
void DFS(ALGraph G,int v);
typedef struct qnode //队列类型
{
int data;
qnode *next;
}qnode,*queueptr;
typedef struct
{
queueptr front;
queueptr rear;
}linkqueue;
typedef struct stack//用栈存储路径
{
char *base;
char *top;
int stacksize;
int size;
}Stack;
Stack s;
int initstack(Stack &s)
{
s.base=(char*)malloc(40*sizeof(char));
s.top=s.base;
s.stacksize=40;
s.size=0;
return 1;
}
int push(Stack &s,char e)
{
*s.top++=e;
s.size++;
return 1;
}
int pop(Stack &s,char &e)
{
if(s.base==s.top)
e=*--s.top;
else {
e=*--s.top;
s.size--;
}
return 1;
}
void printstack(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*s.base);
s.base++;
}
printf("\n");
}
void printstack2(Stack s)
{
while(s.base!=s.top)
{
printf("%c ",*--s.top);
}
printf("\n");
}
int intitqueue(linkqueue &q)//初始化队列
{
q.front=q.rear=(queueptr)malloc(sizeof(qnode));
q.front-＞next=NULL;
return 1;
}
int emptyqueue(linkqueue q)//判断对了是否为空
{
if (q.front==q.rear)
return 1;
return 0;
}
int enqueue(linkqueue &q,int e)//元素入队
{
queueptr p;
p=(queueptr)malloc(sizeof(qnode));
if(!p) exit(0);
p-＞data=e; p-＞next=NULL;
q.rear-＞next=p;
q.rear=p;
return 1;
}
int dequeue(linkqueue &q,int &e)//元素出队
{
queueptr p;
if(q.front==q.rear) return 0;
p=q.front-＞next;
e=p-＞data;
q.front-＞next=p-＞next;
if(q.rear==p) q.rear=q.front;
free(p);
return 1;
}
int LocateVex(ALGraph &G,char v)
{
int i;
for(i=0;i
if(G.vertices[i].data==v)
return i;
return -1;
}
int FirstAdjVex(ALGraph G,int v)
{
if(G.vertices[v].firstarc!=NULL)
return G.vertices[v].firstarc-＞adjvex;
return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
while (G.vertices[v].firstarc-＞nextarc!=NULL)
{
if(G.vertices[v].firstarc-＞adjvex==w)
return G.vertices[v].firstarc-＞nextarc-＞adjvex;
else G.vertices[v].firstarc=G.vertices[v].firstarc-＞nextarc;
}
return -1;
}
void Create(ALGraph &G)
{
int i,j,k;
char v1,v2;
ArcNode *p,*q,*h;
q=NULL;
h=NULL;
printf("输入节点个数和弧的个数:\n");
scanf("%d%d",&G.vexnum,&G.arcnum);
for(i=0;i
{
fflush(stdin);
printf("输入节点名称:\n");
scanf("%c",&G.vertices[i].data);
G.vertices[i].firstarc=NULL;
G.vertices[i].data2=i;
}
for(k=0;k
{
printf("输入弧：a,b:\n");
fflush(stdin);
scanf("%c,%c",&v1,&v2);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
p=(ArcNode*)malloc(sizeof(ArcNode));
p-＞adjvex=j;
p-＞nextarc=NULL;
if (G.vertices[i].firstarc==NULL)
G.vertices[i].firstarc=p;
else
{
q=G.vertices[i].firstarc;
while(q-＞nextarc!=NULL)
q=q-＞nextarc;
q-＞nextarc=p;
}
}
}
void DFSTraverse(ALGraph G)//深度遍历
{
int v;
for(v=0;v
if(!visited[v]) DFS(G,v);
printf("\n");
}
void DFS(ALGraph G,int v)//深度遍历
{
int w;
visited[v]=true;
printf("%c ",G.vertices[v].data);
for(w=FirstAdjVex(G,v);(w＞=0)&&(tfind==0);w=NextAdjVex(G,v,w))
{
if(!visited[w]) DFS(G,w);
}
}
void DFSTree(ALGraph G)//广度遍历
{
int w,u,v;
linkqueue q;
intitqueue(q);
for (v=0;v
{
if (!visited[v])
{
visited[v]=true;
printf("%c ",G.vertices[v].data);
enqueue(q,v);
}
while (!emptyqueue(q))
{
dequeue(q,u);
for (w=FirstAdjVex(G,u);w＞0;w=NextAdjVex(G,u,w))
if (!visited[w])
{
visited[w]=true;
printf("%c ",G.vertices[w].data);
if(w＞0)
enqueue(q,w);
}
}
}
printf("\n");
}
void DFS2(ALGraph G,int v)//用深度遍历算法实现搜索简单路径
{
int w;
char e;
visited[v]=true;
push(s,G.vertices[v].data);
for(w=FirstAdjVex(G,v);(w＞=0)&&(!found);w=NextAdjVex(G,v,w))
{
if(G.vertices[w].data==v2)
{
found=true;
push(s,G.vertices[w].data);
}
else if(!visited[w]) DFS2(G,w);
}
if(!found) pop(s,e);
}
void Simplepath(ALGraph G)//搜索简单路径
{
printf("输入要搜索路径的两点：\n");
fflush(stdin);
scanf("%c",&v1);
fflush(stdin);
scanf("%c",&v2);
DFS2(G,LocateVex(G,v1));
if (!found)
{
printf("can not found zhe path!\n");
}
else printstack(s);
}
void DFSTree2(ALGraph G,int v)//用广度优先求最短路径
{
int w,u;
linkqueue q;
intitqueue(q);
if (!visited[v])
{
visited[v]=true;
G.vertices[v].sngle=-1;
enqueue(q,v);
}
while (!emptyqueue(q))
{
dequeue(q,u);
for (w=FirstAdjVex(G,u);(w＞0)&&(!found);w=NextAdjVex(G,u,w))
if (!visited[w])
{
visited[w]=true;
G.vertices[w].sngle=u;
if(w＞0)
enqueue(q,w);
if(G.vertices[w].data==v2)
{
found=true;
while (G.vertices[w].sngle!=-1)
{
push(s,G.vertices[w].data);
w=G.vertices[w].sngle;
}
}
}
}
printf("\n");
}
void shortcut(ALGraph G)//搜索最短路径
{
printf("输入要搜索路径的两点：\n");
fflush(stdin);
scanf("%c",&v1);
fflush(stdin);
scanf("%c",&v2);
DFSTree2(G,LocateVex(G,v1));
push(s,v1);
printstack2(s);
printf("\n");
}
void main()
{
int v;
ALGraph G;
found=false;
initstack(s);
Create(G);
while(1)
{
for(v=0;v
{
visited[v]=false;
G.vertices[v].sngle=-2;
}
tfind=0;
system("cls");
printf("---------------------\n");
printf("1、深度优先遍历\n");
printf("2、广度优先遍历\n");
printf("3、搜索简单路径\n");
printf("4、搜索最短路径\n");
printf("---------------------\n");
switch (getch())
{
case'1':DFSTraverse(G);break;
case'2': DFSTree(G);break;
case'3':Simplepath(G);break;
case'4':shortcut(G);break;
case'0':exit(0);
}
system("pause");
}
}
五、运行结果：
1、深度优先搜索：
2、广度优先搜索：
3、简单路径：
4、最短路径：
-
数据结构实验报告
实验报告实验课程：数据结构实验项目：实验专业：计算机科学与技术姓名：**学号：***指导教师：**实验时间：20**-12-7重庆…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
数据结构实验———图实验报告
数据结构实验报告目的要求掌握图的存储思想及其存储实现掌握图的深度广度优先遍历算法思想及其程序实现掌握图的常见应用算法的思想及其程序…
-
数据结构实验报告格式
数据结构实验报告格式实验11顺序表的基本操作一实验目的1掌握使用VC上机调试线性表的基本方法2掌握线性表的基本操作插入删除查找等运…
-
数据结构实验报告全集
数据结构实验报告全集实验一线性表基本操作和简单程序1实验目的1掌握使用VisualC60上机调试程序的基本方法2掌握线性表的基本操…
-
数据结构实验报告-静态查找表中的查找
数据结构实验实验一静态查找表中的查找一、实验目的：1、理解静态查找表的概念2、掌握顺序查找和折半查找算法及其实现方法3、理解顺序查…
-
数据结构上机实验报告
实验一线性表的基本操作实验目的学习掌握线性表的顺序存储结构链式存储结构的设计与操作对顺序表建立插入删除的基本操作对单链表建立插入删…
-
数据结构-实验8查找的算法
81实现顺序查找的算法一实验目的1熟悉掌握各种查找方法深刻理解各种查找算法及其执行的过程2学会分析各种查找算法的性能二实验内容81…
- 数据结构图实验报告
-
焦作数据结构实验报告
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
-
数据结构实验报告之排序(终极版)
数据结构实验报告实验四排序一需求分析一实验目的1掌握插入排序算法直接插入希尔排序2掌握交换排序算法冒泡排序快速排序3掌握选择排序算…