数据结构

出版时间：2009-1  出版社：国防工业出版社  作者：陈广山　主编  页数：286  字数：424000  

前言

　　随着计算机应用的普遍，计算机在非数值计算领域的应用越来越广泛，而数据结构知识是解决这类问题的基础，所以，“数据结构”在计算机与信息技术类专业的教学中具有突出的地位和作用。　　“数据结构”是计算机与信息技术类专业的一门重要的专业基础课程，也是该专业的一门核心关键性课程。本书系统地介绍了常用的数据结构以及相应的算法，包括数据结构的基本概念、线性表、栈和队列、串、数组与广义表、树、图、查找和排序等。在计算机与信息科学中，数据结构不仅是一般程序设计的基础，还是设计和实现编译程序、操作系统、数据系统及其他系统程序的重要基础，本课程将为后续课程的学习、程序设计效率的提高奠定良好的基础。　　本书是根据教育部有关“数据结构”教学的建议，以及全国计算机专业硕士研究生入学考试“数据结构”大纲编写的。在编写过程中，以通俗易懂、简明实用为宗旨，以方便教师的教和学生的学为基本理念，以基本知识为基础，重点体现理论够用、实践实用的原则，注意通过典型的案例促进对各种数据结构的理解。本书在编写过程中也注意了语言的形象性，避免晦涩现象的出现；力求抽象与形象相结合，知识点与计算机领域的具体应用相联系；算法与程序、习题相对应。　　全书共分10章：第1章是绪论，主要介绍了数据结构的相关概念和术语，以及算法的特点和评价标准等内容；第2章介绍了线性表的有关概念和基本操作；第3章对栈和队列的知识进行了重点介绍；第4章为数组和广义表，对数组和广义表的基本表示和实现进行了研究；第5章的主要内容是串的基本操作；第6章介绍了典型的非线性结构二叉树，包括树、森林的基本概念、表示与实现，以及哈夫曼树的应用等内容；第7章介绍了图的基本理论，并对最短路径、关键路径、拓扑排序等应用做了重点介绍；第8章主要介绍了几种传统的查找方法，并对散列查找等现代查找方法进行了详细介绍。第9章主要介绍了常用的排序方法；第10章简单地介绍了文件的知识和基本操作。　　为了加强对知识点的理解，每一章的后面都选配了适量的习题，供读者参考。为了方便教师开展教学工作，本书提供电子教案、课件和习题等教学资源。

内容概要

“数据结构”是计算机与信息技术类专业的一门专业基础课，是从事计算机与信息技术工作人员的必修课程之一。本书涵盖了教育部对“数据结构”教学规定的全部内容和全国硕士研究生入学考试“数据结构”大纲中规定的知识点，并融入了编者多年教学经验的总结和对信息技术行业背景知识的进一步思考。全书共分10章，内容涉及数据结构的基本概念、线性表、栈和队列、串、数组与广义表、树、图、查找、排序以及文件等。    本书可作为高等院校计算机与信息技术类专业的本、专科的教材和参考书，也可供从事计算机与信息技术的工程人员参考（如需电子教学资源，请发邮件至[e-mail]索取）。

书籍目录

第1章　绪论  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.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.4　双向链表    2.4.1　双向链表的存储结构    2.4.2　双向链表的基本运算  2.5　循环链表  2.6　静态链表  2.7　线性表的应用  2.8　顺序表和链表的比较  2.9　本章小结  习题第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　本章小结  习题第4章　数组和广义表  4.1　数组的概念  4.2　数组的存储结构    4.2.1　数组的内存映像    4.2.2　数组的顺序存储表示与实现  4.3　矩阵的压缩存储    4.3.1　特殊矩阵    4.3.2　稀疏矩阵  4.4　广义表的概念  4.5　广义表的存储结构  4.6　数组和广义表的应用    4.6.1　数组的应用    4.6.2　广义表的应用  4.7　本章小结  习题第5章　串  5.1　串的基本概念  5.2　串的表示与实现    5.2.1  串的顺序存储表示与实现    5.2.2　串的链式存储表示与实现　……第6章　树和二叉树第7章　图第8章　查找第9章　排序第10章　文件附录A　习题参考答案（部分）附录B　2009年全国计算机专业硕士研究生入学考试大纲（数据结构）参考文献

章节摘录

　　第1章　绪论　　21世纪是一个信息文明的新世纪，计算机已经渗透到人类生活的每一个角落，计算机信息处理已经成为人类活动不可缺少的组成部分。计算机科学是一门研究信息表示和处理的科学，数据是计算机可以直接处理的最基本和最重要的对象。随着计算机科学技术的迅速发展，计算机的应用已经从传统的数值计算领域发展到各种非数值计算领域，处理的对象扩展到字符、表格、声音、图像和动画等多媒体信息。信息处理也不再是单纯的计算，而是诸如信息存储与检索等非数值计算问题。　　因此，如何在计算机中表示数据、如何有效地存取数据以及如何有效地实现数据对象之间的关系是人类必须解决的新问题。传统的解决数值计算问题的理论、方法和技术已经无法满足非数值计算问题的需要，必须建立新的理论、方法和技术体系，　“数据结构”就是在解决前述问题的过程中诞生的一门新学科。　　1.1　数据结构的概念　　“数据结构”是计算机与信息技术类专业的专业基础课，是一门十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解决问题，仅有计算机程序设计语言是不够的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构的有关知识和基本技能。此外，“数据结构”对学习计算机专业的其他课程，如操作系统、编译原理、软件工程、人工智能等都具有十分重要的意义。

编辑推荐

　　《数据结构》可作为高等院校计算机与信息技术类专业的本、专科的教材和参考书，也可供从事计算机与信息技术的工程人员参考。