“数据结构与算法”是软件开发技术的一门重要的专业基础课程。课程主要讨论现实世界中数据之间的各种逻辑结构、在计算机中的存储结构以及各种算法的设计问题。本书讨论的内容包括：线性表、堆栈、队列、串、数组、树、图、查找、排序。其中，线性表、堆栈、队列、串、数组属于线性结构，树和图是非线性结构，查找和排序是两个应用广泛的算法设计问题。
第1章绪论
本章介绍“数据结构与算法”这门课程的相关知识,包括数据结构的概念、课程的主要内容、三种基本逻辑结构、算法的概念和算法评价的度量。通过本章的学习,应能使学生对“数据结构与算法”这门课程有一个基本的了解。
【技能目标】
会用数据结构的概念解释日常生活的问题。
掌握逻辑结构、存储结构的概念。
能找到现实生活中线性、树和图三种结构的实例。
掌握算法的五个特性准则。
会用算法效率的评价指标评价算法的执行效率。
1.1学习数据结构的意义
早期人们都感觉计算机是用来计算的,用来处理数值计算非常方便快捷。随着计算机处理能力越来越强,计算机不再只是简单的数值计算工具,而是被赋予越来越多的功能。现实世界有很多非数值计算的问题,需要一些更科学更有效手段的帮助才能更好地处理这些问题。所以数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作等相关问题的学科。
针对实际问题,要编写出高效率的处理程序,就需要解决如何合理地组织数据,建立合适的数据结构,设计较好的算法,来提高程序执行效率这样的问题。数据结构和算法就是在此背景下形成和发展起来的。
简而言之,软件开发要多动脑筋,想到好的解决办法才能更快更好地编写出效率更高的程序。“数据结构和算法”这门课程的目的正是使学生更快地编写出更高效的程序。
1.1.1引言
计算机完成的任何操作都是在程序的控制下进行的,而程序的根本任务就是进行数据处理。随着计算机在各行各业应用的日益深入,计算机所处理的数据对象也由纯粹的数值型发展到字符、表格、图形、图像和声音等多种形式,计算机要处理这些数据,首先要将这些数据存储在计算机内存中。如何将程序中要处理的数据进行合理地存储,以及采用何种方法能够高效地进行数据处理,是程序设计的关键,也是数据结构要解决的重要问题。
即使是在广泛采用可视化程序设计的今天,借助于集成开发环境可以很快地生成程序,但要想成为一个专业的程序开发人员,至少需要具备以下三个条件。
(1)能够熟练地选择和设计各种业务逻辑的数据结构和算法。
(2)至少能够熟练地掌握一门程序设计语言。
(3)熟知所涉及的相关应用领域知识。
其中,后两个条件比较容易实现,而第一个条件则需要花很多时间和精力才能够达到,而它恰恰是区分程序设计人员水平高低的一个重要标志。数据结构贯穿程序设计的始终,缺乏数据结构和算法的功底,很难设计出高水平的具有专业水准的应用程序。著名的瑞士计算机科学家尼古拉斯·沃斯(NiklausWirth)提出了“算法+数据结构=程序”的观点,正说明了数据结构的重要性。
例如,计算机要处理一批杂乱无章的数据,需对其进行有序化处理,计算机解决问题的步骤是什么呢?
要解决这个问题,首先要考虑应如何将这批数据进行合理地存储;然后考虑应采用什么有效的方法对这些数据进行有序化;最后选择一种编程语言实现以上方法。其实用计算机解决任何数据处理的问题,都需要经过以上过程才能实现。
数据结构主要研究和讨论以下三个方面的问题。
(1)数据集合中各数据元素之间的关系。
(2)在对数据进行处理时,各数据元素在计算机的存储关系,即数据的存储结构。
(3)针对数据的存储结构进行的运算。
解决好以上问题,可以大大提高数据处理的效率。
1.1.2数据结构研究什么
数据结构可定义为一个二元组:Data_Structure=(D,R),其中D表示数据元素的有限集,R表示D之间的关系。数据结构与算法具体应包括以下方面:逻辑结构、逻辑结构的延伸及基本算法、物理结构和运算集合。
1.逻辑结构
数据的逻辑结构是指数据元素之间逻辑关系的描述。根据数据元素之间关系的特性,数据结构有三种基本的逻辑结构,如图1.1所示。
图1.1三种基本逻辑结构
(1)线性结构。结构中的数据元素之间存在一对一的线性关系。线性结构将在第2章详细讲解。
(2)树结构。结构中的数据元素之间存在一对多的层次关系。树结构将在第6章详细讲解。
(3)图结构。结构中的数据元素之间存在多对多的任意关系。图结构将在第7章详细讲解。
2.逻辑结构的延伸及基本算法
(1)串。串是字符串的简称,它的每个数据元素都由一个字符组成。串是一种特殊的线性结构。串结构将在第4章详细讲解。
(2)数组。数组是一种数据类型,它是一种顺序存储结构。将在第5章中详细讲解数组中各个元素的相对存放位置,以及用数组存放特殊矩阵,并实现矩阵的运算。
(3)查找。数据结构要跟算法结合起来才有意义,查找算法是数据结构在各种算法中的基本应用,在现实生活中也经常用到这种算法。查找算法将在第8章详细讲解。
(4)排序。排序算法将在第9章中详细讲解。
3.物理结构
物理结构(又称存储结构)是逻辑结构在计算机中的存储映像,是逻辑结构在计算机中的实现(或存储表示),它包括数据元素的表示和关系的表示。有数据结构Data_Structure=(D,R),对于D中的每一数据元素都对应着存储空间中的一个单元,D中全部元素对应的存储空间必须明显或隐含地体现关系R。逻辑结构与存储结构的关系为:存储结构是逻辑结构的映像与元素本身的映像。逻辑结构是抽象,存储结构是实现,两者综合起来建立了数据元素之间的结构关系。存储结构一般有顺序存储和链表存储两种方式。
4.运算集合
讨论数据结构的目的是为了在计算机中实现所需的操作,施加于数据元素之上的一组操作构成了数据的运算集合,因此运算集合是数据结构很重要的组成部分。
1.2数据结构的基本概念
数据结构有以下这些基本概念。
1.数据
数据是描述客观事物的数值、字符以及所有其他能输入计算机中,且能被计算机处理的各种符号的集合。简言之,数据就是存储在计算机中的信息。
数据不仅仅包括整型、实型等数值类型,还包括字符、声音、图像、视频等非数值类型。比如,现在常用的搜索引擎一般会有网页、图片、音乐、视频等分类。音乐就是声音数据;图片是图像数据;网页就是全部数据的集合,包括数字、字符和图像等数据。
2.数据元素
数据元素是组成数据的基本单位,是数据集合的个体,在计算机中通常作为一个整体进行考虑和处理。
比如,在学生这个群体中,每一个学生就是数据元素。
3.数据项
数据项是有独立含义的不可再分割的最小单位。一个数据元素可由一个或多个数据项组成,如每一个学生的信息是一个数据元素,它包含学号、姓名等多个数据项。
4.数据对象
数据对象是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={'A','B',…,'Z'},无论数据元素集合是无限集(如整数集)、有限集(如字符集),还是由多个数据项组成的复合数据元素,只要性质相同,都是同一个数据对象。
5.数据类型
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。值集合确定了该类型的取值范围,操作集合确定了该类型中允许使用的一组运算。例如高级语言中的数据类型就是已经实现的数据结构。
6.抽象数据类型
抽象数据类型是指基于一类逻辑关系的数据类型。抽象数据类型的定义取决于客观存在的一组逻辑特性,而与其在计算机内如何表示和实现无关。
7.数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
在计算机中,数据元素之间是具有内在联系的数据集合。数据元素之间存在的关系,就是数据的组织形式。为编写出一个高效的程序,必须分析处理对象的特性及各对象之间的关系,这就是数据结构要研究的内容。
1.3算法及其描述
算法是解决问题的方法,是程序设计的精髓,程序设计的实质就是构造解决问题的算法。算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构。
1.3.1算法的概念和特性
算法是对特定问题求解步骤的一种描述,它是指令的有限序列。做任何事情都必须事先想好操作的步骤,然后按部就班地进行,才不会发生错误。计算机解决问题也是如此。对于一些常用的算法应该熟记,比如求阶乘、求素数、计算是否闰年等算法,在解决实际问题时,可参考已有的类似算法,按照业务逻辑设计出符合自己的算法。
一个算法应该具有以下五个重要特性。
(1)有穷性
一个算法应包含有限的操作步骤。即一个算法在执行若干个步骤之后应该能够结束,而且每一步都在有限时间内完成。
(2)确定性
算法中的每一步都必须有确切的含义,不能产生二义性。
(3)可行性
算法中的每一个步骤都应该能有效地执行,并得到确定的结果。
(4)输入
所谓输入,是指在算法执行时,从外界取得必要的数据。计算机运行程序的目的是进行数据处理,在大多数情况下,这些数据需要通过输入得到。有些情况下,数据已经包含在算法中,算法执行时不需要任何数据,所以一个算法可以有零个或多个输入。
(5)输出
一个算法有一个或多个输出,这是算法进行数据处理后的结果。没有输出的算法是毫无意义的。
算法的这些特性可以约束程序设计人员正确地书写算法,并使之能够正确无误地执行,达到求解问题的预期效果。
本书所讨论的算法,可用不同的方式进行描述,常用的有类Pascal、类C、类C++、类Java程序设计语言,本书同时以C和Java两种程序设计语言作为描述工具,以方便广大同学学习。
1.3.2算法设计的要求
算法设计的好坏关乎程序的执行效率,算法的设计必须满足下列四个要求。
(1)正确性
正确性的含义是算法对于一切合法的输入数据都能够得到满足要求的结果,事实上要验证算法的正确性是极其困难的,因为通常情况下合法的输入数据量太大,用穷举法逐一验证是不现实的。所谓的算法正确性是指算法达到了测试要求。
(2)可读性
算法的可读性是指人们对算法阅读理解的难易程度,可读性高的算法便于阅读,有利于算法的理解和交流。通常在书写算法程序时，添加程序注释、采用按缩进格式书写、分模块书写等方法可增加算法的可读性。
(3)健壮性
新书资讯