数据结构概述课件.ppt

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

1、主要内容数据结构讨论的范畴基本概念抽象数据类型算法的特性、分类及度量数据结构的选择和评价数据结构讨论的范畴程序=数据结构+算法数据结构：问题的数据模型数据的逻辑结构数据的物理结构数据的运算算法：求解问题的策略查找排序数据结构讨论的范畴数值计算的程序设计问题圆的面积（函数）结构静力分析计算（线性代数方程组）人口增长预报（微分方程）数据结构讨论的范畴非数值计算问题的程序设计问题学生信息管理系统（表）算法：需要检索的项目如何检索、用户界面模型：各种表格人机对弈（树）算法：对弈的规则和策略模型：棋盘及棋盘的格局教学计划编排问题（图）算法：课表编排的规则模型

2、：课程以及课程间关系数据结构讨论的范畴数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高数据结构基本概念数据（data)所有能输入到计算机中去的描述客观事物的符号是计算机操作的对象的总称是计算机处理的信息的某种特定的符号表示形式数据元素（dataelement）数据结构中讨论的基本单位，也称

3、结点（node）或记录（record）是数据（集合）中的一个“个体”例如：学生信息检索系统中学生信息表中的一个记录、对弈问题中状态树的一个状态、排课问题中的一个顶点等，都被称为一个数据元素数据结构基本概念数据项（dataitem）有独立含义的数据最小单位，也称域(field)数据元素可以是数据项的集合数据对象是性质相同的数据元素的集合，是数据的一个子集。数据元素是数据对象的一个实例例如整数数据对象是集合N={…-2,-1,0,1,2…..}数据结构基本概念数据结构（datastructure)数据结构是相互之间存在着某种逻辑关系的数据元素的集合例如

4、：在一维数组{a1,a2,a3,a4,a5,a6}的数据元素之间存在如下的次序关系{

5、i=1,2,3,4,5}什么是数据结构？数据结构的三个方面数据的逻辑结构从具体问题抽象出来的数学模型，它与数据的存储无关线性结构：线性表、栈、队列非线性结构：树、图数据的存储结构数据结构在计算机中的标识（又称映像）称为数据的物理结构，数据的逻辑结构在计算机存储器中的实现顺序存储链式存储数据的运算检索、排序、插入、删除、修改等什么是数据结构？(1)数据的逻辑结构数据的逻辑结构可以用一组数据（表示为结点集合D），以及这些数据之间的一组二元关系（关系集

6、合S）来表示：(D，S)其中D是数据元素的有限集，是由有限个结点组成的集合，每一个结点都代表一个数据或一组有明确结构的数据S是D上关系的有限集，是定义在集合D上的一组关系，用它描述结点数据之间的逻辑关系Data_Structures=(D,S)什么是数据结构？(2)数据的逻辑结构结点的数据类型高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中基本数据类型：int,char,float,double等构造数据类型：数组、结构体、共用体、枚举指针、空(void)类型用户也可用typedef自己定义数据类型结点的类型可以是基本数据类型，也可以根

7、据应用的需要来灵活定义typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu,*pstu;什么是数据结构？(3)数据的逻辑结构关系S阐明数据结构的特性线性结构（linearstructure）一个对一个树型结构（treestructure）一个对多个图状结构（graphstructure）多个对多个什么是数据结构？(4)数据的逻辑结构线性结构关系S是一种线性关系，或称为‘前后关系’，有时也称为‘大小关系’。关系S是有向的，且满足全序性和单索性等约束条件全序性线性结构的全部结点

8、两两皆可以比较前后（关系S）单索性每一个结点a都存在唯一的一个直接后继结点b什么是数据结构？(5)数据的逻辑结构树型结构树型结构又称为层次结构，其关系S称为层次关系树型结构的最高层次的结点称为根（root）结点只有它没有父结点每一个结点可以有多于一个的‘子结点’，但是它只能有唯一的‘父结点’图状结构也称为结点互联的网络结构，允许结点具有多个‘父结点’图结构的关系S没有任何约束，无法利用关系S的约束来设计图结构的存储结构因特网的web网页链接关系是一个非常复杂的图结构什么是数据结构？(6)数据的逻辑结构三种结构的区别树结构和图结构的基本区别就是“每个

9、结点是否仅仅从属一个父结点”线性结构和树结构的基本区别是“每个结点是否仅仅有一个直接后继”什么是数据结构？(7)数据的存储