数据结构与算法 ◆算法得基本概念 1、 算法:就是对问题处理方案得正确而完整得描述,就是求解问题得方法,就是指令得有效序列。 2、 具有 5 个特性: (1) 有穷性(在有穷步后完成)算法程序得运行时间就是有限得 (2) 确定性(每一步都有确定得含义) (3) 可行性 (4) 输入(一个算法有零个或多个输入) (5) 输出(一个算法有一个或多个输出) 3、 算法得复杂度 包括:时间复杂度与空间复杂度。 二者没有必定得联系。 时间复杂度:执行算法所需要得计算工作量或基本运算次数。 空间复杂度:算法所需要得空间得度量。 ◆数据结构得定义 1、 数据结构包括数据得逻辑结构、数据得存储结构、数据得操作 数据得逻辑结构:数据得外部结构,指各数据元素之间得逻辑关系,反映人们对数据含义得解释。 包括:线性结构(线性表、栈、队列)与非线性结构(树与图) 数据得存储结构:数据得物理结构,指数据得逻辑结构在计算机中得表示。 一个逻辑结构可以有多种存储结构。 ◆ 线性表:线性表中元素得个数 n(n>=0)定义为线性表得长度。 顺序存储就是线性表得一种最常用得存储方式。 线性表得顺序存储结构与线性表得链式存储结构分别就是随机存取得存储结构与顺序存取得存储结构。 1、栈:就是限定在表尾进行插入与删除操作得线性表。 具有记忆功能 只能顺序存储(错) 允许插入与删除得一端叫栈顶。另一端叫栈底。 后进先出得线性表 2 队列:就是限定在一端插入而在另一端删除,插入端叫队尾,删除端叫对头。 先进先出得线性表 3 栈与队列得顺序存储结构 循环队列属于线性表存储结构中顺序存储结构与链式存储结构得前者。 ◆ 树 1、定义:树得结点、度(结点得度)、叶子(终端结点)、数得度、深度、有序树与无序数 2、二叉树:结点至多有两棵子树,并且二叉树得子树有之分,次序不能颠倒。 性质:★在二叉树得第 i 层上至多有 2i1 个结点 ★ 深度为 k 得二叉树至多有 2k1 个结点。 ★ 对任一个二叉树 T,假如其叶子(终端结点数)为 n,度为二得结点数为 m,则 n=m +1、 ★ 具有 n 个结点得完全二叉树得深度为 k+1,其中 k 就是㏒2n 得整数部分。 2、 二叉树得遍历 ▼先序遍历(根—左—右) ▼中序遍历(左—根—右) ▼后序遍历(左—右—根) ◆查找算法 (1)顺序查找 顺序查找得平均查找长度为(n+1)／2,最坏得情况下比较得次数为 n (2) 二分查找最坏情况下次数为 log2n 限定于顺序存储得有序线性表 ◆排序算法 (1)插...
