计算机软件基础课件-数据结构概述

数据结构概述BasicsofComputerSoftware答辩人：XXX基本概念

逻辑结构物理结构数据操作目录数据结构的基本概念1数据的逻辑结构2数据的物理结构3数据操作41.无序表和有序表的查找有序表的查找无序表的查找基本概念

逻辑结构物理结构数据操作问题引入结论01数据的组织结构和算法是密切相关的2.学生成绩表成绩表我们可以采用链表，数组，树形结构，甚至可以用图型结构进行表示和存储，但相应的各种操作算法也不同基本概念

逻辑结构物理结构数据操作问题引入结论：数据结构和算法是相互依赖的关系：基本概念

逻辑结构物理结构数据操作问题引入02算法要作用在特定的数据结构之上算法要结合数据存储的特点，用最优的策略来分析并处理数据。01数据结构是为算法服务的数据结构要配合算法选择最优的存储结构来存储数据。队列可以用线性链表描述家谱可以用树描述交通网可以用图或者网络来描述基本概念

逻辑结构物理结构数据操作什么是数据结构基本概念

逻辑结构物理结构数据操作什么是数据结构描述这类非数值计算问题的数学模型不是数学方程,而是树、表和图之类的数据结构数据结构是一门研究数据组织、存储和运算的一般方法的学科因此从广义上讲，数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示和实现学习数据结构知识有助于编制高质量的计算机应用程序数据结构（DataStructure）形式定义：数学上的抽象的定义

某一数据对象的所有数据成员之间的关系。记为：

Data_Structure={D,S}其中，D是某一数据对象S是该对象中所有数据成员之间的关系的有限集合如：线性表（2，5，7，9）中可以写成：D={2，5，7，9}S={(2,5),(5,7),(7,9)}基本概念

逻辑结构物理结构数据操作什么是数据结构数据(Data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据非数值性数据基本概念

逻辑结构物理结构数据操作基本概念和术语数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据元素又称为元素、结点、记录一个数据元素往往可以由若干数据项(DataItem)组成。数据项是具有独立含义的最小标识单位。数据元素（DataElement）基本概念

逻辑结构物理结构数据操作基本概念和术语数据项(DataItem)

姓名部门名称出生日期入职时间职位业绩年月日基本概念

逻辑结构物理结构数据操作基本概念和术语数据对象(dataobject)具有相同性质的数据元素的集合。整数数据对象N={0,1,2,…}字母字符数据对象

C={‘A’,‘B’,‘C’,…‘F’}基本概念

逻辑结构物理结构数据操作基本概念和术语从逻辑关系上描述数据，与数据的存储方式无关从具体问题抽象出来的数据模型与数据元素本身的形式、内容无关与数据元素的相对位置无关基本概念逻辑结构物理结构数据操作数据的逻辑结构四个基本结构树形结构（一对多）线性结构（一对一）集合（松散结构）图形结构（多对多）基本概念逻辑结构物理结构数据操作数据的逻辑结构基本概念逻辑结构物理结构数据操作数据的逻辑结构02非线性结构树和图（网络）01线性结构逻辑结构的分类bindevetclibuser线性结构基本概念逻辑结构物理结构数据操作数据的逻辑结构102114131211234678955一般的树987456231二叉树3158710119613二叉排序树堆结构123548711102916非线性结构：树型结构基本概念逻辑结构物理结构数据操作数据的逻辑结构125643125436113318146651921图结构网络结构ABECF非线性结构：图型结构基本概念逻辑结构物理结构数据操作数据的逻辑结构数据的存储结构：又称物理结构，指数据结构在计算机中的表示，依赖于计算机语言基本概念逻辑结构物理结构数据操作数据的物理结构增加一个或多个指针，用于存放和该数据元素有关的另一个数据元素的地址，可以不占用连续地址空间。链接存储表示是一种在数据元素的关键码与存储位置之间建立确定对应关系的查找技术。散列存储表示将逻辑上相邻的数据元素存放在内存中的相邻位置中顺序存储表示指除建立存储结点信息外，还建立附加的索引表来标识结点的地址索引存储表示基本概念逻辑结构物理结构数据操作数据的操作构造一个空结构初始化在数据结构中插入一个新元素插入在数据结构中删除满足指定要求的元素删除在数据结构中修改原有的数据元素修改在数据结构中查找指定要求的元素查找将数据按某一关键字排序排序数据操作数据结构的研究内容基本概念逻辑结构物理结构数据操作本章小结数据的逻辑结构数据的存储结构数据的运算1数据的逻辑结构按照某种逻辑关系将数据组织好，即逻辑结构2数据的存储结构将数据及数据之间的关系存储到存储区域中，即存储结构3数据的运算在这些数据上定义一个基本运算的集合反映数据元素之间的逻辑关系1.数据的逻辑结构2.数据的存储结构A.线性结构B.非线性结构A