《数据结构概论》PPT课件.ppt

,第 1 章 数据结构概论,1.1 数据结构的概念 1.2 数据结构的抽象形式 1.3 作为ADT的C+类（自学） 1.4 算法定义 1.5 算法性能分析与度量,本章的基本内容是：,学习要求,理解基本概念并能进行区分比较 理解算法的定义与算法的五个特性 掌握简单的时间复杂度估计和空间复杂度估计方法 掌握用C+语言编写程序的基本技术,1938年出生，25岁毕业于加州理工学院数学系，博士毕业后留校任教，28岁任副教授。30岁时，加盟斯坦福大学计算机系，任教授。从31岁起，开始出版他的历史性经典巨著： The Art of Computer Programming 他计划共写7卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年仅36岁。,数据结构的创始人克努思,1.1 数据结构的概念,1.1.1 数据结构举例,计算机求解问题: 问题抽象出问题的模型求模型的解 问题数值问题、非数值问题 数 值 问 题数学方程 非数值问题数据结构 数据结构是研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。,例1 选课问题表结构,完成什么功能?各表项之间是什么关系？,1.1 数据结构的概念,学生表,课程表,例2 选课问题图结构,如何表示学生选课的情况？,1.1 数据结构的概念,学生 (学号,姓名,性别,籍贯),课程 (课程编号,课程名,学分，课时),选课 (学号,课程号,成绩),“选课单”包含如下信息： 学号 课程编号 成绩 时间,m n,1 1,学生选课系统中实体构成的网状关系,例3 UNIX文件系统的系统结构树结构,各目录之间是什么关系？,1.1 数据结构的概念,1.1 数据结构的概念,数据：信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中并能被计算机程序识别和处理的符号集合。 数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项：构成数据元素的最小单位，分为初等项和组合项两种。 数据结构：由某一数据元素的集合和该集合中数据元素之间的关系组成。,1.1.2 数据与数据结构,数据、数据元素、数据项之间的关系,包含关系：数据是由数据元素组成，数据元素是由数据项组成。 数据元素是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。,1.1 数据结构的概念,依据数据元素之间的关系，数据结构可分为两大类： 线性结构：所有数据元素按某种次序排列在一个序列中。 非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或多个其他数据元素发生联系。又可分为层次结构和群结构。,1.1 数据结构的概念,1.1.3 数据结构的分类,“数据结构”课程是研究系统开发过程中有关设计（包括数据设计、体系结构设计、接口设计和过程设计）的若干基本问题的学科。 选择数据结构的几个步骤： 分析问题，确定算法遇到的资源限制（内外存空间和执行时间） 确定必须支持的基本运算，度量每个运算所受到的资源限制。 选择最接近这些资源开销的数据结构。 数据结构的内容包括3个层次的5个“要素”。,1.1 数据结构的概念,1.1.4 数据结构课程的内容,数据结构的核心技术是分解与抽象。 通过分解得到数据的层次：数据-数据元素-数据项 通过抽象得到数据的逻辑结构 通过分解将处理要求划分成各种功能 通过抽象得到运算的定义 上述两个方面的结合将问题变换为数据结构。,1.1 数据结构的概念,1.1.4 数据结构课程的内容,抽象（逻辑结构）,具体（具体问题）,抽象（逻辑结构）,具体（存储结构和实现运算）,数据的逻辑结构：简称数据结构，指从解决问题的需要出发，为实现必要的功能所建立的数据结构，属于用户的视图，面向问题的。 数据的物理结构：指数据应该如何在计算机中存放，是数据逻辑结构的物理存储方式，属于具体实现的视图，面向计算机的。 数据结构的存储结构可以用以下4种存储方法得到： 顺序存储方法：逻辑关系由存储单元的邻接位置关系来体现。 链接存储方法：逻辑关系由附加的指针指示。 索引存储方法：通过索引项中的地址来指示一个结点或一组相邻结点的物理位置 散列存储方法：根据结点的关键码通过一个函数计算直接得到该结点的存储地址。,1.1 数据结构的概念,1.1.4 数据结构课程的内容,1.2.1 数据类型,数据类型（Data Type）：一组值的集合以及定义于这个值集上的一组操作的总称。 例如：C+中的整型、字符型等基本类型与数组、构造型等构造组合类型。 注意：数据类型的逻辑概念与其在计算机程序中的实现有很重要的区别！,1.2 数据结构的抽象形式,1.2.2 数据抽象与抽象数据类型,1. 抽象（Abstract）:抽出问题本质的特征而忽略非本质的细节。 例：,1.2 数据结构的抽象形式,2. 抽象数据类型（Abstract Data Type，ADT）:一个数据结构以及定义在该结构上的一组操作的总称。,ADT是对数据类型的进一步抽象,ADT的不同视图,1.2 数据结构的抽象形式,ADT 抽象数据类型名 Data 数据元素之间逻辑关系的定义 Operation 操作1 前置条件：执行此操作前数据所必须的状态 输 入：执行此操作所需要的输入 功 能：该操作将完成的功能 输 出：执行该操作后产生的输出 后置条件：执行该操作后数据的状态 操作2 操作n endADT,ADT的定义形式,1.2 数据结构的抽象形式,见P8例,算法的定义,1.算法（Algorithm）:，是对特定问题求解步骤的一种描述，是指令的有限序列。,2. 算法的五大特性： 输入：一个算法有零个或多个输入。 输出：一个算法有一个或多个输出。 有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。,1.4 算法定义,算法的定义,3.算法和程序不同，程序可以不满足有穷性。 4.算法的描述：语言方式、图形方式、表格方式。教材中使用C+语言，有时与自然语言结合来描述算法。,1.4 算法定义,算法的设计,方法：自顶向下、逐步求精的结构化程序设计方法。,1.4 算法定义,例：选择排序：把存放在一个整数数组中的n个乱七八糟的数据按自小到大的顺序排列起来。,选择排序,2,33,45,98,100,100,2,45,33,98,算法思想：从a0到an-1中选择一个最小的，把它交换到a0中；然后从剩下的a1到an-1中选择一个最小的，把它交换到a1中；依次类推直到第n-1个数据交换到an-2中。,1.4 算法定义,算法框架： for(int i=0;in-1;i+) 从ai检查到an-1，寻找最小的整数，其位置记为k； 若ik，则交换ai与ak； ,1.4 算法定义,进一步细化得到下面的算法： void selectSort(int a ,const int n) int temp,i,j,k; for(int i=0;in-1;i+) k=i; for(j=i+1;jn;j+) if(ajak) k=j; if(i!=k) temp=ai; ai =ak;ak=temp; ,1.4 算法定义,1.5.1 算法的性能标准,判断一个算法的优劣，主要有以下几个标准： 正确性：要求算法能够正确地执行预定的功能和性能要求。 可使用性：要求算法能够很方便地使用。 可读性：算法应是可读的。 效率：算法的效率主要指算法执行时计算机资源的消耗，包括存储（空间代价）和运行时间（时间代价）的开销。 健壮性：自动检错、报错并通过与用户对话来纠错的功能。 简单性：指一个算法所采用的数据结构和方法的简单程度。,1.5 算法性能分析与度量,1.5.2 算法的后期测试,度量算法效率的方法： 后期测试：主要通过在算法中的某些部位插装时间函数（如time()来测定算法完成某一规定功能所需的时间。 缺点： 编写程序实现算法将花费较多的时间和精力； 算法的运行时间依赖于所用的计算机系统、编译器、可用存储空间大小等因素。 事前估计：对算法所消耗资源的一种估算方法。,1.5 算法性能分析与度量,见P27例,1.5.3 算法的事前估计,即算法复杂性的度量，可分为空间复杂度度量和时间复杂度度量。 1、空间复杂度度量 1）固定部分：包括存放程序指令代码的空间，常数、简单变量、定长成分变量所占的空间等，属于静态空间。 2）可变部分：包括与问题规模有关的变量所占空间、递归工作栈所用空间，以及在算法运行过程中通过new和delete命令动态使用的空间。,1.5 算法性能分析与度量,算法的时间复杂度分析：主要从程序结构着手，统计算法的程序步数。 程序步：指在语法上或语义上有意义的一段指令序列，而且这段指令序列的执行时间与实例特性无关。 各种语句的程序步数的计算详见书中P29。 确定程序步数的方法： 1、在程序中插入一个计数变量count，见P30-31 2、建立一个表，列出程序内各个语句的程序步数，见P32。,1.5 算法性能分析与度量,1.5.3 算法的事前估计,例 以迭代方式求累加和的函数 float sum ( float a , const int n ) float s = 0.0; count+; /count 统计执行语句条数 for ( int i = 0; i n; i+ ) count+=2; /针对 for 语句 s += ai; count+; /针对 赋值语句 count+=2; /针对 for 语句的最后一次 return s; count+; /针对 return 语句 执行结束得 程序步数 count = 3*n+4,计算程序步数的简化形式 void sum ( float a , int n ) for ( int i = 0; i n; i+ ) count += 3; count += 4; ,注意： 一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。 例如：赋值语句 x = sum (R, n) 本身的程序步数为 1； 一次执行对函数 sum (R, n) 的调用需要的程序步数为 3*n+4； 一次执行的程序步数为 1+3*n+4 = 3*n+5,迭代求和程序中 程序步数计算工作表格,定义 若存在两个正的常数c和n0，对于任意nn0，都有T(n)cf(n)，则称T(n)=O(f(n),当问题规模充分大时在渐近意义下的阶,1.5.4 算法的渐进分析大O渐进表示,1.5 算法性能分析与度量,定理：若A(n)=amnm+am-1nm-1+a1n+a0是一个m次多项式，则A(n)=O(nm)。,说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。,1.5 算法性能分析与度量,1.5.4 算法的渐进分析大O渐进表示,例1-5 +x; 例1-6 for (i=1; i=n; +i) +x; 例1-7 for (i=1; i=n; +i) for (j=1; j=n; +j) +x; 例1-8 for (i=1; i=n; +i) for (j=1; j=i-1; +j) +x;,1.5 算法性能分析与度量,1.5.4 算法的渐进分析大O渐进表示,例1-9 for (i=1; i=n; +i) for (j=1; j=n; +j) cij=0; for (k=1; k=n; +k) cij+=aik*bkj; 例1-10 for (i=1; i=n; i=2*i) +x;,(1)(log2n)(n)(nlog2n)(n2)(n3) (2n)(n!),1.5 算法性能分析与度量,1.5.4 算法的渐进分析大O渐进表示,数据结构的概念（小结）,数据的操作：插入、删除、修改、检索、排序等,本章小结知识结构图,作业：,公元5世纪末，我国古代数学家张丘建在它所撰写的算经中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问鸡翁、母、雏各几何？”意思是说公鸡每只5元，母鸡每只3元，小鸡3只1元，用100元钱买100只鸡，求公鸡、母鸡、小鸡的只数。试设计算法求解该问题，并分析你所设计的算法的时间复杂度。（要求：算法分别用伪代码和C描述）,