数据结构与算法

出版时间：2009-6  出版社：科学出版社  作者：张千帆 编  页数：359  

前言

　　国家教育部于1998年7月6日公布了新的《普通高等学校本科专业目录》，将原来的经济信息管理、信息学、科技信息管理、林业信息管理和管理信息系统等专业合并为管理学科门类中的信息管理与信息系统专业。可以认为，这次合并既是学科相融的必然，也是国家信息化发展的需要。据有关资料介绍，到目前为止，全国已有超过200所高校开设了信息管理与信息系统专业。　　自20世纪40年代以来，信息技术经过60余年的高速发展，它对人类社会各个领域的影响越来越广泛和深入，其影响最大、受益最多的当属管理和经济领域。信息作为最主要的经济资源，已经被人们所接受，并且愈来愈受到重视。信息技术的普及和推广，信息资源的组织、开发和利用，促进了企业的发展和产业结构的调整。当前所实施的电子商务、电子政务和数字图书馆等工程直接加速了生产力的发展和促进了社会的进步。我国政府提出的“以信息化带动工业化”的战略举措，必将有力提升我国的综合国力，同时也为信息管理与信息系统专业带来极大的发展机遇和发展空间。　　信息管理与信息系统是一门交叉学科，它不是信息技术和管理科学的简单组合，而需要融合管理学、经济学、系统科学、运筹学和计算机科学于一体，因而，必须要有一套具有本专业特点的知识结构体系和适合本专业需要的教材体系。　　信息管理与信息系统专业从1998年设立至今的10多年来，许多专家学者在专业建设和教材建设方面倾注了大量的心血，有力地促进了专业和学科的发展。但是，由于该专业具有跨度大、内容新和变化快等特点，如何培养适应现代信息技术高速发展需要的、具有创新能力的、既懂信息技术又懂管理的复合型人才，对广大教育工作者而言是一个巨大的挑战。

内容概要

　　《数据结构与算法：C语言实现》主要介绍各种基本类型的数据结构及其算法实现。《数据结构与算法：C语言实现》所有算法都有算法功能说明、算法思想分析、详尽的实例描述、C语言编写并可编译执行的完整程序及运行结果图示，典型算法附有算法分析。《数据结构与算法：C语言实现》是数据结构的入门书籍，结构严谨，条理清晰，按照线性数据结构、层次数据结构和网状数据结构的顺序，由易到难介绍主要抽象数据类型及其应用，最后介绍各种查找和排序方法。抽象的数据结构原理与算法实现紧密结合的写作特点使读者能够快速而卓有成效地掌握数据结构原理和经典算法，以加深读者对数据结构和算法的理解，从而提高编程能力。　　《数据结构与算法：C语言实现》可以作为高等院校信息管理类专业的本科和专科教材，也可以作为其他理工科专业的选修教材或实验指导教材。

书籍目录

第1章　绪论1.1　数据结构与程序设计1.1.1　学习数据结构的意义1.1.2　数据与数据结构1.1.3　数据结构类型1.2　抽象数据类型1.2.1　C语言中的数据类型1.2.2　抽象数据类型1.3　算法分析1.3.1　问题、算法与程序1.3.2　算法效率的度量本章小结思考与练习题第2章　线性表2.1　线性表的基本概念2.1.1　线性表的定义与特点2.1.2　线性表的两类存储结构2.2　顺序表的算法实现2.2.1　顺序表的创建2.2.2　顺序表内结点的插入2.2.3　顺序表内结点的查找2.2.4　顺序表内元素的删除2.3　单链表的算法实现2.3.1　单链表的结点结构和一般形式2.3.2　单链表的创建2.3.3　单链表内元素的插入2.3.4　单链表内元素的查找2.3.5　单链表内元素的删除2.3.6　两个单链表的合并2.4　双向链表的算法实现2.4.1　双向链表的结点结构和一般形式2.4.2　双向链表的创建2.4.3　双向链表内元素的插入2.4.4　双向链表内元素的查找2.4.5　双向链表内元素的删除2.5　循环链表的算法实现2.5.1　循环链表的结点结构和一般形式2.5.2　循环链表的创建本章小结思考与练习题第3章　栈与队列3.1　栈的基本概念3.1.1　栈的定义与特点3.1.2　栈的两类存储结构3.2　顺序栈的算法实现3.2.1　顺序栈的建立和入栈3.2.2　顺序栈出栈3.3　队列的基本概念3.3.1　队列的定义与特点3.3.2　队列的存储结构3.4　顺序队列的算法实现3.4.1　顺序队列建立和入队3.4.2　顺序队列出队3.5　循环队列的算法实现3.5.1　循环队列建立和入队3.5.2　循环队列出队3.6　链队列的算法实现3.6.1　链队列建立和入队3.6.2　链队列出队3.7　栈和队列的应用——算术表达式求值本章小结思考与练习题第4章　串4.1　串的基本概念4.1.1　串的定义与特点4.1.2　串的存储结构4.2　串的算法实现4.2.1　串赋值算法4.2.2　求子串算法4.2.3　串比较算法4.2.4　串联接算法4.3　串的模式匹配算法实现4.3.1　串的朴素模式匹配算法4.3.2　改进的模式匹配算法本章小结思考与练习题第5章　数组和广义表5.1　数组的基本概念5.1.1　数组的定义与特点5.1.2　数组的存储结构5.2　特殊矩阵的压缩存储5.3　矩阵的算法实现5.4　广义表的基本概念5.4.1　广义表的定义与图形表示5.4.2　广义表的存储结构5.5　广义表的算法实现本章小结思考与练习题第6章　树和二叉树6.1　树的基本概念6.1.1　树的定义与基本术语6.1.2　树的表示形式和存储结构6.2　二叉树的基本概念6.2.1　二叉树的定义与性质6.2.2　二叉树的存储结构6.2.3　树、森林和二叉树的转换6.2.4　二叉树的遍历6.3　二叉树算法实现6.3.1　二叉树的建立6.3.2　递归的二叉树前序遍历6.3.3　非递归的二叉树前序遍历6.3.4　递归的二叉树中序遍历6.3.5　非递归的二叉树中序遍历6.3.6　递归的二叉树后序遍历6.3.7　非递归的二叉树后序遍历6.4　哈夫曼树及其应用6.4.1　哈夫曼树与哈夫曼编码6.4.2　哈夫曼算法实现本章小结思考与练习题第7章　图7.1　图的基本概念7.1.1　图的定义和术语7.1.2　图的表示与存储结构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.4　最小生成树算法实现7.4.1　普里姆算法7.4.2　克鲁斯卡尔算法7.5　图的应用7.5.1　拓扑排序7.5.2　关键路径7.5.3　最短路径本章小结思考与练习题第8章　查找8.1　查找的基本概念8.1.1　相关术语8.1.2　查找表结构8.2　顺序查找算法的实现8.3　折半查找算法的实现8.4　分块查找算法8.4.1　索引表8.4.2　分块查找算法实现8.5　二叉排序树及其算法实现8.5.1　二叉排序树及其查找过程8.5.2　二叉排序树插入结点的过程8.5.3　二叉排序树删除结点的过程8.5.4　二叉排序树的算法实现8.6　平衡二叉树及其算法实现8.6.1　平衡二叉排序树及其构造8.6.2　平衡二叉排序树算法实现8.7　B-树及其算法实现8.7.1　B-树8.7.2　B-树的查找8.7.3　B-树的插入8.7.4　B-树的删除8.7.5　B-树的算法实现8.8　哈希查找的算法实现8.8.1　哈希表8.8.2　哈希函数构造方法8.8.3　哈希冲突的处理方法8.8.4　哈希表的算法实现本章小结思考与练习题第9章　排序9.1　排序的基本概念9.1.1　术语介绍9.1.2　常用的内容排序算法简介类型9.2　插入排序的算法实现9.2.1　直接插入排序9.2.2　希尔排序9.3　快速排序的算法实现9.4　选择排序的算法实现9.4.1　直接选择排序9.4.2　堆排序9.5　归并排序的算法实现9.6　基数排序的算法实现9.7　各种内部排序方法的比较9.7.1　时间性能9.7.2　空间性能9.7.3　排序方法的稳定性9.8　外部排序本章小结思考与练习题第10章　文件10.1　文件的基本概念10.1.1　文件记录与文件结构10.1.2　文件操作10.2　文件的存储结构10.2.1　顺序文件10.2.2　索引文件10.2.3　散列文件10.2.4　多关键字文件10.2.5　倒排序文件本章小结思考与练习题参考文献

章节摘录

　　算法具有以下5个基本特征。　　1）输入：一个算法具有零个或若干个输入，这些输入取自于某个特定的对象集合。　　2）输出：一个算法至少产生一个输出或执行一个有意义操作，这些输出是同输入有着某些特定关系的量。　　3）有穷性：算法的指令执行序列是有限的。　　4）确定性：每一条指令的含义明确，无二义性。　　5）可执行性：每一条指令都应在有限的时间内完成。　　一个好的算法应满足以下5个目标。　　1）正确性：算法应确切地满足具体问题的需求，这是算法设计的基本目标。　　2）可读性：算法的可读性有利于人们对算法的理解，这既有利于程序的调试和维护，也有利于算法的交流和移植。算法的可读性主要体现在两方面：一是类名、对象名、方法名等的命名要见名知义；二是要有足够的注释。　　3）健壮性：当输入非法数据时算法要能做出适当的处理，而不应产生不可预料的结果。　　4）高时间效率：算法的时间效率是指算法的执行时间。对于同一个问题如果有多个算法可供选择，应尽可能选择执行时间短的算法。执行时间短的算法称作高时间效率的算法。　　5）低内存要求：算法在执行时一般要求额外的内存空间。对于同一个问题如果有多个算法可供选择，应尽可能选择内存要求低的算法。

编辑推荐

　　《数据结构与算法：C语言实现》共10章。第1章为数据结构概述，内容包括数据结构和抽象数据类型等概念及算法复杂度的度量。第2章至第7章介绍线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用。第8章介绍查找的基本概念，各种查找方法及其算法实现与算法分析。第9章介绍排序的概念及主要排序方法的排序原理、算法实现与算法分析。第10章介绍文件的基本概念及常用的文件结构。　　《数据结构与算法：C语言实现》可以作为高等院校信息管理类专业的本科和专科教材，也可以作为其他理工科专业的选修教材。教师可以根据本学校的专业特点、学生情况和教学学时，选讲部分章节的内容。