第一章数据结构与算法

– 例：父子关系中儿、女中必有一人无法紧接父亲存放
同一种逻辑结构的数据可以采用不同的存储结
数 据 结 构
构
前一页 下一页
休息
33
数据的存储结构

常见存储结构：
顺序：
把逻辑上相邻的结点存储在物理位置相邻的存储单元里，
数 据 结 构
结点间的逻辑关系由存储单元的邻接关系来体现 例：数组
链接：
前一页 下一页
休息
12
算法的特点练习

算法的有穷性是指
A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的 C）算法程序的长度是有限的 D）算法只能被有限的用户使用
答案： A D
算 法

下列叙述中正确的是
A）算法就是程序 B）设计算法时只需要考虑数据结构的设计 C）设计算法时只需要考虑结果的可靠性 D）以上三种说法都不对
多少科目的成绩？
优秀的定义（总分？平均分？第一名？前五
名？） 数据如何录入？如何输出？
这是初学者认为最简单而在实际工程中最
难的工作。在软件工程中被称作“需求分 析”
前一页 下一页
休息
6
算法和程序

算法设计
算法的概念
要使计算机完成某一问题的解题任务，首先必
须针对该问题设计一个解题步骤，然后再据此 编写程序。这里所说的解题步骤就是“算法”。 算法与程序不同，它是问题求解规则的一种过 程描述。在算法中要精确定义一系列规则，这 些规则指定了相应的操作顺序，以便在有限的 步骤内得到所求问题的解答。
前一页 下一页
休息
13
算法设计基本方法

常用算法的设计方法
列举法（穷举法、枚举法） 例：判断素数
归纳法 例： Fibonacci数列1，1，2，3，5，8，13，... 归纳结果:Fn = Fn-1 + Fn-2 (n≥3) 递推法 是归纳法最常使用的一种 例：求级数和 递归法 回溯法
1.
前一页 下一页
休息
17
算法的表示举例
流程图法
开始
原始数据放在 数组A中；令 i=1 确定A[i]到A[n]中最 小整数的位置,设为j A[i] 和A[j]交换位置 i=i+1

伪代码法：
将原始数据放在数组A中； FOR i = 1 To n { 确定A[i] 到A[n]中最小 整数的位置，设为j ； 交换A[i]和[j] ； i = i +1 }
前一页 下一页
休息
9
算法的通用性

算法所解决的是一类问题而不是一个特定的 问题，例如
排序(sort) ： 包括表格内容的排序，文件夹中文件的排序等 排序方式也可以按数字、文字或日期等排序 查找(search)： 可以在文档中查找某个单词或在硬盘中查找某个文件， 也可在Web上查找某个网页等等
算 法

开发计算机应用的核心是：根据实际问题给 出解题的算法，然后再将该算法在计算机上 实现(即开发成为软件)
休息
10
前一页 下一页
实现算法考虑的问题

实现算法考虑的问题：
如何确定算法－算法设计 如何表示算法－算法表示 如何使算法更有效－算法的复杂性设计
算 法

算法的实现贯穿在整个计算机求解问 题的过程当中
）
A）数据的逻辑结构与存储结构必定是一一对应的 B）由于计算机存储空间是向量式的存储结构，因此，数据 的存储结构一定是线性结构 C）程序设计语言中的数组一般是顺序存储结构，因此，利 用数组只能处理线性结构 D）以上三种说法都不对
前一页 下一页
休息
37
1.3 线性表及顺序存储结构
线性表基本概念 线性表的存储结构 线性表的的运算
常见的线性结构：线性表、栈、队列和线性链
数 据 结 构
表等
非线性结构： 不满足线性结构条件的数据结构 常见非线性结构：树、二叉树和图等
前一页 下一页
休息
35
数据的运算
源自文库
数据的运算
定义： 定义在数据结构上的一组运算(操作)及其实现 方法 常用运算： 检索、插入、删除、更新、排序等。
算法评价

占用的计算机资源－算法的复杂度
时间复杂度－指程序运行耗费的时间 空间复杂度－指程序运行时所占存储空间
的大小

理解度、调试和测试的方便度等
前一页 下一页
休息
20
算法复杂度

算法的时间复杂度
算法的时间复杂度：程序运行耗费的时间 衡量方法：执行算法所需要的计算工作量 工作量计算方法： 执行算法的过程中所需基本运算的执行次数 基本运算是算法中的主要运算 例：
– 矩阵相乘时，乘法是基本运算，加法忽略不计 – 查找运算，以比较为基本运算
前一页 下一页
休息
21
算法复杂度

算法的时间复杂度
工作量计算方法分类： 平均性态分析：
– 指基本运算次数的加权平均值
最坏情况复杂性
– 指基本运算的最大次数
前一页 下一页
休息
22
选择排序算法的时间复杂性

设参加排序的整数有n个
交换操作的次数：
最好情况(原始数据已经排序)时，交换次数为0 最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次
传送)，总的交换次数取最大值为：3(n-1)
所以，直接选择排序的时间复杂性 为 O(n2)
前一页 下一页
休息
23
算法复杂度

算法的空间复杂度
指执行算法所需内存空间大小 算法程序所占空间 原始数据所占空间
i=n?
结束
前一页 下一页
休息
18
算法评价
算法评价指判断算法的好坏 正确性

指给定有效输入后，经过有限时间的计算，
产生正确的输出结果

简单性
算法是否容易理解，是否容易验证其正确
性，程序是否容易调试 简单的算法效率不一定高，要在保证一定 效率的前提下力求算法简单
前一页 下一页
休息
19
数 据 结 构
实现 在数据上定义的运算
前一页 下一页
休息
30
数据的逻辑结构

数据的逻辑结构
指数据集合中各数据元素之间所固有的逻
数 据 结 构
辑关系

数据结构包含的信息：
数据元素本身的信息（用D表示） 各数据元素之间的前后件关系（用 R表示）

数据的逻辑结构的表示：
B =（D,R） 例：季节数据结构： D=｛春、夏、秋、冬｝ R=｛ (春、夏), (夏、秋), (秋、冬) ｝
全国计算机二级考试之公共基础 知识
第一章 数据结构与算法
本章主要内容
算法概述 数据结构 线性表及其顺序存储结构 栈和队列 线性链表 树与二叉树 查找技术 排序技术

前一页 下一页
休息
2
1.1 算法
算法的定义 算法的设计 算法的表示 算法的评价
算法和程序

程序设计
前一页 下一页
休息
31
数据的逻辑结构

常见数据逻辑结构
根结点 (无前件)
H S L Y A D
数 据 结 构
线性结构
例：四季
树形结构
例：组织结构
网状结构
例：课程,学生
结点
前一页 下一页
休息
32
数据的存储结构

数据的存储结构
是其逻辑结构在计算机存储器上的实现 包含内容： 数据元素自身值 数据元素之间关系 例：数组结构，序号反映前后件关系 与逻辑结构的关系 逻辑结构不一定与存储结构一致
前一页 下一页
休息
15
算法的表示

算法表示方法：
文字说明法，缺点： 容易产生歧义，很难 “精确”地进行表达 叙述冗长，很难清楚地表达算法的逻辑流程 流程图
流程图由符号和箭头构成，描述了算法所执行
操作的顺序及执行操作的条件 流程图比文字描述简明，但当算法比较复杂时， 理解困难，容易产生错误
A是伪币
前一页 下一页
休息
8
算法和程序

算法无处不再
例2：EXCEL中如何将表格内容排序？
例1：Word如何在文档中查找用户指定的词语？
算 法
例3：如何把彩色图片转换为灰度(黑白)图片？ 例4：如何在硬盘中找到用户指定的文件？ 例5：媒体播放器如何把MP3文件转换成动听
的音乐？ 例6：搜索引擎如何找到用户需要的网页？
线性表基本概念

线性表
线性表是最简单、最常用的数据结构 是若干个相同类型的数据元素组成的一个
数 据 结 构
前一页 下一页
休息
36
数据结构练习

下列叙述中正确的是（
）
A）算法的效率只与问题的规模有关，而与数据的存储结构 无关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关

答案： B D
下列叙述中正确的是（
比较操作的次数：
设置i的初值为1，循环执行下列操作，直到i = n: { 确定A[i] 到A[n]中最小的整数元素的位置，设 为j ； 交换A[i]和[j] ； i = i +1 }
在第i趟排序中选出最小整数时，需做n-i次比较操作， 因此，总的比较操作次数为：n(n-1)/2
= (n2 -n)/2
前一页 下一页
休息
7
算法定义

算法－解决问题的方法和步骤
例：有三个硬币，其中一个是伪造
开始
算 法
的，另两个是真的，伪币与真币重 量略有不同。现在提供一座天平， 如何找出伪币呢？
分析：
方法明确而有序
是
A＝B？
否
C是伪币
是
A＝ C？
否
B是伪币
按提供的条件进行操作
任何人均可仿照进行(共享智能)

算法(程序) 由2个部分组成：
进行的操作 所涉及的操作对象(数据)
算法
操作对象
程序
说明所要处 理的数据的 名字和类型 描述所要执 行的算法
说 明 语 句 命 令 语 句
休息
27
操作步骤 与条件
前一页 下一页
数据结构的概念

数 据 结 构
数据结构是相互有关联的数据元素的 集合
例：研究季节时：“ 春、夏、秋、冬”
前一页 下一页
休息
11
算法的特点

算法的基本特征
可行性：运算必须在计算机能力范围内可以运行 确定性：运算操作必须清楚明确，无二义性
算 法
有穷性：算法必须在有限步后终止
拥有足够情报（数据）：即计算数据必须完备
其他： 输入：有0~多个输入，包括外界输入和初始化 输出：至少有一个输出
不要求逻辑上相邻的结点在物理位置上亦相邻，结点间
的逻辑关系是由附加的指针字段表示的
索引：
除建立存储结点信息外，还建立附加的索引表来标识结
点的地址
前一页 下一页
休息
34
数据的存储结构

存储结构分类：
线性结构（非空的数据结构） 特点：
– 有且只有一个根结点 – 每一个结点最多有一个前件，也最多有一个后件
B

下列叙述中正确的是
A）算法的效率只与问题的规模有关，而与数据的存储结构 无关 B）算法的时间复杂度是指执行算法所需要的计算工作量 C）数据的逻辑结构与存储结构是一一对应的 D）算法的时间复杂度与空间复杂度一定相关
前一页 下一页
休息
25
1.2 数据结构
数据的逻辑结构 数据的存储结构 数据的运算
数据结构的概念
伪代码（一种介于自然语言和程序设计语
言之间的文字和符号表达工具）
前一页 下一页
休息
16
算法设计

算法设计举例：－对包含n个整数元 素的数组A进行升序排序。 直接选择算法：文字表示
从所有整数中选取最小的，交换到第一 个数位置上； 2. 从剩下未排整数中选出最小的，交换到 已排好序列的最后一个数后面； 3. 反复执行②，直到所有整数都放到已排 好的序列中。
是利用计算机解决问题的全过程
程序设计的过程：
问题 模型 求解 算法 编制 程序 问题 实现
实际 问题
分析 抽象
问题分析
前一页 下一页
模型 求解
算法设计
命令 编程
编程设计
调试 程序
测试执行
休息
4
算法和程序
程序设计的第一步是问题分析 问题分析

问题一：统计一个班级的学生考试成绩，
并选出优秀学生
额外空间：包括运算时占用工作单元和特殊数
据结构存储时的附加空间
注意：
时间和空间复杂度经常是矛盾的，需要根据具
体情况找到平衡点
前一页 下一页
休息
24
算法复杂度练习

答案：
D
下列叙述中正确的是
A）一个算法的空间复杂度大，则其时间复杂度也必定大 B）一个算法的空间复杂度大，则其时间复杂度必定小 C）一个算法的时间复杂度大，则其空间复杂度必定小 D）上述三种说法都不对
是相互关联的数据元素

数据元素的的前后件关系
指数据元素的前后顺序关系 例：春夏关系：春是夏的前件，夏是春的后件 前后件关系是数据元素之间的基本关系
前一页 下一页
休息
29
数据结构的概念
精心设计的数据结构可使算法获得更 高的时间效率或空间效率 研究数据结构一般包括三个方面的内 容：

数据的逻辑结构：数据间关系的描述 数据的存储结构：逻辑结构在存储器上的