本书以高等工科院校本科计算机类专业、信息技术类专业和相关专业“应用型”人才培养为目标而编写。以学习软件设计开发中涉及到的各种数据结构及常用算法和解决基本应用问题的实际应用需求为基本点，深入介绍了各种数据结构的定义（逻辑结构、存储结构和基本算法）和基本应用等方面的知识。本书以“数据结构”的逻辑结构作为引线，突出以实例和应用为特色，把数据结构与算法问题同应用问题结合起来，通过介绍大量的应用问题，缩短了理论知识与应用问题之间的距离。



        全书共11章。在本书第2版编写过程中，编者以有利于读者学习目的，对教材中的有关数据结构与算法的基本知识重新用通俗的语言进行了描述，更换了部分例题；对所有基本算法和源程序进行了调试；为方便教师教学和学生学习，重新编写了每章的教学目标和教学提示；对章后配备的填空题、判断题、选择题、简答题和算法设计题等多种类型的习题，重新进行设计和编排，同时给出了所有习题的参考答案。



        本教材第1版被审定为省级“十一五”规划教材，《数据结构与算法》课程获得省级“精品课程”称号，获得较好的评价。



        本书可作为理工科高等院校计算机工程类、软件工程类和信息技术类等相关专业的教材，也可供从事相关工作的科技工作者参考。

        如何合理地组织数据、高效率地处理数据是扩大计算机应用领域、提高软件效率的关键。在软件开发过程中要求“高效地”组织数据和设计出“好的”算法，并使算法用程序来实现，通过调试而成为软件，必须具备数据结构领域和算法设计领域的专门知识。



        《数据结构与算法》课程主要学习在软件开发中涉及到的各种常用数据结构及其常用算法，在此基础上，学习如何利用数据结构和算法解决一些基本的应用问题。通过学习，使读者基本掌握相关领域的基础知识和基本应用。



        本教材为达到高等工科院校“应用型”人才的培养目标，在吸收了国、内外教材的知识体系结构的基础上，参考了众多的应用资料并根据主编多年在高校讲授《数据结构》课程的体会而编写。教材有以下几个特色。



        （1）学习一种数据结构必须掌握该数据结构的定义（逻辑结构、存储结构和基本算法）和基本应用两个方面的知识。所以，本教材以“结构”为特色，每一个数据结构的学习都围绕着该数据结构的定义，通过数据结构的逻辑结构、存储结构、基本算法和相关应用问题来介绍其基本知识和应用知识。数据的存储结构是学习和掌握算法的基础，本书在“算法的数据类型”部分中加以突出介绍。学生掌握的是数据结构的完整知识并能学为所用。



        （2）本书的知识结构以“数据结构”的逻辑结构作为引线。第1章作为本书的学习基础和预备知识。其后内容分为4个部分，从数据的逻辑结构来看，第一部分学习的是逻辑结构为“线性”的数据结构，包括第2章～第6章；第二部分学习的是逻辑结构为“树形”的数据结构，包括第7章～第8章；第三部分学习的是逻辑结构为“集合型”的数据元素，在散列存储方法下的数据结构，包括第9章；第四部分学习的是逻辑结构为“图形”的数据结构，包括第10章。第11章重点讨论了算法和程序性能分析以及算法设计方法的基本问题。这样划分教材章节的原因是：使采用本书作为教材的读者能够掌握什么是数据结构，如何设计算法以及能解决什么问题。以突出“数据结构”主题。



        （3）教材中注重工科“应用型”人才培养的需求和学习方法。吸收理工科教材的特色，在介绍新的知识点时，没有大段的文字描述，而是尽可能地采用具体的例题来加强其学习效果。



        （4）本教材中介绍了大量的应用问题。把数据结构与算法问题同应用问题结合起来，缩短了理论知识与应用问题之间的距离，在附录A中，给出了第2章～第10章中重要的基本算法和应用问题的源程序，适合工科院校相关专业的学生参考使用。对课程设计环节有很好的辅助作用、指导作用。



        （5）教材中注意了算法设计能力的培养。学习和培养算法设计能力是本课程的主要教学目的之一，本教材中注重介绍算法的设计过程和算法分析；在上机实验环节中，将引领学生编写十余个从简单到有一定难度的算法；在习题中，安排了一定量的基础题和适量的算法设计题，供教师和学生在教学中参考使用。



        本书共分11章。第1章“数据结构和算法”作为全书的导引，主要包括有关数据、数据类型、数据结构、算法、算法实现（算法描述工具——C语言）、C语言使用中的相关问题和算法分析等基本概念和相关知识。其中重点是数据、数据类型、数据结构和算法等概念；对于本教材使用的算法描述工具——C语言，则介绍了指针、结构变量、函数、递归、动态存储分配、文件操作、程序测试与调试问题等内容，以方便本课程与C语言课程的衔接，便于教学。



        第2章～第6章是逻辑结构为“线性”的数据结构及其应用知识内容。



        第2章“顺序表及其应用”主要介绍的是线性逻辑结构的数据在顺序存储方法下的数据结构顺序表（包括顺序串）的概念、数据类型、数据结构、基本运算及相关应用问题。其中重点一是顺序表的定义、数据类型、数据结构、基本算法和性能分析等概念和相关知识；二是顺序表的应用，包括查找问题（简单顺序查找、二分查找、分块查找）、排序问题（直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、归并排序）、字符处理问题（模式匹配）等内容。第3章“链表及其应用”主要介绍的是线性逻辑结构的数据在链接存储方法下的数据结构链表的相关知识。主要是单链表、循环链表的数据类型描述、数据结构、基本运算及其实现以及链表的相关应用问题，在此基础上介绍了链串的相关知识。在应用方面有多项式的相加问题、归并问题、箱子排序问题和链表在字符处理方面的应用问题等。第4章“堆栈及其应用”介绍在两种不同的存储结构下设计的堆栈，即顺序栈和链栈的相关知识，了解堆栈的相关应用，掌握应用堆栈来解决实际问题的思想及方法。第5章“队列及其应用”主要介绍顺序存储和链接存储方法下的两种队列、顺序（循环）队列和链队列的数据结构、基本运算及其性能分析以及应用。第6章“特殊矩阵、广义表及其应用”将学习数组、稀疏矩阵和广义表的基本概念，几种特殊矩阵的存储结构及基本运算，在此基础上学习特殊矩阵的计算算法与广义表应用等相关问题。本章的重点是相关数据结构的存储结构及基本运算算法。



        第7章和第8章是逻辑结构为“树形”的数据结构及其应用知识内容。



        第7章“二叉树及其应用”的知识结构主要是：非线性数据结构二叉树的定义、性质、逻辑结构、存储结构及其各种基本运算算法，包括二叉树的建立、遍历、线索化和表达式求值等算法。在此基础上，介绍二叉树的一些应用问题，包括哈夫曼编码问题、（平衡）二叉排序树问题和堆排序问题等。第8章“树和森林及其应用”介绍树和森林的数据结构、基本算法及其性能分析，树和森林与二叉树之间的转换算法等，在此基础上介绍树的应用——B-树，应用B-树来实现数据元素的动态查找。



        第9章“散列结构及其应用”是逻辑结构为“集合型”的数据元素在散列存储方法下的数据结构及其应用知识内容。主要介绍散列结构的概念、散列存储结构——散列表、散列函数和散列表中解决冲突的处理方法——开放定址法、链地址法以及散列表的基本算法及其性能分析，在散列结构的应用方面介绍散列结构的查找问题、LZW压缩/解压缩问题和直接存取文件问题。



        第10章“图及其应用”是逻辑结构为“图形”的数据结构及其应用知识内容，主要介绍图的定义和基础知识，图的4种存储结构，图的基本算法以及图的典型应用问题（最小生成树、最短路径、拓扑排序和关键路径等）。



        第11章“算法性能分析和算法设计方法简介”主要对算法和程序性能分析中的目的、时间复杂性和空间复杂性、复杂性要素和分析方法、时间复杂性上（下）限值、算法性能测量等问题进行讨论，并结合货箱装船、0/1背包和迷宫老鼠等问题介绍优化问题、分而治之、贪婪算法和回溯算法等基本的算法设计方法的基本知识，介绍NP-复杂问题和NP-完全问题。通过对本章的学习，使读者初步了解算法设计的常用方法，知道什么是“优质”算法和程序以及如何测量、评价算法的知识。



        每章都有教学目标和教学提示，每章后面都配备有一定量的填空题、判断题、选择题、简答题和算法设计题，供读者选用。习题的参考答案或者提示在教学网站中给出，主页地址：http://edu.tqbooks.net。



        本教材适合理工科高等院校本科计算机工程类专业、信息技术类专业和软件工程类相关专业使用。减少部分教学内容，也可以作为专科教学使用。同时也是相关专业的读者了解和学习数据结构与算法的一本很好的入门教材。



        需要特别说明的是，本书中较细致地介绍了较多的应用问题及其算法，教学过程中由于受到教学课时的限制或者根据本校培养目标要求以及学生的实际情况，可以选讲本书中打“*”号的章节内容，也可安排有兴趣的学生选修。



        本教材由王昆仑、李红主编，编写工作由王昆仑、李红和许强完成，其中王昆仑编写了第1、5、6、9、11章，李红编写了第2、3、4、7章，许强编写了第8、10章。教材中的全部算法由项响琴在Microsoft Visual C++ 6.0环境中进行了调试，董靖完成了部分章节的绘图工作，屠菁、黄小杰、林晓燕、彭晓舟等为本书的编写工作给予了很大的支持。另外，本书的编写工作得到了省、校两级精品课程建设项目基金的资助，还得到了计算机教育界同行的关心和帮助，在此一并致谢！



        由于数据结构与算法的应用发展迅速，加之编者水平有限，书中疏漏和不妥之处恳请读者批评指正，电子邮箱：kunlunwang@126.com。
 
编 者

     2007年2月

 

第1章  数据结构与算法

第2章  顺序表及其应用

第3章  链表及其应用

第4章  堆栈及其应用

第5章  队列及其应用

第6章  特殊矩阵、广义表及其应用

第7章  二叉树及其应用

第8章  树和森林及其应用

第9章  散列结构及其应用

第10章  图及其应用

第11章  算法性能分析和算法设计方法简介

无