“算法设计与区分”

“算法分析和设计”实验报告的标题: 名称: 班级: 学生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