课程设计3树图及其应用.docx
《课程设计3树图及其应用.docx》由会员分享，可在线阅读，更多相关《课程设计3树图及其应用.docx（23页珍藏版）》请在冰点文库上搜索。
课程设计3树图及其应用
题目：
树、图及其应用日期：
2012年5月11日星期五
姓名：
学号：
1、二叉树的建立和遍历的演示
一．实习目的
1．学会实现二叉树结点结构和对二叉树的基本操作。
2．掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二．问题描述
建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
三．需求分析
1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历。
2.编写程序生成下面所示的二叉树，并采用先序遍历的递归算法对此二叉树进行遍历。
四．概要设计
从键盘输入二叉树的扩展先序序列，建立二叉树的二叉链表存储结构，然后采用递归算法对其进行遍历（先序、中序、后序），并将遍历结果打印输出
五．详细设计（给出算法的伪码描述）
六．测试分析
白盒测试：
查看代码完整性
黑盒测试：
结构是否完整
七．使用说明
八．附录：
测试数据
测试内容
测试结果
输入扩展先序序列:
L（G（W,C（X,M））.J（H））
正确
先序遍历为：
LGWCXMJH
正确
中序遍历为：
WGXCMLHJ
正确
后序遍历为：
WXMCGHJL
正确
九．附C语言实现源码
#include
#include
#include
#defineMaxNode100
typedefintElemType;
typedefstructnode
{
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;
case'）':
top--;break;
case',':
k=2;break;
default:
p=（BTNode*）malloc（sizeof（BTNode））;
p->data=ch;
p->lchild=p->rchild=NULL;
if（b==NULL）
b=p;
else
{
switch（k）
{
case1:
St[top]->lchild=p;break;
case2:
St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
voidPreOrder（BTNode*b）//前序遍历
{
if（b!
=NULL）
{
printf（"%c",b->data）;
PreOrder（b->lchild）;
PreOrder（b->rchild）;
}
}
voidInOrder（BTNode*b）//中序遍历
{
BTNode*p,*stack[MaxNode];
inttop=0;
if（b==NULL）return;
p=b;
while（!
（p==NULL&&top==0））
{
while（p!
=NULL）
{
if（topelse{printf（"栈溢出"）;return;}
p=p->lchild;
}
if（top<=0）return;
else{
top--;
p=stack[top];
printf（"%c",p->data）;
p=p->rchild;}
}
}
voidLaOrder（BTNode*b）//后序遍历
{
if（b!
=NULL）
{
LaOrder（b->lchild）;
LaOrder（b->rchild）;
printf（"%c",b->data）;
}
}
voidmain（）
{
intnumber;
BTNode*b=NULL;
cout<<"1创建树"<cout<<"2先序遍历树"<cout<<"3中序遍历树"<cout<<"4后序遍历树"<cout<<"5退出"<cout<<"请您的选择"<cin>>number;
while（number!
=5）
{
if（number==1）
{
charstr[100];
printf（"请输入：
"）;
scanf（"%s",&str）;
CreateTree（b,str）;
printf（"树创建成功!
\n"）;
}
elseif（number==2）
{
if（b==NULL）
{
printf（"对不起，您还没有创建树!
\n"）;
}
else
{
printf（"先序遍历树为:
"）;
PreOrder（b）;
printf（"\n"）;
printf（"\n"）;
}
}
elseif（number==3）
{
if（b==NULL）
{
printf（"对不起，您还没有创建树!
\n"）;
}
else
{
printf（"中序遍历树为:
"）;
InOrder（b）;
printf（"\n"）;
printf（"\n"）;
}
}
elseif（number==4）
{
if（b==NULL）
{
printf（"对不起，您还没有创建树!
\n"）;
}
else
{
printf（"后序遍历树为:
"）;
LaOrder（b）;
printf（"\n"）;
printf（"\n"）;
}
}
printf（"请您选择:
\n"）;//1:
创建树;2:
先序遍历;3:
中序遍历;4:
后序遍历;5:
退出
scanf（"%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如图：
九．附C语言实现源码
#defineMAX_VERTEX_NUM2000
#include
#include
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//队列
{
vnode*data;
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{
for（p=g.vertices[i].firstarc;p;p=p->nextarc）
printf（"%c,%c",g.vertices[i].data,g.vertices[p->adjvex].data）;
printf（"\n"）;
}
printf（"\n请输入要进行遍历的模式:
\n\n1.深度优先遍历并生成树\n2.广度优先遍历并生成树\n\n"）;
fflush（stdin）;
scanf（"%d",&j）;
if（j==1）//深度优先遍历
{
for（i=0;iif（!
g.vertices[i].mark）//如果没有遍历过
{
if（!
（tree1=（csnode*）malloc（sizeof（csnode））））exit
（1）;
tree1->data=g.vertices+i;
tree1->firstchild=tree1->nextsibling=NULL;
if（!
tree2）tree2=tree1;
else
tree2->nextsibling=tree1;
tree2=tree1;
dfstree（&g,i,tree1）;
}
printf（"恭喜你深度优先遍历操作完成，请进行下一步操作\n1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"）;
}
elseif（j==2）//广度优先遍历并生成树
{
for（i=0;ig.vertices[i].mark=0;
for（i=0;iif（!
g.vertices[i].mark）//如果没有遍历过
{
if（!
（tree1=（csnode*）malloc（sizeof（csnode））））exit
（1）;
tree1->data=g.vertices+i;
tree1->firstchild=tree1->nextsibling=NULL;
if（!
tree2）tree2=tree1;
else
tree2->nextsibling=tree1;
tree2=tree1;
bfstree（&g,i,tree1）;
}
printf（"恭喜你广度优先遍历操作完成，请进行下一步操作\n1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"）;
}
else
{
printf（"输入错误,程序退出\n"）;
exit
（1）;
}
while（flag1）
{
fflush（stdin）;
scanf（"%d",&j）;
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（"cls"）;
printf（"树的图为\n"）;
for（n=0;n<23;n++）
{
for（m=39;m>=0;m--）
if（b[m][n]=='#'）
printf（""）;
else
printf（"%c",b[m][n]）;
printf（"\n"）;
}
}
elseif（j==3）
preordertraverse3（tree1）;
else
exit
（1）;
flag2=1;
printf（"是否还需要进行其他操作？
（y/n）\n"）;
while（flag2）
{
fflush（stdin）;
scanf（"%c",&ch）;
if（ch=='n'||ch=='N'）
exit
（1）;
elseif（ch=='y'||ch=='Y'）
{flag2=0;system（"cls"）;printf（"1.输出树\n2.输出树图\n3.输出树的边集\n其他输入为退出本程序\n"）;}
else
printf（"输入错误请重新输入\n"）;
}
}
}
voidinitalgraph（algraph*g）//初始化图
{
inti;
for（i=0;ig->vertices[i].firstarc=NULL;
}
intlocatvex（algraph*g,charch）
{
inti;
for（i=0;ivexnum;i++）
if（g->vertices[i].data==ch）
return（i）;
return（-1）;
}
voidbulidalgraph（algraph*g）
{
inti,m,n;
charch1,ch2;
arcnode*p,*q;
initalgraph（g）;
printf（"请输入顶点数\n"）;
fflush（stdin）;
scanf（"%d",&g->vexnum）;
printf（"请输入弧数\n"）;
fflush（stdin）;
scanf（"%d",&g->arcnum）;
printf（"请输入各个顶点的值\n"）;
for（i=0;ivexnum;i++）
{
fflush（stdin）;
scanf（"%c",&g->vertices[i].data）;
g->vertices[i].mark=0;
}
for（i=0;iarcnum;i++）
{
printf（"请输入第%d条弧\n",i+1）;
fflush（stdin）;
ch1=getchar（）;
fflush（stdin）;
ch2=getchar（）;
if（（m=locatvex（g,ch1））<0）exit
（1）;
if（（n=locatvex（g,ch2））<0）exit
（1）;
if（!
（p=（arcnode*）malloc（sizeof（arcnode））））exit
（1）;
p->adjvex=n;
p->nextarc=NULL;
if（!
g->vertices[m].firstarc）g->vertices[m].firstarc=p;
else
{
for（q=g->vertices[m].firstarc;q->nextarc;q=q->nextarc）;
q->nextarc=p;
}
if（!
（p=（arcnode*）malloc（sizeof（arcnode））））exit
（1）;
p->adjvex=m;
p->nextarc=NULL;
if（!
g->vertices[n].firstarc）g->vertices[n].firstarc=p;
else
{
for（q=g->vertices[n].firstarc;q->nextarc;q=q->nextarc）;
q->nextarc=p;
}
}
}
voiddfstree（algraph*g,inti,csnode*t）//深度优先遍历生成树
{
csnode*tree1,*tree2;
arcnode*p;
if（!
g->vertices[i].mark）//如果这个结点没有遍历过
{
g->vertices[i].mark=1;//记录以防重新遍历
for（p=g->vertices[i].firstarc;p;p=p->nextarc）//对该节点的邻接点进行遍历
{
if（!
g->vertices[p->adjvex].mark）
{
if（!
（tree1=（csnode*）malloc（sizeof（csnode））））exit
（1）;//开辟空间
tree1->data=g->vertices+p->adjvex;
tree1->firstchild=tree1->nextsibling=NULL;
if（!
t->firstchild）//如果这是第一次那么应该是t的孩子
t->firstchild=tree1;
else//应该是tree2的兄弟
tree2->nextsibling=tree1;
tree2=tree1;//以便下一次操作
dfstree（g,p->adjvex,tree2）;//递归
}
}
}
}
voidpreordertraverse（csnode*t）
{
if（t）
{
printf（"%c",t->data->data）;
preordertraverse（t->firstchild）;
preordertraverse（t->nextsibling）;
}
else
printf（"0"）;
}
intpreordertraverse1（inti,chara[40][23],csnode*t,intj）//将二叉树的图对应输入到数组中
{
intk,m,n;
m=n=0;
if（t）
{
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->data;
return（m+n+1）;
}
else
return（0）;
}
voidpreordertraverse3（csnode*t）//输出树的边集
{
if（t）
{
if（t->firstchild）
{
printf（"（%c,%c）",t->data->data,t->firstchild->data->data）;
preordertraverse3（t->firstchild）;
}
if（t->nextsibling）
{
printf（"（%c,%c）",t->data->data,t->nextsibling->data->data）;
preordertraverse3（t->nextsibling）;
}
}
}
voidbfstree（algraph*g,inti,csnode*t）//深度优先遍历生成树
{
arcnode*p;
queue*qu1,*qu2,*head,*trail;
csnode*tree1,*tree2;
intj;
tree1=tree2=NULL;trail=qu1=qu2=head=NULL;p=NULL;
if（!
（head=（queue*）malloc（sizeof（queue））））exit
（1）;
if（!
（trail=（queue*）malloc（sizeof（queue））））exit
（1）;
trail->data=g->vertices+i;
trail->next=NULL;
head->next=trail;
if（trail->data->firstarc）
{
while（head!
=trail）
{
head->next->data->mark=1;
p=head->next->data->firstarc;
j=0;
while（p）
{
if（!
g->vertices[p->adjvex].mark）//如果这个结点未遍历过
{
j=1;
g->vertices[p->adjvex].mark=1;
if（!
（tree1=（csnode*）malloc（sizeof（csnode））））exit
（1）;
if（!
（qu1=（queue*）malloc（sizeof（qu
升级会员 