文档介绍：第一章
算法
算法的基本概念:所谓算法是指解题方案的准确而完整的描述。
算法的基本特征:1)可行性
2)确定性
3)有穷性(包括:合理的执行时间的含义)
4)拥有足够的情报
算法的基本要素:1)对数据对象的运算与操作
2)算法的控制结构
算法设计基本方法:1)列举法 2)归纳法 3)递推
4)递归 5)减半递推技术 6)回溯法
算法复杂度
算法的时间复杂度:指执行算法所需的计算工作量
算法的空间复杂度:指执行过程中这个算法所需要的内存空间
数据结构的基本概念
利用计算机进行数据处理是计算机应用的一个重要领域
数据结构作为计算机的一门学科,主要研究和讨论以下三个方面的问题:
数据的逻辑结构:数据集合中各数据元素之间的所具有的逻辑关系
数据的存储结构:在对数据进行处理时,各数据元素在计算机中的存储关系
数据的运算:对各种数据结构进行的运算。
数据的逻辑结构
概念:是指反映数据元素之间的逻辑关系的数据结构。
一个数据结构应包含以下两方面的信息:
表示数据元素的信息
表示各数据元素之间的前后件关系
例如:a→b→c a的后件为b;a称为首(根)结点,c称为尾结点。
*数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构
一般来说,一种数据的逻辑结构根据需要可以表示成多种存储结构,而采用不同的存储结构,其数据处理的效率是不同的。
在数据结构中,没有前件的结点称为根结点,没有后件的结点称为终端结点(也称叶子结点)
线性结构与非线性结构
线性结构满足两个条件:1)有且仅有一个根结点;
2)每一个结点最多有一个前件,也最多一个后件
*如果一个数据结构不是线性结构,那么称之为非线性结构。
线性表的顺序存储结构
线性表的顺序存储结构具有以下特点:
线性表中所有元素所占的存储空间是连续的
线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
栈和队列
栈实际上也是线性表,只不过是一种特殊的线性表。栈是按照“先进后出”(FILO)的原则组织数据的,栈具有记忆作用。
队列是指允许在一端进行插入,而在另一端进行删除的线性表。允许插入的一端称为队列尾,通常用一个称为尾指针的的指针指向队尾元素,即尾指针总是指向最后被插入的元素,允许删除的一端称为排头(也称为“队头”),通常也用一个排头指针指向排头元素的前一个位置。队列是按照“先进先出”原则组织数据的。
*存储结构:1)顺序结构:数据有逻辑结构,存储空间有顺序
2)链式结构:
链式存储方式既可用于表示线性结构,也可表示非线性结构。
树与二叉树
树的基本概念:树是一种简单的非线性结构。
一些知识点:
根结点:没有前件的结点称为根结点(上面无叉叉) ;
叶子结点:没有后件的结点称为叶子结点(下面无叉叉)
父结点:在树结构中,每一个结点只有一个前件,称为父结点;
子结点:在树结构中,每一个结点可以有多个后件,它们被称为该结点的的子结点;
兄弟结点:
结点的度:在树结构中,一个结点所拥有的后件的个数称为该结点的度
树的度: 在树中,所有结点中的最大的度称为树的度
树的深度:树的最大层数称为树的深度。
4)二叉树:任意结点往下不超过两个叉
3、二叉树的特点:
1)非空二叉树只有一个根结点
2