数据结构与算法实用教程
2008-7
机械工业出版社
高佳琴 著
163
数据结构是计算机程序设计的重要基础，是计算机各专业的核心课程。本书以浅显易懂的文字和大量的例题对数据结构的相关主题进行讲解，对问题的解决方法与流程做了详尽的图形剖析，辅以结构化流程图与C语言程序代码进行算法描述，从而增进读者对问题的理解。帮助读者更好地理解和灵活地运用相关知识点。 本书共分lO章，对应的主题分别为数据结构概论、顺序表、链表、栈与队列、字符串与数组、递归、树、查找、排序、图及常用算法介绍。 本书的主要特点有： 1．从应用入手，首先介绍每一个主题的实用性，然后再分解成相关知识点进行剖析。 2．涵盖了“全国计算机等级考试(二、三、四级)”及“中国计算机技术与软件专业技术资格考试”中程序员级别的考核内容。 3．本书对算法的描述充分体现了健壮性及规范性，注重培养学生逐步形成良好的编程习惯。 4．理论知识的阐述由浅入深，加强课程间的联系(特别是与c语言)。将抽象的理论阐述尽量用简明的形式化语言描述，省略了一些复杂的理论推导和数学证明。 5．本书附录B给出了《数据结构与算法》课程标准，该标准从教学内容、教学方法、考核方式等方面进行具体的阐述，对该课程教学和学习有较好的指导作用。 本书建议课时为64学时，上机时数为16学时。 本书由常州轻工职业技术学院高佳琴副教授任主编，参与编写的老师包括蒋晖、乔明中、申燕萍、周国华，陆兵老师对全部书稿进行了审阅。由于编者水平有限，错误之处在所难免，恳请广大读者批评指正。
《普通高等教育“十一五”国家级规划教材·高职高专计算机类专业规划教材：数据结构与算法实用教程》在简要回顾了基本的C程序设计概念的基础上，逐步引入与程序设计相关的算法与数据结构等基本概念，系统地介绍了顺序表、链表、队列与栈、树、图等基本数据结构，以及递归、查找与排序等多种算法。 《普通高等教育“十一五”国家级规划教材·高职高专计算机类专业规划教材：数据结构与算法实用教程》的理论知识点涵盖了“全国计算机等级考试”及“中国计算机技术与软件专业技术资格考试”中程序员级的程序设计及算法基础。全部算法用C语言书写，并配有结构化流程图，结构清晰、重点难点突出、通俗易学，具有较好的可读性与可移植性。 《普通高等教育“十一五”国家级规划教材·高职高专计算机类专业规划教材：数据结构与算法实用教程》共10章，每章都配有丰富的、类型多样的习题，并且提供了体现各主题基本任务的上机实验题。 《普通高等教育“十一五”国家级规划教材·高职高专计算机类专业规划教材：数据结构与算法实用教程》是一本实践性、应用性很强的有关数据结构与常用算法的教材，可作为高职高专软件技术及相关专业的“数据结构”课程教材，对于软件技术从业人员也是一本很好的参考书。
前言第1章概述1．1什么是数据结构1．2基本概念和术语1．3算法和算法分析1．3．1算法及其描述1．3．2算法性能和复杂度分析1．4c语言基础1．4．1数组1．4．2指针1．4．3结构体类型1．4．4c程序的调试方法本章小结习题一第2章顺序表2．1线性表的定义及逻辑结构2．2线性表的基本操作2．3线性表的顺序存储结构2．4顺序表基本操作的实现2．4．1顺序表的初始化2．4．2顺序表中元素的插入2．4．3顺序表中元素的删除2．4．4顺序表的按值查找2．5顺序表应用本章小结习题二实验一顺序表应用第3章链表3．1单链表3．1．1单链表的基本概念3．1．2单链表的数据类型3．2循环链表3．3双向链表3．3．1双向链表的基本概念3．3．2双向链表的插入与删除的算法3．4应用举例及分析本章小结习题三实验二链表的应用第4章栈与队列4．1栈4．1．1栈的基本概念4．1．2栈的存储方式和基本操作的实现算法4．2队列4．2．1队列的基本概念4．2．2队列的基本操作4．2．3队列的存储方式和基本操作的实现算法4．3栈与队列的应用4．3．1栈的应用4．3．2队列的应用本章小结习题四实验三栈的应用第5章字符串与多维数组5，1串5．1．1串的基本概念5．1．2串的存储结构5．1．3串基本操作的实现算法5．1．4串的应用5．2数组5．2．1数组的定义5．2．2数组的存储结构5．2．3特殊矩阵的压缩存储5．2．4稀疏矩阵的压缩存储5．2．5数组的应用本章小结习题五实验四字符串与数组第6章递归6．1递归的基本概念和实现原理6．2递归算法实现6．2．1递归算法实现的基本步骤6．2．2递归的应用6．3递归问题的非递归实现6．3．1简单递归问题的转换6．3．2借助栈实现非递归过程习题六实验五递归第7章树与二叉树7．1树的定义和基本运算7．1．1树的定义7．1．2基本术语7．1．3树的基本运算7．2二叉树7．2．1二叉树的定义7．2．2二叉树的性质7．2．3二叉树的存储7．2．4遍历二叉树7．2．5哈夫曼树7．3树、森林和二叉树的转换7．3．1树的存储结构7．3．2树与二叉树的转换7．3．3森林转换为二叉树7．3．4二叉树转换为树和森林7．3．5树和森林的遍历习题七实验六树第8章排序与查找8．1排序基本概念8．2简单排序方法8．3快速排序8．4归并排序8．5查找基本概念和术语8．6静态查找表8．7动态查找表8．8哈希表查找8．8．1哈希表与哈希方法8．8．2常用的哈希函数8．8．3处理冲突的方法8．8．4哈希表的查找分析习题八实验七排序第9章图9．1图的概念和术语9．2图的存储方式9．3图的遍历9．4最小生成树本章小结习题九实验八图的创建与遍历第10章常用算法10．1穷举法10．2回溯法10．3分治法10．4贪婪法10．5递推法10．6动态规划法附录附录A Turbo c集成环境的调试功能附录B《数据结构与算法》课程标准参考文献
第3章 链 本章主要介绍线性表的链式存储结构及其特点，基于链表的基本操作的实现。具体介绍了链表的三种形式：单链表、循环链表和双向链表。最后分析了链表的一些典型应用。 本章要点： 1）链表的存储方式。 2）单链表的定义、结构和特点，单链表的插入与删除等算法。 3）循环单链表的结构和特点，以及用循环单链表解决问题的方法。 4）双向链表的定义、结构和特点，相关操作的实现。 本章难点： 1）链表的结构特点。 2）各种链表结构中基本操作的实现方法。 3）链表的应用。 插入和删除元素是线性表的两种最常用的操作，在第2章中介绍了顺序表的插人和删除需要移动大量的元素，影响了运行效率。在具体应用时，为了克服顺序存储带来的一些缺点，可以采用另外一种形式来存储线性表，即链式存储结构。通常把链式存储的线性表简称为链表。链表中数据的逻辑结构和物理存储相互独立，逻辑关系上相邻的元素在物理位置上不一定相邻。 3.1 单链表链表是用一组任意的存储单元来存放线性表的数据元素，这些存储单元可以是连续的，也可以是不连续的。那么如何来反映数据元素之间的逻辑关系呢?指针是用来映射数据元素之间的逻辑关系的途径。 3.1.1 单链表的基本概念 链式存储结构中，对线性表的每一个数据元素，都需要用两部分来存储：一部分用于存放数据元素的值，称为数据域；另外一部分用于存放该结点的直接前驱或直接后继结点的地址（指针），称为指针域。
