試談數(shù)據(jù)結構研究(參考版)
2025-06-25 19:50本頁面
【正文】 分割是快速排序算法的關鍵。(4) 對子序列L和R進行快速排序，直到子序列中只含有0或1個記錄。(2) 將剩余的記錄分割成兩個子序列L和R，L中包含所有小于或等于軸值k的記錄，R中包含所有大于軸值k的記錄。: 由于Shell排序按照不斷縮小的增量來將原始序列分成若干個子序列，因此有時也稱為縮小增量排序算法。7_06 Shell排序法 算法 掌握原理 完整程序 先將序列轉化為若干小序列，在這些小序列內進行插入排序； 逐漸擴大小序列的規(guī)模(即擴大小序列中記錄的個數(shù))，而減少小序列個數(shù)，使得待排序序列逐漸處于更有序的狀態(tài)，有利于插入排序操作； 最后，所有序列都合并在原來的大序列中，這個大序列基本有序了(整個序列比較接近于正序狀態(tài))，然后再對整個序列進行掃尾直接插入排序，從而完成排序。5) 直接插入和冒泡算法都有一個共同的缺點：只對相鄰的兩個記錄進行比較和交換，因此一個記錄只能一步步地向它應在的位置移動，效率低下。4) 這3種排序算法雖然簡單，但時間復雜度都比較大，雖然做了很多改進，但仍然沒有太大成效(這些改進沒有從本質上降低算法時間復雜度)，在平均和最壞情況下的時間復雜度均為O(n2)。因此內循環(huán)的循環(huán)變量j的取值是從i+1到n1。2) 在第i趟里怎么選？—— 第i趟要從a[i], a[i+1], ..., a[n1]中選擇最小的數(shù)，記為a[k]，i=0，1，2，...，n2。7_05 選擇法排序 算法 掌握原理 完整程序直接選擇排序法也需要用一個二重循環(huán)來實現(xiàn)，同樣可以帶著以下3個類似問題來理解其思想(有n個數(shù)，要求按照從小到大的順序排序)：1) 要進行多少趟選擇？—— 要進行n1趟選擇(第0趟，第1趟，…，第n2趟)。也就是說，如果在某一趟比較過程中，沒有發(fā)現(xiàn) 前一個數(shù)比后一個數(shù)大的情況，即沒有進行交換數(shù)據(jù)，那么后面就不需要再進行比較了。7_03 插入法排序 算法 掌握原理 完整程序: 逐個處理待排序的記錄，每個新記錄都要與前面那些已排好序的記錄進行比較，然后插入到適當?shù)奈恢谩? 實現(xiàn)排序的系統(tǒng)函數(shù)主要有：qsort、sort函數(shù): qsort函數(shù)： 采用快速排序算法()實現(xiàn)。7_02 用系統(tǒng)函數(shù)實現(xiàn)排序 應用 掌握方法 完整程序: 在實際編程時，可能不需要自己實現(xiàn)排序算法，直接調用系統(tǒng)函數(shù)實現(xiàn)排序即可。: 序列(sequence)：所有待排序記錄的集合稱為序列。: 由于討論的是內排序，在大部分情況下本章都是考慮基于順序存儲的排序，即待排序的數(shù)據(jù)是存儲在數(shù)組中。: 內排序：如果待排序的記錄個數(shù)較少，整個排序過程中所有的記錄都可以直接存放在內存中，這樣的排序叫做內排序(internal sorting)。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。: 求解算法： 權值為非負的單源最短路徑問題(固定源點)－Dijkstra算法(迪克斯特拉算法,1959)； 權值為任意值的單源最短路徑問題(固定源點) －BellmanFord算法(貝爾曼－福特算法)； BellmanFord算法的改進 － SPFA算法； 所有頂點之間的最短路徑問題－FloydWarshall算法(弗洛伊德算法)；6_10 Dijkstra算法 算法 掌握原理 完整程序252。2) 依次檢查每條邊，如果該邊的兩個頂點不屬于同一個集合，則選用該邊、并將這兩個集合合并；否則棄用這條邊。都得遵守以上準則。: 構造最小生成樹的準則：: 必須只使用該網(wǎng)絡中的邊來構造最小生成樹；: 必須使用且僅使用 n1 條邊來聯(lián)結網(wǎng)絡中的 n 個頂點；: 不能使用產生回路的邊。: 按照生成樹的定義，n 個頂點的連通網(wǎng)絡的生成樹有 n 個頂點、n1 條邊。: 生成樹是連通圖的最小連通子圖。6_07 圖的最小生成樹 概念 理解 : 生成樹：連通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹。6_05 圖的深度優(yōu)先搜索 算法 掌握原理 深度優(yōu)先搜索(Depth First Search)：是一個遞歸過程，有回退過程，(a)所示的無向連通圖，采用DFS思想搜索的過程為：(在圖(a)中，箭頭旁的數(shù)字跟下面的序號對應)(1) 從頂點A出發(fā)，訪問頂點序號最小的鄰接頂點，即頂點B；(2) 然后訪問頂點B的一個未訪問過的鄰接頂點，即頂點C；(3) 接著訪問頂點C的一個未訪問過的鄰接頂點，即頂點G；(4) 此時頂點G已經沒有未訪問過的鄰接頂點了，所以回退到頂點C；(5) 回退到頂點C后，頂點C也沒有未訪問過的鄰接頂點了，所以繼續(xù)回退到頂點B；。為了方便求解頂點的出度和入度，在實現(xiàn)時，把出邊表和入邊表同時包含在表示頂點的結構體中。適合求頂點的入度。6_03 圖的鄰接表實現(xiàn) 算法 掌握原理 代碼段: 鄰接表：把同一個頂點發(fā)出的邊鏈接在同一個稱為邊鏈表的單鏈表中。網(wǎng)絡可以用G(V, E)表示，其中邊的集合E中每個元素包含3個分量：邊的兩個頂點和權值。如果一個圖，其所有邊都具有權值，則稱為網(wǎng)絡。: 權值：某些圖的邊具有與它相關的數(shù)，稱為權值。如果G是有向圖，則vi, vp1, vp1, vp2, …, vpm, vj為圖中的有向邊。如果圖中有n個頂點，則生成樹有n1條邊。這是因為，不管是有向圖還是無向圖，在統(tǒng)計所有頂點的度的總和時，每條邊都統(tǒng)計了兩次。頂點u的度數(shù)：deg(u) = od(u) + id(u)。頂點的度(degree)：一個頂點的度是與它相關聯(lián)的邊的條數(shù)，記作deg(u) 在有向圖中，頂點的度等于該頂點的出度與入度之和。V(G)中的元素稱為頂點，用u、v等符號表示；頂點個數(shù)稱為圖的階，通常用n表示。: 對讀入的每個等價對X≡Y，先判定結點X和Y是否屬于同一個集合，如果是，則不管；如果不是，則合并結點X和結點Y所在的集合。例如，如果parent[7] = 4，說明7號結點就是它所在樹的根結點，這棵樹有4個結點。例如，如果parent[4] = 5，就是說4號結點的父親是5號結點。對于每棵樹的根結點，由于它沒有父結點，則可
語文相關推薦
鄂ICP備17016276號-1