递增的有序顺序表，插入元素并保持递增有序。
内存分配按照 2 被原则进行分配。
1 #include <iostream>
2 using namespace std;
3
4 // 递增有序的顺序表
5 template <typename Type>
6 class IncTable
7 {
8 public:
9 typedef Type value_type;
10 typedef Type* p_type;
11 typedef unsigned int size_type;
12 typedef p_type iterator;
13 typedef const p_type const_iterator;
14 private:
15 p_type table;
16 size_type size_;
17 size_type capacity_;
18 public:
19 IncTable(int s = 1)
20 {
21 size_ = 0;
22 capacity_ = s * 2;
23 table = new value_type[capacity_];
24 if (table == 0)
25 {
26 exit(0);
27 }
28 }
29 ~IncTable()
30 {
31 delete [] table;
32 }
33 void insert(value_type item)
34 {
35 if (size_ >= capacity_)
36 {
37 reallocate(size_ * 2);
38 }
39 size_type ix = size_;
40 while (ix > 0 && table[ix - 1] > item)
41 {
42 table[ix] = table[ix - 1];
43 --ix;
44 }
45 table[ix] = item;
46 ++size_;
47 }
48 void reallocate(size_type size)
49 {
50 p_type p = new value_type[size];
51 if (p == 0)
52 {
53 exit(1);
54 }
55 memcpy(p, table, sizeof (value_type) * size_);
56 delete table;
57 table = p;
58 capacity_ = size;
59 }
60 size_type size()
61 {
62 return size_;
63 }
64 size_type capacity()
65 {
66 return capacity_;
67 }
68 iterator begin()
69 {
70 return table;
71 }
72 iterator end()
73 {
74 return table + size_;
75 }
76 const_iterator begin() const
77 {
78 return table;
79 }
80 const_iterator end() const
81 {
82 return table + size_;
83 }
84 };
85
86 int main()
87 {
88 IncTable<int> t;
89 for (int i = 10; i > 0; --i)
90 {
91 t.insert(i);
92 }
93 for (int i = 0; i < 10; ++i)
94 {
95 t.insert(i);
96 }
97 for (IncTable<int>::iterator iter = t.begin(); iter != t.end(); ++iter)
98 {
99 cout << *iter << ' ';
100 }
101 cout << endl;
102 }
posted on 2011-04-24 01:39
unixfy 阅读(557)
评论(0) 编辑 收藏 引用