云南省水富县第二中学八年级信息技术《数据结构与算法》教案.doc

数据结构与算法
一、基本概念：
v 数据(Data)：信息的载体，能够被计算机识别、存储和加工处理的物理符号。包括文本类型的数据(如：字母、数字、汉字)和多媒体类型的数据(如：声音、动画、图像)。
v 数据元素(Data Element)：是数据的基本单位，有时也称为元素、结点、顶点、记录，可以有若干个数据项（字段、域、属性）组成。
v 数据结构（Data Structure）：指的是数据之间的相互关系，即数据的组织形式。其包括三个部分：
1、逻辑结构：数据元素之间的逻辑关系
2、存储结构：数据元素及其关系在计算机存储器内的表示。
3、数据的运算（算法）：即对数据施加的操作

v 数据的逻辑结构有两大类：
1、线性结构：
特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点最多只有一个直接前趋和一个直接后继。
例：一维数组、链表、栈、队列、串
2、非线性结构：
特征是：一个结点可能有多个直接前趋和直接后继。
例：多维数组、广义表、树、图

v 数据的存储结构有以下基本存储方法：
1、顺序存储方法：
该方法是将逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，一般通过数组来实现的。
2、链接存储方法：
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。通过指针类型来实现的。
3、索引存储方法：
该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：关键字，地址。
4、散列存储方法：
该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址，通过散列函数实现。例：除余法散列函数、相乘取整法散列函数

v 算法的基本特征：
1、可行性(Effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。
2、确定性(Definiteness)：算法中的每一个步骤都必须有明确的定义，不允许出现歧义性。
3、有穷性(Finiteness)：算法必须在有限时间内做完，即必须在执行有限个步骤之后终止。

v 时间复杂度：该算法执行的时间耗费，它是该算法所求解问题规模n的函数。
v 空间复杂度：该算法执行时所耗费的存储空间，它也是问题规模n的函数。