数据结构单元1-数据结构与算法.ppt

《数据结构单元1-数据结构与算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构教学目标【知识目标】了解数据、数据元素、数据结构、逻辑结构、存储结构的有关概念掌握数据结构包含的三个方面、逻辑结构的分类、基本逻辑结构、顺序存储和链式存储方法掌握算法及算法的特性理解和掌握算法分析的方法【能力目标】能熟练地对算法进行时间复杂度分析，从而选择一个好的算法。引例描述求两个n阶方阵的乘积C=A×B，其算法如下，计算该算法的时间复杂度。程序段如下：for(i=0;i

2、Data）数据是信息的载体。它能够被计算机识别、存储和加工处理。2.数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。3.数据项（Dataitem）数据项是具有独立含义的最小标识单位。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。4.数据结构（DataStructure）数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：知识储备(1)数据的逻辑结构：数据元素之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看

3、作是从具体问题抽象出来的数学模型。数据（逻辑）结构的形式定义：数据结构是一个二元组（D，R），其中D是数据元素的有限集，R是D上关系的有限集。(2)数据的存储结构：数据元素及数据元素之间的关系在计算机存储器内的表示。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。【示例】某个班学生成绩表，包括：学号、姓名和各科成绩，每一个学生的信息都是一个数据元素，数据元素之间有这样的逻辑关系：在一个数据元素的前面最多有一个与其相邻的数据元素（称为直接前驱），在一个数据元素

4、的后面也最多有一个与其相邻的数据元素（称为直接后继）。数据元素之间的这种关系构成了学生成绩表的逻辑结构。(3)数据的运算：即对数据施加的操作。数据的运算定义在数据的逻辑结构上，只有确定了存储结构，才能具体实现这些运算。数据的运算通常包括以下五个操作：①插入：在指定位置上添加一个新结点。②删除：删去指定位置上的结点。③更新：修改某结点的值。④查找：寻找满足指定条件的结点及其位置。⑤排序：按指定的顺序使结点重新排列。1.2数据的逻辑结构与存储结构1.数据的逻辑结构数据的逻辑结构有以下两大类：①线性结构有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接

5、前驱和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。②非线性结构一个结点可能有多个直接前驱和多个直接后继。多维数组、广义表、树和图等数据结构都是非线性结构。2.基本逻辑结构①集合结构：数据元素的有限集合。数据元素之间除了“属于同一个集合”的关系之外没有其他关系。②线性结构：数据元素的有序集合。数据元素之间形成一对一的关系。③树型结构：树是层次数据结构，树中数据元素之间存在一对多的关系。④图状结构：图中数据元素之间的关系是多对多的。集合结构线性结构树型结构图状结构3.存储结构存储结构可用以下四种存储方法得到：①顺序存储方法：把逻辑上相邻的

6、结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。通常借助程序设计语言的数组来描述。②链接存储方法：该方法不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段来表示的。由此得到的存储表示称为链式存储结构。通常借助程序设计语言的指针来描述。如图：300011301……89.5400011303……90.5305011325……83302011318……78NULLhead3000400030503020③索引存储方法：在建立结点信息的同时，还要建立附加的索引表来标识结点

7、的地址。索引表中的每一项称为索引项，索引项由结点的关键字和该结点的存储地址组成，关键字是能唯一标识一个结点的数据项。④散列存储方法：该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。同一逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构表示相应逻辑结构，视具体要求而定，主要考虑运算方便及算法的时空要求。1.3算法及算法分析一、算法及其特性1.算法是对特定问题求解步骤的一种描述，是指令的有限序列。一个算法是一系列将输入转换为输出的计算步骤。2.算法的重要特性①输入：算法应该有零个或多个输入。②有穷性：算法必须在执行有穷步骤之后正常

8、结束。③确定性：算法中的每一条指令必须