【正文】 qrear]=x。 return(0)。 }}int delete(qqtype *q) /*出隊操作*/{ if (qfront==qrear) return(NULL)。 else return(qqueue[++qfront])。}int empty(qqtype *q) /*判斷隊空否*/{ if (qfront==qrear) return(1)。 return(0)。}void dfs(adjlist g, int k, int visited[]) { arode *p。 int w。 visited[k]=1。 printf(%d, g[k].vertex)。 p=g[k].firstarc。 while(p!=NULL) { w=padjvex。 if(visited[w]==O) dfs(g, w, visited)。 p=pnextarc。 }}void bfs(adjlist g, int k, int visited[]){ arode *p。 int w。 initiate(g)。 visited[k]=1。 printf(%d, g[padjvex].vertex)。 enter(g, k)。 while (empty(g)) { w=delete(g)。 p=g[w].firstarc。 while(p) { if (visited[padjvex]==0) { printf(%d, g[padjvex].vertex)。 visited[padjvex]=1。 enter(adjvex)。 } p=pnextarc。 } }}void trave(adjlist g, int n) { int i, visited[maxnode]。 /*數(shù)組visited標志圖中的定點是否已被訪問*/ for(i=O。 in。 i++) visited[i]=O。 /*數(shù)組初始化*/ dfs(g, i, visted[])。 for(i=O。 in。 i++) visited[i]=O。 /*再次遍歷前須重新初始化*/ bfs(g, i, visted[])。}main(){ int i, j, n, k, v。 arode *p, *q。 adjlist g。 printf(Input node:)。 scanf(%d, amp。n)。 for(k=O。 kn。 k++) /*構(gòu)造圖*/ { printf(node%d=, k)。 scanf(%d, amp。g[k].vertex)。g[k].firstarc=NULL。 } for(。) { printf (Insert edge ij:)。 scanf(%d%d, amp。i, amp。j)。 if(i=1amp。amp。j==1) break。 q=(arode *)malloc(sizeof(arode))。 qadjvex=j。 qnextarc=g[i].firstarc。 g[i].firstarc=q。 p=(arode *)malloc(sizeof(arode))。 padjvex=i。 pnextarc=g[j].firstarc。 g[j].firstarc=p。 } printf(dfs and bfs:)。 trave(g, n)。 printf(\n)。}6．思考與提高a）本程序在刪除結(jié)點時采取的辦法是若被刪結(jié)點有左子樹，取被刪結(jié)點左子樹中的最右結(jié)點替代，但這個算法存在漏洞，比如按照8的順序輸入構(gòu)造二叉排序樹，然后刪除根結(jié)點10，將會出現(xiàn)與定義不符的情形，因此必須將算法改為取被刪結(jié)點右子樹中的最左結(jié)點替代，此時算法改如何修改？b）對一個無向連通圖來說，從圖中任一頂點出發(fā)，都可以訪問到圖中各個頂點。而對于非連通的無向圖則需要多次調(diào)用遍歷函數(shù)，每次調(diào)用得到的頂點訪問序列恰好是各個連通分量中的頂點集。試修改參考程序，使之能求出圖是否連通以及非連通圖中連通分量的個數(shù)。實驗三 查找及排序綜合算法設計1．實驗目的與意義1) 掌握查找的含義2) 掌握基本查找操作的算法和實現(xiàn)3) 掌握動態(tài)查找算法的實現(xiàn)、應用場合與優(yōu)缺點4) 能夠針對具體問題，靈活選用適宜的查找算法5) 掌握排序的基本概念，對排序的穩(wěn)定性及排序的時間復雜度有深刻的認識6) 對比折半插入排序和Shell排序的異同7) 掌握選擇排序中堆排序的基本思想和算法實現(xiàn)8) 掌握快速排序的基本思想和算法實現(xiàn)9) 了解歸并排序算法的基本思想和程序?qū)崿F(xiàn)10) 了解基數(shù)排序算法的基本思想和程序?qū)崿F(xiàn)11) 掌握Hash排序算法的基本思想和程序?qū)崿F(xiàn)2．基本原理和方法本實驗涉及各類查找和排序算法。靜態(tài)查找，折半查找的思想為：設查找表中的元素存放在數(shù)組r中，數(shù)據(jù)元素的下標范圍為[low, high]，要查找的關(guān)鍵字值為key，中間元素的下標為mid=|_(low + high) /2_|（向下取整），令key與r[mid]的關(guān)鍵字比較：① 若key=r[mid].key，查找成功，下標為m的記錄即為所求，返回mid。② 若keyr[mid].key，所要找的記錄只能在左半部分記錄中，再對左半部分使用折半查找法繼續(xù)進行查找，搜索區(qū)間縮小了一半。③ 若keyr[mid].key，所要找的記錄只能在右半部分記錄中，再對右半部分使用折半查找法繼續(xù)進行查找，搜索區(qū)間縮小了一半。重復上述過程，直到找到查找表中某一個數(shù)據(jù)元素的關(guān)鍵字的值等于給定的值key，說明查找成功；或者出現(xiàn)low的值大于high的情況，說明查找不成功。動態(tài)查找，編程實現(xiàn)一個開放式的高校本科招生最低錄取分數(shù)線的查詢系統(tǒng)，供師生和家長等查詢，高校自愿放入該校的信息，可能隨時有高校加入。要求實現(xiàn)的查詢功能有：①查詢等于用戶給定分數(shù)的高校；②查詢大于（或小于）用戶給定分數(shù)的高校③查詢最低錄取分數(shù)線在用戶給定的分數(shù)段中的高校。直接插入排序：將當前無序區(qū)的第一個記錄插入到有序區(qū)中適當位置。折半查找法：在有序表中進行，先確定表的中點位置，再通過比較確定下一步查找哪個半?yún)^(qū)。Shell排序：先取定一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分成d1個組，所有距離為d1倍數(shù)的記錄放在同一個組中，在各組內(nèi)進行直接插入排序；然后取第二個增量重復上述分組和排序，直至所取的增量dt=1(dtdt1…d2d1)，即所有記錄放在同一組中進行直接插入排序為止。堆排序是利用大頂堆（或小頂堆）來選取當前無序區(qū)中關(guān)鍵字最大（或最?。┑挠涗泴崿F(xiàn)排序?？焖倥判蚴菍γ芭莘ǖ母倪M，其基本思想是：通過一趟排序?qū)⒋盼募指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字值均比另一部分記錄的關(guān)鍵字小，然后分別對這兩部分進行排序，以達到整個序列有序。歸并的思想：將兩個或兩個以上的有序表合并成一個有序表。利用歸并的思想實現(xiàn)排序，假設初始的序列含有n個記錄，可以看成n個有序的子序列，每個子序列的長度為m，然后把i(≥2)個子序列歸并，得到n/i個長度為i的子序列；再繼續(xù)歸并，如此重復直到得到一個長度為n的有序序列為止。通常使用的是i=2的二路歸并法?；鶖?shù)排序的基本思想是采用多關(guān)鍵字的排序。設記錄關(guān)鍵字R[i]由d個分量ki1, ki2, …, kid組成，設每個分量的取值范圍為{ti|i=1, 2, …, m，且t1t2…tm}。準備m個箱子，先按低位分箱再按序號一次將各個非空箱子里的記錄收集起來，再對新收集起來的元素依次按較高的位分箱，直到最高位。分箱即將第s個關(guān)鍵字等于ti的全部記錄裝入第i個箱子里。按最高位分箱后，按序號一次將各個非空箱子里的記錄收集起來，得到的元素序列就是有序的。Hash排序是在Hash查找的基礎上演變而來。對待排序列采用單調(diào)的Hash函數(shù)，并用鏈地址法處理沖突，最后用一定規(guī)則收集存儲好的數(shù)據(jù)從而得到有序序列。3．主要儀器設備及耗材安裝有Turbo C++ ，無耗材要求。4．實驗方案或技術(shù)路線本實驗含有五部分內(nèi)容——靜態(tài)查找、動態(tài)查找、插入排序與選擇排序、快速排序與歸并排序、查找及排序算法集成。A．靜態(tài)查找部分查找表的存儲結(jié)構(gòu)為有序表，即表中記錄按關(guān)鍵字大小排序存放。輸入待查數(shù)據(jù)元素的關(guān)鍵字進行查找。為了簡化算法，記錄只含一個整型量關(guān)鍵字字段，記錄的其余數(shù)據(jù)部分忽略不考慮。此程序中要求對整型量關(guān)鍵字數(shù)據(jù)的輸入按從小到大排序輸入。B．動態(tài)查找部分主要的功能是查找，查找表為高校最低錄取分數(shù)信息的集合。根據(jù)題意可知，該查找表中的元素個數(shù)可能隨時增減，所以它是一個動態(tài)查找表，可采用樹狀結(jié)構(gòu)保存。為了提高查詢速度，可建立二叉排序樹并在二叉排序樹中實現(xiàn)查找。C．排序部分考慮對20個整數(shù)的隨機輸入進行排序，各排序功能基本上都可以成為獨立調(diào)用的模塊，因此可以先寫出排序算法，然后用主函數(shù)調(diào)用。5．實驗內(nèi)容及步驟A．靜態(tài)查找部分——建立一個有序表，數(shù)據(jù)元素從下標為1的單元開始放入。實現(xiàn)查找算法時，首先將low賦值為1，high等于最后一個數(shù)據(jù)元素的下標，然后將給定的關(guān)鍵字的值與查找區(qū)間[low, high]中間的數(shù)據(jù)元素的關(guān)鍵字比較，若相等，則查找成功；若小于中間數(shù)據(jù)元素的關(guān)鍵字，則在左半部分查找；若大于中間的數(shù)據(jù)元素的關(guān)鍵字，則在右半部分查找。直到找到查找表中某一個數(shù)據(jù)元素的關(guān)鍵字的值等于給定的關(guān)鍵字的值，說明查找成功；若出現(xiàn)low的值大于high的情況，說明查找不成功。【參考程序】include define KEYTYPE intdefine MAXSIZE 100typedef struct{ KEYTYPE key。 } SSELEMENT。typedef struct{ SSELEMENT r[MAXSIZE]。 int len。 }SSTABLE。int search_bin(KEYTYPE k, SSTABLE *st) /*有序表折半查找*/{ int low, high, mid。 low=1。 high=stlen。 while (low=high) /*繼續(xù)查找的條件*/ { mid=(low+high)/2。 if (k==str[mid].key) return mid。 /*查找成功*/ else if (kstr[mid].key) high=mid1。 /*否則繼續(xù)二分查找*/ else low=mid+l。 } return 0。 /*查找不成功，返回0*/}main(){ SSTABLE a。 int i, j, k。 printf(請從小到大輸入有序表元素（整型量），99為結(jié)束標志：)。 j=0。 k=1。 scanf(%d, amp。i)。 while (i!=99) { j++。 [k].key=i。 k++。 scanf(%d, amp。i)。 } /* 輸入有序表元素*/ =j。 printf(\n有序表元素列表顯示：)。 for (i=l, i=。 i++) printf(%d, [i])。 printf(\n\n輸入待查元素關(guān)鍵字：)。 scanf(%d, amp。i)。 k=search_bin(i, amp。a)。 if (k==0) printf(表中待查元素不存在\n\n)。 else printf(表中待查元素存在\n\n)。}B．動態(tài)查找部分——第一個要求可以直接利用一般的二叉排序樹的查找算法實現(xiàn)。第二個要求可以利用比較二叉排序樹根結(jié)點的關(guān)鍵字值和給定的分數(shù)實現(xiàn)，若前者大于或等于后者，根結(jié)點及其右子樹中的結(jié)點全部滿足要求，再在根結(jié)點的左子樹中查找；否則只在根結(jié)點的右子樹中查找即可。第三個要求可以利用比較二叉排序樹根結(jié)點的關(guān)鍵字值和給定的分數(shù)段賣現(xiàn)，若前者在給定的分數(shù)段中，根結(jié)點就滿足要求，則在根結(jié)點的左、右子樹中繼續(xù)查找即可；若前者在給定的分數(shù)段的左側(cè)，只在根結(jié)點的右子樹中查找即可；若前者在給定的分數(shù)段的右側(cè)，只在根結(jié)點的左子樹中查找即可【參考程序】include includestringhincludeincludedefine NameLen 15 /*高校名稱的最大長度*/typedef int KeyType。typedef struct node{ KeyType key。 /*最低錄取分數(shù)*/ char name[NameLen+1]。 /*高校名稱*/ struct node *lchild, *rchild。 }BSTree。void Traversing(BSTree *bt) /*訪問bt所指的結(jié)點*/{ printf(%d %s\n, btkey, btname)。}void InOrder(BSTree *bt){ if (bt) { InOrder(btlchild)。 Traversing(bt)。 InOrder(btrchild)。 }}/* 下面程序在r指針所指的二叉排序樹