[理学]第01讲绪论.ppt

数据结构,2/41,课程重要性：,编程基础,考研课程 计算机等级考试课程 软件水平考试高级程序员考试课程,Niklaus Wirth Algorithm + Data Structures = Programs,程序设计: 算 法: 数据结构:,为计算机处理问题编制一组指令集,处理问题的策略,问题的数学模型,3/41,Essential of Lecture One ：,一、引言 二、数据结构基本概念 三、数据结构研究的三个方向 四、抽象数据类型 五、算法分析,第一讲 绪论,难点,重点,4/41,例1：书目自动检索系统,书目文件,一、引言,5/41,例2：人机对弈问题,6/41,/ (root),bin,lib,user,etc,math,ds,sw,yin,tao,xie,Stack.cpp,Queue.cpp,Tree.cpp,Unix文件系统的系统结构图,7/41,例3：多叉路口交通灯的管理问题,8/41,求解非数值计算的问题,综合以上例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。 主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？ 因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。,9/41,数据结构课程的形成和发展,形成阶段：60年代初期，“数据结构”有关的内容散见于操作系统、编译原理和表处理语言等课程。1968年，“数据结构”被列入美国一些大学计算机科学系的教学计划。 发展阶段：数据结构的概念不断扩充，包括了网络、集合代数论、关系等“离散数学结构”的内容。70年代后期，我国高校陆续开设该课程。,10/41,数据结构课程所处的地位,数据结构,P29,11/41,二、数据结构基本概念,1、数据 Data,数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据,12/41,二、数据结构基本概念,2、数据元素 Data Element,数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。 有时一个数据元素可以由若干数据项(Data Item)组成。数据元素又称为元素、结点、记录。,13/41,二、数据结构基本概念,3、数据结构 Data Structure,定义: 由某一数据元素的集合及该集合中所有数据元素之间的关系组成。 记为： Data_Structure = D, R 其中，D 是某一数据元素的集合，R 是该集合中所有数据元素之间的关系组成的有限集合。,14/41,三、数据结构研究的三个方向,近期目标,15/41,数据的逻辑结构,数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关 数据的逻辑结构可以看作是从具体问题抽象出来的数据模型,16/41,例：集合结构,一种数据结构 set =（D，R） D = 01,02,03,04,05,06,07,08,09,10, R = 数据元素之间的联系：0:0,17/41,一种数据结构 linearity =（D，R） D = 01,02,03,04,05,06,07,08,09,10, R = , , 数据元素之间的联系： 1:1,例：线性结构,18/41,例：树结构,一种数据结构 tree =（D，R） D = 01,02,03,04,05,06,07,08,09,10, R = , , 数据元素之间的联系： 1:N,树结构示意图,19/41,例：图结构,一种数据结构 graphics =（D，R） D = 01,02,03,04,05,06,07,08,09,10, R = , , , 数据元素之间的联系： M:N,20/41,例：图结构,R = , , ,21/41,数据的存储结构,数据的存储结构（又叫物理结构）是逻辑结构用计算机语言的实现 数据的存储结构依赖于计算机语言 顺序存储表示 链接存储表示,22/41,顺序存储借助元素在存储器中的相对位置来 表示数据元素间的逻辑关系 链式存储借助指示元素存储地址的指针表示 数据元素间的逻辑关系,Ha,a,b,c,d,对比：,c0,c3,c2,c1,c4,c7,c6,c5,c9,c8,23/41,实战:,1、单选 数据的逻辑结构是 关系的整体。 A数据元素之间 B数据项之间 C数据类型之间 D存储结构之间,2、多选 以下属于数据的存储结构的是 。 A二叉树 B索引 C散列 D线性表,a c bc,以下属于逻辑结构的是（ ）。【西安电子 2001】 A顺序表 B 哈希表 C有序表 D 单链表,24/41,四、抽象数据类型,定义：一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称 如C+语言中有如下数据类型 char int float double void 字符型 整型 浮点型 双精度型 无值,数据类型,构造数据类型由不同成分构成 基本数据类型可以看作是计算机中已实现的数据结构,25/41,四、抽象数据类型,由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括含一组相关的服务（或称操作） ADT * 数据对象：D 数据关系：R 基本操作：P ,ADTs: Abstract Data Types,P5,26/41,ADT的两个重要特征,数据抽象,用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）,数据封装,将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节,抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现,27/41,五、算法分析 (Algorithm),算法解决某一特定问题的具体步骤的描述，是指令的有限序列。 算法特性 1、正确性 2、具体性 3、确定性 4、有限性 5、可读性 6、健壮性,28/41,算法的描述方法 用自然语言描述算法 用流程图描述算法 用数学语言或约定的符合语言描述算法 用C+的函数形式来描述算法,思考：算法与程序有何区别？,29/41,算法着重体现思路和方法，程序着重体现计算机的实现 程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，算法中的指令无此限制 一个算法若用计算机语言来书写，它就可以是一个程序,算法和程序的关系,30/41,算法评价标准,时间复杂度 T(n) 空间复杂度 S(n),一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。,31/41,假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：,T (n) = O(f(n),称T (n) 为算法的(渐近)时间复杂度。,时间复杂度,32/41,、x+;s=0; 基本操作是加法及赋值 T(n)=O(2)=O(1) 、for (i=1;i=n;i+) x+;s+=x; 问题规模为n，基本操作是加法及赋值 操作次数为f(n)=n+n T(n)=O(f(n)=O(n+n)=O(2n)=O(n),基本操作执行次数通常是问题规模n的某个函数f(n)。,33/41,、for( i=1;i=n;i+) for (j=1;j=n; j+) x+; s+=x; 2n2 问题规模为n，基本操作是加法及赋值 操作次数为f(n)=n*n+n*n T(n)=O(f(n)=O(2n2)=O(n2),34/41,for(i=1;i=n;i+) for(j=1;j=n;j+) cij=0; for(k=1;k=n;k+) cij=cij+aik*bkj; ,例1：N*N 矩阵相乘,35/41,for (i=1;in;i+) y=y+1; for (j=0; j=(2*n); j+) x+; ,例2：,/* 1 * /,/* 2 * /,语句1的执行次数是：n-1 语句2的执行次数是：,36/41,/* 1 * /,/* 2 * /,语句1的次数是：1 设语句2的次数是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为：O(log2n),例3:,i=1; while (i=n) i=i*2;,37/41,实战:,3、多选 以下是各算法所有语句频度之和的表达式，其中时间复杂度相同的是 。 A T(n)=2n3+3n2+1000 B T(n)=n3-n2log2n-1000 C T(n)=n2log2n+n2 D T(n)=n2+1000,ab,38/41,4、填空 给出以下算法的时间复杂度 。 x=n; y=0; while(x=(y+1)*(y+1) y+;,常见的时间复杂度数量级: (1)(log2n)(n)(nlog2n)(n2)(n3)(2n) O(n!)O(nn),实战:,39/41,本讲小结,重点： 数据结构的基本概念； 存储结构的理解 难点: 算法分析。,Homework：P3233 习题 查询一篇有关数据结构的研