第六次数据结构上机实验报告Word格式文档下载.docx
- 文档编号:8580262
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:14
- 大小:42.28KB
第六次数据结构上机实验报告Word格式文档下载.docx
《第六次数据结构上机实验报告Word格式文档下载.docx》由会员分享,可在线阅读,更多相关《第六次数据结构上机实验报告Word格式文档下载.docx(14页珍藏版)》请在冰点文库上搜索。
}MGraph;
//图的邻接矩阵类型
//定义邻接表类型
typedefstructANode//弧的结点结构类型
{
intadjvex;
//弧的重点位置,就是放值的
structANode*nextarc;
//指向下一条弧的指针
//存放弧的信息(权值)
}ArcNode;
typedefstructVnode
intdata;
//邻接表头结点的的类型
ArcNode*firstarc;
//指向第一条弧
}VNode;
typedefVNodeAdjList[max];
//AdjList是邻接表类型,把大表变成几个小的连接到一起
typedefstruct
AdjListadjlist;
//邻接表
intn,e;
//图中顶点数和和边数
}ALGraph;
//图的邻接表类型
intvisited[max];
//全局数组用于判断后面节点是否被访问过
voidDispMat(MGraphg)//输出邻接矩阵
inti,j;
for(i=0;
i<
g.n;
i++)
{
for(j=0;
j<
j++)
if(g.edges[i][j]==0)
printf("
0"
);
elseprintf("
%d"
g.edges[i][j]);
printf("
\n"
}
}
voidMatToList(MGraphg,ALGraph*&
G)//将邻接矩阵g转换为邻接表G
intn=g.n;
//n为顶点数
ArcNode*p;
//弧节点结构的类型
G=(ALGraph*)malloc(sizeof(ALGraph));
for(i=0;
n;
i++)//给大的邻接表中所有头结点的指针域副初值
G->
adjlist[i].firstarc=NULL;
i++)//检查邻接矩阵的每个元素
if(g.edges[i][j]!
=0)
{
p=(ArcNode*)malloc(sizeof(ArcNode));
//新申请一个节点空间,就是后面的一段段小的节点
p->
adjvex=j;
//这是小节点的放值的域,只要他的列值,链式表只要说明节点之间有关系就行,指终点位置
info=g.edges[i][j];
//存放边的权值
nextarc=G->
adjlist[i].firstarc;
//将*p连接到表后
G->
adjlist[i].firstarc=p;
}
G->
e=g.e;
n=g.n;
voidDispAdj(ALGraph*G)//输出邻接表
{inti;
ArcNode*p;
//弧的类型
G->
p=G->
if(p!
=NULL)
printf("
%d:
"
i);
//这是那个大链表的头
while(p!
=NULL)//顺着那个头向下查看
{printf("
%d"
p->
adjvex);
//输出弧的终点
p=p->
nextarc;
}printf("
voidchange(intvisited[],ALGraph*G)//给全局变量visited赋初值
i++)visited[i]=0;
voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式
{inti,j;
intn=G->
i++)
for(j=0;
g.edges[i][j]=0;
p=G->
while(p!
g.edges[i][p->
adjvex]=p->
info;
g.n=n;
g.e=G->
e;
voidDFS(ALGraph*G,intv)//递归深度优先遍历
{ArcNode*p;
//change(visited,G);
visited[v]=1;
//第一个点设为已被访问并输出,接着以他为主进行遍历
%d"
v);
adjlist[v].firstarc;
if(visited[p->
adjvex]==0)
DFS(G,p->
voidBFS(ALGraph*G,intv)//广度优先遍历,一个点先找和其有关的所有节点,在接着按步骤继续
intqueue[max],front=0,rear=0;
//定义循环队列并初始化
intw,i;
visited[i]=0;
//把输入的第v个作为第一个广度遍历的节点,一直这样进行下去
rear=(rear+1)%max;
//要入队了
queue[rear]=v;
//把v入队
while(front!
=rear)//队列不为空的时候
front=(front+1)%max;
//要出队了
w=queue[front];
adjlist[w].firstarc;
//跟前面差不多开始查找与顶点w邻接的第一个顶点了
if(visited[p->
adjvex]==0)//就是当前节点未被访问
{
printf("
visited[p->
adjvex]=1;
rear=(rear+1)%max;
//又要入队了,马上要重复之前的操作了
queue[rear]=p->
adjvex;
}
p=p->
voidmain()
MGraphg;
ALGraph*G;
//没有定义过的邻接表类型加上*
intA[max][6];
printf("
请输入邻接矩阵:
6;
scanf("
%d"
&
A[i][j]);
g.n=6;
g.e=10;
for(i=0;
for(j=0;
g.edges[i][j]=A[i][j];
//这是给邻接矩阵赋值
这是图的邻接矩阵的形式:
"
DispMat(g);
//输出邻接矩阵的函数
G=(ALGraph*)malloc(sizeof(ALGraph));
MatToList(g,G);
这是图的邻接表的形式:
DispAdj(G);
从顶点0开始的深度优先遍历:
DFS(G,0);
从顶点0开始的广度优先遍历:
BFS(G,0);
}
运行结果:
2、
2.拓扑排序;
(1)选择一个入度为0的顶点并输出之;
(2)从网中删除此顶点及所有出边。
循环结束后,若输出的顶点数小于网中的顶点数,则输出“有回路”信息,否则输出的顶点序列就是一种拓扑序列。
iostream>
usingnamespacestd;
#definemaxsize50
structnode
node*next;
};
structgraph
intvexter;
intin;
node*firstedge;
typedefstruct
int*base;
int*top;
intstacksize;
}sqstack;
voidinitstack(sqstack&
S)
S.base=(int*)malloc(sizeof(int));
S.top=S.base;
S.stacksize=maxsize+1;
}
voidcreateadlist(graphinDegree[],intn,inte)//创建邻接链表
inti,k,j;
node*q;
for(i=1;
=n;
inDegree[i].vexter=i;
inDegree[i].in=0;
inDegree[i].firstedge=NULL;
for(k=1;
k<
=e;
k++)
cout<
<
依次输入每一条边(数字):
;
从"
cin>
>
i;
邻接到"
j;
'
/n'
inDegree[j].in++;
q=(node*)malloc(sizeof(structnode));
q->
next=inDegree[i].firstedge;
inDegree[i].firstedge=q;
voidTopoSort(graphinDegree[],intn)
inti,v,count=0;
sqstackS;
node*p;
initstack(S);
if(inDegree[i].in==0)
*S.top++=i;
while(S.top!
=S.base)
v=*--S.top;
v<
/t"
count++;
p=inDegree[v].firstedge;
inDegree[p->
adjvex].in--;
if(inDegree[p->
adjvex].in==0)
*S.top++=p->
p=p->
next;
endl;
if(count<
n)cout<
有回路"
elsecout<
无回路"
voidmain()
graphinDegree[maxsize];
intv,e;
顶点数:
v;
边条数:
createadlist(inDegree,v,e);
拓扑排序序列为:
TopoSort(inDegree,v);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 数据结构 上机 实验 报告