自考数据结构课件 第一章 绪论.ppt

《自考数据结构课件 第一章 绪论.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构教材:自考《数据结构》苏仕华编著授课教师：涂风华开始日期：2014年3月1日1.1基本概念和术语1.2学习数据结构的意义1.3算法的描述和分析第1章概论数据（data)—是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的"原料"。数据元素（dataelement）—是数据的基本单位，由若干个数据项组成，也称结点、元素、顶点或记录。数据项（dataitem）—是具有独立含义的最小标识单位，有时也称为域（field），即数据表中的字段。1.1基本概念和术语数据结构(datastructure)

2、：指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括以下三方面内容：①数据元素之间的逻辑关系，也称数据的逻辑结构（LogicalStructure）；②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）；③数据的运算，即对数据施加的操作。①数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。②数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，

3、存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。③数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。所谓抽象的操作，是指我们只知道这些操作是"做什么"，而无须考虑"如何做"。只有确定了存储结构之后，才考虑如何具体实现这些运算。3为了增加对数据结构的感性认识，下面举例来说明有关数据结构的概念。【例1．1】学生成绩表，见下表。（1）逻辑结构表中的每一行是一个数据元素（或记录、结点），它由学号、姓名、各

4、科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（ImmediatePredecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（ImmediateSuccessor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中"李四"所在结点的直接前趋结点和直接后继结点分别是"张三"和"王五"所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构

5、。（2）存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3）数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。   搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。2．数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构线性结构的

6、逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。   线性表是一个典型的线性结构。栈、队列、串等都是线性结构。（2）非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。3．数据的四种基本存储方法数据的存储结构可用以下四种基本存储方法得到：（1）顺序存储方法该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。   由此得到的存储表示

7、称为顺序存储结构，通常借助程序语言的数组描述。该方法主要应用于线性的数据结构。非线性的数据结构也可通过某种线性化的方法实现顺序存储。（2）链接存储方法该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构（LinkedStorageStructure）,通常借助于程序语言的指针类型描述。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(元素i)=Lo+（i-1)*m顺序存储1536元

8、素21400元素11346元素3∧元素41345h存储地址存储内容指针1345元素114001346元素4∧…….……..…….1400元素21536…….……..…….1536元素31346链式存储h（3）索引存储方法该方法通常在储存结点信息的同时，还建立附加的索引表。   索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密