资源描述：
《基本数据结构与运算-1线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章 基本数据结构及运算3.1概述3.2线性表3.3栈3.4队列3.5数组3.6树与二叉树3.7图第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。能输入到计算机中并能被计算机程序处理的符号的集合。整数(1,2)、实数(1.1,1.2)字符串(Beijing)、图形、声音。第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。计算机管理图书问题在图书馆里有各种卡片：有按书名编
2、排的、有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。最简单的办法之一是建立一张表，每一本书的信息在表中占一行，如第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。如何将0,1,2,3,4,5,6,7,8,9这10个数存放在计算机中能最快地达到你所需要的目的？目的不同，最佳的存储方方法就不同。从大到小排列：9,8,7,6,5,4,3,2,1,0输出偶数：0,2,4
3、,6,8,1,3,5,7,9数据元素在计算机中的表示第三章 基本数据结构及运算3.1概述数据结构是一门研究数据组织、存储和运算的一般方法的学科。对数据结构中的节点进行操作处理(插入、删除、修改、查找、排序)数据：计算机处理的对象数据元素(DataElement)：数据的基本单位一个数据元素可由若干数据项(DataItem)组成。数据项：数据的最小单位。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素亦称结点或记录数据项
4、亦称字段或域数据结构可描述为Group=（D，R）有限个数据元素的集合有限个结点间关系的集合数据元素间的关系：前后件关系1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队列树形结构图形结构数据结构的三个方面数据结构可描述为Group=（D，R）数组A.线性结构（一对一）特性：1.有且只有一个根结点2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它有且仅有一个前驱和一个后继。）例：（A,B,C,·······，X,Y,Z）例：
5、学生成绩表86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号1．数据的逻辑结构DS1=（D1，R1）集合表示法D1={k1，k2，k3，k4}R1={（k1，k2），（k2，k3），（k3，k4）}DS2=(D2,R2)D2={k1,k2,k3}R2={(k1,k2),(k1,k3)}k1k2k3k4k1k2k3例：例：1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为Gro
6、up=（D，R）数组B．非线性结构:树形结构（一对多）全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构识别“体”字的过程按分支和层次组织的数据，称为：“树形结构”ABCDEFGH树形结构——结点间具有分层次的连接关系HBCDEFGA1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)数组1423D={1,2,3,4}R={(1,2),(1,3),(1,4),(2,3)(3,4),(2,4)}213
7、D={1,2,3}R={(1,2),(2,3),(3,2),(1,3)}B．非线性结构:图形结构（多对多）1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)数组元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*mA.顺序存储每个元素所占用的存储单元个数2、数据的存储结构元素n……..元素i……..元素2元素1存储内容顺序
8、存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。顺序存储结构的三个弱点：1.插入或删除操作时，需移动大量
