【4】Chapter3 线性表1-顺序表及单链表.ppt

《【4】Chapter3 线性表1-顺序表及单链表.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构与算法2011年秋季授课教师：张剑波授课班级：111101-2班1第二部分数据结构第3章-第12章（线性表、数组、栈、队列、树、图等）23.1引言基本概念和术语数据数据元素数据对象数据结构数据结构研究的内容数据结构的描述：抽象数据类型（ADT）31、基本概念和术语——数据1、数据（Data）数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据={x

2、x是计算机操作的对象}数值性数据：如整数、实数、复数、双精度数等。非数值性数据：如字符串、文字、图形、语音等。数据主要有两类：42、数据元素（Dat

3、aElement）数据元素是数据（集合）中的一个"个体"，是数据结构中讨论的"基本单位"；数据元素在计算机程序中通常作为一个整体进行考虑和处理；例如，一个学生基本情况是一个由（学号、姓名、性别、年龄，成绩）等数据项组成的数据元素。基本概念和术语——数据元素5学号姓名性别年龄成绩高数英语物理体育98011张娟女208086819098012赵立军男198272898698013李靖男2092859087……………………组合项初等项数据元素（记录）数据元素在不同的数据结构中称呼也有所不同。例如：在文件中，数据的基本单位称为“记录”；在树、图数据结构中，数据的基本

4、单位称为“节点”或“顶点”。63、数据对象（DataObject）一组实例构成的集合；具有相同性质的数据元素；数据的一个子集。所有的数构成“数”集合，自然数集合N＝{1，2，…}是“数”的数据对象；所有的字符是数据，字母集合LETTER＝{‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}是该数据的数据对象。例如基本概念和术语——数据对象我们研究：数据对象的描述以及与之相关的函数的具体实现。7基本概念和术语——数据结构4、数据结构（DataStructure）数据对象+实例和元素中的存在的各种关系。不同的关系构成不同的结构。数据结构的形式化定义：Dat

5、a_Structure＝（D，R）D是数据元素的有限集合（即某一数据对象）；R是D中所有元素之间的关系的有限集合。8（1）集合：结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系；（2）线性结构：结构中的数据元素存在的是一种线性关系，即一对一的关系；（3）树形结构：结构中的元素存在着一对多的关系；（4）图形结构或网状结构：结构中的数据元素存在着多对多的关系。数据结构中元素关系的四种常见类型93、数据结构的研究内容数据的逻辑结构如：线性表、栈、队列、树、图数据的物理结构（存储结构）如：顺序存储结构、链式存储结构数据的操作实现算法及算法分析如：插入、删

6、除、查找、遍历结构的应用实例10逻辑结构VS.物理结构数据的逻辑结构数据的物理结构（存储结构）数据元素之间存在的一种抽象化的相互关系逻辑结构在存储器中的映象从解决问题的需要出发数据在计算机中如何存放用户视图实现视图面向问题面向计算机算法设计基于数据的逻辑结构算法的实现基于数据的存储结构11（1）逻辑结构的分类线性结构线性表、栈、队列、串、数组非线性结构树型结构图（网络结构）12（2）存储（物理）结构的分类数据结构在计算机中的表示数据的存储结构依赖于计算机语言顺序存储表示链式存储表示索引存储表示散列存储表示13顺序映象——顺序存储结构（公式化描述）x……y借助

7、数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如：&y等于&x+C*sizeof(x)两种主要的存储结构——顺序存储结构14两种主要的存储结构——链式存储结构链式映象——链式存储结构（链接描述）·xy借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。例如：y=x->next;15（3）数据操作操作是定义在数据的逻辑结构上，但具体实现要在存储结构上进行。每种逻辑结构都有一个操作集合，常用的操作有：结构的生成：Create结构的销毁：Destroy在结构中查找（搜索）满足规定条件的数据元素：Search在结构中插入新的数据元素：Insert删

8、除结构中已经存在的数据元素：Delete遍历：Traverse16（4）数据结构应用示例管理信息系统中的查询问题文件中的记录可按顺序方式组织。黄鹏8211编译原理刘东8201算法分析李季为8211编译原理李宾8202算法分析王华8202图形学杜可翔8201编译原理何平8201编译原理陈红英8211算法分析………姓名班级选修课链链头顺序文件导出的链表为提高检索效率，可将所有选修“算法分析”课的同学记录串接到一起，这种串接称为“加链”。174、数据结构的描述：ADT数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。高级程序设计语言中的数据类

9、型有2类：原子类型：整型、实型、字符型、布尔型、枚举