课程设计3树图及其应用Word文档格式.docx

1、 ElemType data; struct node *lchild; struct node *rchild;BTNode;void CreateTree（BTNode *&b,char *str）/建立二叉树 BTNode *St100; BTNode *p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=strj; while（ch!=0） switch（ch） case （:top+;Sttop=p;k=1;break;）top-;,k=2; default:p=（BTNode *）malloc（sizeof（BTNode）; p-data=c

2、h;lchild=p-rchild=NULL; if（b=NULL） b=p; else switch（k） case 1:Sttop-lchild=p; case 2:rchild=p; j+;void PreOrder（BTNode *b）/前序遍历 if（b!=NULL） printf（%c ,b-data）; PreOrder（b-lchild）;rchild）;void InOrder（BTNode *b）/中序遍历 BTNode *p,*stackMaxNode; int top=0; if（b=NULL） return; p=b; while（!（p = NULL & top =

3、 0） while（p! if（toplchild;=0）return; else top-; p=stacktop;%c,p-rchild;void LaOrder（BTNode *b）/后序遍历 LaOrder（b-void main（） int number; BTNode *b=NULL; cout 1 创建树endl; 2 先序遍历树 3 中序遍历树 4 后序遍历树 5 退出endlnumber; while（number!=5） if（number=1） char str100;请输入： scanf（%s,&str）; CreateTree（b,str）;树创建成功!n else

4、if（number=2）对不起，您还没有创建树!先序遍历树为: PreOrder（b）; else if（number=3）中序遍历树为: InOrder（b）; else if（number=4）后序遍历树为: LaOrder（b）;请您选择: n /1:创建树;2:先序遍历;3:中序遍历;4:后序遍历;5:退出%dnumber）;十附程序运行结果截图创建树：先序遍历结果：中序遍历结果：后序遍历结果：2、图遍历的演示学会以图的遍历操作为基础的，试写一个程序，演示无向图的遍历操作很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示无向图的遍历操作，要求以邻接表为存储结构，实现连

5、通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。1. 以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。2. 每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制。注意，生成树的边是有向边，端点顺序不能颠倒。3. （1） 建立无向图G的邻接表表示。按照用户输入顶点数,弧数. 各边（弧尾， 弧头） （2） 输出图中边的表示。用（A,B）表示 （3） 实现无向图的深度优先搜索遍历。实现无向图的广度优先搜索遍历，使用辅助队列q

6、以存储已经被访问的路径长度为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如图：#def

7、ine MAX_VERTEX_NUM 2000#includetypedef struct arcnode/弧int adjvex;struct arcnode *nextarc;int info;arcnode;typedef struct vnode/结点char data;arcnode *firstarc;int mark;vnode,adjlistMAX_VERTEX_NUM;typedef struct/图adjlist vertices;int vexnum,arcnum;algraph;typedef struct csnode/树vnode *data;struct csno

8、de *firstchild,*nextsibling;csnode;typedef struct queue/队列struct queue *next;queue;/队列main（）void bulidalgraph（algraph *g）;/创建图void dfstree（algraph *g,int i,csnode *t）;/深度优先遍历生成树void bfstree（algraph *g,int i,csnode *t）;/广度优先遍历生成树void preordertraverse（csnode *t）;/树的遍历int preordertraverse1（int i,char a

9、4023,csnode *t,int j）;/将二叉树的图对应输入到数组中void preordertraverse3（csnode *t）;/输出树的边集 algraph g;arcnode *p;csnode *tree1,*tree2;int i,j,m,n,flag1=1,flag2=1;char b4023,ch;/留作输出树的图tree1=tree2=NULL;bulidalgraph（&g）;system（clsfor（i=0;inextarc）%c,%c ,g.verticesi.data,g.verticesp-adjvex.data）;printf（n请输入要进行遍历的模式

10、:nn1.深度优先遍历并生成树n2.广度优先遍历并生成树nnfflush（stdin）;scanf（j）;if（j=1）/深度优先遍历 for（i=0;i+）/遍历所有结点以防此图有多个连通分量 if（!g.verticesi.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,

11、i,tree1）;恭喜你深度优先遍历操作完成，请进行下一步操作n1.输出树n2.输出树图n3.输出树的边集n其他输入为退出本程序nelse if（j=2）/广度优先遍历并生成树i+） g.verticesi.mark=0; bfstree（& 恭喜你广度优先遍历操作完成，请进行下一步操作n1.输出树n2.输出树图n3.输出树的边集n其他输入为退出本程序nelse输入错误,程序退出n exit（1）;while（flag1） fflush（stdin）; if（j=1） preordertraverse（tree1）; else if（j=2） for（m=0;m40;m+） for（n=0;n

12、=0;m-） if（bmn= ,bmn）; else if（j=3） preordertraverse3（tree1）; flag2=1;是否还需要进行其他操作？（y/n）n while（flag2）ch）; if（ch=n|ch=N else if（ch=yY flag2=0;1.输出树n2.输出树图n3.输出树的边集n其他输入为退出本程序n输入错误请重新输入nvoid initalgraph（algraph *g）/初始化图int i;MAX_VERTEX_NUM; g-verticesi.firstarc=NULL;int locatvex（algraph *g,char ch）g-ve

13、xnum; if（g-verticesi.data=ch） return（i）; return（-1）;void bulidalgraph（algraph *g）int i,m,n;char ch1,ch2;arcnode *p,*q;initalgraph（g）;请输入顶点数nvexnum）;请输入弧数narcnum）;请输入各个顶点的值nverticesi.data）;verticesi.mark=0;arcnum;请输入第%d条弧n,i+1）; ch1=getchar（）; ch2=getchar（）; if（m=locatvex（g,ch1）0）exit（1）; if（n=locatv

14、ex（g,ch2）verticesm.firstarc=p; for（q=g-verticesm.firstarc;q-nextarc;q=q-nextarc）; q-nextarc=p;adjvex=m;verticesn.firstarc）g-verticesn.firstarc=p;verticesn.firstarc;void dfstree（algraph *g,int i,csnode *t）/深度优先遍历生成树if（!verticesi.mark）/如果这个结点没有遍历过verticesi.mark=1;/记录以防重新遍历 for（p=g-verticesi.firstarc;n

15、extarc）/对该节点的邻接点进行遍历verticesp-adjvex.mark）/开辟空间data=g-vertices+p-adjvex;t-firstchild）/如果这是第一次那么应该是t的孩子 t-firstchild=tree1; else/应该是tree2的兄弟/以便下一次操作 dfstree（g,p-adjvex,tree2）;/递归void preordertraverse（csnode *t）if（t）,t-data- preordertraverse（t-firstchild）;nextsibling）;0int preordertraverse1（int i,char

16、 a4023,csnode *t,int j）/将二叉树的图对应输入到数组中int k,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）; aki=t-data; return（m+n+1）; return（0）;void preordertraverse3（csnode *t）/输出树的边集 if（t-firstchild）（%c,%c） data,t-firstchild- preordertraverse3（t-nextsibl

17、ing）nextsibling-void bfstree（algraph *g,int i,csnode *t）/深度优先遍历生成树queue *qu1,*qu2,*head,*trail;int j;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