数据结构与算法之有序数组(2)——in dart
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法之有序数组(2)——in dart,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5028字,纯文字阅读大概需要8分钟。
内容图文
![数据结构与算法之有序数组(2)——in dart](/upload/InfoBanner/zyjiaocheng/844/4ac09dc6a798490d93672dcbcaf9c4d4.jpg)
本文比第一篇,采用了类实现。增加了运算符重载等功能。本来有序数组是不能修改某个位置的值的,因为这样会打破数组的有序性;但为了演示,保留了修改的方法,但为此增加了排序。
1 import 'dart:math' show Random; 2 3 final _rnd = Random(); 4 final _seed = 100; 5 6 class OrderedArray { 7 List<int> _array; 8 int _realLength; 9 10 OrderedArray(int capacity) { 11 _array = List<int>(capacity); 12 _realLength = 0; 13 } 14 15 int get capacity => _array.length; 16 int get length => _realLength; 17 18 void fill(double percent) { 19 for (var i = 0; i < capacity * percent; i++) { 20 insert(_rnd.nextInt(_seed)); 21 } 22 } 23 24 bool insert(int v) { 25 if (_realLength == capacity) { 26 return false; 27 } else { 28 if (_realLength == 0) { 29 _array[0] = v; 30 } else { 31 int i; 32 for (i = 0; i < _realLength; i++) { 33 if (_array[i] >= v) break; 34 } 35 for (var j = _realLength; j > i; j--) { 36 _array[j] = _array[j - 1]; 37 } 38 _array[i] = v; 39 } 40 41 _realLength++; 42 return true; 43 } 44 } 45 46 int find(int key) { 47 if (_realLength == 0) { 48 return -1; 49 } 50 51 if (key < _array[0] || key > _array[_realLength - 1]) { 52 return -1; 53 } 54 55 int lower = 0, upper = _realLength - 1, mid; 56 while (lower <= upper) { 57 mid = (lower + upper) ~/ 2; 58 if (_array[mid] == key) { 59 return mid; 60 } else if (_array[mid] > key) { 61 upper = mid - 1; 62 } else { 63 lower = mid + 1; 64 } 65 } 66 return -1; 67 } 68 69 // Attention! after modifed the array is maybe not ordered ever. 70 bool modify(int pos, int newValue) { 71 if (pos < 0 || pos > _realLength - 1) { 72 return false; 73 } else { 74 _array[pos] = newValue; 75 // sort(0, _realLength - 1); 76 return true; 77 } 78 } 79 80 bool delete(int key) { 81 var pos = find(key); 82 if (pos < 0) { 83 return false; 84 } else { 85 for (var i = pos; i < _realLength - 1; i++) { 86 _array[i] = _array[i + 1]; 87 } 88 _realLength--; 89 return true; 90 } 91 } 92 93 int operator [](int pos) { 94 if (pos < 0 || pos > _realLength - 1) { 95 return null; 96 } else { 97 return _array[pos]; 98 } 99 } 100 101 // the below is equal to modify, but don't have return type; 102 void operator []=(int pos, int newValue) { 103 if (pos >= 0 && pos < _realLength) { 104 _array[pos] = newValue; 105 // sort(0, _realLength - 1); 106 } 107 } 108 109 void sort(int start, int end) { 110 if (start >= end) return; 111 var pl = start, pr = end, key = _array[pl]; 112 while (pl < pr) { 113 while (_array[pr] >= key && pr > pl) pr--; 114 if (pr > pl) { 115 _array[pl] = _array[pr]; 116 pl++; 117 } 118 while (_array[pl] <= key && pl < pr) pl++; 119 if (pl < pr) { 120 _array[pr] = _array[pl]; 121 pr--; 122 } 123 } 124 _array[pl] = key; 125 126 sort(start, pl - 1); 127 sort(pl + 1, end); 128 } 129 130 void display() { 131 var sb = StringBuffer(); 132 sb.write('['); 133 if (_realLength > 0) { 134 for (var i = 0; i < _realLength - 1; i++) { 135 sb.write('${_array[i]}, '); 136 } 137 sb.write('${_array[_realLength - 1]}'); 138 } 139 sb.write(']'); 140 print(sb.toString()); 141 } 142 } 143 144 void main() { 145 var arr = OrderedArray(100); 146 arr.fill(0.2); 147 arr.display(); 148 149 var key = _rnd.nextInt(_seed); 150 if (arr.insert(key)) { 151 print('insert \'$key\' successed.'); 152 arr.display(); 153 } else { 154 print('insert \'$key\' failed.\n'); 155 } 156 157 key = _rnd.nextInt(_seed); 158 var pos = arr.find(key); 159 if (pos >= 0) { 160 print('found the key: $key at $pos\n'); 161 } else { 162 print('can not find the key: $key\n'); 163 } 164 165 key = _rnd.nextInt(_seed); 166 pos = arr.length ~/ 2; 167 var oldValue = arr[pos]; 168 if (arr.modify(pos, key)) { 169 print('modified the old value ($oldValue) to the new: $key at $pos'); 170 } 171 pos = arr.length; 172 oldValue = arr[pos]; 173 if (arr.modify(pos, key)) { 174 print('modified the old value ($oldValue) to the new: $key at $pos\n'); 175 } else { 176 print('the position to be modified is out of bound.\n'); 177 } 178 arr.display(); 179 180 arr[0] = _rnd.nextInt(_seed); 181 arr[arr.length] = _rnd.nextInt(_seed); 182 arr.display(); 183 184 print('now sort the array:'); 185 arr.sort(0, arr.length - 1); 186 arr.display(); 187 188 key = _rnd.nextInt(_seed); 189 if (arr.delete(key)) { 190 arr.display(); 191 print('has deleted the key: $key'); 192 } else { 193 print('can not find the key to delete: $key'); 194 } 195 196 print('now delete the key: ${arr[arr.length ~/ 2]}'); 197 arr.delete(arr[arr.length ~/ 2]); 198 arr.display(); 199 }
内容总结
以上是互联网集市为您收集整理的数据结构与算法之有序数组(2)——in dart全部内容,希望文章能够帮你解决数据结构与算法之有序数组(2)——in dart所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。