数据结构

出版时间：2009-8  出版社：北京邮电大学出版社  作者：马睿，孙丽云 主编  页数：287  

前言

　　“数据结构”是高等院校计算机、信息管理与信息系统等相关专业的一门必修、经典的核心课程之一，是计算机软件的基础课程。　　本书主要讨论现实世界中数据的各种逻辑结构、在计算机中的存储结构以及进行各种非数值运算的算法，旨在使软件开发和维护人员学习分析研究计算机加工的数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构、存储结构及相应的运算，把现实中的问题转化为计算机内部的数据表示和数据处理。　　本书是在深入研究国内外有关数据结构的教材和大量资料的基础上，结合作者科研任务及多年教学经验组织编写而成的。本教材注重理论与实践的统一，逻辑性强，内容精练。在讲解具体内容时，特别注重实用性，尽量列举实例，在叙述上力求深入浅出，通俗易懂。　　书中所有算法的描述均采用C语言函数的形式来描述，这些函数均已在Turbo C 3．0上调试运行通过，并加以详细的注释，以利于读者理解算法的基本思想，同时方便学生在计算机上验证相关算法。　　全书分成10章，系统地介绍了线性表、栈、队列、串、数组、树、图等基本数据结构的内在逻辑关系、在计算机中的存储表示及其各种运算的实现，介绍了查找和排序的各种算法以及算法的实现。　　本书各章配有丰富的习题和例题。习题的类型包括选择题、填空题、操作题和算法设计题。每章后的习题能够加深对各章内容的认识，让学生通过动手操作掌握知识。　　本书由马睿和孙丽云任主编，其中马睿编写第1章和第7章，孙丽云编写了第3章和第9章，邵兰洁编写了第6章，靳丽编写了第2章，白艳霞编写了第8章，李珊编写了第4章，李立芬编写了第5章，云彩霞编写了第10章，李月军，裘琳玲等也参与了本书的编写工作。　　非常感谢北京化工大学北方学院莫德举院长和北京邮电大学出版社在本书编写过程中给予的指导和帮助。

内容概要

“数据结构”是计算机相关专业的重要基础核心课程之一，是一门集技术性、理论性和实践性于一体的课程。本书重点介绍基本数据结构、C语言数据结构描述、数据结构的应用、算法设计与分析以及算法性能评价等内容，使读者理解数据抽象与编程实现的关系，提高用计算机解决实际fq题的能力。全书共10章，主要内容包括线性表、栈、队列、串、数组、树、图、查找、排序和文件。    本书结构合理，重点突出，内容精练，通俗易懂，实例丰富，算法描述清晰。本书适用于高等院校应用型本科计算机及相关专业，可作为信息类及相关专业的教材或参考书，也可供成人高校、高职高专选用。

书籍目录

第1章 绪论  1.1 引言    1.1.1 为什么要学习数据结构    1.1.2 数据结构课程的主要内容  1.2 基本概念和常用术语    1.2.1 基本概念和术语    1.2.2 数据结构    1.2.3 抽象数据类型  1.3 算法和算法分析    1.3.1 算法的定义    1.3.2 算法评价与分析    1.3.3 算法效率的度量  1.4 本章小结  习题第2章 线性表  2.1 线性表的逻辑结构    2.1.1 线性表的定义    2.1.2 线性表的基本运算  2.2 线性表的顺序存储及运算实现    2.2.1 线性表的顺序存储结构    2.2.2 顺序表上基本运算的实现  2.3 线性表的链式存储及运算实现    2.3.1 单链表    2.3.2 循环链表    2.3.3 双向链表    2.3.4 静态链表    2.3.5 单链表应用举例  2.4 顺序表和链表的比较  2.5 本章小结  习题第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.4.3 链队——队列的链式表示和实现  3.5 本章小结  习题第4章 串  4.1 串及其基本运算    4.1.1 串的基本概念    4.1.2 串的基本运算  4.2 串的存储结构    4.2.1 串的顺序存储结构    4.2.2 串的链式存储结构  4.3 串的模式匹配    4.3.1 朴素的模式匹配算法    4.3.2 KMP算法  4.4 串的应用举例  4.5 本章小结  习题第5章 数组和广义表  5.1 数组的概念    5.1.1 数组的定义    5.1.2 二维数组  5.2 数组的顺序存储  ……第6章 树第7章 图第8章 查找第9章 排序第10章 文件参考文献

章节摘录

　　第1章　绪论　　1.1 引言　　1.1.1 为什么要学习数据结构　　“数据结构”是计算机相关事业的一门专业基础课，它可以为后续专业课程的学习提供必要的知识和技能准备，是十分重要的核心课程。　　计算机相关事业的很多后续课程都要用到本书所涉及的知识和技能，例如，编译原理要使用堆栈、散列表及语法树，操作系统会用到队列、存储管理表及目录树，数据库系统将运用线性表、多链表以及索引树等基本数据结构及其相关的算法。本课程讨论的其他一些数据结构，如广义表、集合以及图的知识也是很多领域经常涉及的。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂的课题的，要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握数据结构的有关知识。　　数据结构作为一门独立的课程，在国外是从1968年才开始的，但在此之前，其有关内容已散见于编译原理及操作系统之中。20世纪60年代中期，美国的一些大学开始设立有关课程，但当时的课程名称并不叫数据结构。1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。从20世纪60年代末到70年代初，出现了大型程序，软件也相对独立，结构程序设计成为程序设计方法学的主要内容，人们越来越重视数据结构。从70年代中期到80年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专业领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们重视。　　……