杭电数据结构实习报告3

《杭电数据结构实习报告3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实习报告题目：图的遍历演示班级：姓名：学号：口期：一、需求分析1、以邻接多重链表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分別输出每种遍历下的结点访问序列和相应生成树的边集。2、设图的结点不超过30个，每个结点用一个编号表示。通过输入图的全部边输入一个阁，每个边为一个数对，可以对边的输入顺序作出某种限制。二、详细设计typedefcharVertexType;typedefintVisitIf,InfoType;intvisited[MAX_VERTEX_NUM];typedefs

2、tructEBox//边的信息{Visitlfmark;//标记该边是否被搜索过intivexjvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;//分别指向依附这两个顶点的下一条边}EBox;typedefstructVexBox//点的信息{VertexTypedata[DATA_LEN];//点的名字EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstructAMLGraph{VexBoxadjmulist[MAX_VERTEX_NUM

3、];intvexnum,edgenum;///?:和边的数目}AMLGraph;typedefstructQueueNode//队列结点{intdata;structQueueNode*next;}*QueueLink,QueueNode;typedefstructQueue//队列{QueueLinkhead;QueueLinktail;}Queue;voidInitQueue(Queue&Q)//构造并初始化一个队列{Q.head=(QueueNode*)malloc(sizeof(QueueNode));Q.

4、head->next=NULL;Q.tail=Q.head;}voidEnQueue(Queue&Q,inte)//入队{QueueNode*p;p=(QueueNode*)malloc(sizeof(QueueNode));p-〉data=e;Q.tail->next=p;p->next=NULL;Q.tail=p;}intQueueEmpty(QueueQ)//队列是否力空，是返回1，不是返回0{if(Q.head==Q.tail)return1;elsereturn0;}voidDeQueue(Queue&Q

5、，int&e)//出队列{if(QueueEmpty(Q)){printf(HERRORn);exit(l);}QueueNode^q;q=Q.head->next;e=q-〉data;Q.head-〉next=q-〉next;if(Q.head->next==NULL)Q.tail=Q.head;free(q);}intLocateVex(AMLGraphQVertexTypeu[])//由点的名字找到点在邻接多重表中vexbox里的下标，找不到返回-1{intk=-1;for(inti=O;i

6、um;i++){if(strcmp(G.adjmulist[i].data,u)==O){k=i;break;}}returnk;}voidCreateGraph(AMLGraph&G)//建立阎{inti，j，k;charv1[DATA_LEN],v2[DATA_LEN];EBox*p;printf("请输入阁中点的数目：");scanf(H%d",&G.vexnum);printff请输入图中边的数目：H);scanf(’'％d’’，&G.edgenum);printf("请依次输入％(1个城市名：

7、’’，G.vexnum);for(i=0;i

8、cateVex(Qv2);if(i〉=O&&j〉=O){p=(EBox*)malloc(sizeof(EBox));p-〉ivex=i;//边的链接过程//边的链接过程//边的链接过程//边的链接过程p->jvex=j;p->ilink=G.adjmulist[i].firstedge;p->jlink=Gadjmulist[j].firstedge;G.a