计算机是一门研究用计算机进行信息表示和处理的科学这

《计算机是一门研究用计算机进行信息表示和处理的科学这》由会员分享，可在线阅读，更多相关《计算机是一门研究用计算机进行信息表示和处理的科学这（24页珍藏版）》请在金锄头文库上搜索。

1、 第一章 绪 论计算机是一门研究用计算机进行信息表示和处理 的科学。这里面涉及到两个问题： 信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程 序的效率。随着计算机的普及，信息量的增加， 信息范围的拓宽，使许多系统程序和应用程序的 规模很大，结构又相当复杂。因此，为了编写出 一个“好”的程序，必须分析待处理的对象的特征 及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。 1.1什么是数据结构 众所周知，计算机的程序是对信息进行加工处理。 在大多数情况下，这些信息并不是没有组织，信息（ 数据）之间往往具有重要的结构关系，这就是数据结 构的内容。那么，什么是数据结构呢？先看以

2、下几个 例子。 例1、电话号码查询系统 设有一个电话号码薄，它记录了N个人的名字和其 相应的电话号码，假定按如下形式安排： (a1，b1)(a2，b2)(an，bn)其中ai，bi(i=1，2n) 分别表示某人的名字和对应的 电话号码要求设计一个算法，当给定任何一个人的名 字时，该算法能够打印出此人的电话号码，如果该电 话簿中根本就没有这个人，则该算法也能够报告没有 这个人的标志。 算法的设计，依赖于计算机如何存储人的名 字和对应的电话号码，或者说依赖于名字和其电 话号码的结构。 数据的结构，直接影响算法的选择和效率。 上述的问题是一种数据结构问题。可将名字 和对应的电话号码设计成：二维数组、

3、表结构、 向量。假定名字和其电话号码逻辑上已安排成N元 向量的形式，它的每个元素是一个数对(ai，bi)， 1in 数据结构还要提供每种结构类型所定义的各 种运算的算法。例2、图书馆的书目检索系统自动化问题 例3、教师资料档案管理系统 例4、多叉路口交通灯的管理问题通过以上几例可以直接地认为：数据结构就是研究数据的逻辑结构和物理结构以及它们 之间相互关系，并对这种结构定义相应的运算， 而且确保经过这些运算后所得到的新结构仍然 是原来的结构类型。 1.2 基本概念和术语数据(Data):是对信息的一种符号表示。在计算 机科学中是指所有能输入到计算机中并被计算机 程序处理的符号的总称。数据元素(D

4、ata Element):是数据的基本单位，在 计算机程序中通常作为一个整体进行考虑和处理 。 一个数据元素可由若干个数据项组成。数据 项是数据的不可分割的最小单位。数据对象(Data Object)：是性质相同的数据元素 的集合。是数据的一个子集。数据结构(Data Structure)：是相互之间存在一 种或多种特定关系的数据元素的集合。数据结构主要指逻辑结构和物理结构 数据之间的相互关系称为逻辑结构。通常分为 四类基本结构：一、集合 结构中的数据元素除了同属于一种类 型外，别无其它关系。二、线性结构 结构中的数据元素之间存在一对 一的关系。三、树型结构 结构中的数据元素之间存在一 对多的

5、关系。四、图状结构或网状结构 结构中的数据元素之 间存在多对多的关系。 数据结构的形式定义为：数据结构是一个二元组 ：Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有 限集。 例 复数的数据结构定义如下：Complex=(C，R) 其中：C是含两个实数的集合C1，C2，分别 表示复数的实部和虚部。R=P，P是定义在集合 上的一种关系C1，C2。 数据结构在计算机中的表示称为数据的物理结构 ，又称为存储结构。 数据对象可以是有限的，也可以是无限的。 数据结构不同于数据类型，也不同于数据对象 ，它不仅要描述数据类型的数据对象，而且要描 述数据对象各元素之间的相

6、互关系。抽象数据类型：一个数学模型以及定义在该模型 上的一组操作。 抽象数据类型实际上就是对该数据结构的定 义。因为它定义了一个数据的逻辑结构以及在此 结构上的一组算法。 用三元组描述如下： （，）数据结构在计算机中有两种不同的表示方法： 顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构 和链式存储结构顺序存储结构:用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素中增加一个 存放地址的指针（ ），用此指针来表示数据元素 之间的逻辑关系。数据类型：在一种程序设计语言中，变量所具 有的数据种类。例1、 在FORTRAN语言中，变量的数据类型

7、有整型、实型、和复数型 例2、在C语言中数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型 、自定义数据对象：某种数据类型元素的集合。例3、整数的数据对象是-3，-2，-1，0，1 ，2，3，英文字符类型的数据对象是A，B，C，D，E ，F， 1.3 抽象数据类型的表示和实现抽象数据类型通常是指由用户定义，用以 表示应用问题的数据类型，抽象数据类型 由基本的数据类型组成，并包括一组相关 的服务（或称操作）。抽象数据类型有些类似于pascal语言中的记 录(record)类型和c语言中的构造(struct)类 型，但它增加了相关的服务。在计算机中使

8、用二进制定点数和浮点数实 现数据的存储和运算，而在汇编中给出数 据的自然表示，到了高级语言，给出了更 高一级的数据抽象，出现了整形、实型、 字符型、双精度行。待到抽象数据类型出现时，可以进一步定 义出更高级的数据抽象。如各种表、队列 、图、甚至窗口、管理器等。抽象数据类型的特征是使用和实现分离， 实行封装和信息隐蔽。下面我们给出自然数(natural number)的抽象 数据类型定义：ADT naturalnumber isObjects:Function:Zero():naturalnumberIszero(x):booleanAdd(x,y):nuturalnumberEqual(x,y

9、):booleanSuccessor(x):naturalnumberSubtract(x,y):naturalnumberEnd naturalnumber 1.4 算法和算法分析算法：是对特定问题求解步骤的一种描述 算法是指令的有限序列，其中每一条指令 表示一个或多个操作。 算法具有以下五个特性：（1）有穷性 一个算法必须总是在执行有穷 步之后结束，且每一步都在有穷时间内完成。（2）确定性 算法中每一条指令必须有确切的 含义。不存在二义性。且算法只有一个入口和 一个出口。（3）可行性 一个算法是可行的。即算法描述 的操作都是可以通过已经实现的基本运算执行 有限次来实现的。4）输入 一个算法

10、有零个或多个输入，这些输 入取自于某个特定的对象集合。5）输出 一个算法有一个或多个输出，这些输 出是同输入有着某些特定关系的量。1.4.2 算法设计的要求评价一个好的算法有以下几个标准:(1) 正确性(Correctness ) 算法应满足具体问 题的需求。(2)可读性(Readability) 算法应该好读。以有 利于阅读者对程序的理解。(3)健状性(Robustness) 算法应具有容错处理 。当输入非法数据时，算法应对其作出反应， 而不是产年莫名其妙的输出结果。(4)效率与存储量需求 效率指的是算法执行的 时间；存储量需求指算法执行过程中所需要的 最大存储空间。一般，这两者与问题的规模

11、有 关。1.4.3 算法效率的度量 对一个算法要作出全面的分析可分成两用人 才个阶段进行，即事先分析和事后测试事先分析 求出该算法的一个时间界限函数事后测试 收集此算法的执行时间和实际占用 空间的统计资料。定义：如果存在两个正常数c和n0，对于所有 的nn0，有f(n) cg(n) 则记作 f(n)=O(g(n) 一般情况下，算法中基本操作重复执行的次数是问 题规模n的某个函数，算法的时间量度记作T(n)=O(f(n) 称作算法的渐近时间复杂度。 例、for(I=1，I1 - I) change=false; for(j=0;jaj+1) aj aj+1; change=TURE 最好情况：0

12、次最坏情况：1+2+3+n-1 =n(n-1)/2 平均时间复杂度为:O(n2)1.4.4 算法的存储空间需求空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小)程序所用的存储空间包括两个部分： 固定部分 可变部分1、固定部分：这部分空间的大小与输入输出的个数多少、数值 大小无关。主要包括存放程序指令代码的空间， 常数、简单变量、定长成分（如数组元素、结构 成分、对象的数据成员等）变量所占的空间等。 这部分属于静态空间，只要作简单的统计就可估 算。2、可变部分：这部分空间主要包括其尺寸与实例特征有关的成 分变量所占空间、引用变量所占空间、以及递归 栈所用的空间，还有算法运行时动态命令使用的 空间。