数据结构162889.ppt

前言二十一世纪是科学技术高速发展的信息时代，而计算机是处理信息的主要工具，因此，人们已经认识到，计算机知识已成为人类当代文化的一个重要组成部分。计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统的数值计算领域发展到各种非数值计算领域。在非数值计算领域里，数据处理的对象已从简单的数值发展到一般的符号，进而发展到具有一定结构的数据。 第一章 绪 论本章介绍数据结构这门学科诞生的背景、发展历史以及在计算机科学中所处的地位，重点介绍数据结构有关的概念和术语。学习本章后应能掌握数据、数据元素、数据对象、数据结构、数据类型、算法等基本概念，并了解如何评价一个算法的好坏。 本章提要 1. 引言 2. 数据结构的发展简史及其在计算机科学中所处的地位 3. 什么是数据结构 4. 基本概念和术语 5. 算法、算法的描述 6. 算法的分析 1.1 引言二十世纪四十年代，电子数字计算机问世的直接原因是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎只局限于科学和工程的计算，其处理的对象是纯数值性的信息，通常，人们把这类问题称为数值计算。近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机本身运算速度不断提高、信息存储量日益扩大、价格逐步下降，更重要的是计算机广泛地应用于情报检索、企业管理、系统工程等方面，已远远超出了科学计算的范围，而且渗透到人类社会活动的一切领域。与此相应，计算机的处理对象也从简单的纯数值性信息发展到非数值性的和具有一定结构的信息。 1.2 数据结构的发展简史及其在计算机科学中所处的地位 发展史： 1. “数据结构”作为一门独立的课程在国外是从1968年才开始设立的。 2. 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一部较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 1.4 基本概念和术语 1．数据数据是对客观事物的符号表示。在计算机科学中，数据的含义非常广泛，我们把一切能够输入到计算机中并被计算机程序处理的符号，(包括文字、表格、图象、声音等)都称为数据。数据是一个集合。 表 1-1 图书目录表 2．数据元素数据元素也叫结点，它是组成数据的基本单位，是数据这个集合中的个体。在程序中通常把结点作为一个整体进行考虑和处理。例如，在表1-1所示的图书目录表中，为了便于处理，把其中的每一行（代表一本书）作为一个基本单位来考虑。一般情况下，一个结点中含有若干个字段（也叫数据项）。例如，在表1-1所示的表格数据中，每个结点都有登录号、书号、书名、作者、出版社等字段构成。数据项是数据的不可分割的最小单位。 3. 数据对象数据对象是性质相同的数据元素的集合，它是数据的一个子集。例1. 字母数据对象：C={A，B，…，Z，a，b，…，z}例2. 图书目录表中的卡片数据对象。它们是两个不同的数据对象。 数据的存储结构（或称物理结构）数据的存储结构就是数据的逻辑结构在物理存储器中的映象。即数据在计算机中的存储表示。 （通常，一个数据元素中的若干个数据项是连续存储的，数据项又称为数据域，一个数据元素所占空间的第一个单元地址表示该元素的地址。） 5．数据类型在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。程序设计语言中数据类型是指各变量可取的数据种类。数据类型是高级程序设计语言中的一个基本概念，它和数据结构的概念密切相关。 　　　在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。可以认为，数据类型是在程序设计中已经实现了的数据结构。 6. 抽象数据类型 (Abstract Data Type 简称ADT)抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。其定义仅取决于数据的逻辑特性，而与机内表示和实现无关。抽象数据类型和数据类型实质上是一个概念。 1.5 算法、算法的描述 1. 算法算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： (1)．有穷性(2)．确定性 (3)．可行性(4)．输入 (5)．输出 算法与数据结构的关系算法和数据结构有着紧密的联系，它们是一个统一体，没有一方另一方就没有意义。Wirth有一句名言：“算法+数据结构=程序” 2. 算法的描述一个算法可以用自然语言、约定的符号（如流程图等）来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用类C语言作为描述算法的工具。现简单说明类C语言的语法结构如下： (1)．预定义常量和类型：# define TRUE 1；# define FALSE 0；# de