第3章_算法与数据结构1.ppt

栈的示意图 * 栈也有两种存储结构 栈的顺序存储结构，简称顺序栈。 栈的链式存储结构简称链栈，一个链栈由栈顶指针唯一确定。 对栈这样一种元素多变的数据结构来说，链式存储结构显得更适宜。 * 栈顶指针和数据元素间的关系 空栈 栈中1个元素 * 栈顶指针和数据元素间的关系 栈满 退出两个元素 * 链栈示意图 * 队 列 队列是一种先进先出（First In First Out）的线性表，简称为FIFO。 队列只允许在表的一端进行插入操作，而在表的另一端进行删除操作。在队列中，将允许插入元素的表端，称为队尾。允许删除元素的表端，称为队头。 * * 假设队列Q有（a1，a2，…，an）共n个数据元素，即Q = (a1，a2，…，an)， a1就是队头元素，an则是队尾元素。 数据元素是按照a1，a2，…，an的顺序进入队列的，也只能按照这个顺序退出队列。也就是说，只有在a1，a2，…，an-1都离开队列以后，an才能退出队列。 队列的示意图 * 出队列 a1 a2 … an 入队列 队头 队尾 * 链队列示意图 3.6 树与图 树型结构是重要的非线性数据结构，其中以树和二叉树最常用。树在客观世界中广泛存在，在计算机领域中也有广泛的应用。 树是n（n≥0）个结点的有限集。在一棵非空树中：①有且仅有一个特定的称为根的结点；②当n＞1时，其余结点可分为m个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，并且称为根的子树。 * 只有根结点的树 * 一般的树 树 二叉树的5种基本形态 * 空二叉树 仅有根结点的二叉树 右子树为空的二叉树 左、右子树非空的二叉树 左子树为空的二叉树 图 图是一种较线性结构和树形结构更为复杂的数据结构。 图的数据元素之间的关系可以是任意的，任意两个数据元素间都可能相关。 @在线性表中，数据元素之间的逻辑关系为线性关系，每个数据元素只有一个直接前驱和一个直接后继。 @在树中，数据元素之间存在明显的层次关系。 * 有向图和无向图 图中的数据元素通常称为顶点。 * 有向图 无向图 图没有顺序映象的存储结构，通常都采用链式存储结构，且其每个结点包含一个数据域和多个指针域，形成多重链表，以利于表达图的顶点间的任意关系。 * 3.7 算法的设计 算法可分为数值计算和非数值计算两类。 各种数值计算都有比较成熟的算法可供选用。通常应用中需要设计的是有关非数值计算问题的算法，其操作对象为诸如表、树、图之类的数据结构。在计算机中查找和排序是典型的非数值计算问题。 * 3.7.1 算法的设计目标 通常一个“好”的算法应具备正确性、可读性和健壮性，并满足效率与存储量需求。 正确性： 设计算法最先应该达到的是正确性目标。 另一方面，正确的算法不应含有语法或逻辑错误，应能无误地处理合法输入数据，得到满足要求的结果。 * 可读性： 算法的主要目的是为了人们阅读和交流，其次才是机器执行。 良好的可读性有助于人们对算法的正确理解，同时也是算法具备可靠性和可维护性等性能指标的基础。 算法应有良好的“文体”，结构清楚、层次分明、思路清晰。 * 算法的效率指的是算法执行时间 算法的存储量需求指的是算法执行时所需的最大存储空间。 效率和存储量需求都与算法所解决问题的规模或复杂度有关。 * 对于同一个问题有多个算法可以解决，执行时间短的算法效率高。而效率高的算法有时可能需要相对更大的存储空间。时间和空间常常是对立的统一体，需要权衡以作出取舍，或者用空间的代价换取时间，或者用时间的代价换取空间。 * 3.7.2 查找和排序算法 所谓“查找”即为在一个含有众多数据元素的数据结构中找出某个特定的数据元素，特定的数据元素可以通过关键字标识。 关键字是数据元素中某个或某些数据项的值，用来唯一标识一个数据元素。即不同的数据元素其关键字不相同。 * 查找某个数据元素的方法，依赖于数据元素所存在的数据结构。也就是说，在计算机中进行查找的方法，因数据结构不同而不同。 * 顺序查找的算法 Begin 设顺序线性表的长度为：n 设查找的给定值为：k 设变量i 表示数据元素的位序 置i的初始值为1 while ( i ≤ n ) 并且 （i 元素的关键字 ≠ k） i ← i+1 endwhile if (i ≤ n ) “查找成功”，并输出 i 值 else “查找不成功” endif End * 直接插入排序法 它的基本操作是将一个数据元素插入到已排列好的有序表中，从而得到一个新的、元素个数加1的有序表。 例：