知行教导冲刺班笔记总结
第一章：公共基本知识
1.1数据构造与算法
１．1.１算法
1．算法基本概念
（1)概念:算法是指一系列处理问题清晰指令。
(2）算法４个基本特性：可行性、确定性、有穷性、拥有足够情报。
(3)算法两种基本要素:对数据对象运算和操作、算法控制构造(运算和操作时间次序)
(4）算法设计基本措施：列举法、归纳法、递推法、递归法、减半递推技术和回溯法。
2．算法复杂度
（1）算法时间复杂度:执行算法所需要计算工作量。
(２）算法空间复杂度:执行算法所需内存空间。
1.1.２数据构造基本概念
数据构造指互有有关联数据元素集合，即数据组织形式。其中逻辑机构反应数据元素之间逻辑关系;存储构造为数据逻辑构造在计算机存储空间中存储形式，有次序存储、链式存储和散列存储四种方式。
数据构造按各元素之间先后件关系复杂度可划分:
（１）线性构造：有且只有一种根节点,且每个节点最多有一种直接前驱和一种直接后继非空数据构造。
（2)非线性构造:不满足线性构造数据构造。
1.１.3线性表及另一方面序存储构造
1.线性表基本概念
线性构造又称线性表,线性表是最简朴也是最常用一种数据构造。
2.线性表次序存储构造
●元素所占存储空间必要连接。
●元素在存储空间位置是按逻辑次序存储。
3.线性表插入运算
在i个元素之前插入一种新元素环节如下：
环节一:把本来第n个节点至第ｉ个节点依次往后移一种元素位置。
环节二：把新节点放在第i个位置上。
环节三:修正线性表机构个数。
4.线性表删除运算
删除第i个位置元素环节如下:
环节一:把第ｉ个元素之后不波及第ｉ个元素ｎ-1个元素依次前移一种位置;
环节二：修正线性表结点个数。
1.1.4栈和队列
1.栈及其基本运算
（１)基本概念:栈是一种特殊线性表,其插入元算与删除运算都只在线性表一端进行,也被称为“先进后出”表或“后进先出表”。
●栈顶:容许插入与删除一端。
●栈底:栈顶另一端。
●空栈:栈中没有元素栈。
（2)特点：
●栈顶元素是最终被插入和最早被删除元素。
●栈底元素是最早被插入和最终被删除元素。
●栈有记忆作用。
●在次序存储构造下，栈插入和删除元算不需移动表中其她数据元素。
●栈顶指针ｔop动态反应了栈中元素变化状况。
(3)次序存储和运算:入栈运算、退栈运算和读栈顶运算
2．队列及其基本元算
(1)基本概念：队列是指容许在一端进行插入，在另一端进行删除线性表，又称“先进先出”线性表。
●队尾:容许插入一端,用尾指针指向队尾元素。
●排头:容许删除一端，用头指针指向头元素前一位置。
(2）循环队列及其运算：入队运算与退队运算。
1．1.５树和二叉树
１．树基本概念
树是简朴非线性构造,树中有且仅有一种没有前驱节点称为“根”，别的节点提成ｍ个互不相交有限集合T ?1??? ??? ?,T2，…，T}rm?? ?m,每个集合又是一颗树，称T １? ? ????，Ｔ2，…,T}rｍ? ? ?m为根节点子树。
●父节点:每一种节点只有一种前件，无条件节点只有一种，称为树根结点（简称树根)。
●子节点:每一种节点可后来多种后件,无后件节点称为叶子节点。
●树度:所有节点最大度。
●树深度：树最大层次。
2．二叉树及其基本性质
二叉树是一种非线性构造,是有限节点集合，该集合为空（空二叉树)或由一种根节点及两棵互不相交左右二叉子树构成。可分为满二叉树和完全二叉树,其中满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。
●二叉树可为空,空二叉树无节点,非空二叉树有且只有一种跟结点;
●每个节点最多可有两颗子树,称为左子树和右子树。
3．二叉树存储构造
二叉树一般采用链式存储构造，存储节点由数据域和指针域(左指针域和右指针域）构成。二叉树链式存储构造也称为二叉链表对满二叉树和完全二叉树可按层次进行次序存储。
4．二叉树遍历
二叉树遍历是指不反复地访问二叉树中所有节点,重要指非空二叉树,对于空二叉树则结束返回。二叉树遍历波及前序遍历,中序遍历和后序遍历。
1．1.6查找技术
（１）次序查找：在线性表中查找指定元素。
（2)二分查找：线性表必要是次序存储构造,且必是有序表,反复查找直到成功或子表长度为０时结束。
1.1.7排序技术
（１)互换类排序法:借助数据元素“互换”进行排序，波及冒泡排序法和迅速排序法。
(2)插入类排序法：波及简朴插入排序法和希尔排序法
(3）选用类排序法：波及简朴选用排序法和堆排序法。
1．２程序设计基本
１．2.１程序设计措施与风格
(1）设计措施：程序设计指设计、编制、调试程序措施和过程,重要有构造化程序设计措施,软件工程措施和面向对象措施。
（2）设计风格:良好设计风格要重视源程序文