《数据结构》数据结构.pdf

数据结构
王宏生宋继红编著
内容简介
数据结构是计算机专业的核心课程,是从事计算机软件开发与计算机应用人
员必备的专业基础。本书从软件开发设计的角度出发,按照面向对象的程序设计
思想,详细介绍了线性表、栈和队列、串、数组和广义表、树与森林、图等不同的数据
结构,以及这些数据结构在计算机中的存储表示和算法实现。最后两章介绍了计
算机中常用的两种运算———查找和排序,并详细介绍了不同的查找、排序运算的实
现及各种算法的效率分析。
本书将数据抽象与面向对象思想作为重点,对传统的“数据结构”赋予新的内涵、新
的处理方式,使其上升为面向对象的数据结构,每种算法都采用语言进行描述。
C++
本书叙述清晰、逻辑性强、利于教学,可作为高等院校计算机专业及信息等相
关专业的教材,也可作为计算机应用技术人员的参考书。
图书在版编目( )数据
CIP
数据结构/王宏生,宋继红编著—北京:国防工业出
.
版社,

ISBN7118042447
数王宋数据结构
Ⅰ. ... Ⅱ.①...②... Ⅲ.
Ⅳ.
中国版本图书馆数据核字( )第号
CIP 2005 145011
(北京市海淀区紫竹院南路号)
23
(邮政编码)
100044
北京奥鑫印刷厂印刷
新华书店经售

开本/ 印张千字
787×1092116 20 462
年月第版年月北京第次印刷
2006 1 1 2006 1 1
印数:—册定价: 元
1 4000
(本书如有印装错误,我社负责调换)
国防书店:( ) 发行邮购:( )
01068428422 01068414474
发行传真:( ) 发行业务:( )
01068411535 01068472764
世纪,人类社会已进入了一个以信息化为标志的飞速发展的时代。数据是信息的
21
载体,随着信息化社会的发展,尤其是因特网已将全世界的计算机连在一起,需要由计算
机处理的数据量迅速增大,数据类型随之增多,数据结构也更加复杂。随着面向对象技术
的蓬勃发展,数据的组织方式对于软件结构的优劣、软件的效率和质量具有举足轻重的作
用,这就给软件的设计与开发带来了一系列新的问题。要想设计出一个结构好、效率高的
软件,就必须分析待处理的对象特性以及各处理对象之间存在的关系,这就是“数据结构”
这门学科研究的内容。
“数据结构”是计算机科学与技术专业的一门必修的、重要的专业基础课,它是计算机
程序设计的重要理论和技术基础。通过本课程的学****不仅可以使学生掌握数据结构的
基本内容、典型算法,而且能够训练其应用数据结构和算法解决实际问题的能力与提高程
序设计的水平。
面向对象技术的发展,使得数据结构在软件开发中的地位越来越重要。在面向对象
技术中,数据是程序的主体,数据结构成为软件的核心,对象是划分与构造软件系统的基
本单位,这与以前的以功能为中心,软件开发采用功能分解的方法有本质的不同,面向对
象技术实质上是数据结构概念的自然扩展与继续。为了适应软件开发的这种趋势,本书
采用语言描述数据结构和算法。为保持数据结构体系的完整性,将有关语言
C++ C++
要点介绍的内容放在附录中。
本书共分章和个附录,具体内容如下。
9 2
第章绪论,是全书的基础。本章介绍数据结构的基本概念、抽象数据类型、数据的
1
存储表示和算法的时间复杂性及空间复杂性等内容。
第章线性表,线性表是最简单的数据结构,是其他复杂数据结构的基础。本章介
2
绍了线性表的概念、线性表的抽象数据类型、线性表的两种存储表示(顺序表和链表),以
及顺序表和链表的类定义和实现。
C++
第章栈和队列,这两种结构都是操作受限的线性表,在计算机科学与技术中具有广
3
泛的应用。本章介绍了栈和队列的定义、抽象数据类型、两种存储表示(顺序栈和链栈),
以及它们的类定义和实现。
C++
第章串,串也是一种特殊的线性表,这个线性表的元素是字符。串在文本编辑、字
4
处理和编译器中都有广泛的应用。本章介绍了串的定义、抽象数据类型、存储表示和串的
模式匹配算法。
第章数组和广义表,数组和广义表是线性表的推广,多维数组可以看做是一维数
5
组中的元素又是一个数组;广义表是一种复杂的非线性结构,其元素可以为原子,也可以
Ⅲ
为子表。本章介绍了数组的概念、抽象数据类型、数组的顺序存储与寻址、数组在科学上
的应用———特殊矩阵和稀疏矩阵的压缩存储与运算。本章最后介绍了广义表的定义、基
本运算和存