重要，注意：
纯系简单数据结构程序，也没仔细推敲检查，有点空余时间才写写的，不屑者不必往下看了！
No_1：链表的应用
根据书中的要求完成了全部功能，并将其做成一个命令加参数的形式使用
这个比较简单，尽管代码是最多的，注释比较少
也这只有这个是用C++写的，因为如果用C的话，估计代码还得多300行
本来这个程序是大一的时候就想写的了，只怪人懒，竟到了现在才完成，实在不像话了。
No_2：约瑟夫问题
按要求完成书中的全部功能，较为简单，只有少量注释
No_3：皇后问题
书中要求是八皇后问题，我这里计算出了n（程序当中是20,要更大只要改程序最上面那个宏的值就行了，当然时间会更长一些）皇后的所有解，每个解是一个0-1阵，在运行的时候，把它重定向到一个文件里慢慢看。
No_4：表达式求值
此程序我同时实现中缀转后缀还记录了临时结果，最后直接给出表达式结果，后缀表达式存在Q指向的队列中，临时结果存放在PostExp函数中A指向的局部栈中。但是只能处理一位数的加减乘除，两位数以上就不行了，感兴趣的朋友可以改进一下。
代码不长，觉得挺有意义的。
No_5：KMP算法
看到kmp我就想到了唐纳德啊！计算机科学巨人！那本《数据结构，课程设计》书上不是用KMP实现的，是改进的第二种模式匹配算法，这里实现了KMP的算法，用改进的求next数组的方法
No_6：文本文件单词的检索与计数
KMP的应用，很简单，注释就稍微少些，只有两个功能，我把它做成命令参数式，上次写一篇报告的时候拿它来试了试，竟然没错。要实际应用这个东西的朋友可以改改。
No_7：稀疏矩阵
本来应该是用真正的三元组表实现矩阵存储的，按书中要求，把三个量顺序放在一个数组里，我感觉这个难度应该比三元组表大些，于是就用一个一维数组来完成的，三个一组为一个数据元素。比如，本来是a[1][1]=2,a[2][2]=3的，存在一个一维数组里就成了1,1,2,2,2,3。
No_8：二叉树
二叉树按对应的完全二叉树建立，所以注意输入
TravelPostOrder
TravelPreOrder
TravelInOrder
以上三个函数分别是以后序、前序、中序访问二叉树
__TravelPostOrder
__TravelPreOrder
__TravelInOrder
这三个分别是上面三个的非递归实现
另外，按书上要求，最后用非递归的后序实现查找二叉树根到指定结点的路径
为使用方便，我的测试数据为：
"ABCD@EF@G@@@@H@@@IJ#"
默认是查找'E'，输出是'A C E'
一些比较明显的地方我就没有写注释了
No_9：Huffman编码
这个挺简单的，书上的代码错挺多的，我改了一下，就放在这了，也没有自己去写。
另外，里面有个select函数用到了引用，c里是没有的，得用g++来编译
没写注释了。
No_10：图
Dij算法，算单源最短路径，在计算过程中，只需要找到最长的一条最优解，若源点能到达的点必然在这条路径上，所以在存储的时候只需要用一个数组保存即可，到某个点的时候，一直向后找，就能回到源点，完成输出
Floyd算法，算任意两点间的最短路径。这里，用全局数组打表，弄清数组P就明白了全部内容在main里，先调用一次Floyd，把全部的路径都算出再查询
原书中要求可以循环查询，这里不再多写了，只是实现了这两个算法，在应用中如果图的数据结构和这里的一致，就可以直接使用这里的函数
输入时，应先建立图的结构，按i,j,w顺序输入邻接阵的行、列、值，再按提示就可以进行查询了
No_11：关键路径
这个程序用了引用，得用g++来编译，gcc会提示出错，现在写代码是不分C还是C++了，混用，哪个能解决问题就用哪个。但貌似C能解决的，C++都能解决，呵。当然还得按书上要求来。
本来这几个程序早该完成了，只怪时间太紧，每个星期写一点，竟写了这么久，实在差劲得紧。只写了这几个我觉得有些意义的内容。
书上还有要求写广义表的应用，这东西用lisp太easy了，懒得写了！最后两个程序是航班信息的查询与检索，和图书管理信息系统的设计与实现，太麻烦了，功能要求太多了，写下来少说得3、4千行吧！
最后，感谢柯老师把这本书借给我看，尽管书中错误挺多的，但还是让我学到不少东西！现在这本书对我应该没用了！
如果下载太慢可以去Tofree社区下载，我在那也放了一个链接：
 |
| 文件: | ds.tar.gz |
| 大小: | 154KB |
| 下载: | 下载 |
|
阅读(2475) | 评论(1) | 转发(0) |
