数据结构设计性实验报告(广工)

《数据结构设计性实验报告(广工)》由会员分享，可在线阅读，更多相关《数据结构设计性实验报告(广工)（29页珍藏版）》请在装配图网上搜索。

1、设计性实验报告项目名称 抽象数据类型的实现 题 目 图ADT的实现 学 院_ 计算机学院_ 专 业_ 软件工程 年级班别_2007级4班 _ 学 号 3107006904 学生姓名_吴国豪_ _辅导教师_刘添添_成 绩_ _2009年6月预 习 报 告1. 题目 采用字符类型为元素类型和邻接表为存储结构，实现抽象数据类型LinGraph。ADT LinGraph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R=VR VR=|v,wV且P（V，W），表示从v，到w的弧， 谓词P（V，W）定义了弧的意义或信息基本操作P：CreateGraph（&G，V，VR）；初始条

2、件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G);初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u);初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G,v,value)；初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjVex(G,v);初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G

3、中没有邻接顶点，则返回空。NextAdjVex(G，v，w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。InsertVex(&G,v);初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图中增添新顶点v。DeleteVex（&G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及相关的弧。InsertArc(&G,v,w)；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧若G是无向的，则还增添对称弧。DeleteArc（&G,v,w）;初始条件：图G存在

4、，v和w是G中两个顶点。操作结果：在G中删除弧若G是无向的，则还删除对称弧。DFSTraverst（G，Visite（）；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。BFSTraverse(G，Visit（）)初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit（）失败，则操作失败。ADT LinGraph2 存储结构定义 #include #include #include

5、#define MAX_NUM 20 /定义顶点数的最大值int visitedMAX_NUM=0; /记录顶点是否已被访问typedef char VertexType; /顶点数据类型为chartypedef struct ArcNode int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 int info; /该弧的权值; ArcNode;typedef struct VNode VertexType data; /顶点信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjLi

6、stMAX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /图当前顶点数和弧数 int kind; /图的种类标志 LinGraph;typedef struct /定义循环队列 int * base; /队列的基地址 int front; /队列头 int rear; /队列尾 Queue;int CreateGraph(void); /创建图int DeGraph(void); /删除图int LocateVex(VertexType u); /定位VertexType GetVex(int v); /取数void PutV

7、ex(int v,VertexType value); /赋值int FirstAdjVex(int v); /第一个邻接点int NextAdjVex(int v,int w); /相对于w的下一个邻接点int InsertVex(VertexType v); /增添v顶点int DeleteVex(VertexType v);/删除顶点vint InsertArc(VertexType v,VertexType w); /插入弧vwint DeleteArc(VertexType v,VertexType w);/删除弧vwvoid Visit(int v); /访问函数int DFS(i

8、nt v); /从顶点v开始深度遍历int DFSTraverse(void);/深度遍历Queue InitQueue(Queue *q);/初始化队列int Push(Queue *q,int v);/入队列int Pop(Queue *q);/出队列int Emptyqueue(Queue *q);/判断队列是否为空int BFSTraverse(void);/广度遍历3. 算法设计 #include GRAPH_.h LinGraph G; /把图定义为全局变量void page_title(char *menu_item) /定义控制版面显示名称函数 system(cls); /清屏

9、 void return_confirm(void) /定义返回函数 printf(n按任意键返回n); getch(); int CreateGraph(void) /创建图 int i,j,n; VertexType a,b; ArcNode *p,*q; page_title(GreateGraph); printf(请选择图的类型：1.有向图 2.有向网 3.无向图 4.无向网n);/选择 /图形类型 scanf( %d,&G.kind); while(G.kind!=1&G.kind!=2&G.kind!=3&G.kind!=4)/对非法输入进/行处理 printf(请重新选择图的类

10、型：1.有向图 2.有向网 3.无向图 4.无向网n); getchar(); scanf( %d,&G.kind); printf(请输入顶点数n); /输入顶点数 while(scanf( %d,&i)!=1) printf(数据错误，请重新输入顶点数); getchar(); printf(请输入弧数n); if(G.kind=3|G.kind=4) while(scanf( %d,&j)!=1|ji*(i-1)/2) /确定顶点数之后对弧 /数进行限制 printf(数据不合理，请重新输入); getchar(); else while(scanf( %d,&j)!=1|ji*(i-1

11、) printf(数据不合理，请重新输入); getchar(); G.vexnum=i; /把顶点数和弧数赋给图 G.arcnum=j; printf(请输入各个顶点元素n); /输入各个顶点的值只限于字母 for(i=0;ia|az) printf(顶点只限字母，请重新输入); getchar(); scanf(%c,&a); G.verticesi.data=a; G.verticesi.firstarc=NULL; printf(请输入图的各条弧的信息n); /输入各条弧 for(i=1;ia|az|ab|bz|a=b) printf(数据不合理，请重新输入); fflush(stdi

12、n); scanf( %c%c,&a,&b); printf(n); j=LocateVex(a); /调用了函数LocateVex来定位弧头位置 n=LocateVex(b); /调用了函数LocateVex来定位弧尾位置 p=(ArcNode*)malloc(sizeof(ArcNode); if(p=NULL)return 0; p-nextarc=G.verticesj.firstarc; /插入弧结点 G.verticesj.firstarc=p; p-adjvex=n; if(G.kind=2|G.kind=4) /如果是有向图则输入权值 printf(请输入这条弧的权值); wh

13、ile(scanf( %d,&p-info)!=1) printf(数据不合理，请重新输入); getchar(); if(G.kind=3|G.kind=4) /无向图则添加对称的弧 q=(ArcNode*)malloc(sizeof(ArcNode); if(q=NULL)return 0; q-nextarc=G.verticesn.firstarc; G.verticesn.firstarc=q; q-adjvex=j; if(G.kind=4)q-info=p-info; return 1; /创建成功返回1 int DeGraph(void) /删除图 int i; char a;

14、 /初始化各个变量 ArcNode *p,*q; page_title(DeGraph); /刷屏 printf(确定要删除当前图，Y/N?); /确定用户要删除图 scanf( %c,&a); if(a=y|a=Y) for(i=0;inextarc; while(q!=NULL) free(p); p=q; q=q-nextarc; /while free(p); /if G.vexnum=G.arcnum=0; /把弧数和顶点数置为0； printf(已经删除图); return_confirm(); return 1; int LocateVex(VertexType u) /定位顶点

15、 int i; for(i=0;iG.vexnum;i+) if(G.verticesi.data=u) /判断哪个顶点与给定点相等返回i； return i; return -1; VertexType GetVex(int v) /取值 if(0=v&vG.vexnum) return G.verticesv.data;/ 所给定位置存在则返回值，否则输出错误信息 else printf(所求顶点不在图中); void PutVex(int v,VertexType value) /赋值 if(0=v&vadjvex); return -1; int NextAdjVex(int v,in

16、t w) /相对于w的下一个顶点 ArcNode *p; if(v=0&vnextarc) if(p-adjvex=w&p-nextarc!=NULL) p=p-nextarc; return (p-adjvex); return -1; int InsertVex(VertexType v) /插入顶点 int i; i=G.vexnum; if(i+1MAX_NUM) return 0; G.verticesi.data=v; G.verticesi.firstarc=NULL; G.vexnum+; /插入成功后顶点数加1； return 1; int DeleteVex(VertexT

17、ype v) /删除顶点 int i,j; ArcNode *p,*q; i=LocateVex(v); /定位顶点 if(i!=-1) /判断顶点是否存在 p=q=G.verticesi.firstarc; /删除该顶点链表上的值 while(q!=NULL) q=p-nextarc; free(p); p=q; G.arcnum-; /每删除一条弧数减一 G.vexnum-; /顶点数减一 for(j=i;jG.vexnum;j+) /把删除顶点后面的顶点向前移1位 G.verticesj.data=G.verticesj+1.data; G.verticesj.firstarc=G.ve

18、rticesj+1.firstarc; for(j=0;jadjvex=i) G.verticesj.firstarc=p-nextarc; free(p); p=NULL; if(G.kind=1|G.kind=2)/有向图的话就要边数减一 G.arcnum-; /if while(p!=NULL) if(p-adjvexi) -(p-adjvex); else if(p-adjvex=i) q-nextarc=p-nextarc; free(p); if(G.kind=1|G.kind=2) G.arcnum-; /有向图的话弧数减1； break; /if q=p; p=p-nextar

19、c; /while /for return 1; /if /Delete int InsertArc(VertexType v,VertexType w) /插入弧 int i,j,n; ArcNode *p,*q; p=(ArcNode*)malloc(sizeof(ArcNode); if(!p) return 0; i=LocateVex(v); j=LocateVex(w); p-info=0; p-adjvex=j; if(G.kind=2|G.kind=4) /如果是网则增添弧的权值 printf(请输入权值n); scanf( %d,&n); p-info=n; p-nextar

20、c=G.verticesi.firstarc; G.verticesi.firstarc=p; if(G.kind=3|G.kind=4) /如果是无向图则增添对称的弧 q=(ArcNode*)malloc(sizeof(ArcNode); if(!q) return 0; q-adjvex=i; q-info=p-info; q-nextarc=G.verticesj.firstarc; G.verticesj.firstarc=q; return 1; int DeleteArc(VertexType v,VertexType w) /删除弧 int i,j; ArcNode *p,*q;

21、 i=LocateVex(v); j=LocateVex(w); p=G.verticesi.firstarc;/寻找vw边； if(p!=NULL) if(p-adjvex=j) G.verticesi.firstarc=p-nextarc; free(p); G.arcnum-; p=NULL; for(q=p;p!=NULL;q=p,p=p-nextarc) if(p-adjvex=j) q-nextarc=p-nextarc; free(p); G.arcnum-; p=q=NULL; break; if(G.kind=3|G.kind=4)/判断是否为无向图，是的话就寻找VW; p=

22、G.verticesj.firstarc; if(p=NULL) return 0; if(p-adjvex=i) G.verticesj.firstarc=p-nextarc; free(p); G.arcnum-; p=NULL; for(q=p;p!=NULL;q=p,p=p-nextarc) if(p-adjvex=i) q-nextarc=p-nextarc; free(p); p=q=NULL; break; /ifelse printf(找不到所求边); return 0; return 1; void Visit(int v)/访问函数 VertexType a; a=G.ve

23、rticesv.data; printf(%c,a); int DFS(int v) /从顶点v开始深度遍历 ArcNode *p; int i; visitedv=1; Visit(v); printf(-); p=G.verticesv.firstarc; for(;p;p=p-nextarc) i=p-adjvex; if(!visitedi) DFS(i); return 1; int DFSTraverse(void) /深度遍历 int i; page_title(DFSTraverse); for(i=0;iG.vexnum;i+) visitedi=0; /把Visited数组

24、初始化为0； for(i=0;ibase=(int*)malloc(MAX_NUM*sizeof(int); if(!q-base)return; q-front=q-rear=0; int Push(Queue *q,int v) if(q-rear+1)%MAX_NUM=q-front) return 0; q-baseq-rear=v; q-rear=(q-rear)+1%MAX_NUM; return 1; int Pop(Queue *q) int v; if(q-front=q-rear) return -1; v=q-baseq-front; q-front=(q-front+1

25、)%MAX_NUM; return v; int Emptyqueue(Queue *q) if(q-front=q-rear) return 1; return 0; int BFSTraverse(void) /广度遍历 ArcNode *p; int i,j; Queue q; InitQueue(&q); page_title(BFSTraverse); for(j=0;jG.vexnum;j+) visitedj=0; for(j=0;j); Push(&q,j); while(!Emptyqueue(&q) i=Pop(&q); for(p=G.verticesi.firstarc

26、;p!=NULL;p=p-nextarc) if(!visitedp-adjvex) visitedp-adjvex=1; Visit(p-adjvex); printf(-); Push(&q,p-adjvex); /if /while /if printf(end);return 1;/BFSint main(void) /主函数 int a,i,j; VertexType b,v; menu: system(cls); printf(*n); printf(*请选择操作*n); printf(*a.创建图 *n); printf(*b.删除图*n); printf(*c.定位顶点*n);

27、 printf(*d.取值*n); printf(*e.对图顶点赋值*n); printf(*f.取顶点的第一邻接点*n); printf(*g.取顶点下一个邻接点*n); printf(*h.增添顶点*n); printf(*i.删除顶点*n); printf(*j.增添弧*n); printf(*k.删除弧*n); printf(*l.深度优先遍历图*n); printf(*m.广度优先遍历图*n); printf(*q.退出*n); printf(*n); switch(getch() case a: i=CreateGraph(); if(i) /判断是否创建成功 printf(图已创

28、建完成); else printf(图创建失败); return_confirm(); break; case b: DeGraph(); break; case c: page_title(LocateVex); printf(输入你要定位的顶点值(字母); scanf( %c,&b); /用户输入定位的顶点 i=LocateVex(b); /调用LocateVex； if(i=-1) /判断定位是否成功 printf(找不到所求顶点); else printf(%d,i); return_confirm(); break; case d: page_title(GetVex); print

29、f(输入你要求的值在图中的位置); scanf( %d,&i); /用户输入要求值的顶点在图/中位置 b=GetVex(i); /调用GetVex printf(%c,b); return_confirm(); break; case e: page_title(PutVex); printf(输入需要赋值的顶点的位置); while(scanf( %d,&i)!=1) getchar(); printf(请输入合理数据); printf(输入要赋的值); scanf( %c,&b); PutVex(i,b); return_confirm(); break; case f: page_tit

30、le(FirstAdjVex); printf(输入顶点(字母); scanf( %c,&b); i=LocateVex(b); /把用户输入的顶点化为位置 j=FirstAdjVex(i); if(j!=-1) b=GetVex(j); printf(%c,b); else printf(该顶点无邻接点); return_confirm(); break; case g: page_title(NextAdjVex); printf(分别输入中心顶点和第一个邻接点(空格隔开); scanf( %c %c,&b,&v); i=LocateVex(b); j=LocateVex(v); i=Ne

31、xtAdjVex(i,j); if(i!=-1) b=GetVex(i); printf(%c,b); else printf(已没有下一个邻接点); return_confirm(); break; case h: page_title(InsertVex); printf(输入要插入的顶点值); scanf( %c,&b); i=InsertVex(b); if(i) printf(插入成功); else printf(顶点已达到限制数量); return_confirm(); break; case i: page_title(DeleteVex); printf(输入要删除的顶点的值)

32、; scanf( %c,&b); DeleteVex(b); return_confirm(); break; case j: page_title(InsertArc); printf(请输入要插入弧); scanf( %c%c,&b,&v); InsertArc(b,v); return_confirm(); break; case k: page_title(DeleteArc); printf(分别输入要删除弧); scanf( %c%c,&b,&v); DeleteArc(b,v); return_confirm(); break; case l: DFSTraverse(); re

33、turn_confirm(); break; case m: BFSTraverse(); return_confirm(); break; case q: return 0; default:break; /switch goto menu; 4 测试 错误处理：对于非法输入运行如下图：对于例子一：a b c d d e e f f g g hb f d e h g f h g a c a定位： 取值： 第一个邻接点： 下一个邻接点： 由于按插入方式的原因所以最后插入的顶点就是第一邻接点即把顺序从后看来（例如：a的第一邻接点就是h）所以数据正确！深度遍历： 广度遍历： 例子二为有向图：a b

34、 c d e e f fb e d a b f c d3 4 5 2 3 4 6 7深度遍历为： 跟着增添边ed后深度遍历为：删除ed删除弧fd后为饿删除顶点a后为：5 调试分析例一主要测试程序的出错处理，需要说明的是当确定了顶点数为n时，弧数就不能大于根例二测试了程序的删除添加功能，由于插入方式的原因例子中是按输入的顺序，所以从后面看来出现第一次的就是它的第一个邻接点。据测试的结果就开始修改，主要是增加出错处理，慢慢发现添加的出错处理差不多是原来代码的三分之一，一开始觉得很烦，但再次测试中发现有了出错处理自己输入变得轻松。原来调试可以锻炼我的编程能力，让我想问题想得更加周到，更加严谨。 6

35、时间复杂度的分析 函数时间复杂度备注 CreateGraphO（n）DeGraphO(n+e)e为弧数LocateVexO(n/2)GetVexO(1)PutVexO(1)FirstAdjVexO(1)NextAdjVexO（e/2）InsertVexO（1）DeleteVexO(3/2n+e)时间花费在移动和找相关弧InsertArcO（1）DeleteArcO（e/2）DFSTraverseO(n+e)BFSTraverseO(n+e)7思考与小结这个图的ADT实现是我学了数据结构后做的第一个程序，遇到的困难较多，由于我用c语言来做，而C语言里面没有引用，所以必须要用指针来实现，完成后发现

36、程序中把图G设为全局变量虽然比用指针方便却浪费了很多空间，并且用起来不灵活，全局变量要到程序结束后才释放。在做int DeleteVex这个函数时，忽略了删除该顶点后的处理，必须把删除的顶点的后面元素向前移，但移动后元素的位置也会发生变化，所以要把各弧指向的顶点位置作一些修改。在测试过程中发现很多遗落问题，其中大多数是一些出错处理，出错处理虽然很烦人，但它却在你输入的时候起到很大作用，就连我在测试的时候都会出现输入错误，更何况用户，所以出错处理还蛮重要的。这让我更好的熟悉C语言还把数据结构上的知识活用起来。还有体会最深的是计划的工作非常重要，一个好的计划可以让你少走很多弯路省下时间。而一个函数的结构更加重要，结构可以引出解题的思路，让你思路清晰。