《Java版数据结构(程序员必须看)讲课稿》由会员分享，可在线阅读，更多相关《Java版数据结构(程序员必须看)讲课稿（1063页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构,计算机科学与技术学院 张 宏,第一章 绪 论,1.1 什么是数据结构 1.2 有关概念和术语 1.3 算法和算法分析 1.3.1 算法 1.3.2 算法设计的要求 1.3.3 算法效率的度量 1.3.4 算法的存储空间的需求,第一章 绪 论,计算机学科一直处于高速发展中,而且这种发展速度还会持续。,计算机科学已经难以完全覆盖学科新的发展，因此扩展后的学科称为计算学科。,包括：计算机科学、计算机工程、软件工程、信息系统,关键问题：利用计算机进行信息表示和处理的涉及： 信息的表示 信息的处理 而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范
2、围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,1.1 什么是数据结构 众所周知，计算机的程序是对信息进行处理。在大多数情况下，这些信息并不是没有组织的，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。什么是数据结构呢？ 例子： 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn) 其中(ai，bi)(i=1，2n) 分别表示某人的名字和对应的电话号码
3、。要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能够报告没有这个人的信息。,数据结构含义： 就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。,所有能被输入到计算机中，且能被计算机处理的符号的集合。,数据:,是计算机操作的对象的总称。,是计算机处理的信息的某种特定的符号表示形式。,1.2 有关概念和术语,是数据（集合）中的一个“个体”,数据元素:,是数据结构中讨论的基本单位,数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑
4、结构。通常分为四类基本结构： 一、集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 二、线性结构 结构中的数据元素之间存在一对一的关系。 三、树型结构 结构中的数据元素之间存在一对多的关系。 四、图状结构或网状结构 结构中的数据元素之间存在多对多的关系。,一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。,数据在计算机中的表示称为数据的物理结构，又称为存储结构。,数据对象可以是有限的，也可以
5、是无限的。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,数据类型：在一种程序设计语言中，变量所具有的数据种类。 例1、 在FORTRAN语言中，变量的数据类型有整型、实型、和复数型 例2、在C+语言中 数据类型：基本类型和构造类型 基本类型：整型、浮点型、字符型 构造类型：数组、结构、联合、指针、枚举型、自定义 数据对象：某种数据类型元素的集合。 例3、整数的数据对象是-3，-2，-1，0，1，2，3， 英文字符类型的数据对象是A，B，C，D，E，F，,1.3 算法和算法分析 1.3.1 算法： 是对特定问题求解步骤的一种
6、描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性： （1）有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 （2）确定性 算法中每一条指令必须有确切的含义。不存在二义性。 （3）可行性 一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 （4）输入 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 （5）输出 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。,1.3.2 算法设计的要求,设计算法时，通常应考虑达到以下目标：,1、正确性 2、可读性 3、健壮性 4、高效率与低存
7、储量需求,1正确性,首先，算法应当满足以特定的“规格说明”方式给出的需求。,其次，对算法是否“正确”的理解可以有以下四个层次：,a程序中不含语法错误；,b程序对于几组输入数据能够得出满足要求的结果；,c程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；,通常以第 c 层意义的正确性作为衡量一个算法是否合格的标准。,d程序对于一切合法的输入数据都能得出满足要求的结果；,2. 可读性,算法主要是为了人的阅读与交流， 其次才是为计算机执行，因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试。,3健壮性,当输入的数据非法时，算法应当恰当地作出反映
8、或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。,4高效率与低存储量需求,通常，效率指的是算法执行时间； 存储量指的是算法执行过程中所需的 最大存储空间，两者都与问题的规模 有关。,1.3.3 算法效率的度量,通常有两种衡量算法效率的方法:,事后统计法,事前分析估算法,缺点：1必须执行程序 2其它因素掩盖算法本质,和算法执行时间相关的因素：,1算法选用的策略,2问题的规模,3编写程序的语言,4编译程序产生的机器代码的质量,5计算机执行指令的速度,一个特定算法的“运行工作量” 的大小，只
9、依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。,假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) 的增长率相同，则可记作：,T (n) = O(f(n),称T(n)为算法的(渐近)时间复杂度。,如何估算 算法的时间复杂度？,算法 = 控制结构 + 原操作 （固有数据类型的操作）,算法的执行时间 = 原操作(i)的执行次数原操作(i)的执行时间,算法的执行时间 与 原操作执行次数之和 成正比,从算法中选取一种对于所研究的问题来说是 基本操作 的原操作，以该基本操作 在算法中重复执行的次数 作为算法运行时间的衡量准则。,void mult(int a, int
10、 b, int c ) for (i=1; i=n; +i) for (j=1; j=n; +j) cij = 0; for (k=1; k=n; +k) cij += aik*bkj; /for /mult,基本操作: 乘法操作,时间复杂度: O(n3),例1,例 +x;s=0; 将x自增看成是基本操作，则语句频度为1 ，即时间复杂度为(1) 如果将s=0也看成是基本操作，则语句频度为1，其时间复杂度仍为(1)，即常量阶。 例 for(i=1;i=n;+i) +x;s+=x; 语句频度为：n其时间复杂度为：O(n) 即时间复杂度为线性阶。,i=0: 赋值次,i=1: 赋值 2 次,i=2:
11、赋值3次,i=n-1:赋值n次,.,1+2+3+n=(1+n)n/2=n2/2+n/2,例 for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x; 语句频度为：n2 其时间复杂度为：O(n2) 即时间复杂度为平方阶。 例 for(i=0;i=n-1;+i) for(j=0;j=i;+j) aij=0;,定义：如果f(n)是正整数n的一个函数，若存在两个正常数c和n0，对于所有的nn0，有f(n) cg(n) |，则记作 f(n)=O(g(n) 例：f(x)=anxn+an-1xn-1+.+a1x+a0，其中an不等0，n为正整数， 则f(x)=O(xn) 证明： |f
12、(x)|=| anxn+an-1xn-1+.+a1x+a0 | anxn |+| an-1xn-1|+| a1x |+| a0 | =|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0|,当x1=n0，n为正整数时，xn+1xn，所以：,|an|*|xn|+|an-1|*|xn-1|+|a1|*|x1|+|a0|*|x0| |an|*|xn|+|an-1|*|xn|+|a1|*|xn|+|a0|*|xn|,=(|an|+|an-1|+|a1|+|a0|)|xn|=c|xn| 其中：n0=1, c= |an|+|an-1|+|a1|+|a0|, g(n)=xn,
13、一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。,1.3.4 算法的存储空间的需求,算法的空间复杂度定义为:,表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n) 的增长率相同。,S(n) = O(g(n),算法的存储量包括:,
14、1输入数据所占空间,2程序本身所占空间,3辅助变量所占空间,若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。,若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。,注意：时间与空间往往是对矛盾，要综合考虑。,最坏时间复杂性,例6：有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而 不同。例如： void bubble-sort(int a，int n) for(i=n-1;i0 ;i-) for(j=0;jaj+1) aj aj+1; 时间： 最好情况：0次 最
15、坏情况：每次都换， (n2),空间：一个数据交换的辅助空间-算法原地工作。,例7： 递归程序的分析 int fact( int n) if(n=1) return 1; else return n*fact(n-1); ,f(n)=c+f(n-1) =c+(c+f(n-2) =2c+f(n-2) =(n-1)c+f(1) =(n-1)c+c0,课时安排与考核,学分 3 :授课 2.5 (40课时) 上机 0.5 (8+8课时) 考核: 平时成绩 20% 作业(课后与课堂)、实验 课程考试 80%,作业： . 计算时间复杂度 sum=1; for(i=0;sumn;i+) sum+=i; 2.设
16、给定若干n值，比较两函数n2和50nlog2n的增长趋势，并确定在什么范围内，函数n2的值大于50nlog2n的值。,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,2.1 线性表的逻辑结构 线性表：由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 例1、26个英文字母组成的字母表 （A，B，C、Z） 例2、某校从1978年到1983年各
