偏序关系中特殊元素判定.docx
《偏序关系中特殊元素判定.docx》由会员分享，可在线阅读，更多相关《偏序关系中特殊元素判定.docx（21页珍藏版）》请在冰点文库上搜索。
偏序关系中特殊元素判定
沈阳航空航天大学
课程设计报告
课程设计名称：
数据结构课程设计
课程设计题目：
偏序关系中特殊元素判定
院（系）：
计算机学院
专业：
计算机科学与技术
班级：
学号：
姓名：
指导教师：
目录
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.3main（）函数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.2.3判断结点位置
判断结点位置主要是判断指定结点可否到达子集所有结点或子集所有结点可否到达指定结点。
判断指定结点可否到达子集所有结点时，首先求取有向图中指定结点可到达的所有结点，然后与子集所有结点比较，如果子集所有结点都在指定结点可到达的结点中，则指定结点可到达子集所有结点。
判断子集所有结点可否到达指定结点时，首先求取有向图中可到达指定结点的所有结点，然后与子集所有结点比较，如果子集所有结点都在可到达指定结点的结点中，则子集所有结点可到达指定结点。
例如，有向图如图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则分别为弧头相同和弧尾相同的弧的链域，表示如下：
typedefstructArcBox{
inttailvex,headvex;
structArcBox*hlink,*tlink;
}ArcBox;
存储顶点的结构体,其中包含三个变量data和指针firstin、firstout，data存储顶点信息,firstin、firstout则分别指向该顶点第一条入弧和出弧，表示如下：
typedefstructVexNode{
VertexTypedata;
ArcBox*firstin,*firstout;
}VexNode;
存储图的结构体,其中包含三个变量xlist[MAX_VERTEX_NUM]和vexnum、arcnum，xlist[MAX_VERTEX_NUM]存储表头向量，vexnum、arcnum则存储有向图的当前顶点数和弧数，表示如下：
typedefstruct{
VexNodexlist[MAX_VERTEX_NUM];
intvexnum,arcnum;
}OLGraph;
2.3main（）函数
功能：
求取偏序关系中的特殊元素。
参数含义：
G：
表示图。
简单工作过程：
给定一个有向图，建立十字链表，输入子集信息，计算子集元素个数，再调用子函数，求解子集对应特殊元素。
最后，将子集对应特殊元素输出。
主函数流程图如图2.2所示。
2.4十字链表建立函数
功能：
建立十字链表。
简单工作过程：
将顶点信息和弧信息依次输入，然后，对弧结点赋值并完成在入弧和出弧链头的插入，建立十字链表。
参数含义：
G：
表示图。
函数流程图如图2.3所示。
2.5求解判断函数
功能：
求取该结点的所有弧尾（s为0）或所有弧头（s为0）。
简单工作过程：
判断s，s为0，将弧尾依次输入到数组中；s不为0，将弧头依次输入到数组中。
参数含义：
G：
表示图；t：
该结点位置；s：
判断标志；h数组：
标记。
函数流程图如图2.4所示。
功能：
取出子集所有结点可到达该结点的所有结点（s为0）或取出该结点可到达的所有结点（s不为0）。
简单工作过程：
将h数组，x初始化，判断s，s为0，依次对h数组中结点调用DFS函数存弧尾；s不为0，依次对h数组中结点调用DFS函数存弧头。
参数含义：
G：
表示图；c：
结点名称；s：
判断标志；h数组：
标记。
函数流程图如图2.5所示。
功能：
判断该结点是否到达子集所有结点（s为0）或判断子集所有结点是否到达该结点（s不为0）。
简单工作过程：
初始化flag数组，判断s，s为0，调用quhu函数，判断若该结点可到达子集所有结点，返回1，否则返回0；s不为0，调用quhu函数，判断若子集所有结点可到达该结点，返回1，否则返回0。
参数含义：
G：
表示图；c：
结点名称；p：
存储结点；m：
结点个数；s：
判断标志；h数组：
标记；flag数组：
标记。
函数流程图如图2.6所示。
2.6特殊元素求解函数
特殊元素求解模块主要包含八个函数，分别用来求解八种特殊元素。
但由于这八个函数大同小异，所以，这里就介绍一个函数以代表。
功能：
求取子集中的最大元。
简单工作过程：
初始化t，依次调用panduan函数判断结点可否到达子集所有结点，若可以，则输出最大值，若全部不可以，则输出无最大值。
参数含义：
G：
表示图；p：
存储结点；m：
结点个数；t：
判断标志。
函数流程图如图2.7所示。
3系统实现
3.1错误分析
（1）在读入字符时，字符无法正常读入。
经过检查，字符读入时将回车读入到指定变量中，运行出现错误。
通过调整读入顺序，再次运行，程序正常。
（2）某些基础函数无法调用。
经过检查，是对库函数忘记引用，导致程序无法调用某些函数，运行出现错误。
通过增加对库函数的引用，再次运行，程序正常。
（3）出现未知变量，程序无法运行。
经过检查，是对函数panduan忘记增加返回值，导致程序运行出现错误。
通过增加函数panduan的返回值，再次运行，程序正常。
（4）调用DFS函数时有时正确，有时返回为空导致程序运行出现错误。
经过检查，是对函数quhu忘记增加判断，导致有时调用DFS函数时产生错误。
通过对函数quhu增加判断，再次运行，程序正常。
（5）程序输出结果与实际不符。
经过检查，是对做标记的全局变量没有及时初始化，致使多次记录，程序输出结果与实际不符。
通过对全局变量及时初始化，再次运行，程序正常。
3.2实现结论
该算法实现了输入一节点子集的信息到代表一个由特定偏序关系导出的哈斯图的有向图中，求解子集对应的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界八种特殊元素的功能。
例如：
输入顶点数和弧数为4和4，依次输入顶点值为abcd，依次输入各弧信息为abacbdcd，输入节点子集信息为bcd。
输出为极大元有bc，极小元有d，没有最大元，最小元是d，上界是a，下界是d，上确界是a，下确界是d。
参考文献
[1]严蔚敏，吴伟民.数据结构（C语言版）［M］.北京：
清华大学出版社，2006
[2]戴艳等.零基础学算法[M].北京：
机械工业出版社，2012
[3]左孝凌，李为坚，刘永才.离散数学[M].上海：
上海科学技术文献出版社
附录（关键部分程序清单）
#include
#include
#include
#defineNULL0
#defineMAX_VERTEX_NUM20
typedefstructArcBox
{
inttailvex,headvex;
structArcBox*hlink,*tlink;
}ArcBox;
typedefstructVexNode
{
chardata;
ArcBox*firstin,*firstout;
}VexNode;
typedefstruct
{
VexNodexlist[MAX_VERTEX_NUM];
intvexnum,arcnum;
}OLGraph;
intLocateVex（OLGraphG,charv1）
{
inti;
for（i=0;iif（G.xlist[i].data==v1）
returni;
returnNULL;
}
voidCreateDG（OLGraph&G）
{
inti,j,k;
charv1,v2;
ArcBox*p;
printf（"请分别输入顶点数和弧数.\n"）;
scanf（"%d,%d",&G.vexnum,&G.arcnum）;
if（G.vexnum==0||G.arcnum==0）
printf（"输入错误.\n"）;exit（0）;
printf（"请依次输入顶点值.\n"）;
for（i=0;i{
getchar（）;
scanf（"%c",&G.xlist[i].data）;
if（G.xlist[i].data==''）
printf（"输入错误.\n"）;exit（0）;
G.xlist[i].firstin=NULL;G.xlist[i].firstout=NULL;
}
printf（"请依次输入各弧信息.\n"）;
for（k=0;k{
getchar（）;
scanf（"%c%c",&v1,&v2）;
if（v1==''||v2==''）
printf（"输入错误.\n"）;exit（0）;
i=LocateVex（G,v1）;j=LocateVex（G,v2）;
p=（ArcBox*）malloc（sizeof（ArcBox））;
p->tailvex=i;p->headvex=j;
p->hlink=G.xlist[j].firstin;p->tlink=G.xlist[i].firstout;
G.xlist[j].firstin=G.xlist[i].firstout=p;
}
}
inth[MAX_VERTEX_NUM],x;
voidDFS（OLGraphG,intt,ints）
{
ArcBox*p;
p=（ArcBox*）malloc（sizeof（ArcBox））;
if（s==0）
{
p=G.xlist[t].firstin;
if（h[0]==-1）h[0]=p->tailvex;
else
h[++x]=p->tailvex;
while（p->hlink!
=NULL）
p=p->hlink;h[++x]=p->tailvex;
}
else
{
p=G.xlist[t].firstout;
if（h[0]==-1）
h[0]=p->headvex;
else
h[++x]=p->headvex;
while（p->tlink!
=NULL）
p=p->tlink;h[++x]=p->headvex;
}
}
voidquhu（OLGraphG,charc,ints）
{
inti,t,flag=0;
for（i=0;ih[i]=-1;
t=LocateVex（G,c）;
x=0;
if（s==0）
{
if（G.xlist[t].firstin）
{
DFS（G,t,s）;
for（i=0;h[i]!
=-1;i++）
if（G.xlist[h[i]].firstin）DFS（G,h[i],s）;
}
}
elseif（G.xlist[t].firstout）
{
DFS（G,t,s）;
for（i=0;h[i]!
=-1;i++）
if（G.xlist[h[i]].firstout）DFS（G,h[i],s）;
}
}
intpanduan（OLGraphG,charc,char*p,intm,ints）
{
inti,j,flag[MAX_VERTEX_NUM];
for（i=0;iflag[i]=0;
if（s==0）
quhu（G,c,1）;
else
quhu（G,c,0）;
for（i=0;iif（c==p[i]）
flag[i]=1;
else
for（j=0;h[j]!
=-1;j++）
if（LocateVex（G,p[i]）==h[j]）
flag[i]=1;
for（i=0;iif（flag[i]==0）
return0;
return1;
}
voidmax（OLGraphG,char*p,intm）
{
inti,t;
for（i=0;it=panduan（G,p[i],p,m,0）;
if（t==1）{printf（"最大元是%c.\n",p[i]）;break;}}
if（t==0）printf（"没有最大元.\n"）;
}
voidmain（）
{
OLGraphG;
inti,j,k,m;
charp[MAX_VERTEX_NUM];
CreateDG（G）;
printf（"请输入节点子集信息.\n"）;
scanf（"%s",p）;
i=0;
while（p[i]）i++;
m=i;
max（G,p,m）;
}
课程设计总结：
通过此次的课程设计，我学会了许多在课堂上学不到的知识。
有一些知识只有你自己亲身去实践，去发现问题，然后依靠自己解决了问题，你才能真正掌握。
对于有向图的存储创建，本来仅仅只局限于邻接矩阵、邻接表，但通过课设，还学会了利用十字链表存储创建有向图，并且，我发现利用十字链表创建的有向图应用范围更广。
在课设过程中，通过翻阅书籍，咨询同学，上网找资料，不但提高了我的查找能力，而且还提高了自己快速融合各种信息，并将其转变为自己的知识的能力。
而且，从这次课程设计活动中我认识到了一定要认真对待每一个问题，因为，很有可能就在一个你不注意的地方导致你失败。
总之，这次课设是自己用心去完成的一项工作，但，由于本人水平有限能力有限，此次课程设计还有很多不足，敬请老师谅解！
在此次课设中，得到了老师及同学不少帮助，所以，我在这里要衷心地感谢老师的耐心指导以及同学们的热心帮助！
指导教师评语：
指导教师（签字）：
年月日
课程设计成绩
出师表
两汉：
诸葛亮
先帝创业未半而中道崩殂，今天下三分，益州疲弊，此诚危急存亡之秋也。
然侍卫之臣不懈于内，忠志之士忘身于外者，盖追先帝之殊遇，欲报之于陛下也。
诚宜开张圣听，以光先帝遗德，恢弘志士之气，不宜妄自菲薄，引喻失义，以塞忠谏之路也。
宫中府中，俱为一体；陟罚臧否，不宜异同。
若有作奸犯科及为忠善者，宜付有司论其刑赏，以昭陛下平明之理；不宜偏私，使内外异法也。
侍中、侍郎郭攸之、费祎、董允等，此皆良实，志虑忠纯，是以先帝简拔以遗陛下：
愚以为宫中之事，事无大小，悉以咨之，然后施行，必能裨补阙漏，有所广益。
将军向宠，性行淑均，晓畅军事，试用于昔日，先帝称之曰“能”，是以众议举宠为督：
愚以为营中之事，悉以咨之，必能使行阵和睦，优劣得所。
亲贤臣，远小人，此先汉所以兴隆也；亲小人，远贤臣，此后汉所以倾颓也。
先帝在时，每与臣论此事，未尝不叹息痛恨于桓、灵也。
侍中、尚书、长史、参军，此悉贞良死节之臣，愿陛下亲之、信之，则汉室之隆，可计日而待也
。
臣本布衣，躬耕于南阳，苟全性命于乱世，不求闻达于诸侯。
先帝不以臣卑鄙，猥自枉屈，三顾臣于草庐之中，咨臣以当世之事，由是感激，遂许先帝以驱驰。
后值倾覆，受任于败军之际，奉命于危难之间，尔来二十有一年矣。
先帝知臣谨慎，故临崩寄臣以大事也。
受命以来，夙夜忧叹，恐托付不效，以伤先帝之明；故五月渡泸，深入不毛。
今南方已定，兵甲已足，当奖率三军，北定中原，庶竭驽钝，攘除奸凶，兴复汉室，还于旧都。
此臣所以报先帝而忠陛下之职分也。
至于斟酌损益，进尽忠言，则攸之、祎、允之任也。
愿陛下托臣以讨贼兴复之效，不效，则治臣之罪，以告先帝之灵。
若无兴德之言，则责攸之、祎、允等之慢，以彰其咎；陛下亦宜自谋，以咨诹善道，察纳雅言，深追先帝遗诏。
臣不胜受恩感激。
今当远离，临表涕零，不知所言。
升级会员 