数据结构

出版时间：2013-1  出版社：水利水电出版社  作者：吴仁群  

内容概要

《普通高等教育"十二五"规划教材:数据结构(Java版)》是针对数据结构初学者编写的基础教程，书中不仅讲解了数据结构常用的基本理论知识，而且提供了大量应用实例，以帮助初学者对知识的理解。全书共分8章：绪论、线性表、栈和队列、串和数组、树和二叉树、图、查找、排序等。

书籍目录

前言 第1章绪论 1.1 基本概念 1.1.1数据和数据结构 1.1.2数据类型 1.1.3抽象数据类型 1.1.4数据结构的符号描述举例 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线性表的含义及ADT描述 2.2顺序存储结构 2.2.1顺序表的存储表示 2.2.2顺序表的基本操作的实现 2.2.3顺序表的基本操作的时间复杂度分析 2.2.4顺序表的优缺点 2.2.5顺序存储结构的应用 2.3链式存储结构 2.3.1单链表的存储表示 2.3.2单链表基本操作的实现 2.3.3循环链表的表示和基本操作的实现 2.3.4双向链表的表示和基本操作的实现 2.3.5链式存储结构的应用 2.4习题 第3章栈和队列 3.1 栈 3.1.1栈的定义及ADT描述 3.1.2栈的顺序存储结构 3.1.3栈的链式存储结构 3.1.4栈的应用 3.2 队列 3.2.1 队列的定义及ADT描述 3.2.2队列的顺序存储结构 3.2.3 队列的链式存储结构 3.2.4队列的应用 3.3 习题 第4章串和数组 4.1 串 4.1.1 串的定义及ADT描述 4.1.2串的顺序存储结构 4.1.3串的链式存储结构 4.1.4串的应用举例 4.2数组 4.2.1数组的定义及ADT描述 4.2.2数组的存储结构 4.2.3矩阵的压缩存储 4.2.4矩阵转置 4.2.5数组的应用举例 4.3 习题 第5章树和二叉树 5.1 树 5.1.1树的概念及ADT描述 5.1.2树的存储结构 5.1.3综合应用举例 5.2二叉树 5.2.1 二叉树的概念及ADT描述 5.2.2二叉树的性质 5.2.3二叉树的存储结构 5.2.4遍历二叉树 …… 第6章图 第7章查找 第8章排序

章节摘录

版权页：   插图：   第7章 查找 7.1 基本概念 查找，也称为检索，是数据处理中常用的一种操作。例如，从电话簿中查找某人的电话，从学生信息表中查找外籍学生信息等。计算机查找可以大大提高工作效率。 在计算机应用中，查找是指在数据元素集合中查找满足某种条件的数据元素的过程。这里常将用于查找的数据元素集合称为查找表。查找表由同一类型的数据元素（或记录）构成的集合（文件或表）。查找条件可能多种多样，但最常用的查找条件是“关键字值等于某个给定值”，即在查找表中检索关键字等于给定值的数据元素（或记录）。除非特别说明，本书约定的查找条件都属于此种类型。 对查找表的操作可以分为四类： （1）在查找表中查看某个特定的数据元素是否在查找表中。 （2）检索某个特定元素的各种属性。 （3）在查找表中插入一个数据元素。 （4）从查找表中删除某个数据元素。 基于操作类型，可以将查找分为静态查找和动态查找，相应地将查找表分为静态查找表和动态查找表。 若只对查找表进行第（1）或（2）操作，则称这类查找表为静态查找表。静态查找表在查找过程中查找表本身不发生变化。对静态查找表进行的查找操作称为静态查找。 若在查找过程中可以将查找表中不存在的数据元素插入，或者从查找表中删除某个数据元素，即允许对查找表进行第（3）或（4）操作，则称这类查找表为动态查找表。动态查找表在查找过程中查找表可能会发生变化。对动态查找表进行的查找操作称为动态查找。 查找的结果有成功、不成功两种可能。若表中存在关键字等于给定值的记录，则称查找成功，此时的查找结果应给出找到记录的全部信息或指示找到记录的存储位置；若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个空记录或空指针。 一般在查找表中，每个数据元素或记录由若干个数据项组成，其中用作查找条件的数据项称为关键字。因此，关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字。反之，则称此关键字为次关键字。例如，银行账户中的账号是主关键字，而姓名是次关键字。若按主关键字查找，查找结果是唯一的；若按次关键字查找，结果可能是多个记录，即结果可能不唯一。 查找表是一种非常灵活的数据结构，对于不同的存储结构，其查找方法不同。为了提高查找速度，有时会采用一些特殊的存储结构。本章将介绍以线性结构、树形结构及哈希表结构为存储结构的各种查找算法。 用于查找的算法有很多，由于在查找过程的主要操作是关键字的比较，因此通常以“平均比较次数”来衡量查找算法的时间效率。 7.2 静态查找 静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的存储位置或各种属性。本节将讨论以线性结构表示的静态查找表及相应的查找算法。 7.2.1一顺序查找 1.顺序查找的基本思想 顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表（顺序表或链表），从第一个数据元素（或记录）开始，将给定值与表中元素逐一进行比较，若某个元素的关键字值与给定值相等，则查找成功，返回该元素的存储位置，反之，若直到最后一个元素，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。对于元素的关键字是无序的表来说，只能采用这种方法。 2.顺序查找示例 顺序表中数据元素的关键字序列为（38，75，19，57，100，48，50，7，62，11），则查找关键字K=48需要6次比较，查找成功；而查找关键字K=53需要11次比较，查找不成功。

编辑推荐

《普通高等教育"十二五"规划教材:数据结构(Java版)》内容实用，结构清晰，实例丰富，可操作性强，可作为高等学校数据结构的教材，也可作为计算机相关专业的培训和自学教材。