第一章
算法:指问题解决方案被正确完整地描述
算法的基础特点:可行性、确定性、贫困性,具有充分的信息
算法设计基础方法:枚举法、归纳法、递归、递归、减半递归技术、回溯法
时间的复杂性和空间的复杂性对算法的复杂性很重要
用算法实施过程中所需的基础运算实施次数来测量算法的工作量
数据结构作为计算机学科,重要研究和讨论以下三个问题
)数据集合中各数据要素间固有的逻辑关系,即数据逻辑结构
)处理数据时,各数据要素在计算机中存储关系。 即,是数据存储结构
)3)运算数据结构
7、数据逻辑结构:指具有结构的数据元素的集合
8、数据结构应包括: (1)表示数据元素的信息
)2)表示各数据要素之间的前后关系
数据逻辑结构是指反应数据要素间逻辑关系数据结构
将数据结构存储在计算机存储空间中的形式称为数据存储结构
根据数据结构中每个数据元素之间前后关系的复杂性,数据结构通常分为两种类型:
线性结构和非线性结构
假设非空数据结构满足以下两个条件
(1)有根节点,只有一个
)每个节点最多有1个前因,最多有1个后果
该数据结构也称为线性结构,也称为线性表
线性表是最简单最常见的数据结构
非线性表具有以下结构特征
(1)有根节点a1,无前因
)2)终点An只有一个,没有后事
)除根节点和终端外,其他所有节点只有一个前因,只有一个后果,
线性表中节点数n称为线性表长,在n=0的情况下称为空表
15线性列表的顺序存储结构有两个基本特征
)线性表中所有元素所占的收纳空间是连续的
)线性列表中的各数据要素按逻辑顺序依次存储在存储空间中
顺序表插入、删除运算
堆栈:限定在一侧插入删除线性表
堆栈基于“优秀后出”或“落后先出”的标准化团体数据,堆栈也称为“优秀后出”表
或“后进先出”表
中个数=bottom-top 1(值大时和值小时再加一个) ) ) ) ) ) ) )。
Top=0表示堆栈空top=m表示堆栈已满
支持子程序调用的数据结构是堆栈
堆栈的基本运算有三种:堆栈、外堆栈和读堆栈的顶级元素
队列:允许在一端插入,在另一端删除线性表
队列被称为“优秀先出”或“后退后出”线性表
列空和列完整条件:列空条件为s=0,列完整条件为s=1,ftont=rear
入队运算是在循环队列的末尾添加新元素
出队运算是指在循环队列的开头转义元素并将其分配给指定的变量
线性表链式存储结构称为线性链表
)1)检索在线链接列表中指定的要素
)2)线性链表插入是指在链存储结构下的线性表中插入新元素
)3)线性链表的删除是指在链存储结构下从线性表中删除包含指定元素的节点
26、树是简单的非线性结构
27、树型数据结构的基础特征
(1)树结构的每个节点只有一个前因。 据说父节点只有一个没有前因的节点
是树根的接合点,简称树根。
在树结构中,每个节点可以有多个后代,它们都被称为该节点的子节点。 没有下文
件节点称为叶节点
(3)在树结构中,一个节点所拥有的后件个数称为其节点度。 叶片的节点度为0
树中,所有节点中最大的大小称为树度
树的最大水平叫做树的深度
将树中聪明悟空节点的一个子节点作为根构成树,称为该节点的一个子树,叶节点没有子节点
树木
二叉树是一种非常有用的非线性结构
二叉树的特征: (1)非空二叉树只有一个根节点
)每个节点最多有两个子树,每个节点度最多为2
二叉树的基础性质: (1)二叉树的第k层最多有2k-1次幂(k=1)个节点
)深度为m的二叉树最多为2m次幂-1个节点(深度为m
二叉树是指二叉树共享m层)
)3)在任何二叉树中,度为0的节点,即叶的节点总是比度
多一个两个节点
)4)包含n个节点的二叉树,其深度最低为【log2N】1,其中【log2N】
表示取其整数部分
二叉树和完全二叉树(1)二叉树(除最后一层外,每层的所有节点都有两个)
子节点
)2)完全二叉树:除最后一层外,所有层节点树实现最多
较大的值只是最后一层缺少右侧的几个节点
完全二叉树的性质:包含“1”m个节点的完全二叉树的深度为【log2N】1
)2)完全二叉树