数据结构 确规定。当时,数据结构几乎是图论,特别是表、树的理论的同义词。随后,数据结构这个 概念被扩充到网络、集合代数论、格及关系等方面,从而成为了现在称之为“离散数学”的 内容。然而,由于数据必须在计算机中进行处理,因此,不仅要考虑数据本身的数学性质, 而且还必须考虑数据的存储结构,这就进一步扩大了数据结构的内容。 从20世纪60年代末到70年代初,出现了大型程序。从软件工程的角度出发,为了提高 程序的可维护性、可调试性等性能要求,程序和数据必须分离。因此人们越来越重视数据结 构,认为程序设计的实质是为确定的问题选择一种好的结构,加上设计种好的算法,正如 瑞士著名的计算机科学家 N. wirth所提出的著名公式“程序=算法+数据结构”所阐述的那样。 数据结构的实践基础是程序设计技术,反过来,程序设计技术又改进和提高数据结构理论的 发展水平。 随着数据库系统技术的不断提高,大型数据库程序设计越来越多,对于数据处理的技 术和范围要求越来越高,因此在数据结构理论中又增加了文件管理(特别是大型文件)的 内容。 今天,虽然数据结构理论已经比较成熟,但它在面向各个专业应用领域的研究还在不断 发展中,如多维图形数据结构、动画数据结构及音频数据结构,特别是它在实际工作和生活 中的应用。 2.数据结构在计算机课程体系中的重要地位 目前在我国,“数据结构”已经不仅仅是计算机科学技术专业教学计划中的核心课程之一, 而且是其他非计算机专业的主要选修课程之一。 “数据结构”的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法等) 的研究范围、而且和计算机软件的研究有着密切的关系,无论是编译程序还是操作系统,都 涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据,以便 查找和存取数据元素更为方便。因此,可以认为据结构是介于数学、计算机硬件和计算机 软件三者之间的一门核心课。在计算机科学中,数据结构不仅是一般程序设计(特别是非 数值的程序设计)的基础,而昱是设讠和实现编译程序、操作系统、数据库系统及其他系统 程序和大型应用程序的重要基础。 随着计算机科学技不前发展,计算机应用的普及,仅仅掌握计算机语言和程序设计的技 巧和方法,而缺乏有关数据结构的知识,很难应付复杂的课题,是不能有效地利用计算机的 14算法评价 4.1算法的定义及表示 1.算法的定义 广义地说,算法就是为解决问题而采取的步骤和方法。在程序设计中,算法是在有限步 骤内求解某一问题所使用的一组定义明确的指令序列,也就是计算机解题的过程。每条指令 表示一个或多个操作。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种 算法。前者是算法实现的逻辑推理,后者是具体操作
第1章概述 2.算法的表示 为了表示一个算法,可以用多种不同的方法,常用的有自然语言、传统流程图、结构化 流程图、NS流程图、伪代码及计算机语言表示法等。本书采用的类C语言精选了C语言的 一个核心子集,同时作了若干扩充修改,增强了语言的描述功能。 14.2算法的特征及评价方法 1.算法的特征 (1)有穷性:一个算法必须保证在执行有限步骤之后结束,而不是无限的 (2)确定性:算法中每一条指令必须有明确的含义,而不能是模棱两可的。 (3)可行性:每一个操作步骤都必须在有限的时间内完成。 (4)输入:一个算法可以有一个或多个输入,也可以没有输入 (5)输出:一个算法可以有一个或多个输出。没有输出的算法是没有实际意义的。 2.算法的评价(算法的设计要求) (1)正确性:算法的正确性通常有很大的差别,大体可分为以下四个层次。 ①程序不含语法错误。 ②程序对于随意的几组合法输入数据能够得出符合要求的结果。 ③程序对于精心设计的典型合法数据输入能够得出符合要求的结果。 ④程序对于所有合法的输入数据都能得出符合要求的结果。 显然,输入所有的合法数据来检验算法的正确性是极其困难的,而对于①、②两个层次的检 验,其结论并不一定全面,所以通常以第③层意义的正确性作为衡量一个程序是否合格的标准。 (2)易读性:一个好的算法往往是能与他人共享的,晦涩难懂的算法既不易于与人交流, 也会造成修改、调试和维护的极大困难。 (3)高效性:如同人们之间的交往,办事效率高的人,人人都愿同他共事。算法也是 样,运行时间越少,其效率越高。特别是在大型程序设计中,如果每一个算法都具有高效性 那么对于缩短整个程序的运行时间无疑是非常有帮助的。算法的效率主要从时间复杂度和空 间复杂度两个方面来衡量。 (4)可维护性:一个好的算法应该对后期的维护保持较低的投入。 15算法分析 算法分析主要是指分析算法的效率。算法效率的度量主要有两个方面:算法的运行时间 和算法所需的存储空间。在早期的计算机应用中,由于CPU的运算速度较慢,运行速度对于 计算机发挥其性能来说,显得尤其重要。因此在大多数情况下,对于算法时间的要求更为重 要。但是算法运行速度和所需存储空间并不能兼顾,要想算法运行速度快就得“牺牲”相应 的空间:;要想算法占用空间少,就得“牺牲”相应的运算速度。要想解决二者的矛盾,就需 要掌握好算法分析的方法。 在算法分析中,算法整个运行过程所耗费的时间,称为算法的时间复杂度。算法整个运 行过程所占用的空间称算法的空间复杂度
数据结构 151算法的时间复杂度分析 1.算法运算时间的度量 度量算法执行时间通常有如下两种方法。 (1)事后统计的方法 很多计算机内部有计时功能,有的甚至可以精确到毫秒级,不同算法的程序可通过一组 或若干组相同的统计数据分辨优劣。但这种方法有两个缺陷:一是必须先运行依据算法编制 的程序;二是所得时间的统计量依赖于计算机的硬件、软件等环境因素。因此人们常采用另 种事前分析估算方法。 (2)事前分析估算的方法 通过对算法中不同语句序列的分析,得出算法中所有语句执行次数的相对大小不是绝对 大小,从而判断算法的运行时间长短。 2.算法运行时间的分析规则 影响程序运行时间的因素是多方面的,如机器的运行速度,编译程序产生的目标代码的 质量及程序的输入等。通常把一个程序的运行时间定义为一个T(n),其中n是该程序输入数 据的规模,而不是某一个具体的输入。Tn)的单位是不确定的,一般把它看成在一台特定计 算机上执行的指令条数。 当讨论一个程序的运行时间时,注重的不是π(η)的具体值,而是它的增长率。Tn)的增 长率与算法中数据的输入规模紧密相关,而数据输入规模往往用算法中的某个变量的函数来 表示,通常是fa)。随着数据输入规模的增大,风n)的增长率与T(n)的增长率相近,因此T(n) 同几)在数量级上是一致的,表示为7n)=OVn) 个程序运行时间的增长率将最终决定该程序在计算机上能解决多大规模的问题。如何 分析一个程序的时间复杂度呢?一般来说,分析程序的时间复杂度是逐步进行的,先求出程 序中各语句和各模块的运行时间,再求整个程序的运行时间。一组语句的运行时间,作为整 个程序运行时间的一部分,可以表示成几个变量或者输入数据的规模n的函数。整个程序的 运行时间,一般表示成惟一参数,输入数据的规模n的函数。 根据语句序列之间的逻辑关系,增长率的统计可分为线性累加规则和几何累加规则两种 情形。设T(n)=Ofn),T2(n)=Og(n),则 线性累加规则是 设T(n)和Tm)是程序段P1和P2的运行时间,则执行P1之后紧接着执行P2的运行时间 T(n)+T2(n)是 Ti(n)+ T2(nO(maxf(n),g(n)) 几何累加规则是 Ti(n)·T2(n)=O(n)·g(m) 在分析过程中,我们会遇到各种语句和各种模块,具体分析大致有以下几种情形。 (1)每个赋值语句或读/写语句的运行时间通常是O(1)。但有一些例外情况,如赋值语句 的右部表达式可能出现函数调用,这时就要考虑计算函数值所耗费的时间。 (2)顺序语句的运行时间由线性规则决定,即为该序列中耗费时间最多的语句的运行 时间
第1章概述 (3)语句i的运行时间为条件语句测试时间(通常取O(1)加上分支语句的运行时间, 语句 if-else-if的运行时间为条件测试时间加上分支语句的运行时间。 (4)循环语句的运行时间是n次重复执行循环体所耗费时间的总和,其中n是重复的次 数,而每次重复所耗费的时间包括两个部分:一是循环体本身的运行时间;二是计算循环参 数、测试循环终止条件和跳回循环开始所花费的时间。后一部分通常取O(1),常数因子忽略 不计,通常认为上述时间是循环次数n和m的乘积,其中m是n次执行循环体当中时间耗费 最多的那一次的运行时间,进而可以按几何累加规则计算这个乘积。 遇到多层循环时,要由内层向外层逐层分析。因此,当分析外层循环的运行时间时,内 层循环的运行时间应该是已知的,这时可以把内层循环看成是外层循环的循环体的一部分。 例11分析以下程序段的时间复杂度。 for(i0; i<n; i++) for(j=0; j<m; j++) A[j}=0 则该程序段的时间复杂度为O(m*n)。 例12分析以下程序段的时间复杂度。 while(s<n) + 语句①为赋值语句,其执行次数为i次,所以其时间复杂度为O) 语句②和语句③构成 while 1环语句的循环体,它们的执行次数由循环控制条件中与n 的值确定。假定循环重复执行x次后结束,则语句②和语句③各重复执行了x次,其时间复 杂度按线性累加规则为O(x)。此时s与n满足关系式s≥n,而s=1+2+3+…+x。所以有1+2+3+ x≥n,可以推出: l±√l+8 2 x与n之间满足xf√n),所以循环体的时间复杂度为O(√),语句①与循环体由线性 累加规则得到该程序段的时间复杂度为OVn) 例13分析以下程序段的时间复杂度 i=1; while(i<=n) i=2*i; 解:其中语句①的执行次数是1,设语句②的执行次数为f),则2≤n。 得Tn)=O(logn) (5)递归调用函数的时间复杂度分析。 若程序中有递归过程,则令每个递归过程对应于一个未知的时间开销T(n),其中n是过 程参数的长度,然后列出一个关于T的递归方程并求解
数据结构 例14有以下程序,分析其中 ordert0函数的时间复杂度。 void order( intj, int m) f int i, temp: if(j<m) for(i=;j<=m;计) if (a[o]a[]) f temp=a; a[]a亦j] order G, m); void main() 1, order(0, 7) for(i=0;i<=7;i++) printf("%d, a[]); 解: orderO函数是一个递归排序过程,设Tn)(nm+1)是排序n个元素所需的时间,在进 行排序时,算法的计算时间主要花费在递归调用上。第一次调用时处理的元素个数为n-1, 也就是对余下的n1个元素进行排序,这部分所需的计算时间为7m-1) 又因为在循环中,需要n1次比较,所以排序n个元素所需的时间为r(n)=T(m-1)+n-1(m>1) 这样得到如下方程: O(1),n≤1 T(n)= 7(n-1)+O(),n>1 求解过程为 7(n)=7(n-1)+(n-1) 7(n-2)+(n-2)]+(n-1) [7(n-3)+(n-3)+(m-2)+(m-1) [7(1)+]+2+3+4+…+(n-3)+(n-2)+n-1) 0+1+2+3+…+(n-1) n(n-1)2 =O(n) 例L有如下递归函数fac(n),分析其时间复杂度。 int fact( int n)