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

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：偏序关系中特殊元素判定 院（系）：计算机学院 专 业：计算机科学与技术 班 级： 学 号： 姓 名： 指导教师：  目 录 1 算法分析 1 1.1假设条件 1 1.2算法描述 1 1.2.1 有向图的存储结构 1 1.2.2 求取有联系结点 1 1.2.3 判断结点位置 2 2 系统设计 3 2.1设计说明 3 2.2数据结构描述 3 2.3 main()函数 4 2.4 十字链表建立函数 5 2.5 求解判断函数 7 2.6特殊元素求解函数 10 3 系统实现 11 3.1错误分析 11 3.2实现结论 11 参考文献 12 附 录（关键部分程序清单） 13  1 算法分析 1.1假设条件 偏序关系中特殊元素判定就是对偏序关系中指定子集对应的特殊元素的求解。该程序首先需要将由特定偏序关系导出的哈斯图输入，然后再将节点子集输入，由此就可求出对应的特殊元素。但该程序有一些限制，输入的哈斯图不能过大，结点不能超过二十个；对一些错误输入无法分辨。 1.2算法描述 本次算法是在一个有向图中，有向图代表一个由特定偏序关系导出的哈斯图，指定一个节点子集，求解子集对应的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界八种特殊元素。 1.2.1 有向图的存储结构 对于输入的有向图，利用十字链表进行存储。 十字链表用顶点结点和弧结点将顶点和弧连接起来。利用顶点结点记录顶点信息和首条入弧及出弧，利用弧结点记录弧信息和弧头相同及弧尾相同的链域，如此，将弧和结点连接起来。 1.2.2 求取有联系结点 求取有联系结点主要是求取有向图中可到达指定结点的所有结点或指定结点可到达的所有结点。 求取有向图中可到达指定结点的所有结点时，可设一全局变量整型数组来记录结点。先求取指定结点的弧尾将其全存入全局变量，然后，不断求取全局变量中结点的弧尾将其全存入全局变量，直到取完，这样，就可求取有向图中可到达指定结点的所有结点。 求取有向图中指定结点可到达的所有结点时，也可设一全局变量整型数组来记录结点。先求取指定结点的弧头将其全存入全局变量，然后，不断求取全局变量中结点的弧头将其全存入全局变量，直到取完，这样，就可求取有向图中可到达指定结点的所有结点。 例如：有向图如图1.1所示，求a可到达的所有结点，a、b、c编号分别为0、1、2，设一整型数组h[10]，先求取a的弧头将其全存入h[10]，则h[0]=1，h[1]=2，然后，求取h[0]也就是b的弧头将其全存入h[10]，但b的弧头为空，所以h[10]没有变化，再求取h[1]也就是c的弧头将其全存入h[10]，但c的弧头也为空，所以h[10]还是没有变化。因此，a可到达的所有结点为b和c。 判断结点位置 判断结点位置主要是判断指定结点可否到达子集所有结点或子集所有结点可否到达指定结点。 判断指定结点可否到达子集所有结点时，首先求取有向图中指定结点可到达的所有结点，然后与子集所有结点比较，如果子集所有结点都在指定结点可到达的结点中，则指定结点可到达子集所有结点。 判断子集所有结点可否到达指定结点时，首先求取有向图中可到达指定结点的所有结点，然后与子集所有结点比较，如果子集所有结点都在可到达指定结点的结点中，则子集所有结点可到达指定结点。 例如，有向图如图1.1所示，子集为{a,b}，判断a可否到达子集所有结点，首先求取有向图中a可到达的所有结点，求取出来为{b,c}，然后与子集所有结点比较，子集中a为其本身，而b在{b,c}中，所以，a可到达子集所有结点。 2 系统设计 2.1设计说明 该程序设计共包括四大模块：主函数模块、十字链表建立模块、求解判断模块、特殊元素求解模块。主函数中调用了其他所有三个模块，求解判断模块与特殊元素求解模块都调用了十字链表建立模块中建立的十字链表，特殊元素求解模块则调用了十字链表建立模块和求解判断模块。函数模块关系如图2.1所示： 2.2数据结构描述 该函数包含三个结构体，即存储弧、存储顶点和存储图的结构体。其结构体分别如下所示： 存储弧的结构体,其中包含四个变量tailvex、headvex和指针hlink、tlink，tailvex、headvex分别指示该弧的尾和头顶点的位置，hlink、tlink则分别为弧头相同和弧尾相同的弧的链域，表示如下： typedef struct ArcBox { int tailvex, headvex; struct ArcBox *hlink, *tlink; } A