课程设计3树图及其应用Word文档格式.docx
- 文档编号:8168239
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:23
- 大小:433.58KB
课程设计3树图及其应用Word文档格式.docx
《课程设计3树图及其应用Word文档格式.docx》由会员分享,可在线阅读,更多相关《课程设计3树图及其应用Word文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
ElemTypedata;
structnode*lchild;
structnode*rchild;
}BTNode;
voidCreateTree(BTNode*&
b,char*str)//建立二叉树
BTNode*St[100];
BTNode*p=NULL;
inttop=-1,k,j=0;
charch;
b=NULL;
ch=str[j];
while(ch!
='
\0'
)
{
switch(ch)
case'
('
:
top++;
St[top]=p;
k=1;
break;
)'
top--;
'
k=2;
default:
p=(BTNode*)malloc(sizeof(BTNode));
p->
data=ch;
lchild=p->
rchild=NULL;
if(b==NULL)
b=p;
else
switch(k)
case1:
St[top]->
lchild=p;
case2:
rchild=p;
}
j++;
}
voidPreOrder(BTNode*b)//前序遍历
if(b!
=NULL)
printf("
%c"
b->
data);
PreOrder(b->
lchild);
rchild);
voidInOrder(BTNode*b)//中序遍历
BTNode*p,*stack[MaxNode];
inttop=0;
if(b==NULL)return;
p=b;
while(!
(p==NULL&
&
top==0))
while(p!
if(top<
MaxNode-1){stack[top]=p;
else{printf("
栈溢出"
);
return;
p=p->
lchild;
=0)return;
else{
top--;
p=stack[top];
%c"
p->
rchild;
voidLaOrder(BTNode*b)//后序遍历
LaOrder(b->
voidmain()
intnumber;
BTNode*b=NULL;
cout<
<
"
1创建树"
endl;
2先序遍历树"
3中序遍历树"
4后序遍历树"
5退出"
endl<
请您的选择"
cin>
>
number;
while(number!
=5)
if(number==1)
charstr[100];
请输入:
scanf("
%s"
&
str);
CreateTree(b,str);
树创建成功!
\n"
elseif(number==2)
对不起,您还没有创建树!
先序遍历树为:
PreOrder(b);
elseif(number==3)
中序遍历树为:
InOrder(b);
elseif(number==4)
后序遍历树为:
LaOrder(b);
请您选择:
\n"
//1:
创建树;
2:
先序遍历;
3:
中序遍历;
4:
后序遍历;
5:
退出
%d"
number);
十.附程序运行结果截图
创建树:
先序遍历结果:
中序遍历结果:
后序遍历结果:
2、图遍历的演示
学会以图的遍历操作为基础的,试写一个程序,演示无向图的遍历操作
很多涉及图上操作的算法都是以图的遍历操作为基础的。
试写一个程序,演示无向图的遍历操作,要求以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。
1.以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。
2.每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。
通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制。
注意,生成树的边是有向边,端点顺序不能颠倒。
3.
(1)建立无向图G的邻接表表示。
按照用户输入顶点数,弧数.各边(弧尾,弧头)
(2)输出图中边的表示。
用(A,B)表示
(3)实现无向图的深度优先搜索遍历。
实现无向图的广度优先搜索遍历,使用辅助队列q以存储已经被访问的路径长度为1,2,```的顶点,并且访问标志数组visited,实现对图的遍历。
六.详细设计(给出算法的伪码描述)
测试数据:
输入图的顶点数和弧数:
格式:
顶点数,弧数;
输入图的顶点数:
6;
输入图的弧数:
9;
接着输入各顶点:
1*2*3*4*5*6(*代表“回车键”);
接着输入各条弧(边):
1*2*1*3*1*6*2*3*3*4*3*5*3*6*4*5*5*6(*代表“回车键”);
顶点数和弧数固定好后,必须按所对应的边输入顶点到顶点的边名。
输入图的顶点数:
6个,弧数:
9条,各顶点为1、2、3、4、5、6,各边为:
12,13,16,23,34,35,36,45,56如图:
#defineMAX_VERTEX_NUM2000
#include<
stdlib.h>
typedefstructarcnode//弧
intadjvex;
structarcnode*nextarc;
intinfo;
}arcnode;
typedefstructvnode//结点
chardata;
arcnode*firstarc;
intmark;
}vnode,adjlist[MAX_VERTEX_NUM];
typedefstruct//图
adjlistvertices;
intvexnum,arcnum;
}algraph;
typedefstructcsnode//树
vnode*data;
structcsnode*firstchild,*nextsibling;
}csnode;
typedefstructqueue//队列
structqueue*next;
}queue;
//队列
main()
voidbulidalgraph(algraph*g);
//创建图
voiddfstree(algraph*g,inti,csnode*t);
//深度优先遍历生成树
voidbfstree(algraph*g,inti,csnode*t);
//广度优先遍历生成树
voidpreordertraverse(csnode*t);
//树的遍历
intpreordertraverse1(inti,chara[40][23],csnode*t,intj);
//将二叉树的图对应输入到数组中
voidpreordertraverse3(csnode*t);
//输出树的边集
algraphg;
arcnode*p;
csnode*tree1,*tree2;
inti,j,m,n,flag1=1,flag2=1;
charb[40][23],ch;
//留作输出树的图
tree1=tree2=NULL;
bulidalgraph(&
g);
system("
cls"
for(i=0;
i<
g.vexnum;
i++)//输出创建完成后的结果
for(p=g.vertices[i].firstarc;
p;
p=p->
nextarc)
%c,%c"
g.vertices[i].data,g.vertices[p->
adjvex].data);
printf("
\n请输入要进行遍历的模式:
\n\n1.深度优先遍历并生成树\n2.广度优先遍历并生成树\n\n"
fflush(stdin);
scanf("
j);
if(j==1)//深度优先遍历
for(i=0;
i++)//遍历所有结点以防此图有多个连通分量
if(!
g.vertices[i].mark)//如果没有遍历过
(tree1=(csnode*)malloc(sizeof(csnode))))exit
(1);
tree1->
data=g.vertices+i;
firstchild=tree1->
nextsibling=NULL;
tree2)tree2=tree1;
tree2->
nextsibling=tree1;
tree2=tree1;
dfstree(&
g,i,tree1);
恭喜你深度优先遍历操作完成,请进行下一步操作\n1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"
elseif(j==2)//广度优先遍历并生成树
i++)
g.vertices[i].mark=0;
{
bfstree(&
}
恭喜你广度优先遍历操作完成,请进行下一步操作\n1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"
else
输入错误,程序退出\n"
exit
(1);
while(flag1)
fflush(stdin);
if(j==1)
preordertraverse(tree1);
elseif(j==2)
for(m=0;
m<
40;
m++)
for(n=0;
n<
23;
n++)
b[m][n]='
#'
;
preordertraverse1(0,b,tree1,0);
system("
树的图为\n"
for(m=39;
m>
=0;
m--)
if(b[m][n]=='
"
b[m][n]);
elseif(j==3)
preordertraverse3(tree1);
flag2=1;
是否还需要进行其他操作?
(y/n)\n"
while(flag2)
ch);
if(ch=='
n'
||ch=='
N'
elseif(ch=='
y'
Y'
{flag2=0;
1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"
输入错误请重新输入\n"
voidinitalgraph(algraph*g)//初始化图
inti;
MAX_VERTEX_NUM;
g->
vertices[i].firstarc=NULL;
intlocatvex(algraph*g,charch)
g->
vexnum;
if(g->
vertices[i].data==ch)
return(i);
return(-1);
voidbulidalgraph(algraph*g)
inti,m,n;
charch1,ch2;
arcnode*p,*q;
initalgraph(g);
请输入顶点数\n"
vexnum);
请输入弧数\n"
arcnum);
请输入各个顶点的值\n"
vertices[i].data);
vertices[i].mark=0;
arcnum;
请输入第%d条弧\n"
i+1);
ch1=getchar();
ch2=getchar();
if((m=locatvex(g,ch1))<
0)exit
(1);
if((n=locatvex(g,ch2))<
(p=(arcnode*)malloc(sizeof(arcnode))))exit
(1);
adjvex=n;
nextarc=NULL;
vertices[m].firstarc)g->
vertices[m].firstarc=p;
for(q=g->
vertices[m].firstarc;
q->
nextarc;
q=q->
nextarc);
q->
nextarc=p;
adjvex=m;
vertices[n].firstarc)g->
vertices[n].firstarc=p;
vertices[n].firstarc;
voiddfstree(algraph*g,inti,csnode*t)//深度优先遍历生成树
if(!
vertices[i].mark)//如果这个结点没有遍历过
vertices[i].mark=1;
//记录以防重新遍历
for(p=g->
vertices[i].firstarc;
nextarc)//对该节点的邻接点进行遍历
vertices[p->
adjvex].mark)
//开辟空间
data=g->
vertices+p->
adjvex;
t->
firstchild)//如果这是第一次那么应该是t的孩子
t->
firstchild=tree1;
else//应该是tree2的兄弟
//以便下一次操作
dfstree(g,p->
adjvex,tree2);
//递归
voidpreordertraverse(csnode*t)
if(t)
t->
data->
preordertraverse(t->
firstchild);
nextsibling);
0"
intpreordertraverse1(inti,chara[40][23],csnode*t,intj)//将二叉树的图对应输入到数组中
intk,m,n;
m=n=0;
m=preordertraverse1(i+1,a,t->
nextsibling,j);
k=m+j;
n=preordertraverse1(i+1,a,t->
firstchild,k+1);
a[k][i]=t->
data;
return(m+n+1);
return(0);
voidpreordertraverse3(csnode*t)//输出树的边集
if(t->
firstchild)
(%c,%c)"
data,t->
firstchild->
preordertraverse3(t->
nextsibling)
nextsibling->
voidbfstree(algraph*g,inti,csnode*t)//深度优先遍历生成树
queue*qu1,*qu2,*head,*trail;
intj;
trail=qu1=qu2=head=NULL;
p=NULL;
(head=(queue*)malloc(sizeof(queue))))exit
(1);
(trail=(queue*)malloc(sizeof(queue))))exit
(1);
trail->
vertices+i;
next=NULL;
head->
next=trail;
if(trail->
firstarc)
while(head!
=trail)
head->
next->
mark=1;
p=head->
firstarc;
j=0;
while(p)
adjvex].mark)//如果这个结点未遍历过
j=1;
adjvex].mark=1;
(qu1=(queue*)malloc(sizeof(qu
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计 及其 应用