课程设计3树图及其应用.docx
- 文档编号:6709241
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:23
- 大小:433.58KB
课程设计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(top else{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;i if(! 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;i g.vertices[i].mark=0; for(i=0;i if(! 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;i g->vertices[i].firstarc=NULL; } intlocatvex(algraph*g,charch) { inti; for(i=0;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;i { fflush(stdin); scanf("%c",&g->vertices[i].data); g->vertices[i].mark=0; } for(i=0;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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 课程设计 及其 应用