電話薄管理系統(tǒng)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-資料下載頁
2025-04-07 21:56本頁面
【正文】 23Qu[rear]=b。while (rear!=front){front=(front+1)%MaxSize。b=Qu[front]。if(blchild!=NULL){printf(%c,blchilddata)。rear=(rear+1)%MaxSize。Qu[rear]=blchild。}if(brchild!=NULL){printf (%c,brchilddata)。rear=(rear+1)%MaxSize。Qu[rear]=brchild。}}printf(\n)。}void PreOrder(BTNode *b)//用遞歸算法的先序遍歷函數(shù){if(b!=NULL){printf (%c,bdata)。PreOrder(blchild)。PreOrder(brchild)。}}void main (){BTNode * b,*p。CreateBTNode (b,a(b(d,e),c(f,g)) )。printf((1)輸出二叉樹:)。DispBTNode (b)。printf(\n)。printf((2)層次遍歷序列：)。TravLevel(b)。printf(\n)。printf((3)先序遍歷序列：)。PreOrder(b)。printf(\n)。}設(shè)計總結(jié)：二叉樹是數(shù)據(jù)結(jié)構(gòu)的的基本內(nèi)容。雖然程序規(guī)模不大，我依然付出了努力，仍免不了各種錯誤的出現(xiàn)。編程過程需要很大的毅力和耐心，而且要有良好的思維和扎實的專業(yè)基礎(chǔ)知識，所以我需要不斷的學(xué)習(xí)，發(fā)現(xiàn)自身不足之處改正它，逐步提高自己。 24需求分析： 設(shè)計分析：拓撲排序的過程中要求找到入度為 0 的頂點，所以采用鄰接表來存儲有向圖，而要得到鄰接表，則先定義有向圖的鄰接矩陣結(jié)構(gòu)，再把鄰接矩陣轉(zhuǎn)化成鄰接表。在具體實現(xiàn)拓撲排序的函數(shù)中，當某個頂點的入度為 0（沒有前驅(qū)頂點）時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減 1，為了避免重復(fù)檢測入度為 0 的頂點，設(shè)立一個棧 St，以存放入度為 0 的頂點。源程序代碼：includeincludedefine MAXV 10 // 最大頂點個數(shù)typedef struct{int edges[MAXV][MAXV]。 // 鄰接矩陣的邊數(shù)組int n。 // 頂點數(shù)}MGraph。typedef struct ANode{int adjvex。 // 該弧的終點位置struct ANode * nextarc。 // 指向下一條弧的指針}ArcNode。typedef struct{int no。 // 頂點信息int count。 // 頂點入度 25ArcNode * firstarc。 // 指向第一條弧}VNode, AdjList[MAXV]。typedef struct{AdjList adjlist。 // 鄰接表int n。 // 圖的頂點數(shù)}ALGraph。void MatTolist(MGraph g, ALGraph * amp。G){int i, j, n=。ArcNode * p。G = (ALGraph *)malloc(sizeof(ALGraph))。for (i=0。 in。 i++)Gadjlist[i].firstarc = NULL。for (i=0。 in。 i++)for (j=n1。 j=0。 j)if ([i][j]!=0){p=(ArcNode *)malloc(sizeof(ArcNode))。padjvex = j。pnextarc = Gadjlist[i].firstarc。Gadjlist[i].firstarc = p。}Gn=n。}void TopSort(ALGraph * G){int i,j,flag=0,a[MAXV]。int St[MAXV], top = 1。 // 棧 St 的指針為 topArcNode * p。for (i=0。 iGn。 i++) // 入度置初值為 0Gadjlist[i].count = 0。 for (i=0。 iGn。 i++) // 求所有頂點的入度{p=Gadjlist[i].firstarc。 26while (p!=NULL){Gadjlist[padjvex].count++。p=pnextarc。}}for (i=0。 iGn。 i++)if (Gadjlist[i].count==0) // 入度為 0 的頂點進棧{top++。 St[top] = i。}while (top1) // 棧不為空時循環(huán){i = St[top]。 top。 // 出棧a[flag++]=i。 // 輸出頂點p=Gadjlist[i].firstarc。 // 找第一個相鄰頂點while (p!=NULL){j = padjvex。Gadjlist[j].count。if (Gadjlist[j].count==0){top++。 St[top] = j。 // 入度為 0 的相鄰頂點進棧}p = pnextarc。 // 找下一個相鄰頂點}}if (flagGn)printf(該圖存在回路，不存在拓撲序列!\n)。else{printf(該圖的一個拓撲序列為:)。for(i=0。 iflag。 i++)printf(%d, a[i])。printf(\n)。 27}}void main(){int i, j。MGraph g。ALGraph * G。G=(ALGraph *)malloc(sizeof(ALGraph))。printf(請輸入圖的頂點數(shù):)。scanf(%d, amp。)。printf(請輸入圖的鄰接矩陣:\n)。for(i=0。 i。 i++)for(j=0。 j。 j++)scanf(%d, amp。[i][j])。MatTolist(g, G)。TopSort(G)。}測試用例：對圖—1 有向圖進行拓撲排序，由于圖中存在回路，則無法得到拓撲序列圖—12 0341 2830對圖—2 有向圖進行拓撲排序，得到拓撲序列實驗總結(jié)：通過對有向圖進行拓撲排序讓我了解到有向圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)以及它們之間的相互轉(zhuǎn)化，學(xué)會了對有向圖的拓撲排序算法，與棧聯(lián)系起來找到拓撲序列，但是，這種算法只能找到一條拓撲序列，所以該算法仍需改進。 110 234
公司管理相關(guān)推薦
鄂ICP備17016276號-1