数据结构与算法之有序数组（2）——in dart

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法之有序数组（2）——in dart，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5028字，纯文字阅读大概需要8分钟。

内容图文

本文比第一篇，采用了类实现。增加了运算符重载等功能。本来有序数组是不能修改某个位置的值的，因为这样会打破数组的有序性；但为了演示，保留了修改的方法，但为此增加了排序。

 

  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 举报，一经查实，本站将立刻删除。

内容手机端

---