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

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

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

2、告(.doc)和源程序(.cpp)压缩成一个rar文件，文件名称为学号_班级_姓名_第几次作业。例如：3010216155_六班_张三_第四次作业.rar。实习报告作为本课程的平时成绩。抄袭、雷同，双方均为0分。需求分析题目需要建立一个图，再根据图的深度遍历的方法，建立一个左子女-右兄弟的森林链表。二、概要设计1.抽象数据类型typedefcharVertexData;//顶点数据类型typedefintEdgeData;//边上权值类型#defineVER_MAX20typedefstruct

3、tree{//树结点链表数据类型chardata;//顶点的数据域structtree*lchild,*rchild;//左右链接}tree;typedefstructnode{//边结点intdest;//目标顶点下标EdgeDatacost;//边上的权值structnode*link;//下一边链接指针}EdgeNode;typedefstruct{//顶点结点VertexDatadata;//顶点数据域EdgeNode*firstAdj;//边链表头指针}VertexNode;typed

4、efstruct{//图的邻接表VertexNodeVexList[VER_MAX];//邻接表intn,e;//图中当前的顶点个数与边数}AdjGraph;2.算法（1）.创建一个有向图。voidCreateGraph(AdjGraph&G){inti,tail,head,weight;cout<<"请输入有向图顶点数和边数：";cin>>G.n>>G.e;//输入顶点个数和边数cout<<"请按顶点下标从小到大的顺序依次输入顶点数据：";for(i=0;i>G.V

5、exList[i].data;//输入顶点信息G.VexList[i].firstAdj=NULL;}for(i=0;i>tail>>head>>weight;EdgeNode*p=newEdgeNode;p->dest=head;p->cost=weight;p->link=G.VexList[tail].firstAdj;G.VexList[tail].firstAdj=p;}}（2）.扩充的深度优先搜索算法

6、。voidDFS(AdjGraphG,int&v,intvisited[],tree*g){intw,first=1;EdgeNode*q;tree*m;cout<dest;q=G.VexList[v].firstAdj;while(visited[w]==0){if(first==1){m=newtree;m-

7、>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->link!=NULL){q=q->link;w=q->dest;}}}}（3）.树的中序遍历。voidprint_t

8、ree(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>x;t=newtree;t->data=T.Vex