《计算机是一门研究用计算机进行信息表示和处理的科学这.ppt》由会员分享，可在线阅读，更多相关《计算机是一门研究用计算机进行信息表示和处理的科学这.ppt（24页珍藏版）》请在金锄头文库上搜索。
1、 第一章 绪 论计算机是一门研究用计算机进行信息表示和处理计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：的科学。这里面涉及到两个问题： 信息的表示信息的表示 信息的处理信息的处理 而信息的表示和组又直接关系到处理信息的程而信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出规模很大，结构又相当复杂。因此，为了编写出一个一个“ “好好” ”的程序，必须分析待处理的对象的特的程序
2、，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题门课所要研究的问题。 1.1什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。众所周知，计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几结构的内容。那么，什么是数据结构呢？先看以下几个例子。个例子。 例例1 1、电话号码查询系统、电话号码查询系统 设
3、有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N N个人的名字和其个人的名字和其相应的电话号码，假定按如下形式安排：相应的电话号码，假定按如下形式安排： (a(a1 1，b b1 1)(a)(a2 2，b b2 2)(a)(an n，b bn n) )其中其中a ai i，b bi i(i=1(i=1，2n) 2n) 分别表示某人的名字和对应的分别表示某人的名字和对应的电话号码要求设计一个算法，当给定任何一个人的名电话号码要求设计一个算法，当给定任何一个人的名字时，该算法能够打印出此人的电话号码，如果该电字时，该算法能够打印出此人的电话号码，如果该电话簿中根本就没有这个人，则该算法也能
4、够报告没有话簿中根本就没有这个人，则该算法也能够报告没有这个人的标志。这个人的标志。 算法的设计，依赖于计算机如何存储人的名算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电字和对应的电话号码，或者说依赖于名字和其电话号码的结构。话号码的结构。 数据的结构，直接影响算法的选择和效率。数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、和对应的电话号码设计成：二维数组、表结构、向量。向量。 假定名字和其电话号码逻辑上已安排成假定名字和其电话号码逻辑上已安排成N
5、N元元向量的形式，它的每个元素是一个数对向量的形式，它的每个元素是一个数对( (a ai i，b bi i) )， 1in 1in 数据结构还要提供每种结构类型所定义的各数据结构还要提供每种结构类型所定义的各种运算的算法。种运算的算法。例2、图书馆的书目检索系统自动化问题例3、教师资料档案管理系统例4、多叉路口交通灯的管理问题 通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 1.2 1.2 基本概念和术语基本概念和术语数据数据(Data(Data): ):是对信息的
6、一种符号表示。在计算是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。程序处理的符号的总称。数据元素数据元素(Data Element(Data Element): ):是数据的基本单位，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处在计算机程序中通常作为一个整体进行考虑和处理。理。 一个数据元素可由若干个数据项组成。数据一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。项是数据的不可分割的最小单位。数据对象数据对象(Data Object)(Data Object)：是性质相
7、同的数据元素是性质相同的数据元素的集合。是数据的一个子集。的集合。是数据的一个子集。数据结构数据结构(Data Structure)(Data Structure)：是相互之间存在一是相互之间存在一种或多种特定关系的数据元素的集合。种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为数据之间的相互关系称为逻辑结构。通常分为四类基本结构：四类基本结构：一、一、集合集合 结构中的数据元素除了同属于一种类结构中的数据元素除了同属于一种类型外，别无其它关系。型外，别无其它关系。二、二、线性结构线性结构 结构中的数据
8、元素之间存在一对结构中的数据元素之间存在一对一的关系。一的关系。三、三、树型结构树型结构 结构中的数据元素之间存在一结构中的数据元素之间存在一对多的关系。对多的关系。四、四、图状结构或网状结构图状结构或网状结构 结构中的数据元素之结构中的数据元素之间存在多对多的关系。间存在多对多的关系。 数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组： Data-Structure=(DData-Structure=(D，S)S)其中：其中：D D是数据元素的有限集，是数据元素的有限集，S S是是D D上关系的有上关系的有限集。限集。例例 复数的数据结构定义如下：复数的
9、数据结构定义如下： Complex=(CComplex=(C，R)R)其中：其中：C C是含两个实数的集合是含两个实数的集合C1C1，C2C2，分别分别表示复数的实部和虚部。表示复数的实部和虚部。R=PR=P，P P是定义在集合是定义在集合上的一种关系上的一种关系 C1C1，C2C2 。数据结构在计算机中的表示称为数据的数据结构在计算机中的表示称为数据的物理结构物理结构，又称为又称为存储结构存储结构。 数据对象可以是有限的，也可以是无限的。数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而
10、且要描述它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。数据对象各元素之间的相互关系。抽象数据类型：一个数学模型以及定义在该模型抽象数据类型：一个数学模型以及定义在该模型上的一组操作。上的一组操作。抽象数据类型实际上就是对该数据结构的定抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。结构上的一组算法。用三元组描述如下：用三元组描述如下：（，）（，）数据结构在计算机中有两种不同的表示方法：数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示顺序表示和非顺序表示由此得出两种
11、不同的存储结构：由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个在每一个数据元素中增加一个存放地址的指针（存放地址的指针（ ），用此指针来表示数据元素），用此指针来表示数据元素之间的逻辑关系。之间的逻辑关系。数据类型数据类型：在一种程序设计语言中，变量所具：在一种程序设计语言中，变量所具有的数据种类。有的数据种类。例例1 1、 在在FORTRANFORTRAN语言中，变量的数据类型语言中，变量的数据类型有整型、实型、和
12、复数型有整型、实型、和复数型 例例2 2、在、在C C语言中语言中数据类型：基本类型和构造类型数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、构造类型：数组、结构、联合、指针、枚举型、自定义自定义数据对象数据对象：某种数据类型元素的集合。：某种数据类型元素的集合。例例3 3、整数的数据对象是、整数的数据对象是-3-3，-2-2，-1-1，0 0，1 1，2 2，3 3，英文字符类型的数据对象是英文字符类型的数据对象是AA，B B，C C，D D，E E，F F， 1.3 抽象数据类型的表示和实现抽象数据类型通常是
13、指由用户定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记录(record)类型和c语言中的构造(struct)类型，但它增加了相关的服务。在计算机中使用二进制定点数和浮点数实现数据的存储和运算，而在汇编中给出数据的自然表示，到了高级语言，给出了更高一级的数据抽象，出现了整形、实型、字符型、双精度行。待到抽象数据类型出现时，可以进一步定义出更高级的数据抽象。如各种表、队列、图、甚至窗口、管理器等。抽象数据类型的特征是使用和实现分离，实行封装和信息隐蔽。下面我们给出自然数下面我们给出自然数(natur
14、al number)(natural number)的抽象的抽象数据类型定义：数据类型定义：ADT ADT naturalnumbernaturalnumber is isObjects:Objects:Function:Function:Zero():naturalnumberZero():naturalnumberIszero(x):booleanIszero(x):booleanAdd(x,y):nuturalnumberAdd(x,y):nuturalnumberEqual(x,y):booleanEqual(x,y):booleanSuccessor(x):naturalnumber
15、Successor(x):naturalnumberSubtract(x,y):naturalnumberSubtract(x,y):naturalnumberEnd End naturalnumbernaturalnumber 1.4 1.4 算法和算法分析算法和算法分析算法算法：是对特定问题求解步骤的一种描述：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令算法是指令的有限序列，其中每一条指令表示一个或多个操作。表示一个或多个操作。 算法具有以下五个特性：算法具有以下五个特性：（1 1）有穷性有穷性 一个算法必须总是在执行有穷步一个算法必须总是在执行有穷步之后结束，且每
16、一步都在有穷时间内完成。之后结束，且每一步都在有穷时间内完成。（2 2）确定性确定性 算法中每一条指令必须有确切的算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和含义。不存在二义性。且算法只有一个入口和一个出口。一个出口。（3 3）可行性可行性 一个算法是可行的。即算法描述一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行的操作都是可以通过已经实现的基本运算执行有限次来实现的。有限次来实现的。4 4）输入输入 一个算法有零个或多个输入，这些输一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。入取自于某个特定的对象集合。5 5）输出输出 一个算法有
17、一个或多个输出，这些输一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。出是同输入有着某些特定关系的量。1.4.2 1.4.2 算法设计的要求算法设计的要求评价一个好的算法有以下几个标准评价一个好的算法有以下几个标准: :(1) (1) 正确性正确性(Correctness )(Correctness ) 算法应满足具体问算法应满足具体问题的需求。题的需求。(2)(2)可读性可读性(Readability)(Readability) 算法应该好读。以算法应该好读。以有利于阅读者对程序的理解。有利于阅读者对程序的理解。 (3)(3)健状性健状性(Robustness)(Robust
18、ness) 算法应具有容错处理。算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。不是产年莫名其妙的输出结果。(4)(4)效率与存储量需求效率与存储量需求 效率指的是算法执行的效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有最大存储空间。一般，这两者与问题的规模有关。关。1.4.3 1.4.3 算法效率的度量算法效率的度量 对一个算法要作出全面的分析可分成两用人对一个算法要作出全面的分析可分成两用人才个阶段进行，即才个阶段进行
19、，即事先分析事先分析和和事后测试事后测试事先分析事先分析 求出该算法的一个时间界限函数求出该算法的一个时间界限函数事后测试事后测试 收集此算法的执行时间和实际占用收集此算法的执行时间和实际占用空间的统计资料。空间的统计资料。定义：如果存在两个正常数定义：如果存在两个正常数c c和和n n0 0，对于所有对于所有的的n nn n0 0，有，有f(n) f(n) c cg(n) g(n) 则记作则记作 f(n)=O(g(n)f(n)=O(g(n)一般情况下，算法中基本操作重复执行的次数是问一般情况下，算法中基本操作重复执行的次数是问题规模题规模n n的某个函数，算法的时间量度记作的某个函数，算法的
20、时间量度记作 T(n)=O(f(n)T(n)=O(f(n)称作算法的渐近时间复杂度。称作算法的渐近时间复杂度。例、例、for(I=1for(I=1，I=n;+I)I=n;+I) for(j=1;j=n;+j) for(j=1;j=n;+j) cIj=0; cIj=0; for(k=1;k=n;+k) for(k=1;k=n;+k) cIj+=aIk*bkj; cIj+=aIk*bkj; 由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总则总次数为次数为: nnn=n: nnn=n3 3时间复杂度为时间复杂度为T(n)=O(nT(n)=O(n3 3) )频度：是指
21、该语句重复执行的次数：是指该语句重复执行的次数例例 +x;s=0;+x;s=0;将将x x自增看成是基本操作，则语句频度为，自增看成是基本操作，则语句频度为，即时间复杂度为即时间复杂度为(1)(1)如果将如果将s=0s=0也看成是基本操作，则语句频度为也看成是基本操作，则语句频度为，其时间复杂度仍为，其时间复杂度仍为(1)(1)，即常量阶。，即常量阶。例、例、for(I=1;I=n;+I)for(I=1;I=n;+I) +x;s+=x; +x;s+=x; 语句频度为：语句频度为：2n2n其时间复杂度为：其时间复杂度为：O(n)O(n) 即时间复杂度为线性阶。即时间复杂度为线性阶。例、例、for
22、(I=1;I=n;+I)for(I=1;I=n;+I)for(j=1;j=n;+j)for(j=1;j=n;+j) +x;s+=x; +x;s+=x; 语句频度为：语句频度为：2n2n2 2其时间复杂度为：其时间复杂度为：O(nO(n2 2) ) 即时间复杂度为平方阶。即时间复杂度为平方阶。定理：若定理：若A(n)=a A(n)=a m m n n m m +a +a m-1m-1 n n m-1m-1 +a +a1 1n+an+a0 0是一个是一个mm次多项式，则次多项式，则A(n)=O(nA(n)=O(n m m) )证略。证略。例例for(i=2;i=n;+I)for(i=2;i=n;+
23、I) for(j=2;j=i-1;+j) for(j=2;j=i-1;+j) +x;ai +x;ai，j=x;j=x;语句频度为：语句频度为： 1+2+3+n-2=(1+n-2) (n-2)/21+2+3+n-2=(1+n-2) (n-2)/2 =(n-1)(n-2)/2 =(n-1)(n-2)/2 =n =n2 2-3n+2-3n+2 时间复杂度为时间复杂度为O(nO(n2 2) ) 即此算法的时间复杂度为平方阶即此算法的时间复杂度为平方阶. . 一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常执行的次数是固定的。
24、因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为数（即零次多项式）来限界。而一个时间为O(nO(n2 2) )的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。 以下六种计算算法时间的多项式是最常用的。其以下六种计算算法时间的多项式是最常用的。其关系为：关系为： O(1)O(1)O(lognO(logn)O(n)O(n)O(nlognO(nlogn) ) O(n O(n2 2)O(n)O(n3 3) )指数时间的关系为：指数时间的关系为： O(2O(2n n)O(n!)O(n!)1 & change;- for(I=n-1;change=TURE;I1 & chang
25、e;-I) I) change=false; change=false; for(j=0;jI;+j) for(j=0;jaj+1) if (ajaj+1) aj aj+1; aj aj+1; change=TURE change=TURE 最好情况：最好情况：0 0次次 最坏情况：最坏情况：1+2+3+n-11+2+3+n-1 =n(n-1)/2 =n(n-1)/2 平均时间复杂度为平均时间复杂度为:O(n:O(n2 2) )1.4.4 1.4.4 算法的存储空间需求算法的存储空间需求空间复杂度空间复杂度: :算法所需存储空间的度量，记作算法所需存储空间的度量，记作: : S(n)=O(f(
26、n) S(n)=O(f(n) 其中其中n n为问题的规模为问题的规模( (或大小或大小) )程序所用的存储空间包括两个部分：程序所用的存储空间包括两个部分： 固定部分固定部分 可变部分可变部分1 1、固定部分：、固定部分：这部分空间的大小与输入输出的个数多少、数值这部分空间的大小与输入输出的个数多少、数值大小无关。主要包括存放程序指令代码的空间，大小无关。主要包括存放程序指令代码的空间，常数、简单变量、定长成分（如数组元素、结构常数、简单变量、定长成分（如数组元素、结构成分、对象的数据成员等）变量所占的空间等。成分、对象的数据成员等）变量所占的空间等。这部分属于静态空间，只要作简单的统计就可估这部分属于静态空间，只要作简单的统计就可估算。算。2 2、可变部分：、可变部分：这部分空间主要包括其尺寸与实例特征有关的成这部分空间主要包括其尺寸与实例特征有关的成分变量所占空间、引用变量所占空间、以及递归分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有算法运行时动态命令使用的栈所用的空间，还有算法运行时动态命令使用的空间。空间。
