《数据结构实验报告六 图》由会员分享,可在线阅读,更多相关《数据结构实验报告六 图(15页珍藏版)》请在金锄头文库上搜索。
1、 (本实验项目方案受“教育部人才培养模式创新实验区(X3108005) ”项目资助)实验难度: A B C 序号 学号 姓名 成绩123指导教师 (签名)学期:2010 秋季学期 任课教师: 张德海 实验题目: 图及其应用 姓 名: 申 平 学 号: 20091120185 电子邮件: 完成提交时间: 2010 年 12 月 27 日云南大学软件学院 数据结构实验报告云南大学软件学院 2010 学年 秋季 学期数据结构实验成绩考核表学号: 姓名: 本人承担角色: 评分项目 评分指标 分值 得分1. 实验目的明确 5实验构思(10% ) 2. 实验内容理解透彻、对实验所涉及到的知识点分析到位51
2、. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整,数据结构、算法选择合理 5实验设计(15% )3.算法结构和程序功能模块之间逻辑清晰、有相应的流程图51. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常,测试结果正确 15实验实现(25% )3. 界面友好、易于操作、有较强的容错性51. 内容详实无缺漏,文字流畅、图表清楚5实验报告撰写(10% )2. 实验结果分析客观、详细,实验体会真实可信,对原实验方案的改进和对实验内容的发散性思考51. 个人完成工作量 152. 个人技术水平 10个人工作量(30% )3. 团队合作精神 51. 有一定用户群 5实验运作(10
3、% ) 2. 应用前景分析 5综合得分: (满分 100 分)指导教师: 年 月 日(注:此表在难度为 C 时使用,每个成员一份。 )(下面的内容由学生填写,格式统一为,字体: 楷体, 行距: 固定行距 18,字号: 小四,个人报告按下面每一项的百分比打分。难度 A 满分 70 分,难度 B 满分 90 分)一、 【实验构思(Conceive ) 】(10%)1. 本演示程序中,元素限定为 char 型。2. 演示程序以用户和计算机的对话方式执行,即在计算机终端显示“提示信息“后,由用户在键盘上输入符合演示程序中规则的图的边数,结点数;相应的先序和按层遍历会显示其后。3. 程序执行命令包括:1
4、)根据用户给出的图字符串进行对临接表的先序构建 2)输出构建的临接表4. 测试数据用户输入:abc/d/e/ 结果:DLR:abcde LDR:cbdae LRD:cdbea Ceng:abecd用户输入:ab/cd/e/ 结果:DLR:abcde LDR:bdcae LRD:dcbea Ceng:abecd二、 【实验设计(Design)】(20%)(本部分应包括:抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明,主程序模块与各子程序模块间的调用关系)为实现上述程序功能,需要三个抽象数据类型:队列和图1图的抽象数据类型定义为: ADT Graph 数据对象 V:顶点集 数据关系
5、 R:R=VR VR=|v,wV,表示从 v 到 w 的弧 基本操作: CreateGraph( /构造图 DestroyGraph( /销毁图 LocateVex(G,u); /顶点 u 在图中位置 GetVex(G,v);/取顶点 v 的值 PutVex( /v 的第一个邻接点 NextAdjVex(G,v,w); /v 相对于 w 的下一个邻接点 InsertVex( /增添顶点 v DeleteVex( /删除顶点 v 及相关弧 InsertArc( /增添弧 DeleteArc( /删除弧 DFSTraverse(G,v,Visit(); /深度优先搜索 DFS BFSTravers
6、e(G,v,Visit(); /广度优先搜索 BFS 2.本程序包含四个模块:1)主程序模块:main()初始化一个空队列;(利用 CreateQueue(函数)进入用户输入图顶点数和边数阶段;进入用户输入图的边信息阶段;根据用户输入的图的边信息进行对邻接表的构建(利用 CreateGraph(这个函数)输出邻接表两种遍历输出构建的邻接表(利用 DFS(q,i); BFS(这 2 个函数)2) 图单元模块-实现图抽象数据类型。3) 邻接表 2 种遍历单元模块(包含队列单元模块)4) 图节点结构单元模块-定义图的节点结构。各模块是之间关系如下:主程序模块图单元模块-邻接表 2 种遍历单元模块图节
7、点结构单元模块三、 【实现描述(Implement ) 】(30%)(本部分应包括:抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、函数设计、函数间的调用关系,关键的程序流程图等,给出关键算法的时间复杂度分析。 )1. 元素类型(此程序固定为 char) 结点类型typedef structint *base;int *top;int length;Queue; /队列结点typedef struct arcNodeint locate;struct arcNode *next;arcNode; /边结点typedef struct VNodechar data;arcNode
8、*firstarc;VNode,V20; /顶点结点typedef struct int vexnum,arcnum;char kind;V vex;ALGraph; /图2 图的基本操作: CreatGraph(ALGraph *p) /创建邻接表 DFS(VNode *p,int a); /先序遍历邻接表 BFS( /按层遍历邻接表图所有操作代码:void CreatGraph(ALGraph *p)int i,arc1,arc2;char a,b;arcNode *m,*n;printf(n Please enter the vexnum,the arcnum and the kind
9、of this Graph.n);scanf(%d,scanf(%d,printf(n Please enter the data of the vex.(Must Be Different!)n); for(i=0;ilocate=arc2;m-next=(*p).vexarc1.firstarc;(*p).vexarc1.firstarc=m;n=(arcNode*)malloc(sizeof(arcNode);n-locate=arc1;n-next=(*p).vexarc2.firstarc;(*p).vexarc2.firstarc=n;printf( ok!n); void DFS
10、(VNode *p,int a)int m;VNode *q;VNode *n;n=p;visita=1;printf(%c,n-data);for(m=Firstarc(n);m!=-1;m=Nextarc(n,m) /*for(m=Firstarc(n);m!=-1m= if(visitm=0) Nextarc(n,m)大错特错!*/q=DFS(q,m);void BFS(ALGraph *G)int i;int m;arcNode *q;for(i=0;inext) /*for(q=(*G).vexi.firstarc;q&visitq-locate= if(visitq-locate=
11、0) 0 ;q=q-next)大错特错!*/IniQueue(2. 主函数和其它函数的算法(1)主函数main()CreateStack( /创建空栈CreateQueue( /先为二叉树的根创建空间printf(Please Enter your tree.(such as: ab/cd/e/)n); /提示信息CreateBitree(T); /先序创建二叉链表printf(nThe DLR of this tree is:);Dlr(T, /先序遍历二叉树printf(nThe LDR of this tree is:);Ldr(T, /中序遍历二叉树printf(nThe LRD of
12、 this tree is:);Lrd(T); /后序遍历二叉树printf(nThe CENG of this tree is:);Ceng(T); /按层遍历二叉树getch();(2)构造创建空栈、指针入栈、指针出栈的函数void CreateStack(SqStack *p) /创建空栈p-base=(BiTree*)malloc(100*sizeof(BiTree); /特别注意:p-base 此时所指内容是 BiTree*型指针,即指向 BiTNode 型的指针 (指针指向指针)p-top= p-base;p-stacksize=100;void Push(SqStack *p,B
13、iTNode *m) /指针入栈 注意:传入的是指向 BiTNode 型的指针if(p-top-p-base=p-stacksize) /当空间不够时p-base=(BiTree*)realloc(p-base,(p-stacksize+10)*sizeof(BiTree);p-top=p-base+p-stacksize; p-stacksize+=10;*(p-top)=m; p-top+;void Pop(SqStack *p,BiTree *m) /指针出栈 注意:传入的是指向 BiTree 型的指针(不同于入栈时传入的是 BiTNode 型的指针) 解释:因为想要让某指针 a 指向其
14、他的地址,必须让另一个指针 b 指向这个指针 a,当改变 b 的内容(*b)时,也就改变了指针a。因此此函数中 m 充当了 b 的角色,而 a 是调用此函数时传入的一个指向 BiTNode 型的指针,例如 Pop(&L,&p)中 p 充当了 a 的角色。 *m=*(p-top-1); /此时改变 m 的内容为另一个地址,即使 p 指针指向另一个新地址,达到了目的p-top-;(3)构造创建空队、指针入队、指针出队的函数void CreateQueue(Queue *p) /创建空队p-base=(BiTree*)malloc(100*sizeof(BiTree);p-top= p-base;p-length=0;void PopQ(Queue *q,BiTree *m) /指针出队 注意:传入的是指向 BiTree 型的指针 *m=*(