数据结构与算法教程
2012-10
唐宁九、游洪跃、孙界平、 朱宏 清华大学出版社 (2012-10出版)
唐宁九，游洪跃，孙界平，等 编
162
《高等学校计算机课程规划教材：数据结构与算法教程（C++版）实验和课程设计》结合C++面向对象程序设计的特点，讨论了数据结构与算法基础知识，并构建了实验与课程设计，对所有算法都在Visual C++6.0、Visual C++2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中进行了严格的测试，并在作者个人网页上提供了大量的教学支持内容。 通过本书的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力。《高等学校计算机课程规划教材：数据结构与算法教程（C++版）实验和课程设计》可作为数据结构、数据结构与算法分析、数据结构与算法设计、数据结构与算法等课程实验与课程设计的教材，也可供其他从事软件开发工作的读者学习参考使用。
第一部分基础知识 1.1绪论 1.1.1数据结构的基本概念 1.1.2算法和算法分析 1.1.3实用程序软件包 1.2线性表 1.2.1线性表的逻辑结构 1.2.2线性表的顺序存储结构 1.2.3线性表的链式存储结构 1.3栈和队列 1.3.1栈 1.3.2队列 1.4 串 1.4.1串类型的定义 1.4.2字符串模式匹配算法 1.5数组和广义表 1.5.1数组 1.5.2矩阵 1.5.3广义表 1.6树和二叉树 1.6.1树的基本概念 1.6.2二叉树 1.6.3二叉树遍历 1.6.4线索二叉树 1.6.5树和森林 1.6.6哈夫曼树与哈夫曼编码 1.6.7树的计数 1.7图 1.7.1图的定义和术语 1.7.2图的存储表示 1.7.3图的遍历 1.7.4图的最小代价生成树 1.7.5有向无环图及应用 1.7.6最短路径 1.8查找 1.8.1查找的基本概念 1.8.2静态表的查找 1.8.3动态查找表 1.8.4散列表 1.9排序 1.9.1概述 1.9.2插入排序 1.9.3交换排序 1.9.4选择排序 1.9.5归并排序 1.9.6基数排序 1.9.7外部排序 1.10文件 1.10.1主存储器和辅助存储器 1.10.2各种常用文件结构 1.11算法设计与分析 1.11.1算法设计 1.11.2算法分析 第二部分实验 实验1不带头结点形式的单链表 实验2改造串类 实验3引用数使用空间表法广义表存储结构 实验4改进哈夫曼树类模板 实验5改造最小生成树的Kruskal算法的实现 实验6链地址法处理冲突的散列表 实验7优化快速排序算法的实现 实验8n皇后问题 第三部分课程设计 项目1算术表达式求值 项目2简单文本编辑器 项目3压缩软件 项目4公园导游系统 项目5专家系统应用——动物游戏 项目6词典变位词检索系统 附录A课本的软件包 附录B实验报告格式 附录C课程设计报告格式 参考文献
版权页： 插图： 1.8 查找 1.8.1 查找的基本概念 查找表（Search Table）是由同一类型的数据元素（或记录）所组成的集合。 对查找表通常有如下4种操作。 ①查询某个“特定的”数据元素是否在查找表中。 ②检索某个“特定的”数据元素的各种属性。 ③在查找表中插入一个数据元素。 ④从查找表中删除某个元素。 前两种操作统称为“查找”的操作，如果只对查找表进行前两种“查找”的操作，也就是查找表的元素不发生变化，这样的查找表称为静态查找表（Static Serach Table）；如在查找过程中同时还要插入查找表中不存在的数据元素或从查找表中删除已存在的某个数据元素，也就是查找表的的数据元素要发生变化，这样的查找表称为动态查找表（DynamicSerach Table）。 关键字是数据元素（或记录）中某个数据项的值，用它可标识（识别）一个数据元素（或记录）。对于查找表，假设每个数据元素都与一个关键字相关，并且记录都可按关键字进行比较，可以使用类型转换函数自动将数据元素类型转换为关键字类型，从而实现将数据元素的比较自动转换为关键字的比较。 1.8.2静态表的查找 1.顺序查找 一般采用数组表示静态表，其查找过程是从第l个记录开始逐个地对记录的关键字的值进行比较，如某个记录的关键字的值和给定值相等，则查找成功，返回此记录的序号；如果直到最后一个记录的关键字的值都和给定值不相等，则表示查找表中没有所查的记录，查找失败，返回—1。 2.有序表的查找 有序表是指查找表的元素按关键字有序，也就是满足： 有序表一般采用折半查找（Binary Serach）来实现，折半查找的本质是首先确定待查元素所在的范围，然后再逐步缩小范围（区间），直到查找到元素或查找失败为止。 折半查找过程是用查找区间的中间位置元素的关键字与给定值进行比较，如相等，则查找成功，如不相等，将缩小范围，直到新的区间中间位置的关键字等于给定值或low>high（表示找查失败）时为止。 对于折半查找，一般通过折半查找判定树进行分析，设待查区间为[low，high]，则折半查找判定树递归定义如下。
《高等学校计算机课程规划教材:数据结构与算法教程(C++版)实验和课程设计》可作为数据结构、数据结构与算法分析、数据结构与算法设计、数据结构与算法等课程实验与课程设计的教材，也可供其他从事软件开发工作的读者学习参考使用。
