第一章绪论 重点：数据结构的基本概念 难点：ADT、算法复杂度 基础：C语言的基本知识
第一章 绪论 重点：数据结构的基本概念 难点：ADT、算法复杂度 基础：C语言的基本知识
第一章绪论 1.1什么是数据结构 1.2基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求 18/54
18/54 第一章 绪论 1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求
1.1什么是数据结构 Niklaus Wirth Algorithm Data Structures Programs Algorithm:求解问题的策略 DS: 问题的数学模型 Programs:为计算机处理问题编制的一组指令 例1：学生成绩单 学号 姓名 数据结构 PB01001 张平 80 PB01002 王晴 85 E 19/54
19/54 1.1 什么是数据结构 Niklaus Wirth Algorithm + Data Structures = Programs Algorithm: 求解问题的策略 DS: 问题的数学模型 Programs: 为计算机处理问题编制的一组指令 例1：学生成绩单 学号 姓名 数据结构 PB01001 张平 80 PB01002 王晴 85 … … …
1.1什么是数据结构 例1：学生成绩单 要求：，给定学生的学号或姓名，要求打印出其成绩， 若学生不存在，则报告没有该学生的信息。 计算机处理该问题时，应考虑： 1)数据及其存储：学生（学号，姓名，成绩） struct student char sNo[8]; char sName[9]; int nScore; astStudent[200]; 2)基本运算的实现 20/54 合
20/54 1.1 什么是数据结构 例1：学生成绩单 要求：给定学生的学号或姓名，要求打印出其成绩； 若学生不存在，则报告没有该学生的信息。 计算机处理该问题时，应考虑： 1) 数据及其存储：学生(学号,姓名,成绩) struct student { char sNo[8]; char sName[9]; int nScore; } astStudent[200]; 2) 基本运算的实现
1.1什么是数据结构 例2：图书馆的书目检索系统自动化问题 例3：计算机和人对弈问题 ■例4：多叉路口交通灯的管理问题 结论 ·描述这类非数值计算问题的数学模型不是数 学方程，而是树、表和图之类的数据结构 ·数据结构描述现实世界实体的数学模型及其 上的操作在计算机中的表示和实现 21/54 合
21/54 1.1 什么是数据结构 例2：图书馆的书目检索系统自动化问题 例3：计算机和人对弈问题 例4：多叉路口交通灯的管理问题 结论 描述这类非数值计算问题的数学模型不是数 学方程,而是树、表和图之类的数据结构 数据结构描述现实世界实体的数学模型及其 上的操作在计算机中的表示和实现
1.2基本概念和术语 数据(Data) ■客观事物的符号表示 ·能输入到计算机中被计算机程序处理的符号集 数据元素(Data Element) ·数据的基本单位 ·在计算机程序中作为一个整体进行考虑和处理 一个数据元素可以由若干数据项(Data Item)组成 ·数据项是具有独立含义的最小标识单位 ■ 数据对象(Data Object) ·性质相同的数据元素的集合 e.g.C='A','B',...'Z') 22/54 合
22/54 1.2 基本概念和术语 数据(Data) 客观事物的符号表示 能输入到计算机中被计算机程序处理的符号集 数据元素(Data Element) 数据的基本单位 在计算机程序中作为一个整体进行考虑和处理 一个数据元素可以由若干数据项(Data Item)组成 数据项是具有独立含义的最小标识单位 数据对象(Data Object) 性质相同的数据元素的集合 e.g. C={ ‘A’, ‘B’, …, ‘Z’ }
1.2基本概念和术语-数据结构 数据结构(Data Structure) ■形式定义 Data Structure =(D,S) ■D一数据对象，数据元素的有限集 ■S一是D上关系的有限集 。四个基本的数据结构 ■集合结构：关系集合是空集 顶点元素间无任何关系，D={}空集 23/54 合
23/54 1.2 基本概念和术语-数据结构 数据结构(Data Structure) 形式定义 Data_Structure = ( D, S ) D — 数据对象,数据元素的有限集 S — 是D上关系的有限集 四个基本的数据结构 集合结构：关系集合是空集 顶点元素间无任何关系，D={} 空集
1.2基本概念和术语-线性结构/树 线性结构：元素间的关系是1：1 0-0-000-0 一个结，点（除头结点外）有且仅有一个直接前驱 一个结点（除尾结，点外）有且仅有一个直接后继 。树型结构：一般树、二叉树、森林 一个结点可以有多个直接后继（除叶子结点外)， 但只有一个直接前驱（除根结，点外) 24/54 合
24/54 1.2 基本概念和术语-线性结构/树 线性结构：元素间的关系是1 : 1 一个结点（除头结点外）有且仅有一个直接前驱 一个结点（除尾结点外）有且仅有一个直接后继 树型结构：一般树、二叉树、森林 一个结点可以有多个直接后继（除叶子结点外）， 但只有一个直接前驱（除根结点外）
1.2基本概念和术语-图状结构 图状结构：元素间的关系是m:n 一个结，点可以有多个直接后继，也可以有多个直接前驱 25/54 合
25/54 1.2 基本概念和术语-图状结构 图状结构：元素间的关系是m : n 一个结点可以有多个直接后继，也可以有多个直接前驱
1.2基本概念和术语-逻辑结构 数据的逻辑结构 ·特征 ■从逻辑关系上描述数据，与数据的存储无关 ■从具体问题抽象出来的数据模型 ■与数据元素本身的形式、内容无关 ■与数据元素的相对位置无关 ·分类 线性结构：线性表 ■非线性结构：树、图 26/54 合
26/54 1.2 基本概念和术语-逻辑结构 数据的逻辑结构 特征 从逻辑关系上描述数据，与数据的存储无关 从具体问题抽象出来的数据模型 与数据元素本身的形式、内容无关 与数据元素的相对位置无关 分类 线性结构：线性表 非线性结构：树、图