|
|
  Arraylist
1 // * -*- mode: c++; -*- */
2/**//**
3 * @file
4* @brief Provide an array based list container.
5*
6* An Array list container provide an o(1) access to its
7* elements. It's quite similar to the std::vector features.
8 */
9
10#include <assert.h>
11
12#ifndef __LIST_H
13#define __LIST_H
14/**//**
15* Define the max unsigned long value available
16* @todo Take this value from @em limits.h.
17*
18*/
19static const unsigned long MAX_UNSIGNED_LONG = 4294967295U;
20
21
22/**//**
23*
24* 例子
25* @code
26* List<int, 20> A;
27* A.size; // Returns 0
28* A.insert(10); // Adds 10 to the end of the list
29* A[0]; // Returns 10
30* A.insert(1,0); // Adds 1 to front of list so list reads 1,10
31* A.replace(5,0, 1); // Replaces element 1 with a 5. List reads 1,5
32* A.del(); // Deletes the last item on the list. List reads 1
33* A.size; // Returns 1
34* @endcode
35*
36*/
37
38template <class list_type,size_t length = 0>
39class Arraylist
40 {
41
42public:
43
44  /**//**
45 * 默认构造函数
46 */
47 Arraylist();
48
49 /**//**
50 * 析构函数
51 */
52 ~Arraylist();
53
54 /**//**
55 * 拷贝构造函数
56 * @param original_copy The Arraylist to duplicate
57 */
58 Arraylist( const Arraylist& original_copy );
59
60 /**//**
61 * 赋值操作符
62 */
63 Arraylist& operator= ( const Arraylist& original_copy );
64
65 /**//**[]操作符
66 * Access an element by its index in the array
67 * @param position The index in the array.
68 * @return the element at position @em position.
69 */
70 list_type& operator[] ( unsigned long position );
71
72 /**//**按照指定位置插入数据
73 * Insert an element at position @em position in the list
74 * @param input The new element.
75 * @param position The position of the new element.
76 */
77 void insert( list_type input, unsigned long position );
78
79 /**//**
80 * 插入数据到末尾
81 * @param input The new element.
82 */
83 void insert( list_type input );
84
85 /**//**替换指定位置的数据
86 * replace the value at @em position by @em input. If the size of
87 * the list is less than @em position, it increase the capacity of
88 * the list and fill slot with @em filler.
89 * @param input The element to replace at position @em position.
90 * @param filler The element use to fill new allocated capacity.
91 * @param position The position of input in the list.
92 */
93 void replace( list_type input, unsigned long position, list_type filler = 0);
94
95 /**//**
96 * replace the last element of the list by @em input
97 * @param input the element used to replace the last element.
98 *///替换末尾数据
99 void replace( list_type input );
100
101 /**//**删除指定位置的元素
102 * Delete the element at position @em position.
103 * @param position the index of the element to delete
104 */
105 void del( unsigned long position );
106
107 /**//**从最后的位置开始删除
108 * Delete the element at the end of the list
109 */
110 void del();
111
112 //判断是否为空
113 bool isempty(void);
114
115 /**//**查找
116 * Returns the index of the specified item or MAX_UNSIGNED_LONG if not found
117 * @param input The element to check for
118 * @return The index or position of @em input in the list.
119 * If input is not in the list MAX_UNSIGNED_LONG is returned.
120 */
121 unsigned long getIndexOf( list_type input );
122
123
124 /**//**获取链表的长度
125 * Get the size of the list
126 */
127 const unsigned long size( void );
128
129 /**//**清空链表
130 * Clear the list
131 */
132 void clear( void );
133
134 /**//**压缩链表
135 * Compress the list, to meet the current state of the list.
136 * @attention
137 * Do not use too often this operation if you are doing a lot of
138 * insert/del operation because it implies memory realocation and copy of
139 * the element of the list.
140 */
141 void compress( void );
142
143 //反转
144 void Reverse( void );
145
146 //增加
147 void add(list_type date);
148
149
150private:
151 /**//**
152 * Store all values //相当于游标
153 */
154 list_type* array;
155
156 /**//**
157 * 链表中的元素个数
158 */
159 unsigned long list_size;
160
161 /**//**
162 * Size of @em array 数组的长度
163 */
164 unsigned long allocation_size;
165};
166
167#endif
168
169#include "Arraylist.h"
170
171template<class list_type,size_t length>
172Arraylist<list_type,length>::Arraylist()
173{
174
175 if (length>0)
176 {
177 allocation_size = length;
178 }
179 else//如果为零，即是Arraylist是空
180 {
181 allocation_size = 16;
182 }
183
184
185 array = new list_type[ allocation_size ];
186 list_size = 0L;
187}
188
189
190template<class list_type,size_t length>
191Arraylist<list_type,length>::~Arraylist()
192{
193 clear();
194}
195
196
197template<class list_type,size_t length>
198Arraylist<list_type,length>::Arraylist( const Arraylist& original_copy )
199{
200 // Allocate memory for copy
201
202 if ( original_copy.list_size == 0 )
203 {
204 list_size = 0L;
205 allocation_size = 0L;
206 }
207 else
208 {
209 array = new list_type [ original_copy.list_size ];
210
211 for ( unsigned long counter = 0L; counter < original_copy.list_size; ++counter )
212 array[ counter ] = original_copy.array[ counter ];
213
214 list_size = allocation_size = original_copy.list_size;
215 }
216}
217
218template<class list_type,size_t length>
219Arraylist<list_type,length>& Arraylist<list_type,length>::operator= ( const Arraylist& original_copy )
220{
221 if ( ( &original_copy ) != this )
222 {
223 clear();
224
225 // Allocate memory for copy
226
227 if ( original_copy.list_size == 0 )
228 {
229 list_size = 0L;
230 allocation_size = 0L;
231 }
232
233 else
234 {
235 array = new list_type [ original_copy.list_size ];
236
237 for ( unsigned long counter = 0L; counter < original_copy.list_size; ++counter )
238 array[ counter ] = original_copy.array[ counter ];
239
240 list_size = allocation_size = original_copy.list_size;
241 }
242 }
243
244 return *this;
245}
246
247template<class list_type, size_t length>
248inline bool Arraylist<list_type,length>::isempty()
249{
250 if ( !allocation_size )
251 {
252 return true;
253 }
254
255 return false;
256}
257
258
259template<class list_type,size_t length>
260inline list_type& Arraylist<list_type,length>::operator[] ( unsigned long position )
261{
262 if ( (position <= list_size) && position && list_size)
263 {
264 return array[ position ];
265 }
266 else
267 {
268 return array[0];
269 }
270
271}
272
273/**///////////////////////////////////////////////////////////////////////////
274//Edit this function's coder
275/**///////////////////////////////////////////////////////////////////////////
276template <class list_type,size_t length>
277void Arraylist<list_type,length>::insert( list_type input, unsigned long position )
278{
279
280 if ( list_size >= allocation_size )
281 {
282 // allocate twice the currently allocated memory
283 list_type * new_array;
284
285 if ( allocation_size == 0L )
286 allocation_size = 16L;
287 else
288 allocation_size *= 2L;
289
290 new_array = new list_type [ allocation_size ];
291
292 // copy old array over
293 for ( unsigned long counter = 0L; counter < list_size; ++counter )
294 new_array[ counter ] = array[ counter ];
295
296 // set old array to point to the newly allocated and twice as large array
297 delete[] array;
298
299 array = new_array;
300 }
301
302 // Reallocate list if necessary
303
304 if ( list_size == allocation_size )
305 {
306 // allocate twice the currently allocated memory
307 list_type * new_array;
308
309 if ( allocation_size == 0L )
310 allocation_size = 16L;
311 else
312 allocation_size *= 2L;
313
314 new_array = new list_type [ allocation_size ];
315
316 // copy old array over
317 for ( unsigned long counter = 0L; counter < list_size; ++counter )
318 new_array[ counter ] = array[ counter ];
319
320 // set old array to point to the newly allocated and twice as large array
321 delete[] array;
322
323 array = new_array;
324 }
325
326 // Move the elements in the list to make room
327 for ( unsigned long counter = list_size; counter != position; counter-- )
328 array[ counter ] = array[ counter - 1 ];
329
330 // Insert the new item at the correct spot
331 array[ position ] = input;
332
333 ++list_size;
334
335}
336
337
338template <class list_type,size_t length>
339void Arraylist<list_type,length>::insert( list_type input )
340{
341 // Reallocate list if necessary
342
343 if ( list_size == allocation_size )
344 {
345 // allocate twice the currently allocated memory
346 list_type * new_array;
347
348 if ( allocation_size == 0L )
349 allocation_size = 16L;
350 else
351 allocation_size *= 2L;
352
353 new_array = new list_type [ allocation_size ];
354
355 // copy old array over
356 for ( unsigned long counter = 0L; counter < list_size; ++counter )
357 new_array[ counter ] = array[ counter ];
358
359 // set old array to point to the newly allocated and twice as large array
360 delete[] array;
361
362 array = new_array;
363 }
364
365 // Insert the new item at the correct spot
366 array[ list_size ] = input;
367
368 ++list_size;
369}
370
371
372template <class list_type,size_t length>
373inline void Arraylist<list_type,length>::replace( list_type input, unsigned long position,list_type filler)
374{
375 if ( ( list_size > 0L ) && ( position < list_size ) )
376 {
377 // Direct replacement
378 array[ position ] = input;
379 }
380
381 else
382 {
383 if ( position >= allocation_size )
384 {
385 // Reallocate the list to size position and fill in blanks with filler
386 list_type * new_array;
387 allocation_size = position + 1;
388
389 new_array = new list_type [ allocation_size ];
390
391 // copy old array over
392 for ( unsigned long counter = 0L; counter < list_size; ++counter )
393 new_array[ counter ] = array[ counter ];
394
395 // set old array to point to the newly allocated array
396 delete[] array;
397
398 array = new_array;
399 }
400
401 // Fill in holes with filler
402 while ( list_size < position )
403 array[ list_size++ ] = filler;
404
405 // Fill in the last element with the new item
406 array[ list_size++ ] = input;
407
408#ifdef _DEBUG
409 assert( list_size == position + 1 );
410#endif
411
412 }
413}
414
415template <class list_type,size_t length>
416inline void Arraylist<list_type,length>::replace( list_type input )
417{
418 if ( list_size > 0L )
419 array[ list_size - 1 ] = input;
420}
421
422template <class list_type,size_t length>
423void Arraylist<list_type,length>::del( unsigned long position )
424{
425 if (position >= list_size)
426 {
427 return;
428 }
429 else
430 {
431 // Compress the array
432 for ( unsigned long counter = position; counter < allocation_size/**//*list_size - 1*/ ; ++counter )
433 array[ counter ] = array[ counter + 1L ];
434
435 --list_size;
436 }
437}
438
439
440template <class list_type,size_t length>
441void Arraylist<list_type,length>::Reverse( void )
442{
443 //assert(list_size);
444 if (!list_size)
445 {
446 return;
447 }
448
449 list_type tmep;
450
451 for(unsigned long i = 0; i < list_size/2; ++i)
452 {
453 tmep = this->operator [](i);
454 this->operator [](i) = this->operator[](list_size - i -1);
455 this->operator[](list_size - i -1) = tmep;
456 }
457}
458
459
460template <class list_type,size_t length>
461inline void Arraylist<list_type,length>::del()
462{
463 // Delete the last element on the list. No compression needed
464 list_size--;
465}
466
467template <class list_type,size_t length>
468unsigned long Arraylist<list_type,length>::getIndexOf( list_type input )
469{
470 for ( unsigned long i = 0; i < list_size; ++i )
471 if ( array[ i ] == input )
472 return i;
473
474 return MAX_UNSIGNED_LONG;
475}
476
477template <class list_type,size_t length>
478inline const unsigned long Arraylist<list_type,length>::size( void )
479{
480 return list_size;
481}
482
483template <class list_type,size_t length>
484void Arraylist<list_type,length>::clear( void )
485{
486 if ( allocation_size == 0L )
487 return ;
488
489 delete [] array;
490
491 list_size = 0L;
492
493 allocation_size = 0L;
494
495 array = 0;
496}
497
498template <class list_type,size_t length>
499void Arraylist<list_type,length>::compress( void )
500{
501 list_type * new_array;
502
503 if ( allocation_size == 0 )
504 return ;
505
506 new_array = new list_type [ allocation_size ];
507
508 // copy old array over
509 for ( unsigned long counter = 0L; counter < list_size; ++counter )
510 new_array[ counter ] = array[ counter ];
511
512 // set old array to point to the newly allocated array
513 delete[] array;
514
515 array = new_array;
516}
517
518template <class list_type,size_t length>
519void Arraylist<list_type,length>::add(list_type date)
520{
521 insert(date);
522}
523
524
Stack
1#ifndef __STACK_H
2#define __STACK_H
3
4
5template<typename Type>class Stack;
6
7template<typename Type>class StackNode
8{
9 friend class Stack<Type>;
10private:
11 Type data;
12 StackNode<Type> *link;
13 StackNode(Type D=0,StackNode<Type> *L=NULL):link(L),data(D){}
14};
15
16template<typename Type>
17class Stack
18{
19public:
20 Stack():top(NULL),NumItem(0)
21 {}
22 void Push(Type item);//压栈
23 Type Pop(); //出栈
24 Type GetTop();//获取栈顶元素
25 void MakeEmpty(); //使栈为空
26 bool ISEmpty(); //判断栈是否空
27 int GetNum(); //获取栈中元素的个数
28
29private:
30 int NumItem;
31 StackNode<Type> *top;
32};
33
34
35#endif //stack.h
36
37#include "Stack.h"
38
39template<typename Type>
40void Stack<Type>::Push(Type item)
41{
42 top=new StackNode<Type>(item,top);
43 NumItem++;
44}
45
46template<typename Type>
47Type Stack<Type>::Pop()
48{
49 StackNode<Type> *p;
50 Type temp;
51 temp=top->data;
52 p=top;
53 top=top->link;
54 delete p;
55 NumItem--;
56 return temp;
57}
58
59template<typename Type>
60Type Stack<Type>::GetTop()
61{
62 return top->data;
63}
64
65template<typename Type>
66bool Stack<Type>::ISEmpty()
67{
68 return top==NULL;
69}
70
71template<typename Type>
72void Stack<Type>::MakeEmpty()
73{
74 while(NumItem = GetNum())
75 {
76 Pop();
77 }
78
79}
80
81template<typename Type>
82int Stack<Type>::GetNum()
83{
84 return NumItem;
85}
Queue
1/**//* Queue.h */
2#ifndef __QUEUE_H__
3#define __QUEUE_H__
4
5template <class T,size_t initSize = 50>
6class Queue
7{
8private:
9 T *qlist; //存放队列元素的指针(数组)
10 int size; //队列大小(容量)
11 int front; //队首位置
12 int rear; //队尾位置(最后一个元素的下一位置)
13 int count; //队列中元素的个数
14public:
15 //构造函数
16 Queue();
17
18 //析构函数
19 ~Queue();
20
21 //判断队列是否为空
22 int QEmpty();
23
24 //判断队列是否已满
25 int QFull();
26
27
28 //队尾插入(追加)元素
29 void QInsert(const T &item);
30
31 //队首删除元素
32 T QDelete();
33
34 //读取队首元素
35 T QFront();
36
37 //队列长度
38 int QLength();
39
40 //读取队尾元素
41 T QBack();
42
43 //清空队列
44 void ClearQueue();
45};
46#endif /* !__QUEUE_H__ */
47
48/**/////////////////////////////////////////////////////////////
49#include "Queue.h"
50
51template<class T,size_t initSize>
52Queue<T,initSize>::Queue()
53{
54 if (initSize < 1)
55 {
56 size = 50;
57 }
58 else
59 {
60 size = initSize;
61 }
62
63
64 qlist = new T[size];
65 front = 0;
66 rear = 0;
67 count = 0;
68}
69//析构函数
70template <class T,size_t initSize>
71Queue<T,initSize>::~Queue()
72{
73 if (qlist)
74 {
75 delete [] qlist;
76 }
77 front = 0;
78 rear = 0;
79 count = 0;
80 size = 0;
81}
82
83//判断队列是否为空
84template <class T,size_t initSize>
85int Queue<T,initSize>::QEmpty()
86{
87 return front == rear;
88}
89
90//判断队列是否已满
91template <class T,size_t initSize>
92int Queue<T,initSize>::QFull()
93{
94 return (rear+1) % size == front;
95}
96
97//队列长度
98template <class T,size_t initSize>
99int Queue<T,initSize>::QLength()
100{
101 return count;
102}
103
104//队尾插入(追加)元素
105template <class T,size_t initSize>
106void Queue<T,initSize>::QInsert(const T &item)
107{
108 if (count == size)
109 {
110 return;
111 }
112 count ++;
113 qlist[rear] = item;
114 rear = (rear + 1) % size; //rear始终指向最后一个元素的下一个位置
115}
116
117//队首删除元素
118template <class T,size_t initSize>
119T Queue<T,initSize>::QDelete()
120{
121 T data;
122 if (count > 0)
123 {
124 data = qlist[front];
125 count --;
126 front = (front + 1) % size; //front移向下一位置
127 }
128 return data;
129}
130
131//读取队首元素
132template <class T,size_t initSize>
133T Queue<T,initSize>::QFront()
134{
135 T temp;
136 if (count > 0)
137 {
138 return qlist[front];
139 }
140
141 return temp;
142}
143
144
145//读取队尾元素
146template <class T,size_t initSize>
147T Queue<T,initSize>::QBack()
148{
149 if (count > 0)
150 {
151 return qlist[rear -1];
152 }
153 return 0;
154}
155
156//清空队列
157template <class T,size_t initSize>
158void Queue<T,initSize>::ClearQueue()
159{
160 front = 0;
161 rear = 0;
162 count = 0;
163}
164
165
166
167
168/**/////////////////////////////////////////////////////////////
HashTable
1
2#ifndef HASHTABLE_H
3#define HASHTABLE_H
4
5template <typename K, typename D, unsigned long int S = 200003L>
6struct HashTableEntry
7{
8 K key_;
9 D data_;
10 HashTableEntry* next_;
11 HashTableEntry() : data_(0), next_(0)
12 {
13
14 }
15 ~HashTableEntry()
16 {
17 delete next_;
18 }
19};
20
21template <typename K, typename D, unsigned long int S = 200003L>
22class HashTable
23{
24
25public:
26 HashTable();
27 ~HashTable();
28 D& operator[] (const K& key);
29 bool find(const K& key);
30 bool end();
31 void clear();
32 bool Add(K key, D data );
33private:
34 void init();
35 HashTableEntry<K,D,S>* find_entry(const K& key, HashTableEntry** prev = 0);
36 int m_iCounter;
37 HashTableEntry** hash_table_;//二维数组
38};
39#endif
40
41#include "HashTable.h"
42
43template <typename K, typename D, unsigned long int S>
44HashTable<K,D,S>::HashTable():hash_table_(0)
45{
46 init();
47}
48template <typename K, typename D, unsigned long int S>
49HashTable<K,D,S>::~HashTable()
50{
51 clear();
52 delete [] hash_table_;
53}
54template <typename K, typename D, unsigned long int S>
55D& HashTable<K,D,S>::operator[] (const K& key)
56{
57 HashTableEntry* prev = 0;
58 HashTableEntry* hte = find_entry(key, &prev);
59 if (!hte)
60 {
61 hte = new HashTableEntry;
62 hte->key_ = key;
63 if (prev) prev->next_ = hte;
64 else
65 {
66 unsigned long int h = (H::hash(key) % S);
67 hash_table_[h] = hte;
68 }
69 }
70 return hte->data_;
71}
72template <typename K, typename D, unsigned long int S>
73bool HashTable<K,D,S>::find(const K& key)
74{
75 return (find_entry(key) != 0);
76}
77template <typename K, typename D, unsigned long int S>
78bool HashTable<K,D,S>::end()
79{
80 return false;
81}
82template <typename K, typename D, unsigned long int S>
83void HashTable<K,D,S>::clear()
84{
85 if (!hash_table_)
86 return;
87
88 for (size_t i = 0; i < S; ++i)
89 {
90 HashTableEntry* hte = hash_table_[i];
91 delete hte;
92 hash_table_[i] = 0;
93 }
94};
95template <typename K, typename D, unsigned long int S>
96bool HashTable<K,D,S>::Add(K key, D data )
97{
98 for (size_t i = 0; i < S; ++i)
99 {
100 HashTableEntry* hte = hash_table_[i];
101
102 int index = 0;
103 while((!hte) && (++index) && (index < S))//如果一行满了就进入下一行
104 {
105 hte = new HashTableEntry;
106 hash_table_[i] = hte ;
107 hash_table_[i]->data_ = data;
108 hash_table_[i]->key_ = key;
109 return true;
110 }
111 }
112
113 return false;
114}
115
116
117template<typename K, typename D, unsigned long int S>
118void HashTable<K,D,S>::init()
119{
120 if (hash_table_)
121 {
122 return;
123 }
124 hash_table_ = new HashTableEntry* [ S ];
125 for (size_t i = 0; i < S; ++i)
126 {
127 hash_table_[i] = 0;
128 }
129}
130
131
132template<typename K, typename D, unsigned long int S>
133HashTableEntry<K,D,S>* HashTable<K,D,S>::find_entry(const K& key, HashTableEntry<K,D,S>** prev)
134{
135 init();
136
137 for (size_t i = 0; i < S; ++i)
138 {
139 HashTableEntry* hte = hash_table_[i];//列
140
141 while (hte)//行
142 {
143 if (hte->key_ == key)
144 {
145 break;
146 return hte;
147 }
148 hte = hte->next_;
149 }
150 }
151
152 return NULL;
153}
154
155
156
|