数据结构与算法知识点必备.pdf

数据结构与方法数据结构与方法1、算法的基本特征：可行性、确定性、有穷性、拥有足够的情报2、算法的基本运算和操作：算术运算、逻辑运算、关系运算、数据传输3、算法的基本控制结构：顺序结构、选择结构、循环（重复）结构4、算法设计的基本方法：列举法、归纳法、递推、递归、减半递推技术、回溯法5、算法的复杂度主要包括：时间复杂度、空间复杂度6、算法的时间复杂度：指执行算法所需要的计算工作量7、算法的空间复杂度：指执行这个算法所需要的内存空间8、数据结构主要研究：数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算9、数据结构研究的目的：提高数据处理的效率10、数据处理的效率：数据处理的速度、减少处理过程中占用计算机的存储空间11、数据处理：指对数据集合中的各元素以各种方式进行运算12、数据元素：指在数据处理中，每一个需要处理的对象都可以抽象成数据元素13、数据结构：指反映数据元素之间关系的数据元素集合的表示14、数据的逻辑结构：指反映数据元素之间逻辑关系的数据结构，两要素：数据元素的集合、数据元素在集合上的关系15、数据的存储结构：指数据的逻辑结构在计算机存储空间的存放形式，常用的存储结构有：顺序、链接、索引等16、数据结构的图形表示中每个元素加上方框成为结点17、数据结构一般分为：线性结构、非线性结构18、线性结构满足：有且仅有一个根结点、每个结点最多有一个前件和后件、在一个线性结构中插入和删除任何一个结点后还是线性结构19、线性表定义：线性表是由 n 个数据元素 a1、a2、a3、a4an 组成的一个有限序列，表中每一个数据元素，除了第一个外，有且仅有一个前件，除了最后一个外，有且仅有一个后件20、非线性表的特征：有且只有一个根节点a1，它无前件、有且只有一个终结点 an，它无1后件、除了第一个和最后一个外，其他所有结点只有一个前件和一个后件21、线性表的长度：线性表中的结点的个数n 成为线性表的长度，当 n=0 时，成为空表22、线性表的顺序存储的特点：所有元素所占的存储空间是连续的、各数据元素在存储空间中是按逻辑顺序一次存放的23、线性表的随机存取地址计算公式：ADD(ai)=ADD(a1)+(i-1)*k24、线性表的主要操作：插入、删除、查找、排序、分解、合并、复制、逆转25、栈的定义：栈是限定在一端进行插入和删除的线性表，它按照“先进后出，后进先出”的原则组织数据26、栈的顺序存储：在程序设计语言中，一般一维数组S（1：m）作为栈的顺序存储空间，其中 m 为栈的最大容量27、栈的基本运算：入栈、退栈、读栈顶元素28、入栈运算：首先将栈顶指针（top）加 1，然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时，说明栈空间已满，称为“上溢”错误29、退栈运算：首先将栈顶元素赋给一个指定的变量，然后将栈顶指针（top）减 1。当栈顶指针为 0 时，说明栈空，成为“下溢”错误30、队列的定义：队列是指允许在一端进行插入，而在另一端进行删除的线性表，它按照“先进先出”的原则组织数据31、循环队列：在实际应用中，队列的顺序存储结构一般采用循环队列的形式。所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用32、循环队列空的状态：s=0，且 front=rear=m循环队列满的状态：s=1，且 front=rear33、循环队列的基本运算：入队、退队34、入队运算：同样队列满时发生“上溢”错误35、退队运算：同样队列空时发生“下溢”错误36、线性链表的基本概念：线性表的链式存储结构37、线性链表的存储结构：线性链表的每个结点中数据域存放数据元素的值，指针域存放好2后件结点的存储地址38、双向链表的存储结构：双向链表的存储结构比线性链表的存储结构多出一个指针域，它用来存放前面的存储地址39、栈的链式结构：栈的链式结构基本上和线性链表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针40、队列的链式结构：队列的链式结构和线性链表的存储结构基本相同。只是队列的链式结构保持有两个指针：一个指向队列头的头指针，一个指向队列尾的尾指针41、线性链表的主要运算：插入、删除、合并、分解、逆转、复制、排列、查找42、线性链表的特点43、树结构中结点的类型：根结点、父结点、子结点、叶子结点44、结点的度：一个结点所拥有的后件个数成为结点的度45、树的度：在所有结点中最大的度数46、树的深度：树的最大层，也就是树的高度47、子树：子结点构成的树48、二叉树的特点：一是非空二叉树只有一个根结点，二是每一个结点最多有两棵子树49、二叉树的性质：在二叉树的第 k 层上，最多有 2 的（k-1）次方个结点 深度为 m的二叉树最多有 2 的 m 次方减 1 个结点 在任意一棵二叉树中，度为0 的结点（即叶子结点）总是比度为 2 的结点多一个 具有 n 个结点的二叉树，其深度至少为log2(n)+1，其中log2(n)表示 log2(n)的整数部分50、满二叉树定义：除最后一层外，每一层上的所有结点都有两个子结点51、完全二叉树定义：除最后一层外，每一层上的结点数均达到最大值，在最后一层上缺少右边的若干结点52：二叉树的存储结构：L（i）左指针域 R（i）右指针域 V（i）数据域53：二叉树的遍历集中用到了递归的思想，主要有三种遍历方式：前序遍历，中序遍历，后序遍历54、查找技术分为：顺序查找、二分查找、55、排序技术分为：交换类排序（冒泡排序法和快速排序法）、插入类排序（简单插入排序3法和希尔排序法）、选择类排序（简单选择排序法和堆排序法）4