《数据结构选讲》ppt课件

《《数据结构选讲》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构选讲DATASTRUCTURE主讲教师：罗熊Instructor:LUOXiongE-mail:xluo@mail.qgzxol.com2021/10/231课程内容：计算机软件的基础知识———数据结构课时安排：数据结构——32学时教材：严蔚敏，吴伟民.数据结构.北京：清华大学出版社，1997.参考书：数据结构习题与解析（C语言篇）李春葆数据结构题集严蔚敏，吴伟民数据结构算法与应用—C++语言描述（英文版）SartajSahniMcGraw-Hill&机械工业出版社2021/10/232数据结构的基本概念数据类型和抽象数据

2、类型C语言的数据类型用C语言描述算法的注意事项算法设计目标和算法效率度量第一章绪论2021/10/2331.1数据结构的基本概念数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}学生数据对象:初等项（不可分割）、组合项（可再划分）2021/10/234数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位）数据类型：具

3、有相同性质的计算机数据集合及在这个集合上的一组操作。数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为：Data_Structure={D,R}其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。2021/10/235数据结构依据视点的不同，分为数据逻辑结构和物理结构：逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。关系：物理结构是逻辑数据的存

4、储映象2021/10/236逻辑结构：线性结构非线性结构物理结构：顺序存储链接存储索引存储散列存储2021/10/237“学生”表格2021/10/238“课程”表格2021/10/239线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素)例：电话号码查询问题方法1：顺序存储，顺序查找2021/10/2310方法2：有序顺序存储，二分查找姓名地址李1李2……张1张2……王1王2……2021/10/2311方法3：部分有序，建立索引表姓名地址李1李2……张1张2……王1王2……姓地址李张……2021/10

5、/2312非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个选课单包含如下信息学号课程编号成绩时间学生选课系统中实体构成的网状关系2021/10/2313UNIX文件系统的系统结构图2021/10/2314树形结构树二叉树二叉搜索树2021/10/2315堆结构“最大”堆“最小”堆2021/10/2316图结构网络结构2021/10/2317例：田径赛的时间安排问题姓名项目1项目2项目3丁1跳高跳远100M马2标枪铅球张3标枪100M200M李4铅球200M跳高王5跳远200M跳高跳远标枪铅球200M100M1、任一

6、选手所选中的项目中应该两两有边相连；2、任一两个有边相连的顶点颜色（时间）不能相同。2021/10/2318在解决问题时可能遇到的典型的逻辑结构（数据结构）逻辑结构的存储映象（存储实现）数据结构的相关操作及其实现。2021/10/23191.2数据类型和抽象数据类型数据类型定义：一个数据的集合,以及定义于这个数据集合上的一组操作的总称。C语言中的数据类型基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型2021/10/2320抽象数据和抽象数据类型(ADTs:AbstractDataTypes)由用户定义，用以表示

7、应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（物理实现封装）2021/10/2321ADT：抽象数据类型名数据对象：数据对象的定义数据关系：数据逻辑关系的定义基本操作：基本操作的定义抽象数据类型的定义：操作名（参数表）操作结果：操作结果描述基本操作的定义：2021/10/2322抽象数据类型2021/10/2323好的和坏的数据结构？如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这

8、是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如果没有线性化的结构逻辑上是不可计算的。树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的