数据结构基本概念.pptxVIP

软件技术基础,数据结构的基本概念,制作 主讲,段景山,第一篇 数据结构 第一章 数据结构的基本概念,数据结构 数据的逻辑结构 数据的存储结构 算法,数据结构,1 数据结构的概念 1.1 数据及数据元素的概念 数据是客观事物在计算机内的抽象描述 数据指一些事实，或一些数，或一些符号集合 组成数据的“事实”、“数值”或“符号”称为数据元素 数据元素可由若干个数据项组成 数据项可以认为是数据元素的一个属性。 一个复合的元素具有多个属性数据项,3,数据、数据元素及数据项,例1、学生花名册,数据元素,数据,学生名字的集合,每个学生的名字,例2、学生成绩表,数据,数据元素,数据项,学生成绩的集合,每个学生的成绩,名字,成绩,4,数据结构的概念,1.2、数据结构 数据结构讨论计算机系统中数据的组织形式及其相互关系 是相互之间存在一种和多种特定关系的数据元素的集合,例：大楼中的电梯,电梯在楼层中只能逐层移动,例：公司的组织关系,楼层间的关系是线性的,员工间形成树型关系,涉及,元素的集合,元素间的关系,在关系里的操作,电梯的运动,人员的管理,5,关于对数据结构的理解,对数据结构的理解可大致分为三种角度 数理角度：强调数据元素间的逻辑关系 计算机角度：强调逻辑关系、存储关系和算法的结合本教材的主流角度 与数理角度相比，是将元素间的关系归结为两种关系，结合算法的需要进行抽象 建模的角度：强调为解决实际问题而进行抽象，为建立科学、规范的模型而进行灵活调整本课程推动的思维角度,6,例：用数据结构描述整数I*数理角度的典例,1、组成整数数据的全部元素的集合I I 0，1，2，3,2、I中元素的关系集合RE,3、I*的运算集合P，比如算术四则运算,4、P中诸运算的运算规则RU， 如乘、除法优先于加、减法等,I* I，RE，P，RU,数据结构的概念数理角度,RE -10,01,12,元素间的关系不止一种,7,数据结构的概念建模角度,例：用数据结构的思想分析以下问题，建模角度 一个十字路口的红绿灯管制 四皇后问题：在一个44的棋盘上放置4个皇后，互相不会相杀，该怎么放？ 过河问题：现有一条河，共有八个人要过河，分别是爸爸，妈妈，两个儿子，两个女儿，一个警察，一个犯人。现有一条木伐，一次最多载两个人，在这八人中，有爸妈警察会开船，即这个船上必须有爸妈，警察三个中的一个，船才会开动。船过去无法自动回来。并且要避免以下三件事发生，1警察不在犯人会伤害一家六口。2爸爸不在，妈妈会伤害儿子。3妈妈不在，爸爸会伤害女儿。,元素 关系 运算,8,数据结构的概念计算机角度,元素集合,元素间的关系,运算,计 算 机 系 统,元素在计算机系统里的表示 字符？字串？整数？ 元素间的逻辑关系逻辑结构 元素在计算机系统中的存储方式， 物理空间关系存储结构 操作指令的集合 算法,9,数据的逻辑结构与数据的存储结构,例：班级里的同学,可能有各种各样的逻辑关系。比如班长、班委、组长、群众等。形成相应的逻辑结构。,上课时，大家的座次形成存储结构,座次（存储结构）可能与逻辑关系有关，也可能无关。,数据结构的概念两种关系,为什么要这样抽象出两种关系？,设想一个发作业的场景,结论：两种关系的抽象是为了能够完成操作，解决在集合中 “找谁来完成”？ “如何找到它”？,10,小结数据结构的三个层次 数据结构包括数据的逻辑结构，数据在计算机系统中的存储结构和数据操作的集合 把数据以一定的逻辑结构组织起来，以适当的方式存储在计算机系统的存储器里，其最终目的是为了有效处理数据，提高数据处理运算速度。,逻辑结构,存储结构,算法,数据结构的概念,要素,目标,三个要素都与我们所要实现的目标相关,有效处理数据,提高数据处理运算速度,11,数据结构的概念,三位一体，提前感受 逻辑结构不同，物理结构相似，算法相似 顺序表和顺序存储的二叉树 逻辑结构相同，物理结构不同，算法相似 顺序表和链表 逻辑结构相同，物理结构相同，算法不同 队列和栈,12,深入思考,研究数据结构的作用 看以下几段话，谈谈感受 小李是经理 小李提升为经理 小李从职员提升为经理 小李从职员越过课长直接提升为经理，这不合常规 小李从1000多个职员中越过课长直接提升为经理，这是很不合常规的 哪句话包含的信息多，多了什么样的信息 结合这个例子，思考研究目的、重点、基础,13,课堂活动,拿出纸笔，开始行动 咨讯：是否了解本次行动的目标和内容 计划：24人自由组合为一组 决策：选取主题，或自拟题目 实施：按数据结构中的“元素的集合”、“元素的关系”、“运算”来描述主题，至少三句话 评价：相互评价描述内容是否适当。,14,数据结构的概念,例：对下列（或自拟）系统，利用数据结构的思想来进行抽象和描述 一个十字路口的红绿灯管制 一个五叉路口的红绿灯管制 包含两部电梯的管理系统 包含三部电梯的管理系统 一条公交路线 书 图书馆 ,元素 关系 运算,15,课堂活动评价,主题选择是否适当 元素抽象是否适当 逻辑结构（关系）与物理结构之间是否有区分度 算法是否适当，与两个结构之间的描述是否有区分度 汇报讲解是否清楚,16,2、数据的逻辑结构 数据元素之间关系的描述 2.1、描述法 二元组 关系：一般抽象为前驱与后继关系， 即表明结构中，一个元素的前一个元素是谁，它的后一个元素又是谁,B （ K， R ）,K：元素集合,R：元素间关系的集合,数据的逻辑结构,17,2.2、图示法 图形要素： 结点和有向线段 结点：表示一个数据元素，一般以方形框代表 不管多么复杂的结点，都看作是一个结点 有向线段：表示元素之间的关系。 箭尾指向的结点是前驱。 箭头指向的结点是后继,Ki,Kh,Kj,Ki的前驱,Ki的后继,数据的逻辑结构,18,3、数据的存储结构（物理结构） 是数据元素在计算机系统存储器中的存放方式 也可以说，是数据逻辑结构在存储器中的存放方式 或者：元素及其逻辑关系在存储器内的表示 ,数据的存储结构,存储器的特点：由地址连续的单元构成,19,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K1,K2,K3,K4,数据的存储结构,逻辑结构,物理结构,20,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,数据的存储结构,逻辑结构,物理结构,21,数据的存储结构,思考：为什么数据逻辑结构与物理结构没有完全统一？,存储器的特点：由地址连续的单元构成。线性关系,存储单元间位置上的线性关系有时不能 直接反映复杂的逻辑关系,22,建立理解模型图书馆,为后续课程内容的理解，我们先观察一个现实生活中的实例一个不那么现代的图书馆（书店）。 图书馆存放了大量的书，都放在书架上,23,图书馆,为便于在海量的图书中寻找到需要的书籍，图书馆往往提供一种索引卡片来帮助找书。 索引卡片上除了记录书的概要信息和分类号码等，还有书籍在书架上的位置，如第几个书架，第几排等。,24,几种物理存储方式 3.1顺序存储方法 连续顺序地存放数据元素 若数据的逻辑结构也是顺序（线性）的，则逻辑结构和物理结构完全统一了 连续存放的数据元素可以在内存中容易找到,数据的存储结构,25,3.2、链接存储方法 元素在内存中不一定连续存放 在元素中附加指针项，通过指针可以找到关系元素,元素指针,结点,元素,指针,数据的存储结构,联想：在一套丛书中每一本书中夹一个卡片，记录下一本书在书架上的位置,26,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K1,K2,K3,K4,链接式存储结构,逻辑结构,物理结构,指向后继结点的指针,27,0300,0310,0320,0330,0340,0350,0370,0380,K1,K2,K3,K4,K5,K6,K1,K2,K3,K4,K5,K6,通过指针，可以方便地找到关系结点,链接式存储结构,逻辑结构,物理结构,28,3.3索引存储方法 为放在内存中的元素建立索引表 元素可以离散存放 通过查索引表找到需要的元素,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,1,2,3,4,索引表,索引号,数据的存储结构,联想：图书馆的查书卡,29,3.4、散列存储方法 结点中设一关键值，利用关键值和相应算式算出结点位置（地址）,例：以用户姓名为关键值,DJS,算式：字母的序号相加,041019 33,ZXM,262413 63,数据的存储结构,所以，DJS放在33号地址单元 ZXM放在63号地址单元,联想：通过书的名字就能确定书的位置,30,小结：数据的逻辑结构与物理结构 1、物理结构是元素在内存中的存储方式，与元素间固有的逻辑关系是相对独立的两个问题 物理结构着眼于结点在内存中的定位 2、简单的逻辑结构可能和物理结构一致 例：线性逻辑关系与顺序存储方法 3、利用物理结构在内存中找到一个结点，而为什么要找这个结点却由元素间的逻辑关系决定 任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构 4、逻辑结构与存储结构是一个问题的两个方面,数据的逻辑结构和存储结构,31,例：一个树形关系结构用索引方式存储,1,2,3,4,5,6,0300,0301,0302,0303,0304,0305,0306,0307,0308,0309,K1,K2,K3,K4,K5,K6,数据的逻辑结构和存储结构,例：一个树形关系结构用链接方式存储,例：一个树形关系结构用顺序方式存储？,32,4、算法 4.1、算法的概念及特点 算法是为解决某一特定类型问题规定的运算规则的有穷集合 有穷性 确定性 有效性 输入 输出,特 点,非无限执行，必须在有限步骤内结束,非二义，下一步必须是明确的,每一步是可执行的,外部输入零个或多个,至少一个,算法,33,4.2、算法与程序 相似：都是解决问题的方法和步骤，是指令的集合 区别： 有穷性 描述方法 联系：程序用某种程序设计语言来实现算法,程序使用程序设计语言,算法可以使用框图及其他语言,算法,类似： while(1) 的语句段，在程序中允许 但在算法中不允许,34,4.3、算法语言 算法应有严格的描述语言（确定性） 一般使用类PASCAL语言 在本课程中使用类C语言，即语言风格类似于C 要求描述一个算法时必须满足： 对输入和输出的描述 描述语句准确、无二义 保证算法的有穷性和有效性,算法,35,算法,算法的写作规范,int seq_search( elemtype s ,keytype k, int n),int low, high, mid;,sn.key = k; i = 0;,while(s i .key != k) i+;,if(i n) return i; else return -1;,36,算法例,37,4.4、在数据结构中常见的问题 创建、插入、删除、更新、检索、排序 注意：每个问题都有一种或多种算法 找到效率最高的 以最容易理解的方式设计 设计的算法不容易出错或出错情况较少,算法,38,算法,4.5、算法的评价 时间复杂度 代码的执行时间，一般是以代码实际执行的指令数量（条） 空间复杂度 代码执行中需要使用内存空间的大小（字节） 变量所占空间变量的数量 代码所在空间代码的静态数量（即不是实际执行的） 例,39,for(i = 0; i 1000; i +) sum = sum + 1; 实际执行了1000条,for(i = 0; i 1000; i +) sumi+1 = sumi + i; 比上一个算法多使用了999个变量,算法评价,时/空复杂度的计算 设算法处理对象有n个，度量结果是随n变化的数量级 = 算法的时/空消耗不随n的变化而变化 算法的时/空消耗随n作线性变化，一般是单重循环 算法的时/空消耗随n做指数平方变化，一般是双重循环,40,算法评价,时间复杂度：O(n) 空间复杂度：O(1) 时间复杂度：O(n) 空间复杂度：O(n),41,for(i = 0; i n; i +) sum = sum + 1; ,for(i = 0; i n; i +) sumi+1 = sumi + i; ,时间复杂度：O(n2) 空间复杂度：O(1) 时间复杂度： log