C++实现数据结构算法详解及示例

目 录 

目 录 .................................................................................................................................................................................................................................................................................. 1 
1、顺序表 ............................................................................................................................................................................................................................................................................ 1 
Seqlist.h ................................................................................................................................................................................................................................................................ 1 
Test.cpp ................................................................................................................................................................................................................................................................... 4 
2、 单链表 ...................................................................................................................................................................................................................................................................... 5 
ListNode.h .............................................................................................................................................................................................................................................................. 5 
SingleList.h ......................................................................................................................................................................................................................................................... 6 
test.cpp ................................................................................................................................................................................................................................................................. 12 
3、 双向循环链表 ........................................................................................................................................................................................................................................................ 13 
NodeList.h ............................................................................................................................................................................................................................................................ 13 
DoubleList.h ....................................................................................................................................................................................................................................................... 14 
Test.cpp ................................................................................................................................................................................................................................................................. 20 
4、 单项循环链表 ........................................................................................................................................................................................................................................................ 21 
ListNode.h ............................................................................................................................................................................................................................................................ 21 
CircularList.h .................................................................................................................................................................................................................................................. 22 
Test.cpp ................................................................................................................................................................................................................................................................. 28 
5、 顺序栈 .................................................................................................................................................................................................................................................................... 29 
SeqStack.h ............................................................................................................................................................................................................................................................ 29 
Test.cpp ................................................................................................................................................................................................................................................................. 32 
6、 链式栈 .................................................................................................................................................................................................................................................................... 33 
StackNode.h .......................................................................................................................................................................................................................................................... 33 
LinkStack.h .......................................................................................................................................................................................................................................................... 33 
Test.cpp ................................................................................................................................................................................................................................................................. 36 
7.顺序队列 ........................................................................................................................................................................................................................................................................ 37 
SeqQueue.h ............................................................................................................................................................................................................................................................ 37 
Test.cpp ................................................................................................................................................................................................................................................................. 40 
8、链式队列 ...................................................................................................................................................................................................................................................................... 41 
QueueNode.h .......................................................................................................................................................................................................................................................... 41 

LinkQueue.h .......................................................................................................................................................................................................................................................... 42 
Test.cpp ................................................................................................................................................................................................................................................................. 44 
9、优先级队列 .................................................................................................................................................................................................................................................................. 45 
QueueNode.h .......................................................................................................................................................................................................................................................... 45 
Compare.h .............................................................................................................................................................................................................................................................. 46 
PriorityQueue.h ................................................................................................................................................................................................................................................ 47 
Test.cpp ................................................................................................................................................................................................................................................................. 50 
10、串 ................................................................................................................................................................................................................................................................................ 52 
MyString.h ............................................................................................................................................................................................................................................................ 52 
MyString.cpp ....................................................................................................................................................................................................................................................... 53 
test.cpp ................................................................................................................................................................................................................................................................. 60 
11、二叉树 ........................................................................................................................................................................................................................................................................ 61 
BinTreeNode.h ..................................................................................................................................................................................................................................................... 61 
BinaryTree.h ....................................................................................................................................................................................................................................................... 66 
Test.cpp ................................................................................................................................................................................................................................................................. 72 
12、线索二叉树 ................................................................................................................................................................................................................................................................ 74 
ThreadNode.h ....................................................................................................................................................................................................................................................... 74 
ThreadTree.h ....................................................................................................................................................................................................................................................... 75 
ThreadInorderIterator.h ............................................................................................................................................................................................................................. 75 
test.cpp ................................................................................................................................................................................................................................................................. 81 
13、堆 ................................................................................................................................................................................................................................................................................ 82 
MinHeap.h .............................................................................................................................................................................................................................................................. 82 
test.cpp ................................................................................................................................................................................................................................................................. 86 
14、哈夫曼树 .................................................................................................................................................................................................................................................................... 87 
BinTreeNode.h ..................................................................................................................................................................................................................................................... 87 
BinaryTree.h ....................................................................................................................................................................................................................................................... 89 
MinHeap.h .............................................................................................................................................................................................................................................................. 92 
Huffman.h .............................................................................................................................................................................................................................................................. 95 
Test.cpp ................................................................................................................................................................................................................................................................. 96 
15、树 ................................................................................................................................................................................................................................................................................ 96