计算机软件基础知识

第1 章计算机软件基础知识

1.1 数据结构与算法

借助于计算机解决问题,首先需要了解所处理对象的性质和特点即所操作对象的数据结构,然后再设计解决问题的方法和步骤即设计一个合理的算法,即通常所说的“程序=数据

结构+算法”。

1.1.1 算法的基本概念

“算法”(Algorithm)一词最早来自公元9 世纪波斯数学家比阿勒·霍瓦里松的一本

影响深远的著作«代数对话录»。20 世纪的英国数学家图灵提出了著名的图灵论点,并抽

象出了一台机器,这台机器被我们称之为图灵机。图灵的思想对算法的发展起到了重要的作用。一般来说,算法是指完成一个任务或解决一个问题所需要的具体步骤和方法的描述。在这里我们说的算法是指计算机能执行的算法。

1.算法分类

计算机算法可分为两大类,一类是数值运算算法,另一类是非数值运算算法。数值运算

算法主要是求数值解,如求方程的解、求函数的定积分等,非数值运算的范围则非常广泛,

如人事管理、图书检索等。

2.算法特征

一个科学的算法必须具备以下特征:

(1)有穷性:一个算法必须保证执行有限步之后结束,而不能是无限的。这是显而易见

的。更进一步说,有穷性是指在合理的范围内结束运算,如果一个算法需计算机执行几

百年或更长时间才结束,这显然是不合理的。

(2)确定性:算法的每一步骤必须有确切的定义而不能模棱两可,算法中不能出现诸如

“一个比较大的数”等模糊描述。

(3)有零个或多个输入

(4)有一个或多个输出。算法的目的是为了解决问题,一个没有输出的算法是不能解决任

何问题因而它是没有意义的.

(5)有效性。算法中的每一个步骤都都应当能有效地执行,并得到确定的结果。例如,

若n=0 则执行m/n 是无法有效执行的。

3.算法表示

一个计算机算法可以用自然语言、流程图、N-S 图等来表示。

4.算法分析

算法分析的任务是对设计出的每一个具体的算法,利用数学工具,讨论各种复杂度,以

探讨某种具体算法适用于哪类问题,或某类问题宜采用哪种算法。

算法的复杂度分时间复杂度和空间复杂度。

.时间复杂度:在运行算法时所耗费的时间为f(n)(即n 的函数)。

.空间复杂度:实现算法所占用的空间为g(n)(也为n 的函数)。

称O(f(n))和O(g(n))为该算法的复杂度。

1.1.2 数据结构的定义

数据结构是计算机科学与技术领域上广泛被使用的术语。尽管它至今还未有一个被一致

公认的定义,但其内容是大家一致公认的。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。

数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的

集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。

一般数据结构可采用下面两类主要的存储方式,大多数数据结构的存储表示都采用其中的

第1页下一页