第01章 算法与数据结构基础1.ppt

第 1 章　算法与数据结构基础 1.1 算法的基本概念 1.2 数据结构基础 1.3 线 性 表 1.4 栈 和 队 列 1.5 树 1.6 排序 1.7 查找 考点1 算法 一、算法的概念：算法就是计算机解决问题的过程或步骤即解题方案的准确而完整的描述。 1算法的基本特征： 可行性、确定性、有穷性、拥有足够的情报 2 算法的基本要素： （1）对数据对象的运算和操作：每个算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 （2）算法的控制结构：算法中各操作之间的执行顺序。 二、算法的复杂度 算法的复杂度包括时间复杂度和空间复杂度 1。算法的时间复杂度指算法的时间耗费（执行算法所需要的计算工作量）。 一般情况下，算法所执行的基本运算次数是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)) 它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。 2。算法的空间复杂度描述算法的存储空间需求（执行这个算法所需要的内存空间）。 运行完一个程序所需要的内存大小是问题规模n的某个函数g(n)，记作： S(n) = O(g(n)) 它表示随着问题规模n的增大，算法运行所需存储空间的增长率S(n)与g(n)的增长率相同。 1.2 数据结构基础 数据：数据是信息的载体，是描述客观事物的数、字符，以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据包括数值性数据和非数值性数据。 数据元素（也称为元素、接点、顶点、记录）：数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成。 数据项：数据项是具有独立含义的最小标识单位。 数据对象：数据的子集，是具有相同性质的数据成员（数据元素）的集合。 数据结构的定义：数据结构是指相关有关联的数据元素的集合（数据之间的相互关系），一个数据结构应包含以下两方面的信息： 1、表示数据元素的信息 2、表示各数据元素之间的前后件关系 数据的逻辑结构：用来描述数据元素之间的逻辑关系。 数据的存储结构：用来描述数据元素及数据元素之间的关系在存储器中的存储形式。 数据的运算：即对数据元素施加的操作。 数据结构的图形表示：用图形来直观地表示数据及其之间的关系。 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为线性结构和非线性结构两类： 线性结构：数据元素之间构成一种顺序的线性关系，如图1-2所示。线性结构包括线性表、堆栈、队列和串。 线性结构的特征有： （1）集合中必存在惟一的一个“第一元素”； （2）集合中必存在惟一的一个“最后元素”； （3）除最后的元素之外，均有惟一的后继； （4）除第一元素之外，均有惟一的前驱。 非线性结构是指不满足以上条件的存储结构。非线性结构包括树、二叉树、 图（或网络）和广义表。 1.3 线 性 表 1.3.1 线性表的顺序存储结构 线性表是最常用且最简单的一种数据结构。 采用顺序存储结构的线性表也叫做顺序表，如n个元素的线性表可以记为：L=（a1，a2，…，an）。 顺序表有插入和删除两种基本操作。 1.3.2 线性表的链式存储结构 链式存储是指用一组地址任意的存储单元存放线性表中的数据元素。 链式存储采用结点来表示数据元素。一个结点由两个部分构成：数据域和指针域。 （1）单链表及其基本操作 （2）双向链表及其基本操作 在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后驱结点。 1.4 栈 和 队 列 1.4.1 栈及其基本操作 栈是规定只能在表的一端进行插入和删除的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。当表中没有元素时称为空栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先被删除，所以又把栈称为后进先出（Last_In_First_Out，简称LIFO）表。栈有插入（即进栈）和删除（即出栈）两种基本操作。 插入也叫入栈或进栈。 1.4.2 队列及其基本操作 队列可以看作是插入在一端进行，删除在另一端进行的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。 队列又称为先进先出（First_In_First_Out,FIFO）表。队列的基本操作有插入（即入队）和删除（即出队）两种。 1.5 树 1.5.1 树的基本概念 树是由n (n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n＞0，则有一个特定的称之为根（root）的结点，根结点只有直接后继，没有直接前驱；除根以外的其他结点划分为m (m≥0)个互不相交的有限集合T0，T1，…，Tm?1，每个集合又是一棵树，并且称之为根的子树（subTree）。每棵