迎战下周自考数据结构实践科目

编写完成重点数据结构和算法： 0.链表 1.栈 2.队列 3.二叉树数据结构和构建 4.前序中序后序遍历二叉树 5.构建哈夫曼树（最优二叉树） 6.图数据结构，图的深度优先遍历和广度优先遍历 7.拓扑排序 8.直接插入排序 9.希尔排序 10.希尔排序 11.冒泡排序 12.快速排序 13.直接选择排序 14.堆排序 15.归并排序 16.箱排序和基数排序 17.顺序查找，二分查找，索引顺序查找
  1 // ExamTest.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include "stdlib.h"
  6 #include <string>
  7 /************************************************************************/
  8 /*                栈数据结构                                              */
  9 /************************************************************************/
 10 #define StackSize 1024    //栈大小
 11 typedef char DataType;
 12 typedef struct  
 13 {
 14     DataType data[StackSize];    //栈数组
 15     int top;    //栈顶索引
 16 }Stack;
 17 
 18 //清空栈
 19 void InitStack(Stack * s)
 20 {
 21     if(s == NULL)
 22         return;
 23     s->top = -1;
 24 }
 25 //判断是否满栈
 26 bool StatckEmpty(Stack* s)
 27 {
 28     if(s == NULL)
 29         return false;
 30     return s->top == StackSize-1;
 31 }
 32 //进栈
 33 void PushStack(Stack* s,DataType x)
 34 {
 35     if(s == NULL)
 36         return;
 37     if(StatckEmpty(s))
 38         return;
 39     else
 40     {
 41         //规定当前入栈完成后指向当前的数据
 42         s->top = s->top +1;
 43         s->data[s->top] = x;
 44     }
 45 }
 46 //出栈
 47 DataType PopStack(Stack* s)
 48 {
 49     if(s == NULL)
 50     {
 51         exit(0);
 52     }
 53     if(StatckEmpty(s))
 54     {
 55         printf("Stack is empty .
");
 56         exit(0);
 57     }
 58     else
 59     {
 60         return s->data[s->top--]; //先用后减
 61     }
 62 }
 63 
 64 //获取栈顶元素
 65 DataType GetTop(Stack* s)
 66 {
 67     if(s == NULL)
 68     {
 69         exit(0);
 70     }
 71     if(StatckEmpty(s))
 72     {
 73         printf("Stack empty . 
");
 74         exit(0);
 75     }
 76     else
 77     {
 78         return s->data[s->top];
 79     }
 80 }
 81 
 82 /************************************************************************/
 83 /*                队列数据结构（循环队列）                              */
 84 /************************************************************************/
 85 #define QUEUESIZE 1024
 86 typedef struct
 87 {
 88     DataType data[QUEUESIZE];    //队列数组
 89     int front;    //队列头
 90     int rear;    //队列尾部
 91 }Queue; 
 92 
 93 //初始化队列
 94 void InitQueue(Queue* q)
 95 {
 96     if(q == NULL)
 97         return;
 98     q->front = 0;
 99     q->rear = 0;
100 }
101 
102 //判断栈是否为空
103 bool QueueEmpty(Queue* q)
104 {
105     if(q == NULL)
106         return false;
107     else
108         return q->front == q->rear;
109 }
110 
111 //判断队列是否满
112 bool QueueFull(Queue* q)
113 {
114     if(q == NULL)
115         return false;
116     return (q->rear + 1) % QUEUESIZE == q->front; 
117 }
118 
119 //入队列
120 void InsertQueue(Queue* q,DataType x)
121 {
122     if(q == NULL)
123         return;
124     if(QueueFull(q))
125     {
126         printf("Queue Full !
");
127     }
128     else
129     {
130         //队尾添加，队尾指向后面一个为空的
131         q->data[q->rear] = x;
132         q->rear = (q->rear + 1) % QUEUESIZE;
133     }
134 }
135 
136 //出队列
137 DataType DelQueue(Queue* q)
138 {
139     DataType x;
140     if(QueueEmpty(q))
141     {
142         printf("Queue is Empty 
");
143         exit(0);
144     }
145     else
146     {
147         x = q->data[q->front];
148         q->front = (q->front + 1) % QUEUESIZE;
149         return x;
150     }
151 }
152 
153 //取队头元素
154 DataType GetFrontData(Queue* q)
155 {
156     if(QueueEmpty(q))
157     {
158         printf("queue is empty!
");
159         exit(0);
160     }
161     else
162     {
163         return q->data[q->front];
164     }
165 }
166 
167 //取队尾元素
168 DataType GetRearData(Queue* q)
169 {
170     if(QueueEmpty(q))
171     {
172         printf("queue is empty !");
173         exit(0);
174     }
175     else
176     {
177         return q->data[q->rear];
178     }
179 }
180 /* 字符串匹配（判断一个子串是否是另一个字符串的子串）*/
181 bool IsSubString()
182 {
183     char parentString[1024];
184     char subString[1024];
185     printf("please input parent string!
");
186     scanf("%s",parentString);
187     printf("please input sub string!
");
188     scanf("%s",subString);
189 
190     int nParent = strlen(parentString);
191     int nSub = strlen(subString);
192     /*
193         1. 如果子串的字符数量大于父串的数量则匹配失败
194         2. 子串的数量大于父串的数量，匹配比较。
195     */
196     if(nSub > nParent)
197         return false;
198     for(int i = 0; i <= nParent; i++)
199     {
200         int k = i;
201         if((nParent - k) < nSub)
202             return false;
203         for(int j = 0; j <= nSub; j++)
204         {
205             if(subString[j] == parentString[k])
206             {
207                 if(j == nSub -1)
208                     return true;
209                 k++;
210             }
211             else
212             {
213                 break;
214             }
215         }
216     }
217     return false;
218 }
219 typedef struct BinNode
220 {
221     DataType data;
222     BinNode* lChild;
223     BinNode* rChild;
224 }BinNTree;
225 
226 typedef BinNode* BinTree;
227 char* str = "ABDH#K###E##CFI###G#J##";
228 //构造一个二叉树，使用前序创建，#表示对应的节点为NULL
229 int index = 0;
230 void creatBinTree(BinNTree** t)
231 {
232     if( (*t) = (BinNTree*) malloc(sizeof(BinNTree)))
233     {
234         char ch = str[index++];
235         if(ch == '#')
236         {
237             (*t) = NULL;
238             return;
239         }
240         (*t)->data = ch;
241         creatBinTree(&(*t)->lChild);
242         creatBinTree(&(*t)->rChild);
243     }
244 };
245 
246 //清空二叉树
247 void clearBinTree(BinNTree* t)
248 {
249     if(t == NULL)
250         return;
251 
252     if(t->lChild)
253         clearBinTree(t->lChild);
254     if(t->rChild)
255         clearBinTree(t->rChild);
256     free(t);
257 }
258 //求二叉树深度
259 int getBinTreeDeep(BinNTree* & t)
260 {
261     int i = 0;
262     int j = 0;
263     if(!t)
264         return 0;
265     if(t->lChild)
266         i = getBinTreeDeep(t->lChild);
267     if(t->rChild)
268         j = getBinTreeDeep(t->rChild);
269     return i > j? i+1:j+1;
270 }
271 
272 //前序遍历
273 void preOrder(BinNTree* t)
274 {
275     if(t == NULL)
276         return;
277     printf("%c ",t->data);
278     preOrder(t->lChild);
279     preOrder(t->rChild);
280 }
281 
282 //中序遍历
283 void inOrder(BinNTree* t)
284 {
285     if(t == NULL)
286         return;
287     inOrder(t->lChild);
288     printf("%c ",t->data);
289     inOrder(t->rChild);
290 }
291 
292 //后序遍历
293 void postOrder(BinNTree* t)
294 {
295     if(t == NULL)
296         return;
297     postOrder(t->lChild);
298     postOrder(t->rChild);
299     printf("%c ",t->data);
300 }
301 
302 //查找二叉树中是否存在某值
303 bool find(BinNTree* t,DataType data)
304 {
305     if(t == NULL)
306         return false;
307     if(t->data == data)
308         return true;
309     if(find(t->lChild,data))
310         return true;
311     return find(t->rChild,data);
312 
313 }
314 
315 int _tmain(int argc, _TCHAR* argv[])
316 {
317     /*    // 字符串匹配函数测试
318     while (1)
319     {
320         if(IsSubString())
321         {
322             printf("this is subString for parentString!
");
323         }
324         else
325         {
326             printf("sorry,this is not subString for parentString
");
327         }
328     }
329     */
330 
331     /************************************************************************/
332     /*            二叉树测试                                                  */
333     /************************************************************************/
334     BinTree t = NULL;
335     creatBinTree(&t);
336     int nDept = getBinTreeDeep(t);
337     printf("this BinTree Depth is: %d
",nDept);
338     printf("前序遍历结果:");
339     preOrder(t);
340     printf("
后序遍历结果:");
341     postOrder(t);
342     printf("
中序遍历结果:");
343     inOrder(t);
344     getchar();
345 }