[工学]数据结构与算法.ppt

数据结构与算法 1.1 算法 一、概念： 算法是解题方案的准确而完整的描述，是有限的运算序列集合。 1.算法的基本特征： 可行性、确定性、有穷性、拥有足够情报。 2. 算法的两个基本要素 算法中对数据的运算和操作 算法的控制结构 二、 算法的复杂度 (1)算法的时间复杂度： 指执行算法所需要的计算工作量。即算法执行过程中所需要的基本运算次数。 数据结构:研究数据元素及其间的关系和数据运算的一门学科 。 （1）数据的逻辑结构：数据集合中数据元素之间固有的逻辑关系。如：线型、树型、图型等。 （2）数据的存储（物理）结构：数据的逻辑结构在计算机存储空间中的存放形式。如：顺序、链式等。 线性结构与非线性结构一般将数据结构分为两种类型：（1）线性结构(即线性表) a. 有且只有一个根结点 b. 每个结点最多有一个前件和一个后件（2）非线性结构 如果一个数据结构不是线性的，则称非线性的。在一个线性结构中插入或删除任何一个结点后还应是线性结构。 1.4 栈和队列 一个栈的入栈序列是a b c d e,则该栈的不可能的输出序列是 A edcba B decba C dceab D abcde 栈和队列都是一种特殊的操作受限的线性表， 共同特点是只允许在端点处插入和删除元素. 二者的区别是： 栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表； 队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种先进先出的线性表。 树结构的基本术语： 根结点：只有一个没有前件的结点叫根结点。如下图中的结点P和结点A 父结点、子结点：一个结点的前件结点是它的父结点，后件结点是它的子结点。 子树：以某结点的一个子结点为根构成的树称为该结点的一棵子树。 结点的度：一个结点拥有子树的个数称为该结点的度，如下图(b)中根结点A、D的度为3，结点B、H的度为2，结点E、I的度为1，结点J、F、C、G、K、L、M的度为0。 叶子结点：没有后件的结点称为叶子结点。叶子结点的度为零。 树的度：树中所有结点度的最大值为树的度。如下图(b)中树的度为3 。 * 每年考4个选择+3个填空:共14分 算法复杂度的评价有两个指标：时间复杂度和空间复杂度。 (2)算法的空间复杂度: 指执行算法所需要的存储空间。 算法的时间复杂度与算法的空间复杂度之间没有必然的联系. 1.2 数据结构的基本概念 程序的执行效率 (1)与数据的存储结构密切相关 (2)与程序的控制结构相关 (3)与所处理的数据量相关 数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是一致的,即数据的逻辑结构与存储结构不一定一一对应. 一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构.采用不同的存储结构,其数据处理的效率不同. 1.3 线性表的顺序存储结构 线性表的顺序存储结构有两个基本特点： （1）所有元素所占的空间是连续的 （2）各元素在存储空间中是按逻辑顺序依次存放的。 在计算机中用一组地址连续的存储单元按逻辑顺序依次存储线性表中的各个数据元素，称作线性表的顺序存储结构。 常用数组存储。 1.4.1 栈及其基本运算 栈是限定在一端允许插入和删除的线性表 栈顶top：允许插入与删除的一端称为栈顶。 栈底bottom：不允许插入与删除的一端称为栈底。 栈是根据“先进后出”或“后进先出“的原则组织数据的。 …… an a1 a0 top bottom 入栈 出栈 栈的顺序存储结构及其基本运算 （1）入栈 指在栈顶插入一个新元素。它包含两步操作：先top+1，后插入新元素 …… an a1 a0 top bottom an+1 （2）退栈 指取出栈顶元素，并赋给一个变量。它包含两步操作：先栈顶元素赋给一个变量，后top-1 1.4.2 队列及其基本运算 队列是一端插入，另一端删除的线性表。 队尾：允许插入的一端。 队头：允许删除的一端。 C A B D front rear 队列是按照“先进先出”或“后进后出”的原则组织数据的。 通常用rear指针指向队尾元素，用front指针指向队头的前一个位置。 空队列： rear=front 队列的顺序存储结构一般采用循环队列形式 队列的顺序存储及其基本运算 front指向连续存储空间的低地址; rear指向连续存储空间的高地址。 C A B D E front rear （1）入队 指往队列的末尾插入一个元素。它包含