数据结构 基本概念课件.ppt

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

1、第一章基本概念什么是数据结构数据结构的抽象层次算法定义性能分析与度量“学生”表格初等项：如学生性别、籍贯等，不能再分割的最小数据单位。组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。选课关系包含如下信息学号课程编号成绩学生选课系统中实体构成的网状关系UNIX文件系统的系统结构图在应用程序中涉及到各种各样的数据，为了存储它们，组织它们，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，并依此实现要求的软件功能。数据：信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据如整数、实数、双精

2、度数等主要用于工程和科学计算，及商业事务处理中使用。非数值性数据如字符串、多媒体信息（文字、图形、语音）等。数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}英文字母数据对象LETTER={‘A’,‘B’,…,‘Z’}学生数据对象什么是数据结构？定义:一组数据对象及数据对象之间的关系组成。记为：Data_Structure={D,R}其中，D是数据对象的有限集合，R是该集合中所有数据对象之间的关系的有限集合。n个网站之间的连通关系以最小代价将n个网站连通树形关系任一网站出现故障而整个网络畅通网状关系数据结构的分类

3、根据数据对象之间的关系不同，分为两大类：线性结构非线性结构线性结构中各个数据对象依次排列在一个线性序列中；非线性结构中各个数据对象不再保持在一个线性序列中，每个数据对象可能与零个或多个其它数据对象有某种特定的联系。根据考虑问题的角度不同，分为两大类：逻辑结构物理结构逻辑结构是指从解决问题出发，为实现必要的功能所建立的数据结构，属于用户视图，面向问题，根据问题所要实现的功能建立；物理结构是指数据应该如何在计算机中存放，是数据逻辑结构的存储方式，是属于具体实现的视图，面向计算机，根据问题所要求的响应速度、处理时间、修改时间、存储空间和单位时间的处理量等建立。抽象数据类

4、型数据类型定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.由用户定义，用以表示应用问题的数据模型，由基本的数据类型组成,并包括一组相关的服务（或称操作）特征是使用与实现相分离，实行信息隐蔽和数据封装。在抽象数据类型设计时，把类型的声明与其实现分离开来。抽象数据类型严格区分抽象数据类型的两个不同视图从使用者角度只要了解该抽象数据类型的规格说明，就可以利用其公共界面中的服务来使用这个类型，而不必关心其物理实现，这样使用者可以在开发过程中抓住重点，集中精力考虑如何解决应用问题，使问题得到简化。从实现者角度把抽象数据类型的物理实现封装起来，有利于编码

5、、测试以及将来修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不至于影响其它模块。如果为了提高效率希望改进数据结构，可能需要改变抽象数据类型的物理实现，但只要界面中的服务的使用方式不变，其它所有使用该数据类型的程序都可以不变，从而大大提高系统稳定性。数据结构的抽象层次最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关联在一起，代表数据结构，并给出数据结构都具有的操作——初始化(initial)、插入(insert)、删除(delete)和查找(search)。线性聚类——线性表类中所有数据成员都按某种次序排列在一个序列中。根据对聚集中元素存取方法的不

6、同：直接存取类数组、记录、文件直接存取某一指定项而不须先访问其前驱。顺序存取类栈、队列、表只能从序列中第一个元素起，按序逐个访问到指定的元素。广义索引类散列表、词典“关键码——值”偶对的集合。非线性聚类所有数据元素与其它数据元素之间不存在简单的线性关系。根据关系的不同：层次聚集类树，二叉树，堆按层次划分的数据元素的集合，指定层次上元素可以有零个或多个处于下一层次上的直接后继。群聚集类集合，图所有元素之间没有任何顺序关系。线性聚集类中各数据成员之间的线性关系树形结构树二叉树二叉搜索树堆结构“最大”堆“最小”堆群聚类图结构网络结构算法定义定义：一个有穷的指令集，这些指

7、令为解决某一特定任务规定了一个运算序列。特性：输入必须有0个或多个输入，是算法开始运算前给于算法的量。输出应有一个或多个输出(处理结果)，输出的量是算法计算的结果。确定性每步定义都是确切、无歧义的，对于每一种情况，需要执行的动作都应严格地、清晰地规定。有穷性算法应在执行有穷步后结束。有效性每一条运算应足够基本，原则上能够精确执行，甚至人们仅用笔和纸做有限次运算就能完成。事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最小数据算法框架：for(inti=0;i

8、i]与a[