文档介绍:第一章数据结构与算法
:是指解题方案的准确而完整的描述。
:可行性、确定性、有穷性、拥有足够的情报。
:算法中对数据的运算和操作;算法的控制结构(描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可用顺序、选择、循环三种基本控制结构组合而成。
:列举法、归纳法、递推、递归、减半递推技术
:时间复杂度(执行算法所需要的额计算工作量)、空间复杂度(执行算法所需要的内存空间)
:①数据的逻辑结构②数据的存储结构③运算
讨论目的:为了提高数据处理的效率。(包括提高处理速度,节省存储空间)
:指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等,也包括对数据元素进行分析。
*①对分查找只适用于有序表。②一般情况下,在具有相同特征的数据元素中,各个数据元素之间存在某种关系,反映了该集合中的数据元素所固有的一种结构,此关系叫前后件关系(或直接前驱与直接后继关系)
:①表示数据元素的信息②表示各元素之间的前后间关系是指他们的逻辑关系,而与存储位置无关
:指反映数据元素之间逻辑关系的数据结构
:①数据元素的集合,记为D ②是D上的关系,它反映了D中各数据元素之间的前后件关系,记为R 即数据结构可表示为B=(D,R)
:数据的逻辑结构在计算机存储空间中的存放形式,也称数据的物理结构。
*在数据结构中,没有前件的结点称为根结点,没有后件的结点称为终端节点(也叫叶子节点)。除了根和终端外的其他结点一般称为内部结点
:是由n个元素a1 a2 …… an 组成的一个有限序列,表中的每一个数据元素,除了第一个外,有且只有一个前件,除了最后一个外,有且只有一个后件。即线性表或是一个空表,或表示为(a1 a2 …ai… an)
:①有且只有一个根结点a1 。它无前件②有且只有一个终端结点an,它无后件③除根结点和终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。线性表结点的个数n称为线性表的长度。当n=0时,称为空表。
:线性表的插入、删除、查找、排序、分解、合并、复制、逆转
:栈实际上也是线性表,只不过是一种特殊的线性表。插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中,一端是封闭的(不允许
…),另一端是开口的(允许…)。允许插入与删除的一端叫栈顶,不允许的叫栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的,因此,栈也被称为“先进后出”表或“后进先出”表。在栈的顺序存储空间S(1:m)中,S(bottom)通常为栈底元素,S(top)为栈顶元素。Top=0表示栈空;top=m表示栈满。
:入栈、退栈、读栈顶元素。
:指允许在一端插入、而在另一端进行删除的线性表。又称为“先进先出”或“后进后出”表,它体现了先来先服务的原则。
:就是将队列存储空间的最