偏序关系中特殊元素判定-2013

1、沈阳航空航天大学 课程 设计报告 课程设计名称： 数据结构课程设计 课程设计题目： 偏序关系中特殊兀素判定 院（系）：计算机学院 专业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师: 目 录 1 算法分析1 1.1假设条件1 1.2算法描述1 1.2.1 有向图的存储结构1 1.2.2 求取有联系结点 1 1.2.3 判断结点位置2 2系统设计4 2.1设计说明4 2.2数据结构描述4 2.3 MAIN ()函数5 2.4十字链表建立函数6 2.5求解判断函数9 2.6特殊元素求解函数12 3 系统实现14 3.1错误分析14 3.2实现结论14 参考文献16 附 录(关键部分程序

2、清单) 17 1算法分析 1.1假设条件 偏序关系中特殊元素判定就是对偏序关系中指定子集对应的特殊元素的求 解。该程序首先需要将由特定偏序关系导出的哈斯图输入，然后再将节点子集输 入，由此就可求出对应的特殊元素。但该程序有一些限制，输入的哈斯图不能过 大，结点不能超过二十个；对一些错误输入无法分辨。 1.2算法描述 本次算法是在一个有向图中，有向图代表一个由特定偏序关系导出的哈斯图, 指定一个节点子集，求解子集对应的极大元、极小元、最大元、最小元、上界、 下界、上确界、下确界八种特殊元素。 1.2.1有向图的存储结构 对于输入的有向图，利用十字链表进行存储。 十字链表用顶点结点和弧结点将顶点和

3、弧连接起来。利用顶点结点记录顶点 信息和首条入弧及出弧，利用弧结点记录弧信息和弧头相同及弧尾相同的链域， 如此，将弧和结点连接起来。 1.2.2求取有联系结点 求取有联系结点主要是求取有向图中可到达指定结点的所有结点或指定结点 可到达的所有结点。 求取有向图中可到达指定结点的所有结点时，可设一全局变量整型数组来记 录结点。先求取指定结点的弧尾将其全存入全局变量，然后，不断求取全局变量 中结点的弧尾将其全存入全局变量，直到取完，这样，就可求取有向图中可到达 指定结点的所有结点。 求取有向图中指定结点可到达的所有结点时，也可设一全局变量整型数组来 记录结点。先求取指定结点的弧头将其全存入全局变量，

4、然后，不断求取全局变 量中结点的弧头将其全存入全局变量，直到取完，这样，就可求取有向图中可到 达指定结点的所有结点。 例如：有向图如图1.1所示，求a可到达的所有结点，a、b、c编号分别为0、 1、2,设一整型数组h10，先求取a的弧头将其全存入h10，则h0=1，h1=2， 然后，求取h0也就是b的弧头将其全存入h10，但b的弧头为空，所以h10 没有变化，再求取h1也就是c的弧头将其全存入h10，但c的弧头也为空，所 以h10还是没有变化。因此，a可到达的所有结点为b和c。 图1.1 有向图示意图 1.2.3判断结点位置 判断结点位置主要是判断指定结点可否到达子集所有结点或子集所有结点可

5、否到达指定结点。 判断指定结点可否到达子集所有结点时，首先求取有向图中指定结点可到达 的所有结点，然后与子集所有结点比较，如果子集所有结点都在指定结点可到达 的结点中，贝U指定结点可到达子集所有结点。 判断子集所有结点可否到达指定结点时，首先求取有向图中可到达指定结点 的所有结点，然后与子集所有结点比较，如果子集所有结点都在可到达指定结点 的结点中，贝U子集所有结点可到达指定结点。 例如，有向图如图1.1所示，子集为a,b，判断a可否到达子集所有结点, 首先求取有向图中a可到达的所有结点，求取出来为b,c，然后与子集所有结点 比较，子集中a为其本身，而b在b,c中，所以，a可到达子集所有结点。

6、 2系统设计 2.1设计说明 该程序设计共包括四大模块：主函数模块、十字链表建立模块、求解判断模 块、特殊元素求解模块。主函数中调用了其他所有三个模块，求解判断模块与特 殊元素求解模块都调用了十字链表建立模块中建立的十字链表，特殊元素求解模 块则调用了十字链表建立模块和求解判断模块。函数模块关系如图 2.1所示: 图2.1函数模块关系图 2.2数据结构描述 该函数包含三个结构体，即存储弧、存储顶点和存储图的结构体。其结构体 分别如下所示： 存储弧的结构体，其中包含四个变量tailvex、headvex和指针hlink、tlink， tailvex、headvex分别指示该弧的尾和头顶点的位置，

7、hlink、tlink则分别为弧头相 同和弧尾相同的弧的链域，表示如下： typedef struct ArcBox int tailvex, headvex; struct ArcBox *hlink, *tlink; ArcBox; 存储顶点的结构体，其中包含三个变量data和指针firstin、firstout , data 存储顶点信息，firstin 、firstout贝U分别指向该顶点第一条入弧和出弧，表示 如下： typedef struct VexNode VertexType data; ArcBox *first in, *firstout; VexNode; 存储图的结构

8、体，其中包含三个变量 xlistMAX_VERTEX_NUM和vex num arcnum, xlistMAX_VERTEX_NUM存 储表头向量，vex num arcnum 则存储有向图 的当前顶点数和弧数，表示如下： typedef struct VexNode xlistMAX_VERTEX_NUM; int vex num, arcnum; OLGraph; 2.3 main()函数 功能：求取偏序关系中的特殊元素。 参数含义：G:表示图。 简单工作过程：给定一个有向图，建立十字链表，输入子集信息，计算子集 元素个数，再调用子函数，求解子集对应特殊元素。最后，将子集对应特殊元素 输出

9、。 主函数流程图如图2.2所示。 图2.2 main()函数流程图 2.4十字链表建立函数 功能：建立十字链表。 简单工作过程：将顶点信息和弧信息依次输入，然后，对弧结点赋值并完成 在入弧和出弧链头的插入，建立十字链表。 参数含义：G:表示图。 函数流程图如图 2.3所示。 图2.3十字链表建立函数流程图 2.5求解判断函数 功能：求取该结点的所有弧尾（s为0）或所有弧头（s为0）。 简单工作过程：判断s, s为0,将弧尾依次输入到数组中；s不为0,将弧头 依次输入到数组中。 参数含义：G:表示图；t:该结点位置；s：判断标志；h数组：标记。 函数流程图如图2.4所示。 图2.4 DFS函数流

10、程图 功能：取出子集所有结点可到达该结点的所有结点（S为0）或取出该结点可 到达的所有结点（S不为0）。 简单工作过程：将h数组，x初始化，判断s, s为0,依次对h数组中结点 调用DFS函数存弧尾；s不为0,依次对h数组中结点调用DFS函数存弧头。 参数含义：G:表示图；c：结点名称；s：判断标志；h数组：标记。 函数流程图如图2.5所示。 :开始 将h数组，x初始化 N J s 为 0 调用DFS函 数 Y N 调用DFS函 数 结束 图2.5 quhu函数流程图 功能：判断该结点是否到达子集所有结点（S为0）或判断子集所有结点是否 到达该结点（S不为0）。 简单工作过程：初始化flag数

11、组，判断s，s为0,调用quhu函数，判断若 该结点可到达子集所有结点，返回 1否则返回0； s不为0,调用quhu函数，判 断若子集所有结点可到达该结点，返回 1,否则返回0。 参数含义：G:表示图；c：结点名称；p：存储结点；m :结点个数；s：判 断标志；h数组：标记；flag数组：标记。 函数流程图如图2.6所示。 开始 将i、flag数组全赋为0 1 r F 调用quhu函数，判 断若子集所有结 点 可到达该结点，将对 应flag全置为1 调用quhu函数，判 断若该结点可到达 子集所有结点，将对 应flag全置为1 Y N N im Y 将i 加 1 J N flagi为 0 返回

12、0 返回1 1 T T 结束 图2.6 panduan函数流程图 2.6特殊元素求解函数 特殊元素求解模块主要包含八个函数，分别用来求解八种特殊元素。但由于 这八个函数大同小异，所以，这里就介绍一个函数以代表。 功能：求取子集中的最大元。 简单工作过程：初始化t,依次调用panduan函数判断结点可否到达子集所有 结点，若可以，则输出最大值，若全部不可以，则输出无最大值。 参数含义：G:表示图；p：存储结点；m：结点个数；t :判断标志。 函数流程图如图2.7所示。 3系统实现 3.1错误分析 （1）在读入字符时，字符无法正常读入。经过检查，字符读入时将回车读入 到指定变量中，运行出现错误。通

13、过调整读入顺序，再次运行，程序正常。 （2）某些基础函数无法调用。经过检查，是对库函数忘记引用，导致程序无 法调用某些函数，运行出现错误。通过增加对库函数的引用，再次运行，程序正 常。 （3）出现未知变量，程序无法运行。经过检查，是对函数 pan duan忘记增加 返回值，导致程序运行出现错误。通过增加函数 pan duan的返回值，再次运行， 程序正常。 （4）调用DFS函数时有时正确，有时返回为空导致程序运行出现错误。经 过检查，是对函数quhu忘记增加判断，导致有时调用 DFS函数时产生错误。通 过对函数quhu增加判断，再次运行，程序正常。 （5）程序输出结果与实际不符。经过检查，是对

14、做标记的全局变量没有及时 初始化，致使多次记录，程序输出结果与实际不符。通过对全局变量及时初始化， 再次运行，程序正常。 3.2实现结论 该算法实现了输入一节点子集的信息到代表一个由特定偏序关系导出的哈斯 图的有向图中，求解子集对应的极大元、极小元、最大元、最小元、上界、下界、 上确界、下确界八种特殊元素的功能。例如：输入顶点数和弧数为4和4，依次 输入顶点值为a b c d,依次输入各弧信息为ab ac bd cd输入节点子集信息为bed。 输出为极大元有be，极小元有d，没有最大元，最小元是d，上界是a，下界是d， 上确界是a，下确界是do 参考文献 1 严蔚敏，吴伟民.数据结构（C语言版

15、）M .北京：清华大学出版社，2006 2 戴艳等.零基础学算法M.北京：机械工业出版社，2012 3 左孝凌，李为坚，刘永才.离散数学M.上海：上海科学技术文献出版社 附 录（关键部分程序清单） #i nclude #i nclude #i nclude #defi ne NULL 0 #defi ne MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex; struct ArcBox *hli nk, *tli nk; ArcBox; typedef struct VexNode char data; ArcBox *fi

16、rst in, *firstout; VexNode; typedef struct VexNode xlistMAX_VERTEX_NUM; int vex num, arcnum; OLGraph; int LocateVex(OLGraph G,char v1) int i; for(i=0;iG.vex nu m;i+) if(G.xlisti.data=v1) return i; return NULL; void CreateDG(OLGraph char v1,v2; ArcBox *p; printf(请分别输入顶点数和弧数.n); sca nf(%d,%d, if(G.vex

17、 num=0|G.arc num=0) printf(输入错误.n);exit(0); printf(请依次输入顶点值.n); for(i=0;iG.vex nu m;i+) getchar(); sca nf(”c, if(G.xlisti.data=) printf(输入错误.n);exit(0); G.xlisti.firsti n=NULL; G.xlisti.firstout=NULL; printf(请依次输入各弧信息.n); for(k=0;ktailvex=i;p-headvex=j; p-hli nk=G.xlistj.firsti n;p-tli nk=G.xlisti.f

18、irstout; G.xlistj.first in=G.xlisti.firstout=p; int hMAX_VERTEX_NUM,x; void DFS(OLGraph G,i nt t,i nt s) ArcBox *p; p=(ArcBox*)malloc(sizeof(ArcBox); if(s=0) p=G.xlistt.firsti n; if(h0=-1) h0=p-tailvex; else h+x=p-tailvex; while(p-hli nk!=NULL) p=p-hli nk;h+x=p-tailvex; else p=G.xlistt.firstout; if(

19、h0=-1) h0=p-headvex; else h+x=p-headvex; while(p-t in k!=NULL) p=p-tli nk;h+x=p-headvex; void quhu(OLGraph G,char c,i nt s) int i,t,flag=0; for(i=0;iMAX_VERTEX_NUM;i+) hi=-1; t=LocateVex(G,c); x=0; if(s=0) if(G.xlistt.firsti n) DFS(G,t,s); for(i=0;hi!=-1;i+) if(G.x isthi.firsti n) DFS(G,hi,s); else

20、if(G.xlistt.firstout) DFS(G,t,s); for(i=0;hi!=-1;i+) if(G.x isthi.firstout) DFS(G,hi,s); int pan dua n( OLGraph G,char c,char *p,i nt m,i nt s) int i,j,flagMAX_VERTEX_NUM; for(i=0;im;i+) flagi=0; if(s=0) quhu(G,c,1); else quhu(G,c,0); for(i=0;im;i+) if(c=pi) flagi=1; else for(j=0;hj!=-1;j+) if(Locat

21、eVex(G,pi)=hj) flagi=1; for(i=0;im;i+) if(flagi=0) return 0; return 1; void max(OLGraph G,char *p,i nt m) int i,t; for(i=0;im;i+) t=pa ndua n( G,pi,p,m,0); if(t=1)printf( 最大元是 c.n,pi);break; if(t=0) printf(”没有最大元.n); void mai n() OLGraph G; int i,j,k,m; char pMAX_VERTEX_NUM; CreateDG(G); printf(请输入节

22、点子集信息.n); sca nf(%s,p); i=0; while(pi) i+; m=i; max(G,p,m); 课程设计总结： 通过此次的课程设计，我学会了许多在课堂上学不到的知识。 有一些知识只 有你自己亲身去实践，去发现问题，然后依靠自己解决了问题，你才能真正掌握。 对于有向图的存储创建，本来仅仅只局限于邻接矩阵、邻接表，但通过课设，还 学会了利用十子链表存储创建有向图， 并且，我发现利用十子链表创建的有向图 应用范围更广。在课设过程中，通过翻阅书籍，咨询同学，上网找资料，不但提 高了我的查找能力，而且还提高了自己快速融合各种信息， 并将其转变为自己的 知识的能力。而且，从这次课程设计活动中我认识到了一定要认真对待每一个问 题，因为，很有可能就在一个你不注意的地方导致你失败。 总之，这次课设是自己用心去完成的一项工作， 但，由于本人水平有限能力 有限，此次课程设计还有很多不足，敬请老师谅解！在此次课设中，得到了老师 及同学不少帮助，所以，我在这里要衷心地感谢老师的耐心指导以及同学们的热 心帮助！ 指导教师评语： 指导教师（签字）:年 月日 课程设计成绩 出师表 两汉：诸葛亮 先帝创业未半而中道崩殂