第2章数据结构的基本概念

下一页,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,*,页,上一页,停止放映,第,2,章,数据结构的基础,计算机软件技术基础,Fundamentals of Computer software,什么是数据结构？,数据结构是计算机的专业技术基础课。它研究的主要问题：,分析数据（加工对象）的特征,选择逻辑存储结构和物理存储结构,在存储结构基础上实现对数据的操作,2,第,2,章 数据结构的基础,教学目标：,了解数据结构的有关概念,什么是线性,DS,、,线性表,了解线性,DS,的特点,了解线性,DS,的逻辑结构、物理结构以及操作,3,学习要求,通过本单元的学习，了解并掌握：,有关,数据结构（,DS,）,的基本概念,数据元素、,DS,、,逻辑结构,、,物理结构,、,DS,的分类及特点等,线性,DS,的常用存储结构,顺序、链表、索引、散列存储结构,单向、双向、循环链表等,4,数据结构问题的由来,计算机求解问题的过程步骤：,分析抽象,模型求解,命令,编程,调试程序,编制,程序,运行,程序,求解,结果,结果输出,用户,需求,数据类型、格式、,逻辑结构,数据,逻辑,运算,数据的物理,操作,实际问题,问题,模型,求解算法,5,问题模型,结构分析,线性方程组,人口预报,微分方程,优化问题,线性规划、非线性规划,震动问题,矩阵分析；特征值、特征向量,信息管理,二维数据表,下棋,人工智能,(,树型结构,),交通管理,最佳道路选择,(,图型结构,),6,下棋问题,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,7,一、什么是数据结构,数据,能存于计算机、并被计算机处理的符号的集合。它是客观事物的符号表示。,数据元素,是数据的基本单位、数据集合中的个体。,数据项：,称数据的最小单位为数据项，又称数据域。,8,、基本概念,数据对象：,指具有相同性质的数据元素的集合，是数据的一个子集,数据处理：,指对数据集合中的各元素，以各种方式进行处理，包括对数据的插入、删除、查找、更新、排序等基本运算，也包括对数据元素进行分析。,9,、数据结构,数据结构（,Data Structure,）,是带有结构特征的数据元素的集合,三要素：,DS=,数据的逻辑结构,+,存储结构,+,数据的运算,数据结构是以数据为加工对象，研究数据组织方式和相关操作方法的学问。,按某种逻辑关系组织起来的一批数据，按一定的存储方式把它存储在计算机存储器中，并在这些数据上定义了一个运算的集合，叫做一个数据结构,(Data Structures),。,10,数据结构分类,线性表,堆栈,队列,串,数组,树,二叉树,图,线性结构,非线性结构,数据结构,DS,11,.,数据的逻辑结构,它是描述数据间的顺序（逻辑）关系，只是抽象地反映数据元素的结构，而不管它们在计算机中如何存放。一般用下列二元组来描述：,DS=,（,D,，,R,）,其中：,D,：,是数据元素的有限集合；,R,：,是数据元素之间关系的集合。,与数据在计算机中的存放的,物理位置无关,12,举例,课题组由,1,名教师、,13,名研究生、,16,名本科生组成；成员关系是：教师指导研究生、研究生指导,12,名本科生。,定义,DS,如下：,Group=,（,D,，,R,）,其中：,D=T,，,G1,，,Gn,S11,Snm,1,n,3,1,m,2,R=R1,R2,R1=|1,i,n,1,n,3,R2=|1,i,n,1,j,m,1,n,3,1,m,2,13,.,数据的存储结构,又称物理结构,是指数据结构在计算机中的表示,(,又称映象,),即数据在计算机中的存放。,数据库中的数据存放在计算机中的物理位置,14,逻辑结构和物理结构的关系,数据的,逻辑结构,是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。,数据的,存储结构,是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。,任何一个,算法的设计,取决于选定的逻辑结构；而,算法的最终实现,依赖于采用的存储结构。,15,数据存储结构分类,顺序存储结构,链式存储结构,索引存储结构,散列存储结构,16,顺序存储结构,把数据元素按某种顺序存放在一块连续的存储单元中的存储形式。数据结点结构,:,d,1,d,2,d,n,数据域,特点,:,连续存放,;,逻辑上相邻,物理上也相邻。,结构简单，易实现。,插入、删除操作不便（需大量移动元素）。,17,链式存储结构,以链表形式将数据元素存放于任意存储单元中，可连续存放，也可以不连续存放，以指针实现链表间的联系。数据结点结构,:,d,1,.,d,2,d,n,数据域 指针域,特点,:,非连续存放,借助指针来表示元素间的关系,;,插入、删除操作简单，只要修改指针即可；,结构较复杂，需要额外存储空间。,18,索引存储结构,数据按索引形式存放。存储时分为：数据项和索引号；通过索引表记录逻辑号（记录号）和物理号（存储序号）之间的对应关系。数据结点结构,:,序 号：,1 2 3 4 5 6 7,数据项：,索引号：,12 21 35 2 45 5 10,4 3 2 7 1 6 5,数据域 索引顺序号,特点：,非连续存放；,检索速度快；,增、删操作简单。,19,散列存储结构,在数据元素与存储位置之间建立一种存储关系,F,，,根据这种关系,F,，,已知元素,E,，,就可以得到它的存储地址，即,D=F,（,E,）。,哈希查找中的哈希表就是这样一种存储结构。,特点：,数据元素间无内在联系；,存储形式不定。,20,.,数据运算,数据运算是指对存放在物理结构上的数据,按定义的逻辑结构进行的各种操作。,常见操作有：,输入、检索、插入、删除、修改、排序等。,21,二、数据结构的图形表示,一个数据结构，除了用二元关系表示外，还可以直观地用图形表示。在数据结构的图形表示中，对于数据集合,D,中的每一个数据元素用中间标有元素值的方框或圆表示，一般称之为数据结点，简称为结点；为了进一步表示，各数据元素之间的前后件关系，对于关系,R,中的每一个二元组，用一条有向线段从前件结点指向后件结点。,22,举例,春,夏,秋,冬,图,2-1,一年四季的数据结构图,父亲,儿子,女儿,图,2-2,家庭成员间辈分关系的数据结构图,23,三、线性结构与非线性结构,如果在一个数据结构中一个数据元素都没有，则称该数据结构为空的数据结构。在一个空的数据结构中插入一个新的元素就变为非空。,根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为线性结构与非线性结构两大类型。,24,线性结构,如果一个非空的数据结构满足三个条件：,有且只有一个根结点；,每一个结点最多有一个前件，也最多有一个后件；,插入或删除任一个结点后，前两个条件仍成立。,则称该数据结构为线性结构。线性结构又称线性表。例如，一年四季这个数据结构，就属于线性结构。,25,非线性结构,如果一个数据结构不是线性结构，则称之为非线性结构。非线性结构有树和图两种基本类型。例如，反映家庭成员之间辈分关系的数据结构就属于非线性结构中的树类型。,26,