數據結構課設紅樓夢人物關系數據結構課設紅樓夢人物關系實用文檔/數據結構課設紅樓夢人物關系課程設計報告題目：基于社會網絡分析技術的《紅樓夢》人物關系分析課程名稱：數據結構專業班級：學號：姓名：指導教師：報告日期：計算機科學與技術學院任務書設計內容用圖模型設計與表示《紅樓夢》人物關系網，并以文件形式保存相關信息；運用社會網絡分析技術與算法對紅樓夢人物關系網進行分析，獲取有意義的結果，并以圖形方式呈現；提供對人物屬性與人物關系的查詢功能。設計要求⑴設計一定的界面，能夠將分析所得人物關系結果直觀顯示，支持人物關系的查詢。人物關系數據以文件形式保存。若界面友好，有特色，可酌情加分。⑵選用兩種以上分析模型如核心人物分析、中心性分析、小團體分析、相似子結構分析等進行分析處理，分析模型在社會網絡分析相關文獻中具有嚴格定義，設計中對分析模型的表示與處理基于對應的定義，以避免僅從字面理解而出現不嚴謹、簡單化的設計。⑶設計程序中處理的不同人物數量不少于100人，并根據人物數量情況、所使用的分析模型與算法的復雜程度分易、中、難三級評分。參考文獻[1]孫曉玲,林鴻飛.人際網絡關系抽取和結構挖掘.微電子學與計算機,2008,25(9):233-236[2]杜一鳴,滕桂法,馬建斌.社會網絡搜索關鍵技術研究概述.情報分析與研究，2010，189(2):68-73[3]徐偉,陳光輝,曾玉.關系研究的新取向:社會網絡分析.心理科學，2011，34（2）：499-504[4]張樹人,劉穎,陳禹.社會網絡分析在組織管理中的應用.中國人民大學學報，2006，（3）：74-80[5]韓毅.社會網絡分析與挖掘的若干關鍵問題研究.國防科學技術大學博士學位論文，2011.6[6]MohsenJamaliandHassanAbolhassani.DifferentAspectsofSocialNetworkAnalysis.[7]KateEhrlichandIngaCarboni.InsideSocialNetworkAnalysis.[8][9]嚴蔚敏,吳偉民.數據結構（C語言版）.北京:清華大學出版社,1997[10]王曉東.計算機算法設計與分析.北京:電子工業出版社,2007

目錄任務書 =1\*ROMANI1引言 11.1課題背景與意義 11.2國內外研究現狀 31.3程序設計的主要研究工作 102系統需求分析與總體設計 12.1系統需求分析 12.2系統總體設計 103系統詳細設計 203.1有關數據結構的定義 203.2主要算法設計 234系統實現與測試 404.1系統實現 14.2系統測試 105總結與展望 40HYPERLINK6體會 40參考文獻 44附錄程序源碼 451引言1.1課題背景與意義我選的課程設計題目為基于社會網絡的《紅樓夢》人物關系分析系統。1.1.1課題背景經過一個學期對數據結構這門課程的學習之后，我們被要求獨立完成一份課程設計，備選題目有四個：中國行政區域圖染色與信息查詢、基于社會網絡分析技術的《紅樓夢》人物關系分析、基于查找表的單詞檢索軟件和簡易HTML文檔解析程序。由于《紅樓夢》是我很喜歡的一部文學作品，我選擇了基于社會網絡分析技術的《紅樓夢》人物關系分析這個題目。1.1.2意義通過這次完成課程設計，我能更加深刻地理解圖、無向圖的鄰接多重表存儲結構和與圖相關的算法（如弗洛伊德算法），將課本上的知識付諸實踐，并且提高了運用知識的熟練度。初步了解了界面的制作方法，學習了Qt的基礎知識。同時重溫了《紅樓夢》一書，增長了其他方面的知識。1.2國內外研究現狀目前國內外對社會網絡分析技術的研究主要是基于關系的圖形結構和六度分隔理論的研究，主要有以下幾種分析方法：中心性分析，即通過程度中心性、親近中心性、中介中心性三個指標，判斷個體在群體中居于怎樣的地位、擁有怎樣的權利。小團體分析，主要方法是找出關系結構圖中聯系相對緊密的子圖成分,然后按照子圖的重疊程度與關系的緊密程度進一步組合,最終確定小團體成員。位置分析，即分析不同群體中的個體在群體內相似的角色作用，擁有類似的網絡位置。1.3課程設計的主要研究工作通過查閱論文、網絡搜索等方式學習社會網絡分析技術的概念，找到適用于本課程設計的分析方法。權衡難度之后，我確定了中心性分析法作為本次課程設計的主要分析方法。之后詳細學習這種分析方法，搞清楚程度中心性、親近中心性和中介中心性三個指標應該如何求得，再查書、查百度找合適的算法。界面方面的難度比較大，我選擇用Qt做界面，但是我從未學習過C++，這給我對Qt的學習帶來了許多麻煩。我買了C++的書、在網上查了Qt的教程，一邊理解面向對象的概念，一邊跟著教程摸索Qt的功能，最終成功做出了（很丑的）界面。

2系統需求分析與總體設計2.1系統需求分析《紅樓夢》人物關系系統應具有一定的界面，支持人物關系的查詢（包括直接關系和間接關系），支持查詢特定人物的特定關系者，支持查詢人物的詳細信息。人物關系數據以文件形式保存。用中心性分析和核心人物分析兩種分析模型進行分析，能夠將分析所得人物關系結果直觀顯示。系統應能存儲不少于100人的人物信息以及相互關系。2.2系統總體設計本系統應當有一個可視化菜單，鏈接到四個功能模塊：人物信息查詢模塊、人物關系查詢模塊、按關系搜索人物模塊和人物關系分析模塊。人物信息查詢模塊能夠搜索用戶輸入的人物名字，然后在界面中顯示人物的基本信息。如果未找到用戶輸入的人物，將顯示提示。人物關系查詢模塊能夠查詢任意兩個人物之間的關系，如果兩個人有直接關系（即兩個結點相鄰）則顯示關系信息，如果兩個人之間無直接關系但有間接關系（即兩個結點不相鄰但有通路）則顯示兩個人之間的關系鏈，即顯示通路上每一結點的人物姓名。若兩個人之間無關系（即兩個結點之間無通路），則顯示“人物之間無關系”。按關系搜索人物模塊能夠搜索并顯示與任意人物有特定關系的所有人物。如搜索與“林黛玉”有“表兄妹”關系的人，系統將顯示“賈鏈賈寶玉”，若無搜索結果則顯示“未找到！”人物關系分析模塊有三個功能：程度中心性分析、親近中心性分析、中介中心性分析和核心人物分析。程度中心性分析能夠計算并顯示用戶搜索的人物的程度中心性，親近中心性分析能夠計算并顯示用戶搜索的人物的親近中心性，中介中心性分析功能能夠計算并顯示用戶搜索的人物的中介中心性，核心人物分析能夠計算并顯示系統中每個人物的程度中心性且按從小到大排序，從而分析出程度中心性最高的人物為核心人物，并顯示其簡介。圖2-1系統模塊結構圖

3系統詳細設計3.1有關數據結構的定義系統中包含的數據如下：表3-1系統包含的數據表數據數據名稱數據類型人物姓名nameQString人物性別genint人物簡介cinfoQString人物關系信息rinfoQString人物關系的人物AivexQString人物關系中的人物BjvexQString系統采用鄰接多重表的方式創建關系圖。個人信息結構體除了包含人物姓名、人物性別和人物簡介之外，還包含一個指向第一條邊的指針*firstedge，以數組的方式存儲；人物關系的信息以鏈表方式存儲，其結構體包含此邊兩個結點的人物姓名和兩個指針*ilink和*jlink，分別指向兩個結點的鄰邊。3.2主要算法設計人物信息查詢模塊：系統獲取用戶輸入的內容，遍歷圖并比較每一結點的人物姓名項與用戶輸入的內容，發現相同時，以QString的形式返回人物的其他信息,并在textBrowser中顯示。人物關系查詢模塊：系統獲取用戶輸入的內容，遍歷圖并比較每一結點的人物姓名項與用戶輸入的人物A姓名，發現相同時，遍歷這一結點的所有邊，并比較每條邊另一結點與用戶輸入的人物B姓名，發現相同時，以QString的形式返回此邊的人物關系信息。若未找到直接關系，則用迪杰斯特拉算法求兩個結點之間的最短通路并存儲到數組中，以QString的形式返回中間人物的姓名。按關系查詢人物模塊：系統獲取用戶輸入的內容，遍歷圖并比較每一結點的人物姓名項與用戶輸入的姓名，發現相同時，遍歷這一結點的所有邊，并比較每條邊另一結點與用戶輸入的關系內容，發現相同時，以QString的形式返回此邊的另一個結點內容。人物關系分析模塊：分為四個部分，分別介紹：程度中心性分析：即求結點的度，再除以所有的結點數目-1，以float的形式返回程度中心性。親近中心性分析：先通過迪杰斯特拉算法求出所有此結點出發的通路，將每條通路的長度相加，再求倒數，以float的形式返回親近中心性。中介中心性分析：先通過弗洛伊德算法求出圖中所有最短通路，并統計通過此節點的通路個數和所有通路個數，再求兩個數據的比值，以float的形式返回中介中心性。核心人物分析：計算并顯示系統中每個人物的程度中心性且按從小到大排序，從而分析出程度中心性最高的人物為核心人物，并以QString形式返回其簡介。

4系統實現與測試4.1系統實現《紅樓夢》人物關系系統應具有一定的界面，支持人物關系的查詢（包括直接關系和間接關系），支持查詢特定人物的特定關系者，支持查詢人物的詳細信息。人物關系數據以文件形式保存。用中心性分析和核心人物分析兩種分析模型進行分析，能夠將分析所得人物關系結果直觀顯示。系統應能存儲不少于100人的人物信息以及相互關系。應用的數據結構及函數如下：typedefenum{unvisited,visited}VisitIf;typedefstructchara_info{//人物信息類型QStringname;intgen;//性別，1為男，0為女QStringcinfo;//人物簡介}pers;typedefstructEBox{VisitIfmark;intivex,jvex;structEBox*ilink,*jlink;QStringrinfo;}EBox;typedefstructVexBox{persdata;EBox*firstedge;}VexBox;typedefstruct{VexBoxadjmulist[120];intvexnum,edgenum;}AMLGraph;typedefstructvex_rela{QStringivex,jvex;QStringrinfo;}vex_rela;typedefstructDEG{floatd;intloc;}DEG;boolcreate_graph(AMLGraph&G,VexBoxV[],vex_relaVR[]);voidtravers(AMLGraphG);boolget_info(VexBoxV[],vex_relaVR[]);intget_vex(AMLGraphG,QStringsearch);QStringsearch_rela(AMLGraphG,QStringnamea,QStringnameb);floatget_degree(AMLGraphG,intloc);floatShortestPath(AMLGraphG,intv);floatfloyd(AMLGraphG,intv0);QStringcore(AMLGraphG);intpartition(DEGdeg[],intlow,inthigh);voidQSort(DEGdeg[],intlow,inthigh);QStringfind_pers(AMLGraph,intv,QStringserela);QStringfind_path(AMLGraphG,intv1,intv2);voiddestroy_graph(AMLGraphG);程序詳見附錄。4.2系統測試菜單界面：顯示四個功能人物信息查詢：用戶輸入姓名，顯示人物信息。輸入信息正確時：輸入信息錯誤時：查找人物關系：查詢任意兩個人物之間的關系，如果兩個人有直接關系（即兩個結點相鄰）則顯示關系信息，如果兩個人之間無直接關系但有間接關系（即兩個結點不相鄰但有通路）則顯示兩個人之間的關系鏈，即顯示通路上每一結點的人物姓名。若兩個人之間無關系（即兩個結點之間無通路），則顯示“人物之間無關系”。按關系查詢：人物關系分析：程序除了界面不太好看之外，基本滿足了設計要求。

5總結與展望5.1全文總結在這次課程設計過程中，我所做的主要工作如下：（1）通過查閱論文、網絡搜索等方式學習社會網絡分析技術的概念，找到適用于本課程設計的分析方法。（2）詳細學習中心性分析法，搞清楚程度中心性、親近中心性和中介中心性三個指標應該如何求得，再查書、查百度找合適的算法。（3）學習Qt和一些C++的知識，制作可視化界面。5.1工作展望這次的課程設計還有很多不盡人意的地方。比如算法過于單一、功能比較少、界面太過簡單不好看等。在以后的課程設計中，我將更把注意力放在功能上，盡量用更好地算法寫更多功能。同時在界面的美化上下一些功夫，做出好看的界面。

6體會通過這次完成課程設計，我能更加深刻地理解圖、無向圖的鄰接多重表存儲結構和與圖相關的算法（如弗洛伊德算法），將課本上的知識付諸實踐，并且提高了運用知識的熟練度。初步了解了界面的制作方法，學習了Qt的基礎知識。同時意識到了C++等面向對象編程思想的重要性，不理解這種思想，就不能很好地使用Qt或者MFC做界面。現在學習過的C遠遠不夠用，還需多學一些。

參考文獻[1]孫曉玲,林鴻飛.人際網絡關系抽取和結構挖掘.微電子學與計算機,2008,25(9):233-236[2]杜一鳴,滕桂法,馬建斌.社會網絡搜索關鍵技術研究概述.情報分析與研究，2010，189(2):68-73[3]徐偉,陳光輝,曾玉.關系研究的新取向:社會網絡分析.心理科學，2011，34（2）：499-504[4]張樹人,劉穎,陳禹.社會網絡分析在組織管理中的應用.中國人民大學學報，2006，（3）：74-80[5]韓毅.社會網絡分析與挖掘的若干關鍵問題研究.國防科學技術大學博士學位論文，2011.6[6]MohsenJamaliandHassanAbolhassani.DifferentAspectsofSocialNetworkAnalysis.[7]KateEhrlichandIngaCarboni.InsideSocialNetworkAnalysis.[8][9]嚴蔚敏,吳偉民.數據結構（C語言版）.北京:清華大學出版社,1997[10]王曉東.計算機算法設計與分析.北京:電子工業出版社,2007

附錄程序源碼function.h源碼：#ifndefFUNCTION_H#defineFUNCTION_H#include<stdio.h>#include<string.h>#include<stdlib.h>#include<QString>#include<QMessageBox>typedefenum{unvisited,visited}VisitIf;typedefstructchara_info{//人物信息類型QStringname;intgen;//性別，1為男，0為女QStringcinfo;//人物簡介}pers;typedefstructEBox{VisitIfmark;intivex,jvex;structEBox*ilink,*jlink;QStringrinfo;}EBox;typedefstructVexBox{persdata;EBox*firstedge;}VexBox;typedefstruct{VexBoxadjmulist[120];intvexnum,edgenum;}AMLGraph;typedefstructvex_rela{QStringivex,jvex;QStringrinfo;}vex_rela;typedefstructDEG{floatd;intloc;}DEG;boolcreate_graph(AMLGraph&G,VexBoxV[],vex_relaVR[]);voidtravers(AMLGraphG);boolget_info(VexBoxV[],vex_relaVR[]);intget_vex(AMLGraphG,QStringsearch);QStringsearch_rela(AMLGraphG,QStringnamea,QStringnameb);floatget_degree(AMLGraphG,intloc);floatShortestPath(AMLGraphG,intv);floatfloyd(AMLGraphG,intv0);QStringcore(AMLGraphG);intpartition(DEGdeg[],intlow,inthigh);voidQSort(DEGdeg[],intlow,inthigh);QStringfind_pers(AMLGraph,intv,QStringserela);QStringfind_path(AMLGraphG,intv1,intv2);voiddestroy_graph(AMLGraphG);#endif//FUNCTION_Hfunction.cpp源碼：#include<function.h>#include<QMessageBox>#include<QFile>#include<QTextStream>#include<QString>boolget_info(VexBoxV[],vex_relaVR[]){//讀取文件信息inti=0;//QStringen;//節點讀取QFile*vQFile(":/");if(!vfile->open(Q)){returnfalse;}QTextStreamvin(vfile);V[i].=vin.readLine();V[i].data.gen=vin.readLine().toInt();V[i].data.cinfo=vin.readLine();//en=vin.readLine();i++;while(!V[i-1]..isNull()){V[i].=vin.readLine();V[i].data.gen=vin.readLine().toInt();V[i].data.cinfo=vin.readLine();//en=vin.readLine();if(++i==120)break;}//邊讀取i=0;QFile*vrQFile(":/");if(!vrfile->open(Q)){returnfalse;}QTextStreamvrin(vrfile);VR[i].ivex=vrin.readLine();VR[i].jvex=vrin.readLine();VR[i].rinfo=vrin.readLine();i++;while(!VR[i-1].ivex.isNull()){VR[i].ivex=vrin.readLine();VR[i].jvex=vrin.readLine();VR[i].rinfo=vrin.readLine();i++;}returntrue;}intget_vex(AMLGraphG,QStringsearch){inti,j;for(i=0;i<120;i++){//j=strcmp(search,G.adjmulist[i].);j=QString::compare(search,G.adjmulist[i].);if(!j)returni;//if(search==G.adjmulist[i].)returni;}return-1;}QStringsearch_rela(AMLGraphG,QStringnamea,QStringnameb){QStringoutput;intm,n;EBox*p;intpath[G.vexnum];m=get_vex(G,namea);n=get_vex(G,nameb);if(m==-1||n==-1){return"未找到人物！";}p=G.adjmulist[m].firstedge;while(p){if(p->ivex==m){if(p->jvex==n)break;p=p->ilink;}elseif(p->jvex==m){if(p->ivex==n)break;p=p->jlink;}}if(!p){//printf("兩人無直接關系！\n\n查找間接關系：\n");output=find_path(G,m,n);//if(path[1]==-1)printf("未找到兩人關系！\n");if(output=="")return"未找到人物關系！";returnoutput;}//printf("兩人關系為：%s\n",p->rinfo);output=p->rinfo;returnoutput;}floatget_degree(AMLGraphG,intloc){//求人物程度中心性intdegree=0;floatma,av;ma=G.vexnum-1;EBox*p;if(G.adjmulist[loc].data.gen==-1){// printf("不存在所查人物！\n");return-1;}if(!G.adjmulist[loc].firstedge){// printf("人物程度中心性為：0！\n");return0;}if(loc==G.adjmulist[loc].firstedge->ivex){for(p=G.adjmulist[loc].firstedge;p;){degree++;if(p->ivex==loc)p=p->ilink;elseif(p->jvex==loc)p=p->jlink;}}elseif(loc==G.adjmulist[loc].firstedge->jvex){for(p=G.adjmulist[loc].firstedge;p;){degree++;if(p->ivex==loc)p=p->ilink;elseif(p->jvex==loc)p=p->jlink;}}av=degree/ma;returnav;}floatShortestPath(AMLGraphG,intv0){//求人物親近中心inti,v,w,min,final[G.vexnum],D[G.vexnum],dis=0,path[G.vexnum][G.vexnum];EBox*p;floata=1,b;for(v=0;v<G.vexnum;++v){final[v]=0;//當final[v]=1即已求得v0->v的最短路徑D[v]=10000;path[v][v]=10000;}for(i=0;i<G.vexnum;i++){p=G.adjmulist[i].firstedge;while(p){if(i==p->ivex){path[i][p->jvex]=1;path[p->jvex][i]=1;p=p->ilink;}else{path[i][p->ivex]=1;path[p->ivex][i]=1;p=p->jlink;}}}if(v0==G.adjmulist[v0].firstedge->ivex){for(p=G.adjmulist[v0].firstedge;p;){if(p->ivex==v0){D[p->jvex]=1;//無權圖，相當于所有權值都為1p=p->ilink;}elseif(p->jvex==v0){D[p->ivex]=1;p=p->jlink;}}}//v=ivex情況elseif(v0==G.adjmulist[v0].firstedge->jvex){for(p=G.adjmulist[v0].firstedge;p;){if(p->ivex==v0){D[p->jvex]=1;p=p->ilink;}elseif(p->jvex==v0){D[p->ivex]=1;p=p->jlink;}}}//v=jvex情況D[v0]=0;final[v0]=1;//D初始化完成for(i=1;i<G.vexnum;++i){min=10000;//min是目前的離v0最近距離，初始化為∞for(w=0;w<G.vexnum;++w)if(!final[w])if(D[w]<min){//當w頂點離v0更近v=w;min=D[w];}final[v]=1;for(w=0;w<G.vexnum;++w){if(!final[w]&&(min+path[v][w]<D[w])){//如果min+1更近，修改當前D[W]D[w]=min+1;}}//更新當前最距離完成}//對其余頂點循環for(i=0;i<G.vexnum;i++){// printf("d=%d",D[i]);dis+=D[i];}b=a/dis;returnb;//printf("人物親近中心性為：%4f\n",b);}//求人物親近中心floatfloyd(AMLGraphG,intv0){//求人物中介中心性intD[G.vexnum][G.vexnum];//D[v][w]是從v到w最短距離intu,v,w,i,num=0,total=0,disa=0,disb=0;floatdisaf,degree;EBox*p;for(v=0;v<G.vexnum;++v){for(w=0;w<G.vexnum;++w)D[v][w]=10000;//D初值為∞}for(v=0;v<G.vexnum;++v){while(!G.adjmulist[v].firstedge)v++;for(w=0;w<G.vexnum;++w){if(v==G.adjmulist[v].firstedge->ivex){for(p=G.adjmulist[v].firstedge;p;){if(p->ivex==v){D[v][p->jvex]=1;//無權圖，相當于所有權值都為1p=p->ilink;}elseif(p->jvex==v){D[v][p->ivex]=1;p=p->jlink;}}}//v=ivex情況elseif(v==G.adjmulist[v].firstedge->jvex){for(p=G.adjmulist[v].firstedge;p;){if(p->ivex==v){D[v][p->jvex]=1;p=p->ilink;}elseif(p->jvex==v){D[v][p->ivex]=1;p=p->jlink;}}}//v=jvex情況//D初始化完成}}//各對節點之間初始已知路徑及距離填充完成for(u=0;u<G.vexnum;++u){for(v=0;v<G.vexnum;++v){for(w=0;w<G.vexnum;++w){if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];}}}D[u][u]=0;}//統計for(v=0;v<G.vexnum;++v){for(w=0;w<G.vexnum;++w){if(D[v][w]<10000){total++;disb+=D[v][w];}}}for(v=0;v<G.vexnum;++v){if(v==v0)v++;if(v>=G.vexnum)break;for(w=0;w<G.vexnum;++w){if(w==v0)w++;if(w>=G.vexnum)break;if(D[v][w]<10000)if(D[v][v0]+D[v0][w]<=D[v][w]){disa+=D[v][w];num++;}if(D[v][w]<10000){}}}num=num/2;total=total-G.vexnum;total=total/2;disaf=disa;degree=disaf/disb;//printf("人物中介中心性為：%4f\n",degree);returndegree;}//求人物中介中心性QStringcore(AMLGraphG){//分析獲取核心人物QStringotpt;DEGdeg[G.vexnum];inti;for(i=1;i<=G.vexnum;i++){deg[i].d=get_degree(G,i-1);deg[i].loc=i-1;}QSort(deg,1,G.vexnum);for(i=1;i<=G.vexnum;i++){//printf("%s程度中心性為：%4f\n",G.adjmulist[deg[i].loc].,deg[i].d);otpt+=G.adjmulist[deg[i].loc].;otpt+=QString("程度中心性為%1\n").arg(deg[i].d);}//printf("\n經過排序，獲得核心人物為：\n\n");otpt+="\n經過排序，獲得核心人物為：\n\n";for(i=1;i<=G.vexnum;i++){if(deg[i].d==deg[G.vexnum].d){//printf("%s，其程度中心性為：%4f\n",G.adjmulist[deg[i].loc].,deg[i].d);otpt+=G.adjmulist[deg[i].loc].;otpt+=QString(",其程度中心性為%1\n").arg(deg[i].d);//printf("人物簡介：%s\n\n",G.adjmulist[deg[i].loc].data.cinfo);}otpt+="人物簡介：";otpt+=G.adjmulist[deg[i].loc].data.cinfo;}}returnotpt;}intpartition(DEGdeg[],intlow,inthigh){deg[0]=deg[low];floatpivokey=deg[low].d;while(low<high){while(low<high&°[high].d>=pivokey)--high;deg[low]=deg[high];while(low<high&°[low].d<=pivokey)++low;deg[high]=deg[low];}deg[low]=deg[0];returnlow;}//分析獲取核心人物voidQSort(DEGdeg[],intlow,inthigh){if(low<high){intx=partition(deg,low,high);QSort(deg,low,x-1);QSort(deg,x+1,high);}}QStringfind_pers(AMLGraphG,intv,QStringserela){EBox*p;inta=1,b=0;QStringotpt=G.adjmulist[v].;otpt+="的";otpt+=serela;otpt+="有:\n";p=G.adjmulist[v].firstedge;while(p){//a=strcmp(serela,p->rinfo);a=QString::compare(serela,p->rinfo);if(p->ivex==v){if(!a){b=1;//printf("%s ",G.adjmulist[p->jvex].);otpt+=G.adjmulist[p->jvex].;otpt+="";}p=p->ilink;}else{if(!a){//printf("%s ",G.adjmulist[p->ivex].);otpt+=G.adjmulist[p->ivex].;otpt+="";b=1;}p=p->jlink;}}if(!b)return"未找到！\n";returnotpt;}QStringfind_path(AMLGraphG,intv1,intv2){QStringoutput;EBox*p;intD[G.vexnum],pa[G.vexnum],final[G.vexnum],path[G.vexnum][G.vexnum];inti,j,min,v,w;for(i=0;i<G.vexnum;i++){pa[i]=v1;//到點i的前驅頂點D[i]=10000;//到點i的距離for(j=0;j<G.vexnum;j++)path[i][j]=10000;final[i]=0;}for(i=0;i<G.vexnum;i++){p=G.adjmulist[i].firstedge;while(p){if(i==p->ivex){path[i][p->jvex]=1;path[p->jvex][i]=1;p=p->ilink;}else{path[i][p->ivex]=1;path[p->ivex][i]=1;p=p->jlink;}}}p=G.adjmulist[v1].firstedge;while(p){if(v1==p->ivex){D[p->jvex]=1;p=p->ilink;}elseif(v1==p->jvex){D[p->ivex]=1;p=p->jlink;}}D[v1]=0;final[v1]=1;for(i=1;i<G.vexnum;++i){min=10000;for(j=0;j<G.vexnum;++j){if(!final[j])if(D[j]<min){min=D[j];v=j;}final[v]=1;}for(j=0;j<G.vexnum;++j){if(!final[j]&&(min+path[v][j]<D[j])){D[j]=min+path[v