文档介绍：【本章考试要点】Ø算法的基本概念;算法复杂度的概念和意义(时间复杂度和空间复杂度)。Ø数据结构的定义;数据的逻辑结构与存储结构;数据结构的图形表示;线性结构与非线性结构。Ø线性表的定义;线性表的顺序存储结构及其插入与删除。Ø栈和队列的定义;栈和队列的顺序存储结构有其基本运算。Ø线性单链表、双向链表与循环链表的结构及其基本运算。Ø树的基本概念;二叉树的定义及其存储结构;二叉树的前序、中序和后序遍历。Ø顺序查找与二分法查找算法;基本排序算法(交换类排序、选择类排序、插入类排序)。一、算法算法是指解题方案的准确而完整的描述。1、算法的基本特征▲可行性——算法的每一条指令都必须是基本的,可执行的。▲确定性——算法的每一个步骤都必须是有明确定义的,不允许有模棱两可的解释,也不允许有多义性。▲有穷性——算法必须在有限的时间内完成,即算法必须能在执行有限个步骤之后终止。▲拥有足够的情报——不同的输入将会有不同的结果。当算法拥有足够的情报时,算法才有效。算法是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。2、算法的基本要素▲数据对象的运算和操作基本运算和操作包括以下四类:Ø算术运算,Ø逻辑运算,Ø关系运算,Ø数据传输▲算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。一个算法通常由顺序、选择、循环三种基本控制结构组合而成。3、算法设计基本方法Ø列举法,Ø归纳法,Ø递推,Ø递归,Ø减半递推技术,Ø回溯法4、算法复杂度Ø算法的时间复杂度——指执行算法所需要的计算工作量(用基本运算的次数来度量)。Ø算法的空间复杂度——指执行算法所需要的内存空间。二、数据结构的基本概念1、数据结构的定义Ø数据结构是指相互有关联的数据元素的集合。Ø在数据处理领域里,每一个需要处理的对象都可以抽象数据元素(元素)。Ø在具有相同特征的数据元素集合中,各个数据之间存在有某种关系(即联系),这种关系反映了该集合中的数据元素所固有的一种结构。通常把数据元素之间这种固有的关系简单地用前后件关系(或直接前驱与直接后继)来描述。数据结构是指反映数据元素之间关系的数据元素集合的表示。或者说,数据结构是指带有结构的数据元素的集合。所谓结构实际上就是指数据元素之间的前后件关系。(1)数据的逻辑结构一个数据结构应包含两个方面的信息:Ø表示数据元素的信息Ø表示各数据元素之间的前后件关系(逻辑关系,与数据在计算机中的存储位置无关)所谓数据的逻辑结构,是指反映数据元素之间逻辑关系的数据结构。(2)数据的存储结构Ø数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(物理结构)。Ø在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系。Ø常用的存储结构有顺序、链接、索引等存储结构。Ø采用不同的存储结构,其数据处理的效率是不同的。Ø插入与删除是对数据结构的两种基本运算。2、数据结构的图形表示Ø每一个数据元素用中间标有元素值的方框表示,称之为数据结点。Ø用一条有向线段从前件指向后件,以表示数据元素之间的前后件关系。Ø没有前件的结点称为根结点;没有后件的结点称为终端结点(叶子结点)。3、线性结构与非线性结构▲如果在一个数据结构中一个数据元素都没有,则该数据结构称为空的数据结构。▲根据数据结构中各数据元素之间的前后件关系的复杂程度,将数据结构分为两大类:线性结构和非线性结构。(1)线性结构一个非空数据结构如果:Ø有且只有一个根结点Ø每一个结点最多有一个前件和一个后件则称之为线性结构(线性表)。▲一个线性结构中插入或删除任何一个结点后还应是线性结构。▲如果一个线性结构满足上述两个条件,但当在此数据结构中插入或删除任何一个结点后不再满足上述条件,则该数据结构不能称线性结构。(2)非线性结构一个数据结构不是线性结构,则称之为非线性结构。▲线性结构和非线性结构都可以是空的数据结构。▲空的数据结构是线性结构还是非线性结构,要根据具体情况定。Ø对该数据结构的运算按线性结构的规则处理,则属线性结构。Ø对该数据结构的运算按非线性结构的规则处理,则属非线性结构三、线性表及其存储结构1、线性表的概念Ø线性表是最简单、最常用的一种数据结构。Ø线性表由一组数据元素构成,一个数据元素可以是个简单项,也可以由若干个数据项组成。(由若干个数据项组成的数据元素称为记录,而由多个记录构成的线性表称为文件)。Ø线性表线性表是由n(n≥0)个数据a1,a2,a3,…,ai,…,an组成的一个有限序列,表中的每一个数据元素,除第一个外,有且只有一个前件;除了最后一个外,有且只有一个后件。即线性表可能表示为:(a1,a2,a3,…ai,…,an)Ø线性表中结点的个数n称为线性表的长度。当n=0时,称为空表。非空线性表的结构特征:Ø有且只有一个根结点a1