【正文】 Y 遍歷標(biāo)記 = “ F ” ？ N Y 修改該頂點(diǎn)的遍歷標(biāo)記“ F → T ” 輸出頂點(diǎn) w 將 w 插入到鏈隊(duì)列中 取 u1 的下一個鄰接點(diǎn) 廣度優(yōu)先算法 ? void BFSTraverse(ALGraph G,void(*Visit)(char*)) ? { ? int v,u,w。 ? VertexType u1,w1。 ? LinkQueue Q。 ? for(v=0。v。++v) ? visited[v]=FALSE。 ? InitQueue(amp。Q)。 ? for(v=0。v。v++) ? if(!visited[v]) ? { ? visited[v]=TRUE。 ? Visit([v].data)。 ? EnQueue(amp。Q,v)。 廣度優(yōu)先算法 ? while(!QueueEmpty(Q)) ? { ? DeQueue(amp。Q,amp。u)。 ? strcpy(u1,*GetVex(G,u))。 ? for(w=FirstAdjVex(G,u1)。w=0。 ? w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) ? if(!visited[w]){ ? visited[w]=TRUE。 ? Visit([w].data)。 ? EnQueue(amp。Q,w)。 ? } ? } ? } ? printf(\n)。 ? } 主函數(shù) main() { ALGraph G。 CreateGraph(amp。G)。 Display(G)。 printf(Breadth_First Search:\n)。 BFSTraverse(G,print)。 DestroyGraph(amp。G)。 } 進(jìn)入 TC 鄰接矩陣創(chuàng)建無向圖執(zhí)行結(jié)果 廣度優(yōu)先遍歷執(zhí)行結(jié)果 實(shí)驗(yàn)八：實(shí)驗(yàn)?zāi)康募耙? ?理解排序的概念，及直接插入排序、快速排序算法的思想。 ?在 C語言環(huán)境中將一個無序序列的數(shù)據(jù)元素，按照直接插入排序和快速排序的算法分別重新排列成按關(guān)鍵字有序。 實(shí)驗(yàn)內(nèi)容 ? 直接插入排序 ? 快速排序 退出 快速排序 ?存儲結(jié)構(gòu) ?快速排序算法函數(shù) ?輸出結(jié)果函數(shù) ?主函數(shù) 直接插入排序 注意：對每一個關(guān)鍵字的排序都有輸出 。 開始排序后 ， 第一個輸出語句指明是第幾趟排序 ， 第二個輸出語句指明是哪個關(guān)鍵字排序 ， 第三個輸出語句通過循環(huán)實(shí)現(xiàn)已排序的關(guān)鍵字的輸出 ， 并且用括號括起來 ， 以示與未排序的關(guān)鍵字的區(qū)別 ， 第四個輸出語句也是通過循環(huán)輸出尚未排序的關(guān)鍵字 。 存儲結(jié)構(gòu) 源程序 主函數(shù) 直接插入排序 — 存儲結(jié)構(gòu) define MAXSIZE 20 typedef int KeyType。 typedef struct { KeyType key。 }ElemType。 //用順序存儲的線性表來存儲待排序的關(guān)鍵字。 typedef struct { ElemType r[MAXSIZE+1]。 int length。 }SqList。 直接插入排序 void InsertSort(SqList *L) { int i,j,k。 SqList temp。 temp=*L。 printf( )。 for(i=2。i=(*L).length。++i) { if ((*L).r[i].key(*L).r[i1].key) { (*L).r[0]=(*L).r[i]。 for(j=i1。(*L).r[0].key(*L).r[j].key。j) (*L).r[j+1]=(*L).r[j]。 (*L).r[j+1]=(*L).r[0]。 } ? 直接插入排序 printf(\ni=%d: (%d) ,i,[i].key)。 printf((%d,(*L).r[1].key)。 for(k=2。k=i。k++) printf( %d,(*L).r[k].key)。 printf() )。 for(。k=(*L).length。k++) printf(%d ,(*L).r[k].key)。 } } void SqListPrint(SqList L) {//輸出順序存儲的線性表 int i。 for(i=1。i=。i++) printf(%d ,[i].key)。 printf(\n)。 } 主函數(shù) 算法思想 ： 本函數(shù)依然使用輸入待排序的關(guān)鍵字個數(shù)來控制輸入的關(guān)鍵字，輸入關(guān)鍵字時(shí)用空格分隔。需要注意的是， 0號單元作為排序時(shí)的哨兵，關(guān)鍵字從1號單元開始存儲。 進(jìn)入 TC 主函數(shù) void main() { ElemType *d。 SqList la。 int I。 clrscr()。 printf(Input datanum:)。 scanf(%d,amp。)。 printf(Input elements separated by blank:)。 for(i=1。i=。i++){ scanf(%d,amp。[i].key)。 } printf(Datalist before sort:\n)。 SqListPrint(la)。 printf(Datalist after sort:)。 InsertSort(amp。la)。 } 快速排序 存儲結(jié)構(gòu)： int count=0。 define MAXSIZE 20 typedef int KeyType。 typedef struct { KeyType key。 }TElemType。 typedef struct { TElemType r[MAXSIZE+1]。 int length。 }SqList。 快速排序 int Partition(SqList *L,int low,int high) {//一趟快速排序。 KeyType pivotkey。 int i。 (*L).r[0]=(*L).r[low]。 pivotkey=(*L).r[low].key。 while(low high) { while(lowhighamp。amp。(*L).r[high].key=pivotkey) high。 (*L).r[low]=(*L).r[high]。 while(lowhighamp。amp。(*L).r[low].key=pivotkey) ++low。 (*L).r[high]=(*L).r[low]。 } (*L).r[low]=(*L).r[0]。 printf(\nNo.%d sort: ,++count)。 for(i=1。i=(*L).length。i++) printf(%d ,(*L).r[i].key)。 return low。 } 快速排序 //對順序表 L中的子序列 [low…h(huán)igh] 作快速排序。 遞歸調(diào)用快速排序函數(shù)實(shí)現(xiàn)一個無序序列的關(guān)鍵字的排序。 void QSort(SqList *L,int low,int high) { int pivotloc。 if(lowhigh) { pivotloc=Partition(L,low,high)。 QSort(L,low,pivotloc1)。 QSort(L,pivotloc+1,high)。 } } //對順序表 L作快速排序。 void QuickSort(SqList *L) { QSort(L,1,(*L).length)。 } 快速排序 //輸出存儲在線性表中的關(guān)鍵字。 void print(SqList L) { int i。 for(i=1。i=。i++) printf(%d ,[i].key)。 printf(\n)。 } 主函數(shù) 在主函數(shù)中輸入待排序的關(guān)鍵字序列。 主要思想是：在輸入關(guān)鍵字時(shí)進(jìn)行判斷，有重復(fù)的 加以標(biāo)識。 進(jìn)入 TC 代碼段 主函數(shù) void main() { TElemType *d。SqList la。 int i。 clrscr()。 printf(Input datanum:)。 scanf(%d,amp。)。 printf(Input elements seperated by blank:)。 for(i=1。i=。i++){ scanf(%d,amp。[i].key)。 } printf(Datalist befort sort:\n)。print(la)。 printf(Sorting...)。QuickSort(amp。la)。 printf(\nDatalist after sort:\n)。 print(la)。 } 直接插入排序執(zhí)行結(jié)果 快速排序執(zhí)行結(jié)果 綜合訓(xùn)練 ?迷宮 ?稀疏矩陣相乘 ?最優(yōu)二叉樹 ?最小生成樹 ?關(guān)鍵路徑 ?最短路徑 退出 迷宮 在計(jì)算機(jī)中用下圖所示的方塊表示迷宮，圖中空白方塊表示為通道，帶陰影線的方塊表示為墻，帶豎線條的為入口處，橫線條的為出口處。所求路徑必須是簡單路徑，即在求得的路徑上不能重復(fù)出現(xiàn)同一通道塊。 迷宮 ? 算法思想：在算法中以二維坐標(biāo)定義一個當(dāng)前位置，若當(dāng)前位置可通，則納入當(dāng)前路徑（入棧），并按照東南西北的順序繼續(xù)下一位置探索，即切換下一位置為當(dāng)前位置，重復(fù)直至到達(dá)出口。若當(dāng)前位置不可通，留下不能通過的標(biāo)記 1，繼續(xù)向當(dāng)前路徑的其他方向探索，若四個方向都不通，則刪除當(dāng)前路徑的棧頂元素（出棧），再將新的棧頂元素作為當(dāng)前位置繼續(xù)探索。 ? 初始定義時(shí)若該位置可通用 1表示，若該位置不通用 0表示。當(dāng)算法執(zhí)行時(shí)，迷宮的起始點(diǎn)就是所求路徑中的第 1個通道，所求的路徑依次用 3…… 表示，即通道上的二維坐標(biāo)的值由 1修改為第 N個路徑值。 進(jìn)入 TC 核心代碼 迷宮 若迷宮 maze中存在從入口 start到出口 end的通道，則求得一條。 存放在棧中 (從棧底到棧頂 )，并返回 TRUE；否則返回 FALSE。 Status MazePath(PosType start,PosType end) { SqStack S。 PosType curpos。 SElemType e。 InitStack(amp。S)。 curpos=start。 do { if(Pass(curpos)) { // 當(dāng)前位置可以通過，即是未曾走到過的通道塊 迷宮 FootPrint(curpos)。 // 留下足跡 =curstep。 =。 =。 =0。 Push(amp。S,e)。 curstep++。 // 足跡加 1 if(==amp。amp。==) // 到達(dá)終點(diǎn) (出口 ) { DestroyStack(amp。S)。 return TRU