“算法分析和設計”實驗報告的標題: 名稱: 班級: 學生ID: 講師: 完成時間: 1.給定實驗主題的一系列鍵和權重，構造一個最佳二元排序樹以使總數最少搜索量. 二，實驗目的1.理解時間復雜度的概念. 2.深入掌握C語言編程. 3.通過編程直觀地了解算法分析的重要性. 3.實驗要求給定一系列關鍵值和權重，構造一個最佳的二元排序樹，以使搜索總數最小化. 所需的輸出格式為: 第一行是最佳搜索次數，第二行是以下順序: 遍歷最佳二進制排序樹的順序，然后是空行，然后是源代碼. 算法的輸入如下（冒號前的鍵值，冒號后的權重）: 1: 0 2:56 3:19 4:80 5:58 6:47 7:35 8:89 9:82 10:74 11 : 17 12:85 13:71 14:51 15:30 16: 1 17: 9 18:36 19:14 20:16 21:98 22:44 23:11 24: 0 25: 0 26:37 27:53 28: 57 29:60 30:60 31:16 32:66 33:45 34:35 35: 5 36:60 37:78 38:80 39:51 40:30 41:87 42:72 43:95 44: 92 45: 53 46:14 47:46 48:23 49:86 50:20 51:77 52:84 53:99 54:99 55:61 56:39 57:26 58:29 59:84 60: 2 61 : 37 62: 9 63:67 64: 5 65: 0 66:91 67:27 68:27 69:58 70:69 71:83 72:72 73:48 74:20 75:74 76:46 77:45 78: 94 79:74 80:10 81:59 82:38 83:73 84:60 85:57 86:36 87:15 88:22 89:42 90:80 91:51 92:98 93:75 94: 34 95: 16 96:65 97:49 98: 6 99:69 100: 50 101: 14 102: 94 103: 14 104: 90 105: 69 106: 30 107: 42 108: 7 109: 96 110: 68 111 : 15 112: 87 113: 82 114: 58 115: 19 116: 17117: 81 118: 47 119: 15 120: 50 121: 73 122: 40 123: 27 4.程序流程圖5.程序代碼#include #include 結構節點{int鍵；詮釋v; }; int sum [1000]，c [1000] [1000]二叉排序樹算法，y [1000] [1000]; struct node a [10000]; int n，ans; void df（int left，int right）{if（left> right）return; int k = y [left] [right]; printf（“％d”，k）; df（left，k-1）; df（k + 1，right）;} void fi（int left，int right，int t）{if（left> right）return; ans = ans + t; int k = y [left] [right]; fi（左，k-1，t + 1）; fi（k + 1，right，t + 1）;} void in（）{char ch; freopen（“ input.txt”，“ r”，stdin）; n = 1; while（1）{do {if（scanf（“％c”，＆ch）== EOF）返回； if（ch！=': '）a [n] .key = a [n] .key * 10 +（ch-'0'）; } while（ch！=': '）; do {if（scanf（“％c”，＆ch）== EOF）返回； if（ch！=''）a [n] .v = a [n] .v * 10 +（ch-'0'）; } while（ch！=''）; n ++;} n--;} int main（）{int i，j，k，u;在（）; sum [0] = 0; for（i = 1; i <= n;="" i="" ++）sum="" [i]="sum" [i-1]="" +="" a="" [i]="" .v;="" for（i="0;" i=""><= n;="" i="" ++）for（j="0;" j=""><= n;="" j="" ++）c="" [i]="" [j]="0;" for（i="1;" i=""><= n;="" i="" ++）{y="" [i]="" [i]="i;" c="" [i]="" [i]="0;}" for（u="2;" u=""><= n;="" u="" ++）{for（i="1;" i=""><= n-u="" +="" 1;="" i="" ++）{j="i" +="" u-1="" ;="" c="" [i]="" [j]="10000000;" for（k="i;" k=""><= j;="" k="" ++）如果（c="" [i]="" [k-1]="" +="" c="" [k="" +="" 1]="" [j]="" +="" sum="" [j]="" -sum="" [i-1]="" -a="" [k="" ]="" .v="">

按順序遍歷二進制排序樹可以獲得基于關鍵字的有序序列. 通過構建二進制排序樹，可以將無序序列轉換為有序序列. 構造樹的過程是對無序進行排序的過程. 插入的每個新節點都是二進制排序樹中的一個新葉節點. 插入時二叉排序樹算法，無需移動其他節點，只需將節點的指針從空罐更改為非空罐即可. 搜索，插入和刪除的時間復雜度等于樹的高度，以及期望的O（logn）和最差的O（n）（順序是有序的，并且樹退化為線性表，例如a右對角樹）.

本文來自本站，轉載請注明本文網址：
http://www.pc-fly.com/a/jisuanjixue/article-245296-1.html