1、算法是指解题方案的准确而完整的描述。 算法例：计算三角形的面积的算法1.输入底的长度值a2.输入高的长度值b3.如果底和高都大于0进入步骤4，否则进 入步骤7 4. 计算面积值c=a*b/2 5. 屏幕输出面积c 6. 结束7.显示出错例：把大象放进冰箱的算法。1.把冰箱打开2.把大象放进去3.把冰箱门关上算法的基本要素：1.对数据的运算和操作(运算符号和函数)算术、逻辑、关系、数据传输 2.算法的控制结构顺序、选择、循环程序举例!算法4个特征：可行性确定性有穷性拥有足够的情报。评价算法的优劣：时间复杂度和空间复杂度 数据结构数据结构概念包括3个内容：数据之间的逻辑关系（逻辑结构）数据在计算机
2、中的存储方式（存储结构）以及在这些数据上定义的运算的集合（数据的运算） 数据结构算法只是描述数据运算的方法和过程，其具体实现的效率要以数据结构为基础。程序数据结构算法数据结构举例：处理N个学生的学号逻辑结构线性表： 07020001 07020002 07020003存储结构顺序表： 数据的运算有：新增、删除、查找学号070200030702000207020001逻辑结构（描述数据之间的逻辑关系）：分类： 线性结构线性结构 非线性结构非线性结构分类：线性表线性表 *集合集合树树 *图或网图或网前件、后件的各种对应关系决定不同的逻辑结构。线性表线性表（注意前后件特征）（注意前后件特征）、普通线
3、性表（不限制操作）、栈（以先进后出的原则，只能在一端插入或删除元素）*、队列（以先进先出的原则，只能在两端插入或删除元素）*对线性表常用操作：对线性表常用操作： 插入新元素、删除元素、读取元素值、查找元素等节点线性表分类：线性表分类：一、一、栈栈 栈是一种特殊的线性表，在这种线性表中，一端是封栈是一种特殊的线性表，在这种线性表中，一端是封闭的，不允许插入与删除元素，另一端是开口的，允许插闭的，不允许插入与删除元素，另一端是开口的，允许插入与删除元素。入与删除元素。 栈顶：允许插入与删除的一端称为栈顶。栈顶：允许插入与删除的一端称为栈顶。 栈底：不允许插入与删除的一端称为栈底。栈底：不允许插入与
4、删除的一端称为栈底。 栈是根据栈是根据“先进后出先进后出”或或“后进先出后进先出“的原则组织数的原则组织数据的。据的。ana1a0栈顶栈顶栈底栈底栈结构举例：练习题： 栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是_。栈底E技巧：判断连续的两个元素的进栈和出栈顺序是否违背“先进后处原则”，如果违背就淘汰该选项。二、队列二、队列 队列是一种特殊的线性表，在这种线性表中，需队列是一种特殊的线性表，在这种线性表中，需要加入的元素总是插入到线性表的末尾，并且又总要加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出元素。即一端插入，另一端是从线
5、性表的头部取出元素。即一端插入，另一端删除的线性表。删除的线性表。 队尾：允许插入的一端队尾：允许插入的一端 队头：允许删除的一端队头：允许删除的一端 队列是按照队列是按照“先进先出先进先出”或或“后进后出后进后出”的原则的原则组织数据的，体出了组织数据的，体出了“先来先服务先来先服务”的思想。的思想。 CABD对头对头对尾对尾队列结构举例： 树与二叉树树与二叉树（注意前后件特征）（注意前后件特征）一、树一、树 树是一种简单的非线性结构。在这种结构中，所有数据树是一种简单的非线性结构。在这种结构中，所有数据元素之间的关系具有明显的层次特性。元素之间的关系具有明显的层次特性。计算机软件计算机软件
6、计算机学科计算机学科计算机应用计算机应用计算机网络计算机网络人工智人工智能能软件理论软件理论安全学安全学系统结构系统结构说明：在树的图形表示中，省略表示前后关系的箭头，总是认为上端结点说明：在树的图形表示中，省略表示前后关系的箭头，总是认为上端结点是前件，下端结点是后件。是前件，下端结点是后件。计算机学科计算机学科计算机应用计算机应用计算机网络计算机网络人工智能人工智能软件理论软件理论安全学安全学系统结构系统结构树基本概念：根节点父节点子节点叶子节点节点的度树的度(最大的节点度)子树节点的层次树的深度 二叉树及其基本性质二叉树及其基本性质二叉树是具有以下两个特点的树：（1）非空二叉树只有一个根
7、结点（2）每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树（其他定义：每个结点的度最大为2的树）二叉树的基本性质：性质1 在二叉树的第k层上，最多有2(k-1)个结点例题：一棵二叉树第六层（根结点为第一层）的结点数最多为 _ 个。性质2 深度为m的二叉树最多有2m-1个结点ABCDE性质性质3 在任意一棵二叉树中，度为在任意一棵二叉树中，度为0的结点（叶子结的结点（叶子结点）总比度为点）总比度为2的结点多一个。的结点多一个。例题：例题：某二叉树中度为2的结点有18个，则该二叉树中有 【1】 个叶子结点性质性质4 具有具有n个结点的二叉树，其深度至少为个结点的二叉树，其深度至少为log
8、2n+1完全二叉树：完全二叉树：除最后一层外，每一层上的结点数均达到最大值；且除最后一层外，每一层上的结点数均达到最大值；且在最后一层只在右边连续缺少结点在最后一层只在右边连续缺少结点。ABCDABCDEEABCDFDABCF 满二叉树：满二叉树：所有层的节点数都达到最大值所有层的节点数都达到最大值ABCDEFG性质性质5 具有具有n个结点的完全二叉树，其深度为个结点的完全二叉树，其深度为log2n+1例题：设一棵完全二叉树共有700个结点， 则在该二叉树中有_个叶子结点。完全二叉树性质：当完全二叉树节点个数为奇数时，度为完全二叉树性质：当完全二叉树节点个数为奇数时，度为1的节点有的节点有0个
9、；偶个；偶 数时有数时有1个。个。两个特殊的二叉树：完全二叉树、满二叉树两个特殊的二叉树：完全二叉树、满二叉树abcdef二叉树二叉树 遍历遍历从根节点开始，遇到每个节点时，都递归使用以下步骤。前序遍历： 、访问根节点2、前序遍历左子树3、前序遍历右子树中序遍历： 、中序遍历左子树2、访问根节点3、中序遍历右子树后序遍历： 、后序遍历左子树2、后序遍历右子树3、访问根节点前序遍历：从上方进入节点时，访问该节点中序遍历： 从左子树回到节点时，访问该节点后序遍历： 从右子树回到节点时，访问该节点前序、中序、后序abcdef练习题：写出前、中、后序遍历以下二叉树的遍历顺序。 从根节点开始，遇到每个节
10、点时，都递归使用以下步骤：前序遍历： 、访问根节点2、前序遍历左子树3、前序遍历右子树中序遍历： 、中序遍历左子树2、访问根节点3、中序遍历右子树后序遍历： 、后序遍历左子树2、后序遍历右子树3、访问根节点内存内存 20 21 22 23 24 25 20 21 22 23 24 25顺序存储顺序存储 20 21 23 24 25 .26链式存储链式存储线性表线性表线性表的线性表的顺序存储结构顺序存储结构和和链式存储结构链式存储结构的优缺点的优缺点 20 21 22 23 24 25顺序存储：利于直接（随机）存取元素，但不利于插入和删除操作顺序存储：利于直接（随机）存取元素，但不利于插入和删除操作链式存储：利于插入和删除操作，但不利于直接（随机）存取元素链式存储：利于插入和删除操作，但不利于直接（随机）存取元素 20 21 23 24 25 26查找算法（在线性表中查找元素）查找算法（在线性表中查找元素）顺序查找：二分法查找：最好的情况下比较次数为，最坏为N（假如一共N个元素）最好的情况下比较次数为，最坏为Log2N冒泡排序算法
