数据结构01绪论幻灯片.ppt

* 数据项有“型”和“值”两个概念。所谓型是指数据项的类型定义，包括数据名；所谓值是指数据项对应的具体数据 * 在理解逻辑结构时应注意的是： ① 数据的逻辑结构与数据元素的内部结构和内容无关；只考量元素之间的联系。 ② 数据的逻辑结构与数据元素的相对位置无关；只考量元素之的间联系方式。 ③ 数据的逻辑结构与数据元素个数无关。只考量元素之间有无联系，有什么样的联系，即使元素个数为0。 * 这是一个比较难的问题，需要一定的数学知识基础。这里是浅谈。 时间效率分析和空间效率分析与问题的规模有关 * 时间效率通常指的是算法执行时间。 一个算法的执行时间＝所有语句执行时间的总和。 一条语句执行的时间＝该语句的执行次数（频度）×该语句执行一次所需时间 基本操作(或语句)执行次数总和称为语句频度 即：一个算法耗费的时间=所有语句的频度之和。 第一章 绪论 第一章 绪论 主要内容 数据结构的基本概念 1 算法 2 算法分析 3 数据结构的应用价值 4 1.1 数据和数据结构 Q1. 　为什么要学习数据结构？ Q2. 什么是数据结构？ Q3. 数据结构研究什么？ 在开始学习数据结构前，必须认识以下3个问题： Q1.为什么要学习数据结构 寻求数学模型 早期 数值计算的关键 加工处理的对象： 计算机的主要用途 主要用于数值计算 纯粹的数值 如何得出数学模型（方程）？ 分析问题，从中提取操作的对象及其之间含有的关系，建立方程 寻求数学模型 处理领域 非数值计算的焦点 加工处理的对象： 　计算机的主要用途　 逐渐扩大到非数值计算领域 字符、图形图像、 音频、视频等 数量越来越大 类型越来越多 关系越来越复杂 对相关的各种信息如何表示、组织、存储和处理？ 数据元素之间的相互关系一般无法用数学方程加以描述 Q2.什么是数据结构 数据元素 数据 信息 数据项 数据结构 基本概念及术语 是相互之间存在一种或多种特定关系的数据元素的集合。 是现实世界中客观事物的属性表征及其运动状态的真实反映所形成的关于事物的概念。 信息符号化的结果，是用以表示、存储、传输信息的一种结构化符号串。 为计算机输入、处理和输出的对象 不可再分的 具有独立意义的 可标识的最小数据单位。 由一个或多个相关数据项组成，是数据结构的组成单位。简称元素或称记录 学号 姓名 政治 成绩 数学 成绩 英语 成绩 信息技术成绩 数据结构成绩 210806101 陈敏敏 78 83 68 92 77 210806102 李学好 83 86 86 84 67 210806103 顾家新 65 94 97 78 91 210806104 黄玲玲 90 100 75 66 90 210806105 柯向民 100 79 83 73 74 210806106 王怀国 72 77 61 95 68 210806107 徐晶晶 56 84 64 99 79 210806108 余美美 98 73 88 87 77 210806109 张全理 88 99 91 85 88 分析“学生成绩登记表”数据 从表中可以认识到每个学生的学习情况信息 数据项，也称初等项，字段 数据元素，简称元素，或称记录 每行是 一个 记录 Q3.数据结构研究什么 1 研究对象的特性及其相互之间的关系 2 有效地组织这种特性和关系在计算机内的存储 3 有效地实现对象之间的“运算”关系，即基于某种存储结构对数据施加的操作或运算 逻辑结构 存储结构 算法 数据结构的研究内容 2 3 逻辑结构是数据本身的固有特性或应用特性， 独立于计算机。 存储结构是逻辑结构在计算机存储器中的映像，依赖于计算机。 算法是对数据施加的运算，服务于逻辑结构，依赖于存储结构。 1 这三个方面的关系是： ４ 运算功能服从于逻辑结构，实现运算的算法依赖于存储结构。 逻辑结构 四类基本结构 集合： 数据元素同属于一 　　种类型，元素间无关系 线性结构：一对一 树型结构：一对多 图结构：任意关系 是一种用户数据视图 是按用户观点组织数据形成的结构， 是用户直接观察和表现数据的格局。 物理结构 顺序存储 顺序存储结构就是按存储单元的顺序依次连续存放数据结构中所有结点。 逻辑上相邻的两个结点，在存储器上的物理位置也相邻。 保持着逻辑结构和物理结构的“一致” 链式存储 数据元素连续存储并附加存储一个指针,形成结点。 指针的作用是指出该结点逻辑上后继结点的存储位置。 最后一个结点的指针为空，表示结束 两种结构 数据元素的存储方式 与 数据结构的存储方式 同一类逻辑结构可以视应用和处理的需要采用不同存储结构；