对本科使用的数据结构课本感情很深, 当初学的时候, 并不需要上机编程, 考试时只需写出伪代码即可. 而今, 实现的细节已经变得必须了, 所以, 再次拿出课本, 复习一下实现细节
数据结构和算法
1. 堆的实现(插入, 删除, 初始化, 以最大根为例)
2. 快排的实现
3. 归并排序的实现
4. 数组实现队列
1. 堆的实现, 代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97 |
template
<class
T>class
MaxHeap {public: MaxHeap(int
MaxHeapSize = 10); ~MaxHeap(delete
[] heap); int
Size() const
{ return
CurrentSize; } T Max() const
{ if(CurrentSize == 0) return
OutOfBounds(); return
heap[1]; } MaxHeap<T>& Insert(const
T &x); MaxHeap<T>& Delete(T &x); void
Initialize(T a[], int
size, int
ArraySize);private: int
CurrentSize, MaxSize; T *heap;};template
<class
T>MaxHeap<T>::MaxHeap(int
MaxHeapSize) { MaxSize = MaxHeapSize; CurrentSize = 0; heap = new
T[MaxHeapSize+1];}template
<class
T>MaxHeap<T>& MaxHeap<T>::Insert(const
T &x) { if(CurrentSize == MaxSize) throw
NoMem(); int
i = ++ CurrentSize; while(i != 1 && x > heap[i/2]) { heap[i] = heap[i/2]; i /= 2; } heap[i] = x; return
*this;}template
<class
T>MaxHeap<T>& MaxHeap::Delete(T &x) { if(CurrentSize == 0) return
OutOfBounds(); x = heap[1]; T y = heap[CurrentSize--]; int
i = 1, ci = 2*i; while(ci <= CurrentSize) { if(ci < CurrentSize && heap[ci] < heap[ci+1]) ci ++; if(y >= heap[ci]) break; heap[i] = heap[ci]; i = ci; ci *= 2; } heap[i] = y; return
*this;}template
<class
T>void
MaxHeap<T>::Initialize(T a[], int
size, int
ArraySize) { delete
[] heap; heap = a; CurrentSize = size; MaxSize = ArraySize; for(int
i = CurrentSize/2; i >= 1; i --) { T y = heap[i]; int
c= 2 * i; while(c <= CurrentSize) { if(c < CurrentSize && heap[c] < heap[c+1]) c ++; if(y >= heap[c]) break; heap[c/2] = heap[c]; c *= 2; } heap[c/2] = y; }} |
2. 快排的实现
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 |
template
<class
T>void
QuickSort(T *a, int
n) { quickSort(a, 0, n-1);}template
<class
T> void
quickSort(T *a, int
l, int
r) { if(l >= r) return; int
i = l; j = r+1; T pivot = a[i]; // it should be aware that replace T[i] < pivot to T[i] <= pivot // the correctness of program can be remained while(true) { do
{ i = i + 1; } while(T[i] < pivot); do
{ j = j - 1; } while(T[j] > pivot); if(i >= j) break; swap(T[i], T[j]); } a[l] = a[j]; a[j] = pivot; quickSort(T, l, j-1); quickSort(T, j+1, r);} |
3. 归并排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49 |
template
<class
T>void
MergeSort(T a[], int
n) { T *b = new
T[n]; int
seg = 1; // the size of segment while(seg < n) { MergePass(a, b, seg, n); seg ++; MergePass(b, a, seg, n); } delete
[]b;}template
<class
T>void
MergePass(T a[], T b[], int
seg, int
n) { int
i = 0; while(i < n - 2*seg) { Merge(a, b, i, i+seg-1, i+2*seg-1); i += 2*seg; } if(i < n - seg) { Merge(a, b, i+seg-1, n-1); } else
{ for(int
j = i; j <= n-1; j ++) b[j] = a[j]; }}template
<class
T>void
Merge(T a[], T b[], int
l, int
m, int
r) { int
i = l, j = m+1, k = l; while(i <= m && j <= r) { if(a[i] < b[j]) { b[l++] = a[i++]; } else
{ b[l++] = b[j++]; } } while(i < m) { b[l++] = a[i++]; } while(j < m) { b[l++] = b[j++]; }} |
4. 数组实现队列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 |
template
<class
T>class
Queue {public: Queue(int
MaxQueueSize = 10); ~Queue() { delete
[]queue; } bool
IsEmpty() const
{ return
(front == rear); } bool
IsFull() const
{ return
(rear+1)%MaxSize == front ? 1:0; } T First() const; T Last() const; Queue<T>& Add(const
T &x); Queue<T>& Delete();private: int
front; int
rear; int
MaxSize; T *queue;};template
<class
T>Queue<T>::Queue(int
MaxQueueSize) { MaxSize = MaxQueueSize + 1; queue = new
T[MaxSize]; front = rear = 0;}template
<class
T>T Queue<T>::First() const
{ if(IsEmpty()) throw
OutOfBounds(); return
queue[(front+1)%MaxSize];}template
<class
T>T Queue<T>::Last() const
{ IsFull(IsEmpty()) throw
OutOfBounds(); return
queue[rear];}template<class
T>Queue<T>& Queue::Add(const
T &x) { if(IsFull()) throw
NoMem(); rear = (rear+1) % MaxSize; queue[rear] = x; return
*this;}template
<class
T>Queue<T>& Queue::Delete() { if(IsEmpty()) throw
OutOfBounds(); front = (front+1) % MaxSize; x = queue[front]; return
*this;} |
原文：http://www.cnblogs.com/zhouzhuo/p/3684420.html