第1章 绪论
随着计算机产业的飞速发展,计算机的应用领域越来越广泛,已不再局限于科学计算,而是更多地用于控制、管理及数据处理等非数值计算的处理工作。所有的系统软件和应用软件都要用到各种类型的数据结构,在计算机中如何组织数据、处理数据就成了人们进行程序设计的关键所在。因此,我们必须研究数据的特性和数据间的相互关系及其对应的存储表示,并设计出相应的算法,更好地实现程序。数据结构是计算机专业的核心课程,该课程的学习可以帮助人们更好地进行程序设计,解决实际问题。
11数据结构的研究对象
自然界中的许多问题是可以用数学工具进行描述的。例如,造桥中的受力问题可描述为线性方程,人口增长的情况可描述为微分方程。但更多的非数值计算问题无法用数学方程加以描述。因此,解决这类问题的关键不再是数学分析��计算方法,而是要设计出合适的数据结构,才能有效地解决问题。请看以下列举的具体问题。
例1学生信息检索系统。当我们需要查找某个学生的有关信息或某个专业的情况时,只要建立了相应的数据结构,按照某种算法编写了程序,就可以实现计算机自动检索。由此,可以在学生信息检索系统中建立一个按学号顺序排列的学生信息表和按专业排列的索引表,如表11所示。由这个表构成的文件便是学生信息检索的数学模型,计算机的操作就是按照某种要求对学生信息文件进行查询。
表11学生信息查询系统中的数据结构
a)学生信息表
学号姓名性别专业年级
200701002001韦志君男信息管理与信息系统2007级
200701001088唐立男计算机科学与技术2007级
200701002002宋奇锋男信息管理与信息系统2007级
200701001089熊伟男计算机科学与技术2007级
200701001091许文锋男计算机科学与技术2007级
200701002003张小龙男信息管理与信息系统2007级
200701002004陈亚雯女信息管理与信息系统2007级
200701001084彭金萍女计算机科学与技术2007级
b)专业索引表
信息管理与信息系统1,3,6,7
计算机科学与技术2,4,5,8
诸如此类的还有电话自动查号系统、考试查分系统、仓库库存管理系统等。在这类文档管理的数学模型中,计算机处理的对象之间存在一种简单的线性关系,因此这类数学模型可称为线性数据结构。
例2八枚硬币问题。假设有八枚硬币,分别表示为a,b,c,d,e,f,g,h,其中有且仅有一枚硬币是假币,并且假币的重量与真币的重量不同,可能比真币轻,也可能比真币重。现要求以天平为工具,用*少的比较次数挑选出假币,并同时确定这枚假币的重量比其他真币轻还是重。解决这个问题的*自然的想法就是把硬币分成两组,依次进行判断。其判断的全过程如图11所示。这里用到的是树形数据结构。
图11八枚硬币问题的数据结构
例3教学计划编排问题。一个教学计划包含许多课程,在这些课程之间,有些课程要按规定的先后次序进行,有些则没有次序要求。也就是说,有些课程之间有先修和后继的关系,有些课程可以任意安排次序。假设计算机专业的课程设置如表12所示,则这些课程之间的次序关系可以用一个称为有向图的数据结构来表示,如图12所示。有向图的每个结点表示一门课程,若从结点Ci到Cj之间存在有向边,则表示课程Ci必须先于课程Cj开设;若两门课程之间没有有向边,则表示这两门课程之间没有开设的先后次序。
表12计算机专业的课程设置
课 程 编 号课 程 名 称先 修 课 程
C1计算机导论无
C2高等数学无
C3C语言程序设计C1
C4离散数学C2,C3
C5数据结构C1,C3,C4
C6汇编语言C1,C3
C7接口技术C6
C8操作系统C5
C9数据库原理C5,C8
C10编译原理C3
图12教学计划编排问题的数据结构
由以上例子可知,描述这类非数值计算问题的数学模型不再是数学方程,而是诸如表、树、图之类的数据结构。使用计算机解决这些实际问题,大致需要经过下列三个步骤:
1)从具体问题中抽象出一个适当的数学模型。
2)设计一个解此数学模型的算法。
3)编出程序、进行测试、调整直至得到*终答案。
数据结构这门课程就是要解决这三个步骤中的**步和第二步中所提到的问题。建立数学模型的实质是分析问题,从中提取操作的对象,并找出这些操作对象之间含有的关系,然后用数学的语言加以描述。设计解数学模型的算法就是给出处理问题的策略。
概括地说,数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。实质上,好的程序设计就是好的算法加上好的数据结构。
数据结构在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及计算机硬件(特别是编码理论、存储装置和存取方法等)的研究范围,而且和计算机软件的研究有着密切的关系,无论是编译程序还是操作系统,都涉及数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据,以便更为方便地查找和存取数据元素。因此,数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。在计算机科学中,数据结构不仅是一般程序设计(特别是非数值计算的程序设计)的基础,而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
数据结构课程集中讨论软件开发过程中的设计阶段,同时涉及编码和分析阶段的若干基本问题。此外,为了构造好的数据结构及其实现,还需考虑数据结构及其实现的评价与选择。因此,数据结构的内容包括3个层次的5个要素,如表13所示。
表13数据结构课程的内容体系