《数据结构选讲datastructure课件》由会员分享，可在线阅读，更多相关《数据结构选讲datastructure课件（49页珍藏版）》请在金锄头文库上搜索。
1、数据结构选讲 DATA STRUCTURE,主讲教师： 罗 熊 Instructor: LUO Xiong E-mail: ,课程内容： 计算机软件的基础知识数据结构 课时安排： 数据结构32学时 教 材： 严蔚敏，吴伟民. 数据结构. 北京：清华大学出版社，1997. 参考书： 数据结构习题与解析（C语言篇） 李春葆 数据结构题集 严蔚敏，吴伟民 数据结构算法与应用C+语言描述 （英文版） Sartaj Sahni McGraw-Hill & 机械工业出版社,数据结构的基本概念 数据类型和抽象数据类型 C语言的数据类型 用C语言描述算法的注意事项 算法设计目标和算法效率度量,第一章 绪 论,
2、1.1 数据结构的基本概念 数据：数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。 数值性数据 非数值性数据 数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象 N = 0, 1, 2, 学生数据对象:初等项（不可分割）、组合项（可再划分）,数据元素：是数据的最小单位，有时一个数据元素由数据项组成（具有独立含义的最小标识单位） 数据类型：具有相同性质的计算机数据集合及在这个集合上的一组操作。 数据结构：由某一数据对象及该对象中所有数据成员之间的关系组成。记为： Data_Structure = D, R 其中
3、，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。,数据结构依据视点的不同，分为数据逻辑结构和物理结构：,逻辑结构：从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。 物理结构：指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。 关系：物理结构是逻辑数据的存储映象,逻辑结构： 线性结构 非线性结构 物理结构： 顺序存储 链接存储 索引存储 散列存储,“学生”表格,“课程”表格,线性结构中各数据成员之间的线性关系:有直接前驱和直接后继(除最前、最后一个元素),例：电话号码查询问题 方法1：顺序存储
4、，顺序查找,方法2：有序顺序存储，二分查找,方法3：部分有序，建立索引表,非线性结构中各数据成员之间的没有线性关系:前驱和后继可能多于一个,选课单包含如下信息 学 号 课程编号 成 绩 时 间 学生选课系统中实体构成的网状关系,UNIX文件系统的系统结构图,树形结构,树 二叉树 二叉搜索树,堆结构,“最大”堆 “最小”堆,图结构 网络结构,例：田径赛的时间安排问题,跳高,跳远,标枪,铅球,200M,100M,1、任一选手所选中的项目中应该两两有边相连； 2、任一两个有边相连的顶点颜色（时间）不能相同。,在解决问题时可能遇到的典型的逻辑结构（数据结构） 逻辑结构的存储映象（存储实现） 数据结构的
5、相关操作及其实现。,1.2 数据类型和抽象数据类型,数据类型 定义：一个数据的集合, 以及定义于这个数据集合上的一组操作的总称。 C语言中的数据类型 基本数据类型、指针类型、数组类型、结构体类型、公用体类型、枚举类型,抽象数据和抽象数据类型 (ADTs: Abstract Data Types),由用户定义，用以表示应用问题的数据模型 由基本的数据类型组成, 并包括一组相关的服务（或称操作） 信息隐蔽和数据封装，使用与实现相分离（物理实现封装）,ADT：抽象数据类型名 数据对象：数据对象的定义 数据关系：数据逻辑关系的定义 基本操作：基本操作的定义,抽象数据类型的定义：,操作名（参数表） 操作
6、结果：操作结果描述,基本操作的定义：,抽象数据类型,好的和坏的数据结构？,如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如果没有线性化的结构逻辑上是不可计算的。,树是好的DS它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质。,2019/1/6,25,1.3 C语言的数据类型,1、基本数据类
7、型,int short; long; unsigned float float; double; long double,2、指针类型 3、数组类型 4、字符串 5、结构体类型 6、共用体类型 7、枚举类型 8、自定义类型,1.4 用C语言编写算法的注意事项,1、避免使用出现二义性的表达式,i+; i = + i; i = 1; j = i + + + i - -;,2、避免使用转向语句 3、避免使用预处理 4、避免函数返回值隐含说明,1.5 算法设计目标和算法效率度量,定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列 特性： 输入 有0个或多个输入 输出 有一个或多个输出
8、(处理结果) 确定性 每步定义都是确切、无歧义的 有穷性 算法应在执行有穷步后结束 有效性 每一条运算应足够基本 算法的描述:c+,c,PASCAL等语言,2019/1/6,28,算法有这样一些特点： 1、有穷性：要求序列中的指令是有限的；每条指令的执行包含有限的工作量；整个指令序列的执行在有限的时间内结束。 2、确定性：算法中的每一个步骤都必须是确定的，而不应当含糊、模棱两可。 3、有零个或多个输入 4、有一个或多个输出 5、有效性：算法中的每一个步骤都应当能被有效的执行，并得到确定的结果。例如：被零除的计算动作是不能被有效执行的。,设计算法的基本方法:把一个具体问题转变成一个算法 事例学习
9、：选择排序问题 明确问题：非递减排序 解决方案：逐个选择最小数据 算法框架： for ( int i=0; in-2; i+ ) /n-1趟 从ai检查到an-1; 若最小的整数在ak, 交换ai与ak; 细化程序：程序 SelectSort,算法设计 自顶向下，逐步求精,性能分析与度量,算法的性能标准 算法的后期测试 算法的事前估计,2019/1/6,31,分析评价算法时应考虑的因素： 1、正确性 在给定有效的输入数据后，算法经过有穷时间的计算能给出正确的答案。 2、复杂度 时间复杂度 3、简单性 4、最优性 算法A是最优的是指：在给定问题的所有算法中，A执行的进步运算次数最少 5、可读性
10、要求算法易于理解，便于分析 6、可修改可扩展性 如果问题P 的一个算法是A，为了解答一个与P类似的问题，希望对A稍做改动就可正确运行，如算法A满足这一点，则说A的可修改性好。,2019/1/6,32,与算法效率有关的因素,程序设计语言 编译的代码质量 机器执行指令的速度 问题的规模,2019/1/6,33,求解同样一个问题可能会有许多不同的算法，如何评价这些算法的好坏呢？ 首先算法必须是正确的。此外还需考虑： 1、算法易于理解，易于编程（在计算机上实现） ，易于调试。 2、要求算法高效，节省时间与空间。 一个算法运行所需时间的长短、空间的大小具有非常重要的意义。 时间和空间相互之间有一种制约关
11、系，何者为重需视具体情况而定。,2019/1/6,34,算法高效与算法易理解、易编程之间也有一种制约关系 这两个要求有时互相矛盾。因此，对反复运行的算法，首先考虑的是高效性，对偶尔运行的算法，则需突出算法易理解和易编程（以排序为例 冒泡排序和快速排序）。,2019/1/6,35,我们重点考虑时间因素。 一个算法所耗费的时间，应该是该算法中每条语句的执行时间之和，而每条语句的执行时间又是该语句的执行次数（频度）与该语句执行一次所需时间的乘积。 我们假定，每条语句一次执行的时间都是相同的，为单位时间。这样我们对时间的分析就可以独立于软硬件系统。,2019/1/6,36,我们将算法求解问题的输入量称
12、为问题的规模，用一个整数来表示，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是问题规模的函数 T( n )。 当问题的规模n 趋于无穷大时，把时间复杂度T( n )的数量级（阶）称为算法的渐进时间复杂度（有时简称为时间复杂度）。 严格的数学定义为：若T( n ) 和 f( n ) 是定义在正整数集合上的两个函数，当存在两个正的乘数C和n0时，使得对所有的,成立，则,都有,这时称T( n )的时间复杂度为f( n )数量级。,2019/1/6,37,算法运行所需要的时间与两个因素有关： 1、问题实例的大小 （如1000个数的排序）； 2、实例的具体情况 （如1000个数的排列情况
13、）,2019/1/6,38,算法分析 1、假定每条语句的执行时间为单位时间。算法的时间复杂度是该算法中所有语句的执行频度之和。,2019/1/6,39,例：求两个方阵的乘积 CA*B define n 自然数 MATRIXMLT(float Ann,float Bnn,float Cnn) int i,j,k; for(i=0;in;i+) / for(j=0;jn;j+) / Cij=0; / for( k=0;kn;k+) / Cij=Aik*Bkj / ,2019/1/6,40,2、一般情况下，对步进循环语句只考虑循环体语句的执行次数，而忽略该语句中部长加一、终值判别、循环转移等成份。因
14、此，当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度所决定的。,2019/1/6,41,例： x=0;y=0; for (k=1;k=n;k+) x+; for (i=1;i=n;i+) for (j=1;j=n;j+) /n*n y+;,一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，而忽略循环体中步长加1、终值判断、控制转移等成分。,2019/1/6,42,例： x=1; for (i=1;i=n;i+) for (j=1;j=i;j+) for (k=1;k=j;k+) x+;,2019/1/6,43,3、选择执行的成分，如 if 语句的执行时
15、间，决定于then 子句、else 子句耗时较多的部分 4、如果算法的执行时间是一个与问题规模n无关的常数，则算法的时间复杂度为常数阶，记作T(n)=O(1)。,例： temp = i; i = j; j = temp;,2019/1/6,44,5、很多算法的时间复杂度不仅与问题的规模有关，而且还与它所处理的数据集的状态有关。通常是根据数据集中可能出现的最坏情况估计出算法的最坏时间复杂度。,2019/1/6,45,例： i=n-1; while (i=0),此问题不仅与规模 n 有关，而且与数组A中各元素的取值有关。,例： fact(n) if (n = 1) return 1; else return (n*fact(n-1); 设 fact 的运行时间函数为T（n），则有,2019/1/6,48,常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 K次方阶 指数阶,常见的时间复杂度，按数量级递增排序：,算法的后期测试,在算法中的某些部位插装时间函数 time ( ) 测定算法完成某
