3.数据结构与算法.ppt

3.3 常见的数据结构 队列 队列广泛应用于FIFO的数据组织场合，如组织排队 队列既可以采取顺序存储，也可以采取链式存储 队列的基本操作有 入队操作 出队操作 循环队列（引入、队满） 典型例题：若一个队列入队顺序为abcde，出队顺序只能是：abcde 3.3 常见的数据结构 树(Tree)与二叉树(Binary Tree)(非线性结构) 树是一种表现数据元素之间层次关系的数据结构 3.3 常见的数据结构 树与二叉树 树有关的术语 根结点 叶子结点 父结点(前驱) 子结点(后继) 结点的度(子结点的个数) 树的度 层 深度(最大层次数) 子树 森林 有序树 3.3 常见的数据结构 树与二叉树 树既可以顺序存储，也可以链式存储 树广泛应用于组织层次结构等过程中  通常使用二叉树而不直接使用树结构（如何转换？） value degree subtree1 subtree2 …… subtreen 3.3 常见的数据结构 树与二叉树(BinaryTree) 二叉树是一种特殊的树，除了满足树的所有特征之外，它还具有两个特点： 每一个节点最多有两个子树，分别称为左子树和右子树 节点的度最大为2 数据结构与算法 Data Structure Algorithm 本章提要 数据结构的基本概念 算法的基本概念 常见的数据结构 线性表 栈 队列 树与二叉树 图 常见的查找与排序算法 3.1 数据结构的基本概念 数据结构(Data Structure)的基本概念 使用计算机进行大批量数据处理是计算机最重要的应用领域之一。对于需要处理的数据，我们需要考虑3个方面的因素： 数据之间的关系是什么？ 数据如何存储在计算机里？(节省空间) 可以对这些数据执行什么操作？(提高效率) 3.1 数据结构的基本概念 什么是数据结构？ 简单的说，数据结构指的是相互有关联的数据元素的集合。数据元素既可以是简单类型的，也可以是复杂类型的。 数据结构是计算机科学最重要的学科之一，它研究的内容有三个方面(D,S,P)： D：数据元素 S：数据关系(逻辑结构、存储结构) P：可以对D执行的操作集 3.1 数据结构的基本概念 数据的逻辑结构 数据的逻辑结构是指数据元素的描述以及数据元素之间关系的集合 描述方法： 二元关系表示：B=（D，R） 也可以使用图形来表示 父亲 儿子 女儿 B=(D,R) D={父亲、儿子、女儿} R={(父亲，儿子)，(父亲，女儿)} 3.1 数据结构的基本概念 数据的逻辑结构 主要有两大类的逻辑结构： 线性结构：是n个数据元素的有序（次序）集合。数据元素之间存在着“一对一”的线性关系 (首元素、尾元素、前驱/件、后继/件) 非线性结构：数据元素之间存在“一对多”的关系。 3.2 算法的基本概念 算法(algorithm )的基本概念 指解题方案的准确而完整的描述，是解决问题一系列清晰的指令 求一元二次方程X2＋2X－15＝0的解 将等式因式分解为(X+5)(X-3)=0 得到X+5=0和(X-3)=0 方程的解为X=-5或3 3.2 算法的基本概念 算法的基本特征 可行性(effectiveness)：某一个算法必须能够在特定的计算工具上执行。 确定性(definiteness)：算法中每一个步骤都要明确定义。 有穷性(finiteness)：算法必须能在执行有限个步骤后终止(能够终止+合理时间内) 拥有足够的情报：算法的执行依赖于初始数据的完整性和正确性 3.2 算法的基本概念 算法的基本要素 一个算法通常由两种基本要素组成： 对数据对象的运算和操作：包括算数运算、逻辑运算、关系运算、数据传输等操作。 算法的控制结构：控制各操作之间的执行顺序。控制结构主要有顺序、选择、循环3种 描述算法通常可以使用程序流程图、N-S结构化流程图、算法描述语言(伪C代码) 3.2 算法的基本概念 算法设计的基本思路 列举法：列举出所有可能 归纳法：从特殊到一般 递推：从初始条件出发得到中间和最终结果 递归：将复杂问题分解 减半递推：分治法，缩小问题规模 回溯法：多次“尝试”，探寻最好步骤及结果 3.2 算法的基本概念 算法的3种描述方式 程序流程图 N-S结构化流程图 开始 开监听程序 while(收到短信) { 读取短信 显示到文本框 if(程序终止) { 关闭听程序 } else { 收短信 } } 伪C代码 3.2 算法的基本概念 算法的时间复杂度 指执行算法所需要的计算工作量(基本步骤的数量) 时间复杂度可从