数据结构实验报告六 图.doc

云南大学软件学院 数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助） 实验难度： A B C 序号学号姓名成绩123指导教师 （签名）学期：2010秋季学期 任课教师: 张德海 实验题目: 图及其应用 姓 名: 申 平 学 号: 20091120185 电子邮件: 完成提交时间： 2010 年 12 月 27 日云南大学软件学院2010学年 秋季 学期数据结构实验成绩考核表学号： 姓名： 本人承担角色： 评分项目评分指标分值得分实验构思（10%）1. 实验目的明确52. 实验内容理解透彻、对实验所涉及到的知识点分析到位5实验设计（15%）1. 有对基本数据结构的抽象数据类型定义52. 实验方案设计完整，数据结构、算法选择合理 53.算法结构和程序功能模块之间逻辑清晰、有相应的流程图5实验实现（25%）1. 代码编写规范、风格统一、注释清楚易读 52. 程序运行正常，测试结果正确153. 界面友好、易于操作、有较强的容错性5实验报告撰写（10%）1. 内容详实无缺漏，文字流畅、图表清楚52. 实验结果分析客观、详细，实验体会真实可信，对原实验方案的改进和对实验内容的发散性思考5个人工作量（30%）1. 个人完成工作量152. 个人技术水平103. 团队合作精神5实验运作（10%）1. 有一定用户群52. 应用前景分析5综合得分： （满分100分）指导教师： 年 月 日（注：此表在难度为C时使用，每个成员一份。）（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%)1. 本演示程序中，元素限定为char型。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端显示“提示信息“后，由用户在键盘上输入符合演示程序中规则的图的边数，结点数；相应的先序和按层遍历会显示其后。3. 程序执行命令包括：1）根据用户给出的图字符串进行对临接表的先序构建 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图的抽象数据类型定义为：n ADT Graph n 数据对象V：顶点集n 数据关系R：R=VR n VR=|v,wV,表示从v到w的弧n 基本操作：n CreateGraph(&G,V,VR); /构造图n DestroyGraph(&G); /销毁图n LocateVex(G,u); /顶点u在图中位置n GetVex(G,v)；/取顶点v的值n PutVex(&G,v,value); /顶点v赋值n FirstAdjVex(G,v); /v的第一个邻接点n NextAdjVex(G,v,w); /v相对于w的下一个邻接点n InsertVex(&G,v); /增添顶点vn DeleteVex(&G,v); /删除顶点v及相关弧n InsertArc(&G,v,w); /增添弧n DeleteArc(&G,v,w); /删除弧n DFSTraverse(G,v,Visit(); /深度优先搜索DFSn BFSTraverse(G,v,Visit(); /广度优先搜索BFSn 2.本程序包含四个模块：1）主程序模块：main()初始化一个空队列；（利用CreateQueue(&Q);函数）进入用户输入图顶点数和边数阶段；进入用户输入图的边信息阶段；根据用户输入的图的边信息进行对邻接表的构建（利用CreateGraph(&G);这个函数）输出邻接表两种遍历输出构建的邻接表（利用DFS(q,i); BFS(&G);这2个函数）2) 图单元模块-实现图抽象数据类型。3) 邻接表2种遍历单元模块（包含队列单元模块）4) 图节点结构单元模块-定义图的节点结构。各模块是之间关系如下：主程序模块图单元模块-邻接表2种遍历单元模块图节点结构单元模块三、【实现描述（Implement）】(30%)（本部分应包括：抽象数据类型具体实现的函数原型说明、 关键操作实现的伪码算法、 函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。）1. 元素类型（此程序固定为char） 结点类型typedef struct int *base; int *top; int length;Queue; /队列结点typedef struct arcNode int locate; struct arcNode *next;arcNode; /边结点typedef struct VNode char data; arcNode *firstarc;VNode,V20; /顶点结点typedef struct int vexnum,arcnum; char kind; V vex;ALGraph; /图2图的基本操作： n CreatGraph(ALGraph *p) /创建邻接表n DFS(VNode *p,int a); /先序遍历邻接表n BFS(&G); /按层遍历邻接表图所有操作代码：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 of this Graph.n); scanf(%d,&(*p).vexnum); scanf(%d,&(*p).arcnum); printf(n Please enter the data of the vex.(Must Be Different!)n); for(i=0;i(*p).vexnum;i+) (*p).vexi.data=getche(); (*p).vexi.firstarc=NULL; printf(nn Please enter the arc of this Graph,such as ac.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(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!=-1&visitm=0;m= if(visitm=0) Nextarc(n,m)大错特错！*/ q=&(G.vexm); 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=0) 0 ;q=q-next)大错特错！*/ IniQueue(&Q,q-locate); 2. 主函数和其它函数的算法（1）主函数main() CreateStack(&L); /创建空栈 CreateQueue(&Q); /创建空队列 T=(BiTNode*)malloc(sizeof(BiTNode); /先为二叉树的根创建空间 printf(Please Enter your tree.(such as: ab/cd/e/)n); /提示信息 CreateBitree(T); /先序创建二叉链表 printf(nThe DLR of this tree is:); Dlr(T,&L); /先序遍历二叉树 printf(nThe LDR of this tree is:); Ldr(T,&L); /中序遍历二叉树 printf(nThe LRD of 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,BiTNode *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指向其他的地址，必须让另一个指针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=*(q-base); q-base+; q-length-;void IniQueue(Queue *q,BiTNode *p) /指针入队注意：传入的是指向BiLNode型的指针 if(p-data!=#) /指针为空时就不必入队了，没必要再去访问空指针的内容了 *(q-top)=p; q-top+; q-length+; 函数的调用关系：Main CreateStack CreateQueue CreateBitree Dlr Ldr Lrd CengPush Pop IniQueue PopQ四、【测试结果（Testing）】(10%)（本部分应包括：对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）1 进入演示程序后即显示文本方式的用户界面：2 进入主函数命令后，即提示键入您欲创建的二叉树的字符串，结束符为回车，输出结果测试结果:执行命令Please Enter your tree.(such as: ab/cd/e/) 键入abc/d/e/ 输出：DLR:abcde LDR:cbdae LRD:cdbea Ceng:abecd 键入ab/cd/e/ 输出：DLR:abcde LDR:bdcae LRD:dcbea Ceng:abecd键入abd/ef/g/c/h/输出: DLR:abdefgch LDR:dbfgeach LRD:dgfebhca Ceng:abcdehfg五、【实验总结】(10%)（本部分应包括：自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；对所完成实验的经验总结、心得）开始的时候把T=(BiTNode*)malloc(sizeof(BiTNode)写在了CreateBitree函数中，发现结果总是不对，所有的元素都没被指针指上，也就是指针发生了错误，没有指向希望要指的内容。于是我将开空间T=(BiTNode*)malloc(sizeof(BiTNode)写在了调用CreateBitree函数之前，这样T就指向了希望指的内容。开始Pop函数是这样写的void Pop(SqStack *p,BiLNode *m) m=*(p-top-1); p-top-;应用是这样的：Pop(&L,p)。结果总不对，即指针仍然指向