《数据结构实验报告六 图》由会员分享，可在线阅读，更多相关《数据结构实验报告六 图（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=*(
