文档介绍：(算法+数据结构) 程序
计算机能快速计算,能证明“四色定理”,能帮助工程师设计图纸,能帮助医生为病人
诊断配药⋯⋯它之所以如此神通广大、聪明能干,是因为人们教给了它本领。人是用“程
序”来“教”计算机的。要想让计算机具备解题的能力,就要为计算机编写程序。随着计算
机科学与技术的不断发展,计算机的应用领域也在不断扩大“。程序”越来越庞大、越来越
复杂,因而解题的过程就不仅仅是编写程序了,而是一个包括编程序在内的软件开发过
程,该过程包括对用户的需求进行分析,对要开发的系统进行软件设计,然后编程序,再进
行测试和改错,最后再运行等一系列的工作“。软件”不单纯是指程序,而是指程序以及开
发程序的过程中所产生的各种文档。软件开发的目的是产生能让计算机有效工作的程序,
因此程序是软件的核心
程序到底是什么呢?计算机科学家,图灵奖获得者给出过一个著名的公式:
算法+数据结构程序。从这个公式可以看到,数据结构和算法是构成程序的两个同样重
要的组成部分。这个公式在软件开发的进程中产生了深远的影响。但是它并没有强调数
据结构与解题的算法是一个整体。该公式现在已经受到了挑战。
我们知道,非面向对象的过程语言,如和,其数据结构是问
题解的中心。一个软件系统的结构是围绕一个或几个关键数据结构为核心而组成的。“算
法+数据结构程序”完全体现了这种思想。但随着软件系统的规模越来越大、复杂性不
断增长,人们不得不对“关键数据结构”重新评价。在这种系统中,许多过程和函数(子程
序)的实现严格依赖于关键数据结构,如果这些关键数据结构的一个或几个数据有所改
变,则涉及到整个软件系统,许多过程和函数必须重写,甚至因为几个关键数据结构的改
变,导致软件系统整个结构彻底崩溃。
世纪年代,面向对象的方法得到了很大的重视,并得到了比较广泛的推广和应
用。在面向对象程序设计中,密切相关的数据与过程被定义为一个整体(即对象),而且一
旦作为一个整体定义了之后,就可以使用它,而无需了解其内部的实现细节,从而提高软
件开发的效率。
封装和数据隐藏是面向对象问题解和面向对象程序设计的基本要素。它可以使软件
的许多维护问题简单化。一旦数据(类型)结构修改了,只要对实现模型的局部代码作适当
修改,软件系统的其余部分无需修改。
有人主张将的公式“算法十数据结构程序”修改为“(算法+数据结构) 程
序”,以体现面向对象的方法。
本书以面向对象的观点来介绍各种数据结构以及与这些数据结构有关的算法的知
识。
本章将介绍数据结构以及算法的基本概念,并介绍用来描述数据结构和算法的语言
+ 。
数据结构的基本概念
计算机科学是一门研究信息表示和处理的科学,人们是用程序来处理信息的。信息的
表示和组织直接关系到处理信息的程序的效率。由于许多系统软件和应用软件的程序规
模很大,结构又相当复杂,因而必须对程序设计方法进行系统的研究。这不仅涉及到研究
程序结构和算法,同时也涉及到研究程序加工的对象。
用计算机解题,首先应从具体问题抽象出一个适当的数学模型,然后才能设计算法和
编制程序。而构建数学模型的过程就是分析和概要设计的过程,要从对问题的分析中提取
操作的对象,并找出这些操作对象之间的关系,然后用数学的语言加以描述。例如,许多工
程中的数值计算问题采用的数学模型是线性方程组或微分方程。但更多的非数值计算问
题是难以用数学方程来描述的。
两个简单的数据结构实例
为了获得对数据结构的感性认识,我们先来看两个简单的例子。
【例】人事登记表。
在任何一个单位,人事登记表是人事部门关于职工信息的必不可少的表格。例如,某
个单位人事部门的工作人员想要查找当年退休的人员,或要查找基本工资在元以下
的人员,如果该单位有千名职工,那么由人工来查找显然是很费时的;但如果在计算机
中有一个关于职工信息的登记表,由有关的检索系统来查找,那是很方便的。表所示
就是一张简单的人事登记表。
表人事登记表
表中,每个职工的信息放在一行中,我们称之为一个数据元素,所有职工的信息
按照某一种顺序依次存放在表中。一般称这种由记录组成的线性表为文件。
类似这样表格在不同的计算机软件系统中是很多的,如学校的学生信息管理系统中
的学生学籍登记表、图书馆管理系统中的图书目录表等。这类表格有一个共同的特性,就
是各数据元素之间的关系是线性的关系,即一个元素的前面只有一个元素,后面也只有一
个元素,第一个数据元素前面和最后一个数据元素后面没有元素。这样的一类表格就是一
种数据结构,称为线性数据结构。
【例】一个典型的学