偏序關(guān)系中特殊元素判定-2013

1、沈陽航空航天大學(xué) 課程 設(shè)計(jì)報(bào)告 課程設(shè)計(jì)名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目： 偏序關(guān)系中特殊兀素判定 院（系）：計(jì)算機(jī)學(xué)院 專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 學(xué) 號(hào)： 姓 名： 指導(dǎo)教師: 目 錄 1 算法分析1 1.1假設(shè)條件1 1.2算法描述1 1.2.1 有向圖的存儲(chǔ)結(jié)構(gòu)1 1.2.2 求取有聯(lián)系結(jié)點(diǎn) 1 1.2.3 判斷結(jié)點(diǎn)位置2 2系統(tǒng)設(shè)計(jì)4 2.1設(shè)計(jì)說明4 2.2數(shù)據(jù)結(jié)構(gòu)描述4 2.3 MAIN ()函數(shù)5 2.4十字鏈表建立函數(shù)6 2.5求解判斷函數(shù)9 2.6特殊元素求解函數(shù)12 3 系統(tǒng)實(shí)現(xiàn)14 3.1錯(cuò)誤分析14 3.2實(shí)現(xiàn)結(jié)論14 參考文獻(xiàn)16 附 錄(關(guān)鍵部分程序

2、清單) 17 1算法分析 1.1假設(shè)條件 偏序關(guān)系中特殊元素判定就是對(duì)偏序關(guān)系中指定子集對(duì)應(yīng)的特殊元素的求 解。該程序首先需要將由特定偏序關(guān)系導(dǎo)出的哈斯圖輸入，然后再將節(jié)點(diǎn)子集輸 入，由此就可求出對(duì)應(yīng)的特殊元素。但該程序有一些限制，輸入的哈斯圖不能過 大，結(jié)點(diǎn)不能超過二十個(gè)；對(duì)一些錯(cuò)誤輸入無法分辨。 1.2算法描述 本次算法是在一個(gè)有向圖中，有向圖代表一個(gè)由特定偏序關(guān)系導(dǎo)出的哈斯圖, 指定一個(gè)節(jié)點(diǎn)子集，求解子集對(duì)應(yīng)的極大元、極小元、最大元、最小元、上界、 下界、上確界、下確界八種特殊元素。 1.2.1有向圖的存儲(chǔ)結(jié)構(gòu) 對(duì)于輸入的有向圖，利用十字鏈表進(jìn)行存儲(chǔ)。 十字鏈表用頂點(diǎn)結(jié)點(diǎn)和弧結(jié)點(diǎn)將頂點(diǎn)和

3、弧連接起來。利用頂點(diǎn)結(jié)點(diǎn)記錄頂點(diǎn) 信息和首條入弧及出弧，利用弧結(jié)點(diǎn)記錄弧信息和弧頭相同及弧尾相同的鏈域， 如此，將弧和結(jié)點(diǎn)連接起來。 1.2.2求取有聯(lián)系結(jié)點(diǎn) 求取有聯(lián)系結(jié)點(diǎn)主要是求取有向圖中可到達(dá)指定結(jié)點(diǎn)的所有結(jié)點(diǎn)或指定結(jié)點(diǎn) 可到達(dá)的所有結(jié)點(diǎn)。 求取有向圖中可到達(dá)指定結(jié)點(diǎn)的所有結(jié)點(diǎn)時(shí)，可設(shè)一全局變量整型數(shù)組來記 錄結(jié)點(diǎn)。先求取指定結(jié)點(diǎn)的弧尾將其全存入全局變量，然后，不斷求取全局變量 中結(jié)點(diǎn)的弧尾將其全存入全局變量，直到取完，這樣，就可求取有向圖中可到達(dá) 指定結(jié)點(diǎn)的所有結(jié)點(diǎn)。 求取有向圖中指定結(jié)點(diǎn)可到達(dá)的所有結(jié)點(diǎn)時(shí)，也可設(shè)一全局變量整型數(shù)組來 記錄結(jié)點(diǎn)。先求取指定結(jié)點(diǎn)的弧頭將其全存入全局變量，

4、然后，不斷求取全局變 量中結(jié)點(diǎn)的弧頭將其全存入全局變量，直到取完，這樣，就可求取有向圖中可到 達(dá)指定結(jié)點(diǎn)的所有結(jié)點(diǎn)。 例如：有向圖如圖1.1所示，求a可到達(dá)的所有結(jié)點(diǎn)，a、b、c編號(hào)分別為0、 1、2,設(shè)一整型數(shù)組h10，先求取a的弧頭將其全存入h10，則h0=1，h1=2， 然后，求取h0也就是b的弧頭將其全存入h10，但b的弧頭為空，所以h10 沒有變化，再求取h1也就是c的弧頭將其全存入h10，但c的弧頭也為空，所 以h10還是沒有變化。因此，a可到達(dá)的所有結(jié)點(diǎn)為b和c。 圖1.1 有向圖示意圖 1.2.3判斷結(jié)點(diǎn)位置 判斷結(jié)點(diǎn)位置主要是判斷指定結(jié)點(diǎn)可否到達(dá)子集所有結(jié)點(diǎn)或子集所有結(jié)點(diǎn)可

5、否到達(dá)指定結(jié)點(diǎn)。 判斷指定結(jié)點(diǎn)可否到達(dá)子集所有結(jié)點(diǎn)時(shí)，首先求取有向圖中指定結(jié)點(diǎn)可到達(dá) 的所有結(jié)點(diǎn)，然后與子集所有結(jié)點(diǎn)比較，如果子集所有結(jié)點(diǎn)都在指定結(jié)點(diǎn)可到達(dá) 的結(jié)點(diǎn)中，貝U指定結(jié)點(diǎn)可到達(dá)子集所有結(jié)點(diǎn)。 判斷子集所有結(jié)點(diǎn)可否到達(dá)指定結(jié)點(diǎn)時(shí)，首先求取有向圖中可到達(dá)指定結(jié)點(diǎn) 的所有結(jié)點(diǎn)，然后與子集所有結(jié)點(diǎn)比較，如果子集所有結(jié)點(diǎn)都在可到達(dá)指定結(jié)點(diǎn) 的結(jié)點(diǎn)中，貝U子集所有結(jié)點(diǎn)可到達(dá)指定結(jié)點(diǎn)。 例如，有向圖如圖1.1所示，子集為a,b，判斷a可否到達(dá)子集所有結(jié)點(diǎn), 首先求取有向圖中a可到達(dá)的所有結(jié)點(diǎn)，求取出來為b,c，然后與子集所有結(jié)點(diǎn) 比較，子集中a為其本身，而b在b,c中，所以，a可到達(dá)子集所有結(jié)點(diǎn)。

6、 2系統(tǒng)設(shè)計(jì) 2.1設(shè)計(jì)說明 該程序設(shè)計(jì)共包括四大模塊：主函數(shù)模塊、十字鏈表建立模塊、求解判斷模 塊、特殊元素求解模塊。主函數(shù)中調(diào)用了其他所有三個(gè)模塊，求解判斷模塊與特 殊元素求解模塊都調(diào)用了十字鏈表建立模塊中建立的十字鏈表，特殊元素求解模 塊則調(diào)用了十字鏈表建立模塊和求解判斷模塊。函數(shù)模塊關(guān)系如圖 2.1所示: 圖2.1函數(shù)模塊關(guān)系圖 2.2數(shù)據(jù)結(jié)構(gòu)描述 該函數(shù)包含三個(gè)結(jié)構(gòu)體，即存儲(chǔ)弧、存儲(chǔ)頂點(diǎn)和存儲(chǔ)圖的結(jié)構(gòu)體。其結(jié)構(gòu)體 分別如下所示： 存儲(chǔ)弧的結(jié)構(gòu)體，其中包含四個(gè)變量tailvex、headvex和指針hlink、tlink， tailvex、headvex分別指示該弧的尾和頭頂點(diǎn)的位置，

7、hlink、tlink則分別為弧頭相 同和弧尾相同的弧的鏈域，表示如下： typedef struct ArcBox int tailvex, headvex; struct ArcBox *hlink, *tlink; ArcBox; 存儲(chǔ)頂點(diǎn)的結(jié)構(gòu)體，其中包含三個(gè)變量data和指針firstin、firstout , data 存儲(chǔ)頂點(diǎn)信息，firstin 、firstout貝U分別指向該頂點(diǎn)第一條入弧和出弧，表示 如下： typedef struct VexNode VertexType data; ArcBox *first in, *firstout; VexNode; 存儲(chǔ)圖的結(jié)構(gòu)

8、體，其中包含三個(gè)變量 xlistMAX_VERTEX_NUM和vex num arcnum, xlistMAX_VERTEX_NUM存 儲(chǔ)表頭向量，vex num arcnum 則存儲(chǔ)有向圖 的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)，表示如下： typedef struct VexNode xlistMAX_VERTEX_NUM; int vex num, arcnum; OLGraph; 2.3 main()函數(shù) 功能：求取偏序關(guān)系中的特殊元素。 參數(shù)含義：G:表示圖。 簡單工作過程：給定一個(gè)有向圖，建立十字鏈表，輸入子集信息，計(jì)算子集 元素個(gè)數(shù)，再調(diào)用子函數(shù)，求解子集對(duì)應(yīng)特殊元素。最后，將子集對(duì)應(yīng)特殊元素 輸出

9、。 主函數(shù)流程圖如圖2.2所示。 圖2.2 main()函數(shù)流程圖 2.4十字鏈表建立函數(shù) 功能：建立十字鏈表。 簡單工作過程：將頂點(diǎn)信息和弧信息依次輸入，然后，對(duì)弧結(jié)點(diǎn)賦值并完成 在入弧和出弧鏈頭的插入，建立十字鏈表。 參數(shù)含義：G:表示圖。 函數(shù)流程圖如圖 2.3所示。 圖2.3十字鏈表建立函數(shù)流程圖 2.5求解判斷函數(shù) 功能：求取該結(jié)點(diǎn)的所有弧尾（s為0）或所有弧頭（s為0）。 簡單工作過程：判斷s, s為0,將弧尾依次輸入到數(shù)組中；s不為0,將弧頭 依次輸入到數(shù)組中。 參數(shù)含義：G:表示圖；t:該結(jié)點(diǎn)位置；s：判斷標(biāo)志；h數(shù)組：標(biāo)記。 函數(shù)流程圖如圖2.4所示。 圖2.4 DFS函數(shù)流

10、程圖 功能：取出子集所有結(jié)點(diǎn)可到達(dá)該結(jié)點(diǎn)的所有結(jié)點(diǎn)（S為0）或取出該結(jié)點(diǎn)可 到達(dá)的所有結(jié)點(diǎn)（S不為0）。 簡單工作過程：將h數(shù)組，x初始化，判斷s, s為0,依次對(duì)h數(shù)組中結(jié)點(diǎn) 調(diào)用DFS函數(shù)存弧尾；s不為0,依次對(duì)h數(shù)組中結(jié)點(diǎn)調(diào)用DFS函數(shù)存弧頭。 參數(shù)含義：G:表示圖；c：結(jié)點(diǎn)名稱；s：判斷標(biāo)志；h數(shù)組：標(biāo)記。 函數(shù)流程圖如圖2.5所示。 :開始 將h數(shù)組，x初始化 N J s 為 0 調(diào)用DFS函 數(shù) Y N 調(diào)用DFS函 數(shù) 結(jié)束 圖2.5 quhu函數(shù)流程圖 功能：判斷該結(jié)點(diǎn)是否到達(dá)子集所有結(jié)點(diǎn)（S為0）或判斷子集所有結(jié)點(diǎn)是否 到達(dá)該結(jié)點(diǎn)（S不為0）。 簡單工作過程：初始化flag數(shù)

11、組，判斷s，s為0,調(diào)用quhu函數(shù)，判斷若 該結(jié)點(diǎn)可到達(dá)子集所有結(jié)點(diǎn)，返回 1否則返回0； s不為0,調(diào)用quhu函數(shù)，判 斷若子集所有結(jié)點(diǎn)可到達(dá)該結(jié)點(diǎn)，返回 1,否則返回0。 參數(shù)含義：G:表示圖；c：結(jié)點(diǎn)名稱；p：存儲(chǔ)結(jié)點(diǎn)；m :結(jié)點(diǎn)個(gè)數(shù)；s：判 斷標(biāo)志；h數(shù)組：標(biāo)記；flag數(shù)組：標(biāo)記。 函數(shù)流程圖如圖2.6所示。 開始 將i、flag數(shù)組全賦為0 1 r F 調(diào)用quhu函數(shù)，判 斷若子集所有結(jié) 點(diǎn) 可到達(dá)該結(jié)點(diǎn)，將對(duì) 應(yīng)flag全置為1 調(diào)用quhu函數(shù)，判 斷若該結(jié)點(diǎn)可到達(dá) 子集所有結(jié)點(diǎn)，將對(duì) 應(yīng)flag全置為1 Y N N im Y 將i 加 1 J N flagi為 0 返回

12、0 返回1 1 T T 結(jié)束 圖2.6 panduan函數(shù)流程圖 2.6特殊元素求解函數(shù) 特殊元素求解模塊主要包含八個(gè)函數(shù)，分別用來求解八種特殊元素。但由于 這八個(gè)函數(shù)大同小異，所以，這里就介紹一個(gè)函數(shù)以代表。 功能：求取子集中的最大元。 簡單工作過程：初始化t,依次調(diào)用panduan函數(shù)判斷結(jié)點(diǎn)可否到達(dá)子集所有 結(jié)點(diǎn)，若可以，則輸出最大值，若全部不可以，則輸出無最大值。 參數(shù)含義：G:表示圖；p：存儲(chǔ)結(jié)點(diǎn)；m：結(jié)點(diǎn)個(gè)數(shù)；t :判斷標(biāo)志。 函數(shù)流程圖如圖2.7所示。 3系統(tǒng)實(shí)現(xiàn) 3.1錯(cuò)誤分析 （1）在讀入字符時(shí)，字符無法正常讀入。經(jīng)過檢查，字符讀入時(shí)將回車讀入 到指定變量中，運(yùn)行出現(xiàn)錯(cuò)誤。通

13、過調(diào)整讀入順序，再次運(yùn)行，程序正常。 （2）某些基礎(chǔ)函數(shù)無法調(diào)用。經(jīng)過檢查，是對(duì)庫函數(shù)忘記引用，導(dǎo)致程序無 法調(diào)用某些函數(shù)，運(yùn)行出現(xiàn)錯(cuò)誤。通過增加對(duì)庫函數(shù)的引用，再次運(yùn)行，程序正 常。 （3）出現(xiàn)未知變量，程序無法運(yùn)行。經(jīng)過檢查，是對(duì)函數(shù) pan duan忘記增加 返回值，導(dǎo)致程序運(yùn)行出現(xiàn)錯(cuò)誤。通過增加函數(shù) pan duan的返回值，再次運(yùn)行， 程序正常。 （4）調(diào)用DFS函數(shù)時(shí)有時(shí)正確，有時(shí)返回為空導(dǎo)致程序運(yùn)行出現(xiàn)錯(cuò)誤。經(jīng) 過檢查，是對(duì)函數(shù)quhu忘記增加判斷，導(dǎo)致有時(shí)調(diào)用 DFS函數(shù)時(shí)產(chǎn)生錯(cuò)誤。通 過對(duì)函數(shù)quhu增加判斷，再次運(yùn)行，程序正常。 （5）程序輸出結(jié)果與實(shí)際不符。經(jīng)過檢查，是對(duì)

14、做標(biāo)記的全局變量沒有及時(shí) 初始化，致使多次記錄，程序輸出結(jié)果與實(shí)際不符。通過對(duì)全局變量及時(shí)初始化， 再次運(yùn)行，程序正常。 3.2實(shí)現(xiàn)結(jié)論 該算法實(shí)現(xiàn)了輸入一節(jié)點(diǎn)子集的信息到代表一個(gè)由特定偏序關(guān)系導(dǎo)出的哈斯 圖的有向圖中，求解子集對(duì)應(yīng)的極大元、極小元、最大元、最小元、上界、下界、 上確界、下確界八種特殊元素的功能。例如：輸入頂點(diǎn)數(shù)和弧數(shù)為4和4，依次 輸入頂點(diǎn)值為a b c d,依次輸入各弧信息為ab ac bd cd輸入節(jié)點(diǎn)子集信息為bed。 輸出為極大元有be，極小元有d，沒有最大元，最小元是d，上界是a，下界是d， 上確界是a，下確界是do 參考文獻(xiàn) 1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版

15、）M .北京：清華大學(xué)出版社，2006 2 戴艷等.零基礎(chǔ)學(xué)算法M.北京：機(jī)械工業(yè)出版社，2012 3 左孝凌，李為堅(jiān)，劉永才.離散數(shù)學(xué)M.上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社 附 錄（關(guān)鍵部分程序清單） #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(請(qǐng)分別輸入頂點(diǎn)數(shù)和弧數(shù).n); sca nf(%d,%d, if(G.vex

17、 num=0|G.arc num=0) printf(輸入錯(cuò)誤.n);exit(0); printf(請(qǐng)依次輸入頂點(diǎn)值.n); for(i=0;iG.vex nu m;i+) getchar(); sca nf(”c, if(G.xlisti.data=) printf(輸入錯(cuò)誤.n);exit(0); G.xlisti.firsti n=NULL; G.xlisti.firstout=NULL; printf(請(qǐng)依次輸入各弧信息.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(請(qǐng)輸入節(jié)

22、點(diǎn)子集信息.n); sca nf(%s,p); i=0; while(pi) i+; m=i; max(G,p,m); 課程設(shè)計(jì)總結(jié)： 通過此次的課程設(shè)計(jì)，我學(xué)會(huì)了許多在課堂上學(xué)不到的知識(shí)。 有一些知識(shí)只 有你自己親身去實(shí)踐，去發(fā)現(xiàn)問題，然后依靠自己解決了問題，你才能真正掌握。 對(duì)于有向圖的存儲(chǔ)創(chuàng)建，本來僅僅只局限于鄰接矩陣、鄰接表，但通過課設(shè)，還 學(xué)會(huì)了利用十子鏈表存儲(chǔ)創(chuàng)建有向圖， 并且，我發(fā)現(xiàn)利用十子鏈表創(chuàng)建的有向圖 應(yīng)用范圍更廣。在課設(shè)過程中，通過翻閱書籍，咨詢同學(xué)，上網(wǎng)找資料，不但提 高了我的查找能力，而且還提高了自己快速融合各種信息， 并將其轉(zhuǎn)變?yōu)樽约旱?知識(shí)的能力。而且，從這次課程設(shè)計(jì)活動(dòng)中我認(rèn)識(shí)到了一定要認(rèn)真對(duì)待每一個(gè)問 題，因?yàn)?，很有可能就在一個(gè)你不注意的地方導(dǎo)致你失敗。 總之，這次課設(shè)是自己用心去完成的一項(xiàng)工作， 但，由于本人水平有限能力 有限，此次課程設(shè)計(jì)還有很多不足，敬請(qǐng)老師諒解！在此次課設(shè)中，得到了老師 及同學(xué)不少幫助，所以，我在這里要衷心地感謝老師的耐心指導(dǎo)以及同學(xué)們的熱 心幫助！ 指導(dǎo)教師評(píng)語： 指導(dǎo)教師（簽字）:年 月日 課程設(shè)計(jì)成績 出師表 兩漢：諸葛亮 先帝創(chuàng)業(yè)未半而中道崩殂