ess基础知识总结.doc

二级教程——公共基础知识算法是指解题方案的准确而完整的描述。程序的编制不可能优于算法的设计。算法的基本特征:;;(不允许有模能两可的解释,也不允许有多义性);。算法的两种基本要素:一是数据对象的运算和操作;二是算法的控制结构。算法设计的基本算法:;;;;;。算法的复杂度主要包括时间复杂度和空间复杂度。算法的时间复杂度(理解):是指执行算法所需要的计算工作量。算法的基本运算反映了算法运算的主要特征,用基本算法的次数来度量算法工作量是客观的也是实际可行的。算法的空间复杂度(理解):指执行这个算法所需要的内存空间。数据结构主要研究和讨论的三个方面问题:,即数据的逻辑结构;,各数据元素在计算机中的存储关系,即数据的存储结构;。。:;。(也称数据的物理结构)。常用的存储结构有顺序、链接、索引等存储结构。,一般将数据结构分为两的类:线性结构和非线性结构。,一个非空的数据结构需满足以下两个条件构成线性结构:一是有且只有一个根节点;二是每一个节点最多有一个前件,也最多有一个后件。、最常用的一种数据结构。,而复杂的线性表中,由若干数据相组成的数据元素成为记录,而由多个记录构成的线性表又称为文件。线性表是一种线性结构。数据元素在线性表中的位置只取决于它们自己的序号,即数据元素之间的相对位置是线性的。:;。。在这种特殊的线性表中,其插入与删除运算都只在线性表的一端进行。。栈也被称为“先进后出”表或“后进先出”表,其具有记忆作用。通常用指针top来指示栈顶的位置,用指针bottom只想线索。:入栈,退栈与读栈顶元素。:;,将该用户程序加入到线性表的末尾进行等待;,就从线性表的头部取出一个用户程序执行。在这种线性表中,需要加入的元素总是插入到线性表的末尾,并且又总是从线性表的头部取出(删除)元素。这种线性表成为队列。:一是顺序查找;二是二分法查找(二分法查找只需要比较㏒2n次,而顺序查找需要查找n次。:交换类排序法:;。插入类排序法:(简单插入排序需要n(n-1)/2次比较,希尔排序所需要比较次数O(n),堆排序需要比较的次数为O(n㏒2n)).,主要应注重和考虑下述一些因素:a