《数据结构》课程教学课件（讲稿，C语言描述）第1章 绪论

第1章绪论数据结构（C语言描述

第1章 绪论 数据结构（C语言描述）

目录1.1什么是数据结构1.2 算法的描述1.3算法分析1.4本章作业

目 录 1.1 什么是数据结构 1.2 算法的描述 1.3 算法分析 1.4 本章作业

1.1什么是数据结构1.1.1数据结构示例1、纟线性表示例址学号通讯地姓名性别籍贯电话8男长沙01张三麓山南路327号8639000男02李四北京学院路435号23456789女广州03王五天河路478号30472589男04上海赵六南京路1563号41237568女05钱七南京南京大学5013472女06刘八武汉武汉大学61543726男07朱九昆明云南大学4089651女08杭州孙十6154372西湖路635号图 1-1学生数据表

1.1 什么是数据结构 1.1.1 数据结构示例 学号 姓名 性别 籍贯 电 话 通 讯 地 址 01 张三 男 长沙 8639000 麓山南路 327 号 02 李四 男 北京 23456789 学院路 435 号 03 王五 女 广州 30472589 天河路 478 号 04 赵六 男 上海 41237568 南京路 1563 号 05 钱七 女 南京 5013472 南京大学 06 刘八 女 武汉 61543726 武汉大学 07 朱九 男 昆明 4089651 云南大学 08 孙十 女 杭州 6154372 西湖路 635 号 图 1-1 学生数据表 1、线性表示例

2、树形结构示例一层T二层0O三层aO四层Ca图1-2树形结构示意图

2、树形结构示例 a1 a b c a b1 2 Tt b2 c1 c2 d d1 d2 d3 图 1-2 树形结构示意图 一层 二层 三层 四层

3、图形结构示例1A图1-3图形结构示意图除此以外，我们熟悉的数据结构还有集合，它是元素之间关系最松散的结构

3、图形结构示例 1 2 3 4 5 6 图 1-3 图形结构示意图 除此以外，我们熟悉的数据结构还有集合，它是元 素之间关系最松散的结构

1.1.2基本术语1.数据（data)数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。2.数据元素（dataelement）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但有时它还可以分割成若干个具有不同属性的数据项（字段），故数据元素不是组成数据的最小单位。数据项才是数据的不可分割的最小单位

2．数据元素（data element） 数据元素是组成数据的基本单位。 数据元素是一个数据整体中相对独立的单位。但 有时它还可以分割成若干个具有不同属性的数据 项（字段），故数据元素不是组成数据的最小单 位。数据项才是数据的不可分割的最小单位。 1.1.2 基本术语 1． 数据（data） 数据是指能够输入到计算机中，并被计算机识别 和处理的符号的集合。 例如：数字、字母、汉字、图形、图像、声音 都称为数据

3．数据对象（dataobject）是性质相同的数据元素组成的集合，是数据的一个子集例如，整数数据对象的集合可表示为N三{0，土1，土2..…..，字母字符数据对象的集合可表示为CA',B"....'Z'.4．数据类型（data type）是相互之间存在一种或多种特定关系的数据元素的集合。例如，高级语言中用到的整数数据类型，是指由一32768到32767中值构成的集合及一组操作（加、减、乘、除、乘方等）的总称

3． 数据对象（data object） 是性质相同的数据元素组成的集合，是数据的一个子 集。 例如，整数数据对象的集合可表示为N＝{0，±1， ±2.} ， 字 母 字 符 数 据 对 象 的 集 合 可 表 示 为 C={‘A’,’B’,.’Z’}。 4． 数据类型（data type） 是相互之间存在一种或多种特定关系的数据元素的集 合。 例如，高级语言中用到的整数数据类型，是指由－ 32768到32767中值构成的集合及一组操作（加、减、 乘、除、乘方等）的总称

抽象数据类型CAbstractType)5.7Data是指一个数学模型以及定义在该模型上的一组操作。在本书中，描述一种抽象数据类型将采用如下书写格式:ADT[Data:Relation.Operations:)ADT抽象数据类型名

5． 抽象数据类型（Abstract Data Type） 是指一个数学模型以及定义在该模型上的 一组操作。 在本书中，描述一种抽象数据类型将采用如下书写格 式： ADT { Data: Relation: Operations: }ADT抽象数据类型名

1.1.3数据结构数据结构（datastructure）1是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三个方面的内容福即数据的逻辑结构，数据的存贮结构和对数据所施加的这三个方面的关系为：(1)数据的逻辑结构独立于计算机，是数据本身所固(2)孕贮结构是逻辑结构在计算机存贮器中的映像，依赖于计算机。(3)运算是指所施加的一组操作总称。运算的定义直按依赖于逻辑结构，但运算的实现必依赖于存贮结构

1.1.3 数据结构 1． 数据结构（data structure） 是指相互之间存在一种或多种特定关系的数据元素所组 成的集合。具体来说，数据结构包含三个方面的内容， 即数据的逻辑结构，数据的存贮结构和对数据所施加的 运算。这三个方面的关系为： （1）数据的逻辑结构独立于计算机，是数据本身所固 有的。 （2）存贮结构是逻辑结构在计算机存贮器中的映像， 必须依赖于计算机。 （3）运算是指所施加的一组操作总称。运算的定义直 接依赖于逻辑结构，但运算的实现必依赖于存贮结构

2．从逻辑结构划分数据结构数据结构从逻辑结构划分为：（1）线性结构元素之间为一对一的线性关系，第一个元素无直接前驱，最后一个元素无直接后继，其余元素都有一个直接前驱和直接后继（2）非线性结构元素之间为一对多或多对多的非线性关系，每个元素有多个直接前驱或多个直接后继

2． 从逻辑结构划分数据结构 数据结构从逻辑结构划分为： （1）线性结构 元素之间为一对一的线性关系，第一个元素无直接 前驱，最后一个元素无直接后继，其余元素都有一 个直接前驱和直接后继。 （2）非线性结构 元素之间为一对多或多对多的非线性关系，每个元 素有多个直接前驱或多个直接后继