计算机考研基础讲义数据结构基础.pptx

第一章绪论什么是数据结构直观定义:数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中,并在这些数据上定义一个运算集合,这就是数据结构。学****数据结构的重要性“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计(特别是非数值性程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。§、基本概念数据:能输入计算机且被能计算机处理的一切对象。数据元素:对现实世界中某独立个体的数据描述。数据项:具有独立意义的最小数据单位。数据类型:每个数据项必须属于某确定的数据类型。基础§、基本概念数据对象:具有相同特征的数据元素的集合。关系:在数据对象中各数据元素之间存在着某种关系(或联系)。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域,通常把数据之间这种固有的关系简单的用前驱和后继关系描述。§、数据的逻辑结构设D表示数据元素的集合,R表示D上的关系的集合,则一个数据结构B可表示为:B=(D,R)由此可见数据结构由两部分构成(1)表示各元素的信息D(2)表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素,则二元组<a,b>表示a是b的前驱,b是a的后继。§、数据结构的分类线性结构:除了一个根结点外,其他各结点有唯一的前驱;除了一个终端结点外,其他各结点有唯一的后继。树状结构:除了一个根结点外,各结点有唯一的前驱;所有的结点都可以有多个后继。网状结构:各结点可以有多个前驱或多个后继。§。数据结构包括结点的值及结点之间的关系,其存储结构除了必须存储结点的值外,还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式:1、顺序方式顺序结构最适合于线性结构,它把逻辑上相邻的结点存放到物理上相邻的存储单元中,顺序存储结构只存储结点的值,不存储结点的关系,结点的关系通过存储单元相邻关系隐含表示出来。§、链接方式链接存储方式不仅存储结点的值,而且还存储结点之间的关系。它利用结点附加的指针字段,存储其后继结点的地址。3、索引方式在线性结构中,各结点可以依前驱、后继关系排成一个序列(a1,a2,a3,……an)。每个结点ai在序列中都对应一个序号i序号i也称为结点ai的索引号。索引存储就是通过建立一个附加的索引表,然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。§、散列方式利用该结点的值确定该结点的存储单元地址。§、数据运算按一定的逻辑结构把数据组织起来,采用适当的存储方式把数据结构存储到计算机中,最终的目的是为了有效地处理数据,提高数据的运算效率。1)插入:往数据结构中添加新的结点称为插入。2)删除:把指定的结点从数据结构中删除。3)更新:改变指定结点的值或者改变某些结点的关系称为更新。4)查找:在数据结构中查找某些满足条件的结点。5)排序:对线性表的各结点,按指定数据项的值从小到大或从大到小的重新排列。排序运算实际上是破坏线性表的旧关系,重新建立线性表的新关系。