【正文】 return TRUE。==) // 到達(dá)終點(diǎn) (出口 ) { DestroyStack(amp。 // 足跡加 1 if(==amp。S,e)。 =0。 =。 do { if(Pass(curpos)) { // 當(dāng)前位置可以通過，即是未曾走到過的通道塊 迷宮 FootPrint(curpos)。S)。 SElemType e。 Status MazePath(PosType start,PosType end) { SqStack S。 進(jìn)入 TC 核心代碼 迷宮 若迷宮 maze中存在從入口 start到出口 end的通道，則求得一條。 ? 初始定義時(shí)若該位置可通用 1表示，若該位置不通用 0表示。 迷宮 ? 算法思想：在算法中以二維坐標(biāo)定義一個(gè)當(dāng)前位置，若當(dāng)前位置可通，則納入當(dāng)前路徑（入棧），并按照東南西北的順序繼續(xù)下一位置探索，即切換下一位置為當(dāng)前位置，重復(fù)直至到達(dá)出口。 } 直接插入排序執(zhí)行結(jié)果 快速排序執(zhí)行結(jié)果 綜合訓(xùn)練 ?迷宮 ?稀疏矩陣相乘 ?最優(yōu)二叉樹 ?最小生成樹 ?關(guān)鍵路徑 ?最短路徑 退出 迷宮 在計(jì)算機(jī)中用下圖所示的方塊表示迷宮，圖中空白方塊表示為通道，帶陰影線的方塊表示為墻，帶豎線條的為入口處，橫線條的為出口處。 printf(\nDatalist after sort:\n)。QuickSort(amp。print(la)。[i].key)。i=。 printf(Input elements seperated by blank:)。 scanf(%d,amp。 clrscr()。SqList la。 主要思想是：在輸入關(guān)鍵字時(shí)進(jìn)行判斷，有重復(fù)的 加以標(biāo)識。 printf(\n)。i=。 void print(SqList L) { int i。 void QuickSort(SqList *L) { QSort(L,1,(*L).length)。 QSort(L,pivotloc+1,high)。 if(lowhigh) { pivotloc=Partition(L,low,high)。 遞歸調(diào)用快速排序函數(shù)實(shí)現(xiàn)一個(gè)無序序列的關(guān)鍵字的排序。 return low。i=(*L).length。 printf(\nNo.%d sort: ,++count)。 (*L).r[high]=(*L).r[low]。amp。 (*L).r[low]=(*L).r[high]。amp。 pivotkey=(*L).r[low].key。 int i。 快速排序 int Partition(SqList *L,int low,int high) {//一趟快速排序。 int length。 }TElemType。 define MAXSIZE 20 typedef int KeyType。la)。 printf(Datalist after sort:)。 } printf(Datalist before sort:\n)。i++){ scanf(%d,amp。 for(i=1。)。 printf(Input datanum:)。 int I。 進(jìn)入 TC 主函數(shù) void main() { ElemType *d。 } 主函數(shù) 算法思想 ： 本函數(shù)依然使用輸入待排序的關(guān)鍵字個(gè)數(shù)來控制輸入的關(guān)鍵字，輸入關(guān)鍵字時(shí)用空格分隔。i++) printf(%d ,[i].key)。 for(i=1。k++) printf(%d ,(*L).r[k].key)。 for(。k++) printf( %d,(*L).r[k].key)。 for(k=2。 } ? 直接插入排序 printf(\ni=%d: (%d) ,i,[i].key)。j) (*L).r[j+1]=(*L).r[j]。 for(j=i1。i=(*L).length。 printf( )。 SqList temp。 }SqList。 typedef struct { ElemType r[MAXSIZE+1]。 }ElemType。 存儲結(jié)構(gòu) 源程序 主函數(shù) 直接插入排序 — 存儲結(jié)構(gòu) define MAXSIZE 20 typedef int KeyType。 實(shí)驗(yàn)內(nèi)容 ? 直接插入排序 ? 快速排序 退出 快速排序 ?存儲結(jié)構(gòu) ?快速排序算法函數(shù) ?輸出結(jié)果函數(shù) ?主函數(shù) 直接插入排序 注意：對每一個(gè)關(guān)鍵字的排序都有輸出 。 } 進(jìn)入 TC 鄰接矩陣創(chuàng)建無向圖執(zhí)行結(jié)果 廣度優(yōu)先遍歷執(zhí)行結(jié)果 實(shí)驗(yàn)八：實(shí)驗(yàn)?zāi)康募耙? ?理解排序的概念，及直接插入排序、快速排序算法的思想。 DestroyGraph(amp。 printf(Breadth_First Search:\n)。G)。 ? } 主函數(shù) main() { ALGraph G。Q,w)。 ? Visit([w].data)。w=0。 ? strcpy(u1,*GetVex(G,u))。Q,amp。Q,v)。 ? Visit([v].data)。v。Q)。++v) ? visited[v]=FALSE。 ? for(v=0。 ? VertexType u1,w1。 關(guān)于隊(duì)列的操作不在描述 。 注：這里用到了隊(duì)列 ,因?yàn)樗南冗M(jìn)先出的特點(diǎn) ,能夠方便地輸出圖中的頂點(diǎn) ,實(shí)現(xiàn)“ 先被訪問的頂點(diǎn)的鄰接點(diǎn) ” 先于 “ 后被訪問的頂點(diǎn)的鄰接點(diǎn) ” 被訪問 。 ? } ? printf(\n)。 ? while(p) ? { ? printf(%d,padjvex)。printf(%d:,i)。i。 ? printf(\n)。 ? } ? } ? } 輸出圖的鄰接表 ? void Display(ALGraph G) ? { ? int i。 ? free(p)。 ? while(p) ? { ? q=pnextarc。i(*G).vexnum。 (*G).arum=0。 ArcNode *p,*q。 ? else ? return pnextarcadjvex。padjvex!=w1) ? p=pnextarc。 ? while(pamp。 ? w1=LocateVex(G,w)。 ? int v1,w1。 } 標(biāo)注：在鄰接表的頂點(diǎn)向量中查找指定的頂點(diǎn) v，返回頂點(diǎn) v的第一個(gè)鄰接點(diǎn)，如存在返回鄰接表中弧結(jié)點(diǎn)的信息，如沒有返回 1 查找指定頂點(diǎn)的鄰接點(diǎn) ? //返回下一個(gè)鄰接點(diǎn)。 if(p) return padjvex。 v1=LocateVex(G,v)。 ? } 查找指定頂點(diǎn)的鄰接點(diǎn) int FirstAdjVex(ALGraph G,VertexType v) { ArcNode *p。 ? (*G).vertices[j].firstarc=p。 pinfo=NULL。 ? p=(ArcNode*)malloc(sizeof(ArcNode))。 ? pnextarc=(*G).vertices[i].firstarc。 ? padjvex=j。 ? if(i==1||j==1) ? exit(0)。 i=LocateVex(*G,va)。k(*G).arum。 ? } ? printf(Please input vex1 and vex2 separated by blank:\n)。++i) ? { ? scanf(%s,(*G).vertices[i].data)。 ? for(i=0。(*G).arum)。 ? scanf(%d,%d,amp。 ? (*G).kind = DN。 ? VertexType va,vb。如果實(shí)現(xiàn)有向圖的創(chuàng)建，在此就應(yīng)該只生成一個(gè)弧結(jié)點(diǎn)。而在有向圖中就不是這樣，如在有向圖中 v1到 v2有一條弧，描述成 v1， v2，表示從 v1到 v2有一弧，如果在有向圖的定義中沒有指明 v2， v1，則不存在從 v2到 v1的弧。 }ALGraph。 //頂點(diǎn)的向量 int vexnum,arum。 typedef struct {//圖的結(jié)構(gòu)。 //頂點(diǎn)信息 ArcNode *firstarc。 typedef struct{//鄰接表的頂點(diǎn)結(jié)構(gòu)。 //指向下一條弧的指針 InfoType *info。 typedef struct ArcNode{ int adjvex。 void(*VisitFunc)(char* v)。 QueuePtr front,rear。 }QNode,*QueuePtr。 typedef struct QNode { QElemType data。 Bool visited[MAX_VERTEX_NUM]。 typedef enum{DG,DN,UDG,UDN}GraphKind。 typedef int QElemType。 } 進(jìn)入 TC 鄰接表存儲結(jié)構(gòu) define MAX_VERTEX_NUM 20 define OK 1 define ERROR 0 define OVERFLOW 2 typedef int InfoType。G)。 clrscr()。 printf(\n)。j++) if([i][j].adj==INFINITY) printf( *)。i++) { for(j=0。 for(i=0。++i) printf([%d]=%s\n,i,[i])。 for(i=0。 return 1。i。 int i。 ? }(*G).kind=UDN。 j=LocateVex(*G,vb)。w)。k(*G).arum。 } ? printf(Input details(eg. V1 V2 5): \n)。++j){ ? (*G).arcs[i][j].adj=INFINITY。++i) ? for(j=0。 ? for(i=0。i(*G).vexnum。 ? printf(Please input %d vexs:\n,(*G).vexnum)。(*G).vexnum,amp。 ? printf(Please input vexnum, arum:)。 流程圖 源代碼 創(chuàng)建無向圖 開始 輸入 無向網(wǎng)的 頂點(diǎn) 數(shù) 、弧數(shù) 輸入各個(gè)頂點(diǎn) 如： 用兩層循環(huán)創(chuàng)建圖的鄰接矩陣，每個(gè)值為最大值 k =0 k 弧 數(shù) ? N Y k +1 輸入 弧的兩個(gè) 頂點(diǎn) 、權(quán)值