【導(dǎo)讀】數(shù)據(jù)結(jié)構(gòu)旨在使讀者學(xué)會(huì)分析研究數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)的組織方法，題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示和處理。解決實(shí)際問(wèn)題的能力。實(shí)現(xiàn)通訊錄的建立和輸出、通訊者的插入、刪除和查詢(xún)等幾種操作功能。*：使用數(shù)字0~5來(lái)選擇菜單項(xiàng)，其他輸入無(wú)效，并給出錯(cuò)誤提示。運(yùn)行，并且要考慮到未建立通訊錄鏈表的情況下其他功能無(wú)法實(shí)現(xiàn)的情況。為了達(dá)到選擇各功能,采用switch判定選擇項(xiàng)并跳轉(zhuǎn)入相應(yīng)功能函數(shù)。實(shí)現(xiàn)分別用了不同函數(shù)，并且有用到函數(shù)的嵌套以減少代碼的重復(fù)。實(shí)現(xiàn)循環(huán)運(yùn)行的功能時(shí)定義一個(gè)變量j=1，在選擇退出后再將j賦值為0，使尾指針指向新結(jié)點(diǎn)；提示是否繼續(xù)建表，讀入一個(gè)結(jié)束的標(biāo)志；尾結(jié)點(diǎn)的指針域置空置NULL。序通訊表相應(yīng)位置，以保持通訊錄的有序性。插入的基本思想是：

　　

【正文】 。 if(b!=NULL) printf(%c,bdata)。 rear++。 23 Qu[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)輸出二叉樹(shù) :)。DispBTNode (b)。printf(\n)。 printf((2)層次遍歷序列： )。TravLevel(b)。printf(\n)。 printf((3)先序遍歷序列： )。PreOrder(b)。printf(\n)。 } 設(shè)計(jì)總結(jié)： 二叉樹(shù)是數(shù)據(jù)結(jié)構(gòu)的的基本內(nèi)容。雖然程序規(guī)模不大，我依然付出了努力 ， 仍免不了各種錯(cuò)誤的出現(xiàn)。編程過(guò)程需要很大的毅力和耐心，而且要有良好的思維和扎實(shí)的專(zhuān)業(yè)基礎(chǔ)知識(shí)，所以我需要不斷的學(xué)習(xí)，發(fā)現(xiàn)自身不足之處改正它，逐步提高自己。 24 需求分析： 設(shè)計(jì)分析： 拓?fù)渑判虻倪^(guò)程中要求找到入度為 0的頂點(diǎn)，所以采用鄰接表來(lái)存儲(chǔ)有向圖，而要得到鄰接表，則先定義有向圖的鄰接矩陣結(jié)構(gòu)，再把鄰接矩陣轉(zhuǎn)化成鄰接表。 在具體實(shí)現(xiàn)拓?fù)渑判虻暮瘮?shù)中，當(dāng)某個(gè)頂點(diǎn)的入度為 0（沒(méi)有前驅(qū)頂點(diǎn)）時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減 1，為了避免重復(fù)檢測(cè)入度為 0的頂點(diǎn)，設(shè)立一個(gè)棧 St，以存放入度為 0的頂點(diǎn)。 源程序代碼： include include define MAXV 10 // 最大頂點(diǎn)個(gè)數(shù) typedef struct { int edges[MAXV][MAXV]。 // 鄰接矩陣的邊數(shù)組 int n。 // 頂點(diǎn)數(shù) }MGraph。 typedef struct ANode { int adjvex。 // 該弧的終點(diǎn)位置 struct ANode * nextarc。 // 指向下一條 弧的指針 }ArcNode。 typedef struct { int no。 // 頂點(diǎn)信息 int count。 // 頂點(diǎn)入度 25 ArcNode * firstarc。 // 指向第一條弧 }VNode, AdjList[MAXV]。 typedef struct { AdjList adjlist。 // 鄰接表 int n。 // 圖的頂點(diǎ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 的指針為 top ArcNode * p。 for (i=0。 iGn。 i++) // 入度置初值為 0 Gadjlist[i].count = 0。 for (i=0。 iGn。 i++) // 求所有頂點(diǎn)的入度 { p=Gadjlist[i].firstarc。 26 while (p!=NULL) { Gadjlist[padjvex].count++。 p=pnextarc。 } } for (i=0。 iGn。 i++) if (Gadjlist[i].count==0) // 入度為 0 的頂點(diǎn)進(jìn)棧 { top++。 St[top] = i。 } while (top1) // 棧不為空時(shí)循環(huán) { i = St[top]。 top。 // 出棧 a[flag++]=i。 // 輸出頂點(diǎn) p=Gadjlist[i].firstarc。 // 找第一個(gè)相鄰頂點(diǎn) while (p!=NULL) { j = padjvex。 Gadjlist[j].count。 if (Gadjlist[j].count==0) { top++。 St[top] = j。 // 入度為 0 的相鄰頂點(diǎn)進(jìn)棧 } p = pnextarc。 // 找下一個(gè)相鄰頂點(diǎn) } } if (flagGn) printf(該圖存在回路，不存在拓?fù)湫蛄?!\n)。 else { printf(該圖的一個(gè)拓?fù)湫蛄袨?:)。 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(請(qǐng)輸入圖的頂點(diǎn)數(shù) :)。 scanf(%d, amp。)。 printf(請(qǐng)輸入圖的鄰接矩陣 :\n)。 for(i=0。 i。 i++) for(j=0。 j。 j++) scanf(%d, amp。[i][j])。 MatTolist(g, G)。 TopSort(G)。 } 測(cè)試用例： 對(duì) 圖 — 1 有向圖進(jìn)行拓?fù)渑判?，由于圖中存在回路，則無(wú)法得到拓?fù)湫蛄? 圖 — 1 2 0 3 4 1 28 對(duì)圖 — 2 有向圖進(jìn)行拓?fù)渑判?，得到拓?fù)湫蛄? 實(shí)驗(yàn)總結(jié)： 通過(guò)對(duì)有向圖進(jìn)行拓?fù)渑判?讓 我了解 到 有向圖的鄰接矩陣和鄰接 表的存儲(chǔ)結(jié)構(gòu)以及它們之間的相互轉(zhuǎn)化，學(xué)會(huì)了對(duì)有向圖的拓?fù)渑判蛩惴ǎ?與棧聯(lián)系起來(lái)找到拓?fù)湫蛄?， 但 是， 這種 算法只能找到一條拓?fù)湫蛄校?所以該算法仍需改進(jìn)。1 1 0 2 3 4