数据结构(C语言版)第1章合编.ppt

第1章 绪 论 学习目标与要求： 了解数据、数据元素、数据项、数据对象、数据类型及抽象数据类型等基本概念。 掌握数据结构和算法的概念。 掌握数据结构的逻辑结构、存储结构和数据操作(运算)3个方面的概念及其相互之间的关系。 掌握算法的评价标准。 分析算法的时间复杂度，评价一个算法的好坏。 1.1 引 言 1968年美国唐·欧·克努特(Donald E.Knuth)开创了数据结构的最初体系。 数据结构是一门介于数学、计算机硬件和计算机软件三者之间的核心课程(如图1.1所示)。 1.1 引 言 为了使读者对数据结构有一个感性的认识，下面给出几个数据结构的示例，读者可以通过这些示例去理解数据结构的概念。 【示例1】 职工基本情况表。 参见教材P2 【示例2】 井字棋对弈问题。 【示例3】 教学计划编排问题。 1.2 基本概念与术语 数据(Data)是对客观事物的一种符号表示，是指所有能输入到计算机中并被计算机程序加工处理的符号的总称。 数据元素(Data Element)是组成数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项(Data Item)是数据不可分割的、具有独立意义的最小数据单位，是对数据元素属性的描述。 数据、数据元素、数据项反映了数据组织的3个层次，即数据可以由若干个数据元素组成，数据元素又由若干个数据项组成。 数据对象(Data Object)是性质相同的数据元素的集合。 数据类型(Data Type)是指一组结构相同的值构成的值集(类型)和定义在这个值集(类型)上的操作集。 数据结构(Data Structure)是指数据元素之间的逻辑关系和这种关系在计算机中的存储表示，以及在这种结构上定义的运算。 1.2 基本概念与术语 1. 逻辑结构 (1) 线性结构。 (2) 集合结构。 (3) 树形结构。 (4) 图状结构。 数据的四种基本逻辑结构如图1.4所示。 1.2 基本概念与术语 2. 存储结构 (1) 顺序存储结构是指把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 (2) 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，结点之间的逻辑关系由附加的指针域来体现。 (3) 索引存储结构是用结点的索引号来确定结点的存储地址。 1.2 基本概念与术语 3. 数据的运算 对几种常用的运算进行简要介绍。 (1)检索：即在数据结构里查找满足一定条件的结点，一般是给定某字段的值，找具有该字段值的结点。 (2)插入：即往数据结构里增加新的结点。 (3)删除：把指定的结点从数据结构里去掉。 (4)更新：改变指定结点的一个或多个字段的值。 1.3 抽象数据类型 首先我们了解一下在程序设计语言中出现的各种数据类型。 1.3.1 数据类型 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 在高级程序设计语言中，数据类型可分为两类：一类是原子类型，另一类则是结构类型。 在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。 1.3.2 抽象数据类型概述 抽象数据类型(Abstract Data Type，ADT)，是指一个数学模型以及定义在此数学模型上的一组操作。 抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。 抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。 1.3.2 抽象数据类型概述 抽象数据类型的形式化定义如下： ADT=(D,S,P) D={数据对象} S={D上的关系集} P={对D的基本操作集} 定义形式： ADT 抽象数据类型名称 { 数据对象： … 数据关系： … 基本操作： 操作名1： … 操作名n： }ADT抽象数据类型名称 1.4 算法和算法分析 在计算机领域，一个算法实质上是针对所处理问题的需要，在数据的逻辑结构和存储结构的基础上实施的一种运算。 由于数据的逻辑结构和存储结构不是唯一的，所以处理同一个问题的算法也不是唯一的；即使对于具有相同逻辑结构和存储结构的问题而言，由于设计思想和设计技巧不同，编写出来的算法也不大相同。 学习数据结构这门课程的目的，就是要学会根据实际问题的需要，为数据选择合适的逻辑结构和存储结构，进而设计出合理和实用的算法。 1.4.1 算法的基本概念 1. 算法 2. 算法的特征 (1) 有穷性。 (2) 确定性。 (3) 可行性。 (4) 有输入。 (5) 有输出。 3. 算法与