天大数据结构_实验作业四_图

天大数据结构_实验作业四_图

ID:14190326

大小:66.50 KB

页数:5页

时间:2018-07-26

天大数据结构_实验作业四_图_第1页
天大数据结构_实验作业四_图_第2页
天大数据结构_实验作业四_图_第3页
天大数据结构_实验作业四_图_第4页
天大数据结构_实验作业四_图_第5页
资源描述:

《天大数据结构_实验作业四_图》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、实验作业四:图1.试扩充深度优先搜索算法,在遍历图的过程中建立生成森林的左子女-右兄弟链表。(提示:在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前,建立子女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。)编写实习报告要求:一、需求分析二、概要设计1.抽象数据类型2.算法三、详细设计程序代码(注释)四、调试分析调试过程中所做的工作,时间复杂度等五、测试结果输入数据和输出数据示例六、说明(如果有)编程语言:C语言或C++语言实习报告提交方式:下次上机前,将实习报告(.doc)和源程序(.cpp)压缩成一个rar文件,文件名称

2、为学号_班级_姓名_第几次作业。例如:3010216155_六班_张三_第四次作业.rar。实习报告作为本课程的平时成绩。抄袭、雷同,双方均为0分。需求分析题目需要建立一个图,再根据图的深度遍历的方法,建立一个左子女-右兄弟的森林链表。二、概要设计1.抽象数据类型typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型#defineVER_MAX20typedefstructtree{//树结点链表数据类型chardata;//顶点的数据域structtree*lchild,*rchild;//左右链

3、接}tree;typedefstructnode{//边结点intdest;//目标顶点下标EdgeDatacost;//边上的权值structnode*link;//下一边链接指针}EdgeNode;typedefstruct{//顶点结点VertexDatadata;//顶点数据域EdgeNode*firstAdj;//边链表头指针}VertexNode;typedefstruct{//图的邻接表VertexNodeVexList[VER_MAX];//邻接表intn,e;//图中当前的顶点个数与边数}AdjGraph;2.算法(1).创建一个有向图。v

4、oidCreateGraph(AdjGraph&G){inti,tail,head,weight;cout<<"请输入有向图顶点数和边数:";cin>>G.n>>G.e;//输入顶点个数和边数cout<<"请按顶点下标从小到大的顺序依次输入顶点数据:";for(i=0;i>G.VexList[i].data;//输入顶点信息G.VexList[i].firstAdj=NULL;}for(i=0;i>tail>>head>>weight;EdgeNo

5、de*p=newEdgeNode;p->dest=head;p->cost=weight;p->link=G.VexList[tail].firstAdj;G.VexList[tail].firstAdj=p;}}(2).扩充的深度优先搜索算法。voidDFS(AdjGraphG,int&v,intvisited[],tree*g){intw,first=1;EdgeNode*q;tree*m;cout<

6、t[v].firstAdj->dest;q=G.VexList[v].firstAdj;while(visited[w]==0){if(first==1){m=newtree;m->data=G.VexList[w].data;m->lchild=NULL;m->rchild=NULL;g->lchild=m;g=m;first=0;}else{m=newtree;m->data=G.VexList[w].data;m->lchild=NULL;m->rchild=NULL;g->rchild=m;g=m;}DFS(G,w,visited,g);if(q->

7、link!=NULL){q=q->link;w=q->dest;}}}}(3).树的中序遍历。voidprint_tree(tree*p){if(p!=NULL){print_tree(p->lchild);cout<data<<'';print_tree(p->rchild);}}三、详细设计intmain(){intx;AdjGraphT;tree*t;CreateGraph(T);int*visited=newint[T.n];for(x=0;x

8、>x;t=newtree;t->data=T.Vex

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。