二级VF公共基础知识.doc

第一章数据结构与算法
1．1算法
1．算法定义：是指解题方案的准确而完整的描述。
2．基本特征：可行性、确定性、有穷性、拥有足够的情报。
3．基本要素：算法中对数据的运算和操作；算法的控制结构（描述算法的工具有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可用顺序、选择、循环三种基本控制结构组合而成。
4．设计基本方法：列举法、归纳法、递推、递归、减半递推技术
5．算法的复杂度包括：时间复杂度（执行算法所需要的额计算工作量）、空间复杂度（执行算法所需要的内存空间）

1．2数据结构的基本概念
1．数据结构研究和讨论问题包括：①数据的逻辑结构②数据的存储结构③运算
讨论目的：为了提高数据处理的效率。（包括提高处理速度，节省存储空间）
2．数据处理定义：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等，也包括对数据元素进行分析。
*①对分查找只适用于有序表。②一般情况下，在具有相同特征的数据元素中，各个数据元素之间存在某种关系，反映了该集合中的数据元素所固有的一种结构，此关系叫前后件关系（或直接前驱与直接后继关系）
３．数据结构应包括：①表示数据元素的信息②表示各元素之间的前后间关系是指他们的逻辑关系，而与存储位置无关
４．数据的逻辑结构定义：指反映数据元素之间逻辑关系的数据结构
５．数据的逻辑结构要素：①数据元素的集合，记为Ｄ②是Ｄ上的关系，它反映了Ｄ中各数据元素之间的前后件关系，记为Ｒ即数据结构可表示为Ｂ＝（Ｄ，Ｒ）
６．数据的存储结构定义：数据的逻辑结构在计算机存储空间中的存放形式，也称数据的物理结构。
*在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端节点（也叫叶子节点）。除了根和终端外的其他结点一般称为内部结点

1．3线性表及其顺序存储结构
1.线性表的规律：是由n个元素a1a2……an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或表示为（a1a2…ai…an）
2.非空线性表的结构特征：①有且只有一个根结点a1。它无前件②有且只有一个终端结点an，它无后件③除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表结点的个数n称为线性表的长度。当n=0时，称为空表。
3.线性表的顺序结构运算：线性表的插入、删除、查找、排序、分解、合并、复制、逆转

1．4栈和队列
1.栈的含义：栈实际上也是线性表，只不过是一种特殊的线性表。插入与删除运算都只在线性表的一端进行。即在这种线性表的结构中，一端是封闭的（不允许…），另一端是开口的（允许…）。允许插入与删除的一端叫栈顶，不允许的叫栈底。栈是按照“先进后出”或“后进先出”的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。在栈的顺序存储空间S(1:m)中，S(bottom)通常为栈底元素，S(top)为栈顶元素。Top=0表示栈空；top=m表示栈满。
2.栈的基本运算：入栈、退栈、读栈顶元素。
3.队列的含义：指允许在一端插入、而在另一端进行删除的线性表。又称为“先进先出”或“后进后出”表，它体现了先来先服务的原则。
4.循环队列的定义：就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的循环空间，供队列循环使用。在循环队列中，队列空的条件为s=0；队列满的条件为s=1且pront=rear。在队尾加入一个新元素叫入队运算；在队列派头位置退出一个元素并赋给指定变量叫退队运算。

1．5线性链表
1.线性链表的基本概念：①为了在顺序存储的线性表中插入或删除一个元素，需要移动线性表中约一半的元素；在最坏的情况下，则需要移动线性表中的所有元素。因此，对于大的线性表，特别是元素的插入或删除很频繁的情况下，采用顺序存储结构是很不方便的，插入与删除运算的效率很低。②在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结点的前一个或后一个结点（即前件或后件）。③线性表的链式存储结构称为线性链表。在线性链表中，各数据元素之间的前后件关系是由各结点的指针域来指示的，指向线性表中的第一个结点的指针HEAD称为头指针，当HEAD=NULL(或0)时称为空表。上面讨论的线性链表又称为线性单链表。为了弥补线性单链表的缺点，在某些应用中，对线性链表的每个结点设置两个指针，一个称为左指针，另一个是右指针。这样的线性链表称为双向链表。
2.线性链表的基本运算：①插入②删除③合并④分解⑤逆转⑥复制⑦排序⑧查找

1．6树与二叉树
1.树结构的基本术语：①在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称树的根