2019-2020年高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案 (I)

《2019-2020年高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案 (I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2019-2020年高中信息技术竞赛班数据结构专项培训教程01数据结构概论教案(I)§1.1什么是数据结构数据结构(DataStructure)：数据间的相互关系，即数据的组织形式。包括三方面的内容：(1)数据元素之间逻辑关系，即数据的逻辑结构(LogicalStructure)(2)数据元素及其关系在计算机存储器内的表示，即数据的存储结构(StorageStructure)(3)数据的运算，即对数据施加的操作。数据结构的定义：按某种逻辑关系组织起来的一批数据，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。在不易混淆的情况下，常常将数据的逻辑结构

2、简称为数据结构。·数据的逻辑结构有两大类：（1）线性结构逻辑特征是：有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。（2）非线性结构逻辑特征是：一个结点可能有多个直接前趋和直接后继。·数据的存储结构有四种基本方法（1）顺序存储方法该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。称为顺序存储结构（SequentialStorageStructure)（2）链结存储方法该方法不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。称为链式存储结构(LinkedStora

3、geStructure)。（3）索引存储方法该方法通常是在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项、索引项的一般形式是：（关键字，地址），关键字是唯一标识一个结点的那些数据项。（4）散列存储方法该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址。§1.2算法算法：由若干条指令组成的有穷序列，它必须满足下述准则：（1）输入：具有0个或多个输入的外界量，它们是算法开始前对算法最初给出的量。（2）输出：至少产生一个输出，它们是同输入有某种关系的量。（3）有穷性：每一条指令的执行次数必须是有限的。（4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性

4、：每条指令的执行时间是有限的。选用的算法首先应该是“正确的”。此外，主要考虑如下三点：（1）执行算法所耗费的时间；（2）执行算法所耗费的存储空间，其中主要考虑辅助存储空间；（3）算法应易于理解，易于编码，易于调试等等。练习：1.算法是指（　　） A.为解决问题而编制的计算机程序B.为解决问题而采取的方法与步骤 C.为解决问题而需要采用的计算机语言D.为解决问题而采用的计算方法2.下面关于算法的错误说法是()　A)算法必须有输出　B)算法必须在计算机上用某种语言实现　C)算法不一定有输入D)算法必须在有限步执行后能结束