古怪的思路：因为大型软件的开发不是一个人能完成的，相互之间需要交流，所写代码必须 被人容易理解。 3、健壮性(robustness)又称鲁棒性，是robust音译。容错性：输入不合法时，除数n <0时，能够反馈给用户相应的提示信息，而不是终止程序的执行，或显示调试时出现的一 些错误信息 4、时间效率与空间效率要求 研究数据结构的目的之一就是为了提高算法的时间效率和空间效率，要提高算法的时间 效率和空间效率，必须首先会度量它，下面两小节就要来讲述怎样度量算法的效率。 1.4.3算法时间效率的度量 1、算法执行时间：依据该算法编制的程序在计算机上运行所消耗的时间。可以利用计算 机内部计时功能来获取程序的运行时间。但是该种度量标准有两个缺陷： (1)必须首先运行依据算法绵制的程序。 (2)所得时间的统计量依赖于计算机硬件、软件的因素，容易掩盖算法本身的优劣。如 书写程序的语言级别越高，执行效率越低，运行时间越长：同一个算法，用汇编语言书写要比才 JAVA语言执行效率高，运行时间要短：同样的源代码，编译程序所产生的机器代码的质量越高， 运行时间就越短，反之就越长；机器执行指令的速度越快，运行时间就越短，反之就越长。 分析算法时间效率时，必须撒开这些与算法无关的软硬件因素。通常的做法是：从算法 中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为 算法的时间度量：称之为算法的渐进时间复杂度，简称算法的时间复杂度。 2、算法的渐进时间复杂度(asymptotic time complexity） 定义：基本操作重复执行的次数 double fun(int n) double S=1: for (inti=0;i<n;i++) S*=(+ return S; 求阶乘的算法可以把乘法操作看作原操作。 例题1：假设把划横线的语句看作是原操作，分析以迭代方式求累加和算法的时间复杂 度。 float sum(float []a,int n) float s =0.0f; 11
11 古怪的思路；因为大型软件的开发不是一个人能完成的，相互之间需要交流，所写代码必须 被人容易理解。 3、健壮性（robustness）又称鲁棒性，是 robust 音译。容错性：输入不合法时，除数 n ＜0 时，能够反馈给用户相应的提示信息，而不是终止程序的执行，或显示调试时出现的一 些错误信息。 4、时间效率与空间效率要求 研究数据结构的目的之一就是为了提高算法的时间效率和空间效率，要提高算法的时间 效率和空间效率，必须首先会度量它，下面两小节就要来讲述怎样度量算法的效率。 1.4.3 算法时间效率的度量 1、算法执行时间：依据该算法编制的程序在计算机上运行所消耗的时间。可以利用计算 机内部计时功能来获取程序的运行时间。但是该种度量标准有两个缺陷： （1）必须首先运行依据算法编制的程序。 （2）所得时间的统计量依赖于计算机硬件、软件的因素，容易掩盖算法本身的优劣。如 书写程序的语言级别越高，执行效率越低,运行时间越长:同一个算法,用汇编语言书写要比才 JAVA 语言执行效率高,运行时间要短;同样的源代码,编译程序所产生的机器代码的质量越高, 运行时间就越短,反之就越长;机器执行指令的速度越快,运行时间就越短,反之就越长。 分析算法时间效率时，必须撇开这些与算法无关的软硬件因素。通常的做法是：从算法 中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为 算法的时间度量；称之为算法的渐进时间复杂度，简称算法的时间复杂度。 ２、算法的渐进时间复杂度（asymptotic time complexity） 定义：基本操作重复执行的次数 double fun(int n) { double S = 1; for (int i = 0; i < n; i++) { S *= (i+1); } return S; } 求阶乘的算法可以把乘法操作看作原操作。 例题 1：假设把划横线的语句看作是原操作，分析以迭代方式求累加和算法的时间复杂 度。 float sum(float []a, int n) { float s = 0.0f;
for int i=0;i<n;i++) s=s afili return s; 该例题中，基本操作执行+1次，该算法的时间复杂度记为O()：基本操作执行次数 与n成正比的即antb均记为On):基本操作执行次数与m2成正比的即cn2+antb均记为0(n), 依次类推.分析算法的时间复杂度时一般只关注增长最快的项，在一些常用的项中到底哪个 项增长快呢？有下面的不等式成立：增长最快，其次3”，以此类推： c<logn<n<nlogn<n<n<2<3<n! 例题2：划横线线的均为可视为基本操作，分析下面算法的时间复杂度，： static void example (float [][]x,int n) f f1oat「1sum=new float「n1: for int i=0;icn;i++) {1/x[][]中各行 sum[i]0.0f; 1/数据累加 for int j=0;j<n;j++) sum[il=sum[il+x[il[ili for(inti=0;i<n;i+)/输出各行数据和 system.out.println("Line"+i+":"sumfi]); 该算法基本操作总共执行了n*n+2n次，该算法的渐进时间复杂度O(max(*n,n》,即 On*n)。 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例3：假设把数据交换操作看作原操作，分析下面冒泡排序算法的时间复杂度： static void bubble_sort1(int []a,int n) for(int i=n-1;i>0;i-) for(int i=0iisiitti) if (alilza[i+11) f int temp alili alil ali 1li a[i 11 temp: 1 此算法对输入数据序列进行排序。算法执行完毕后，数组中的数据元素依次递增，即第 一个元素最小，最后一个元素最大。排序过程如下所示： 首先比较第一个和第二个数据，将其中较小的数据放到第一个位置，较大的放到第二个 位置：然后比较第二个和第三个数据，仍将较大的放到后一个位置。依此类推，直到比较第
12 for ( int i=0; i<n; i++ ) s= s + a[i]; return s; } 该例题中，基本操作执行 n+1 次，该算法的时间复杂度记为 O(n) ；基本操作执行次数 与 n 成正比的即 an+b 均记为 O(n)；基本操作执行次数与 n 2成正比的即 cn 2+an+b 均记为 O(n 2)， 依次类推.分析算法的时间复杂度时一般只关注增长最快的项，在一些常用的项中到底哪个 项增长快呢？有下面的不等式成立：n!增长最快，其次 3 n ，以此类推： c < log2n < n < nlog2n < n 2 < n 3 < 2 n < 3 n < n! 例题 2：划横线线的均为可视为基本操作，分析下面算法的时间复杂度，： static void example (float [][]x, int n) { float []sum=new float[n]; for ( int i=0; i<n; i++ ) { //x[ ][ ]中各行 sum[i] = 0.0f; //数据累加 for ( int j=0; j<n; j++ ) sum[i] = sum[i]+ x[i][j]; } for ( int i = 0; i < n; i++ ) //输出各行数据和¨ System.out.println("Line"+i+": "+ sum[i]); } 该算法基本操作总共执行了 n *n+2 n 次，该算法的渐进时间复杂度 O(max (n *n, n))，即 O(n *n)。 有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。 例 3：假设把数据交换操作看作原操作，分析下面冒泡排序算法的时间复杂度： static void bubble_sort1(int []a,int n) { for(int i=n-1; i>0;i-) for(int j=0;j<i;++j) if (a[j]>a[j+1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; } } 此算法对输入数据序列进行排序。算法执行完毕后，数组中的数据元素依次递增，即第 一个元素最小，最后一个元素最大。排序过程如下所示： 首先比较第一个和第二个数据，将其中较小的数据放到第一个位置，较大的放到第二个 位置；然后比较第二个和第三个数据，仍将较大的放到后一个位置。依此类推，直到比较第
n-l和第n个数据。这样，就将待排序序列中的最大的一个放到了第n个位置，这个过程称 为第一趟排序；一趟排序冒出一个泡来，故此算法称为冒泡排序法。第二趟排序对前-1个 数据重复这个过程，第二趟不用考虑第个数据，因为它己经是最大的了，第二趟排序又将 次大的数据放到了第-1个位置。第三趙排序选出第三大的数据，放到倒数第三个位置。重 复这个过程，直到数据依次递增为止（共-1趟）。 有一个数组，数组元素分别为： 46,82,40,52,67,31,21,73。它的n趟排序状态如下所示 [初态]：4682 40 52 6731 2173 第1趟： 40 52 31 21 73 82 第2墙： 40 46 52 31 21 67 73 第3趟： 40 31 21 73 第4趟： 0 21 46 67 73 第5趟 31 0 46 51 73 第6趟： 21 3 40 46 67 73 第7趟： 21 0 6 67 73 假设数组中数据元素个数是n, 数据交换操作是基本操作： 最坏的情况：当初始状态完全逆序，即数据元素递减有序：要进行多少次数据交换？ 「初态1：82 73 67 52 46 40 3121 第1趟： 3 6 40 2182n-1 第2销： 67 52 46 0 31 21 73 82 第3趟 46 40 21 么3 第4趙： 46 40 31 21 52 67 73 82 第5趟： 40 31 3 46 52 82 第6趟： 31 21 40 46 52 67 73 第7越： 21 31 40 46 52 61 82 1 数据交换次数=1+2+ +n-2+n-l=m(n-1)/2 最好的情况：当初始状态已经递增有序时，基本操作执行多少次？0次 [初态]：21 31 40 46 52 67 73 82 第1趟： 21 31 40 6 52 67 3 82 0 第2趟： 21 31 40 46 52 61 0 第3趟： 21 31 40 % 52 3 8 第4趟： 21 31 40 46 2 67 73 82 0 第5趟： 21 31 40 52 0 第6趟： 21 31 % 6 82 0 第7諧： 21 3140 46 52 6 73 0 计算时间复杂度以最坏情况为准，为0)。 当某一趟排序没有数据交换时，表明数据元素己经按递增有序，接下来的排序过程可以 13
13 n-1 和第 n 个数据。这样，就将待排序序列中的最大的一个放到了第 n 个位置，这个过程称 为第一趟排序；一趟排序冒出一个泡来，故此算法称为冒泡排序法。第二趟排序对前 n-1 个 数据重复这个过程，第二趟不用考虑第 n 个数据，因为它已经是最大的了，第二趟排序又将 次大的数据放到了第 n-1 个位置。第三趟排序选出第三大的数据，放到倒数第三个位置。重 复这个过程，直到数据依次递增为止（共 n-1 趟）。 有一个数组，数组元素分别为： 46，82，40，52，67，31，21，73。它的 n 趟排序状态如下所示： [初态]：46 82 40 52 67 31 21 73 第 1 趟： 46 40 52 67 31 21 73 82 第 2 趟： 40 46 52 31 21 67 73 82 第 3 趟： 40 46 31 21 52 67 73 82 第 4 趟： 40 31 21 46 52 67 73 82 第 5 趟： 31 21 40 46 52 67 73 82 第 6 趟： 21 31 40 46 52 67 73 82 第 7 趟： 21 31 40 46 52 67 73 82 假设数组中数据元素个数是 n，数据交换操作是基本操作； 最坏的情况：当初始状态完全逆序，即数据元素递减有序：要进行多少次数据交换？ [初态]：82 73 67 52 46 40 31 21 第 1 趟： 73 67 52 46 40 31 21 82 n-1 第 2 趟： 67 52 46 40 31 21 73 82 n-2 第 3 趟： 52 46 40 31 21 67 73 82 n-3 第 4 趟： 46 40 31 21 52 67 73 82 . 第 5 趟： 40 31 21 46 52 67 73 82 . 第 6 趟： 31 21 40 46 52 67 73 82 2 第 7 趟： 21 31 40 46 52 67 73 82 1 数据交换次数=1+2+.+n-2+n-1=n(n-1)/2 最好的情况：当初始状态已经递增有序时，基本操作执行多少次？0 次 [初态]：21 31 40 46 52 67 73 82 第 1 趟： 21 31 40 46 52 67 73 82 0 第 2 趟： 21 31 40 46 52 67 73 82 0 第 3 趟： 21 31 40 46 52 67 73 82 0 第 4 趟： 21 31 40 46 52 67 73 82 0 第 5 趟： 21 31 40 46 52 67 73 82 0 第 6 趟： 21 31 40 46 52 67 73 82 0 第 7 趟： 21 31 40 46 52 67 73 82 0 计算时间复杂度以最坏情况为准，为 O(n 2)。 当某一趟排序没有数据交换时，表明数据元素已经按递增有序，接下来的排序过程可以
不必进行。但此算法依然进行完7趟排序过程才终止。怎样解决此问题？可以设置一个变量 change-TRUE,用它来记录一趟排序过程中是否有数据交换。在每趟排序之前置change的值 为FALSE,每当产生交换数据，change的值就改为TRUE。每趙排序之后，判断change的值， 若为TRUE,则继续下一趟排序：若为FALSE,表明这一趟没有交换任何数据，排序己经完 成。 static void bubble_sort(int []a,int n) int i;boolean change=true; for(i=n-1;i>0&&change;-i) change=false; for(int j=0;j<i;++j) if(a[j]>a[j+1]) int temp a[j];a[j]a[j 1];a[j +1]temp; change=true; [初态]：2131404652677382 第1趟： 2131 4046526773 82 第一趟没有数据交换，change的值为FALSE,不满足循环条件，退出循环。 l.4.3算法的空间复杂度(space complexity) 一个算法的空间复杂度是指程序在从运行开始到结束所需的存储量与问题规模 的对应关系。 冒泡排序法所占存储空间： 一个长度为n整型数组，三个整型变量i,j,temp -个布尔型变量change。. static void bubble_sort(int []a,int n) int i:boolean changestrue: for(i=n-1;1>08&change;-i) change=false; for(int j=0;ji;++j) f(a[j]>a[j+1]) 14
14 不必进行。但此算法依然进行完 7 趟排序过程才终止。怎样解决此问题？可以设置一个变量 change=TRUE，用它来记录一趟排序过程中是否有数据交换。在每趟排序之前置 change 的值 为 FALSE，每当产生交换数据，change 的值就改为 TRUE。每趟排序之后，判断 change 的值， 若为 TRUE，则继续下一趟排序；若为 FALSE，表明这一趟没有交换任何数据，排序已经完 成。 static void bubble_sort( int []a,int n) { int i;boolean change=true; for(i=n-1;i>0&&change;-i) { change=false; for(int j=0;j<i;++j) if (a[j]>a[j+1]) { int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; change=true; } } } [初态]：21 31 40 46 52 67 73 82 第 1 趟： 21 31 40 46 52 67 73 82 第一趟没有数据交换，change 的值为 FALSE,不满足循环条件，退出循环。 1.4.3 算法的空间复杂度（space complexity） 一个算法的空间复杂度是指程序在从运行开始到结束所需的存储量与问题规模 的对应关系。 冒泡排序法所占存储空间：一个长度为 n 整型数组，三个整型变量 i,j，temp， 一个布尔型变量 change。 static void bubble_sort( int []a,int n) { int i;boolean change=true; for(i=n-1;i>0&&change;-i) { change=false; for(int j=0;j<i;++j) if (a[j]>a[j+1]) {
int temp a[j];a[j]a[j +1];a[j +1]temp; change=true; 第2章线性表 2.1线性表的类型定义 1.线性表的定义 线性表是由n(≥0)个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=(a,a,a-wa,a,a） 其中：L为线性表名称，习惯用大写书写：a:为组成该线性表的数据元素，习惯用小写 书写：线性表中数据元素的个数被称为线性表的长度，当=0时，线性表为空，又称为空线 性表。表中相邻元素之间存在着前后次序关系：将a-,称为a,的直接前驱，将a+,称为a,的 直接后继。 举例： LA=(34,89,765,12,90,-34,22)数据元素类型均为int LB=(Hello'","World”,"China","Welcome）数据元素类型均为string。 LC=(book1,book2,·,book100)数据元素类型均为下列所示的结构类型： class bookinfo int No; /◆图书编号幸/ String name; /*图书名称* String auther; /*作者名称*/ }； 2.线性表的特点 (1)存在唯一的一个被称作”第一个“的数据元素。 (2)存在难一的一个被称作"最后一个”的数据元素 (3)除第一个之外，集合中的每个数据元素均只有一个直接前驱。 (4)除最后一个外，集合中的每个数据元素均只有一个直接后继。 3.线性表的抽象数据类型定义 ADT List
15 int temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp; change=true; } } } 第 2 章 线性表 2.1 线性表的类型定义 1．线性表的定义 线性表是由 n（n≥0）个类型相同的数据元素组成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L 为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写 书写； 线性表中数据元素的个数被称为线性表的长度，当 n=0 时，线性表为空，又称为空线 性表。表中相邻元素之间存在着前后次序关系:将 ai-1,称为 ai的直接前驱，将 ai＋1,称为 ai的 直接后继。 举例: LA=(34,89,765,12,90,-34,22) 数据元素类型均为 int。 LB=(Hello,World,China,Welcome) 数据元素类型均为 string。 LC=(book1,book2,.,book100)数据元素类型均为下列所示的结构类型： class bookinfo { int No; /*图书编号*/ String name; /*图书名称*/ String auther; /*作者名称*/ .; }; 2．线性表的特点 （1）存在唯一的一个被称作"第一个"的数据元素。 （2）存在唯一的一个被称作"最后一个"的数据元素。 （3）除第一个之外，集合中的每个数据元素均只有一个直接前驱。 （4）除最后一个外，集合中的每个数据元素均只有一个直接后继。 3．线性表的抽象数据类型定义 ADT List {