21世纪高职高专新概念教材 据
21世纪高职高专新概念教材 数据结构（C语言描述） 王路群 主编
前 言 二十一世纪是科学技术高速发展的信息时代,而计算机是处理信 息的主要工具,因此,人们已经认识到,计算机知识已成为人类 j代文化的一个重要组成部分 计算机科学技术以惊人的速度向前发展,它的广泛应用已从传统 的数值计算领域发展到各种非数值计算领域。在非数值计算领域 里,数据处理的对象已从简单的数值发展到一般的符号,进而发 展到具有一定结构的数据。在这里,面临的主要问题是:针对每 种新的应用领域的处理对象,如何选择合适的数据表示(构 构),如何有效地组织计算机存贮,并在此基础上又如何有效地 实现对象之间的“运算”关系。传统的解决数值计算的许多理论 方法和技术已不能满足解决非数值计算问题的需要,必须进行新 的探索。数据结构就是研究和解决这些问题的重要基础理论。因 此,“数据结构”课程已成为计算机类专业的一门重要专业基础 课
前 言 二十一世纪是科学技术高速发展的信息时代，而计算机是处理信 息的主要工具，因此，人们已经认识到，计算机知识已成为人类 当代文化的一个重要组成部分。 计算机科学技术以惊人的速度向前发展，它的广泛应用已从传统 的数值计算领域发展到各种非数值计算领域。在非数值计算领域 里，数据处理的对象已从简单的数值发展到一般的符号，进而发 展到具有一定结构的数据。在这里，面临的主要问题是：针对每 一种新的应用领域的处理对象，如何选择合适的数据表示（构 构），如何有效地组织计算机存贮，并在此基础上又如何有效地 实现对象之间的“运算”关系。传统的解决数值计算的许多理论、 方法和技术已不能满足解决非数值计算问题的需要，必须进行新 的探索。数据结构就是研究和解决这些问题的重要基础理论。因 此， “数据结构”课程已成为计算机类专业的一门重要专业基础 课
数提结构是程荐设计的中级银程第一章绪论 主要培养学生分析数据、组织数第二章线性表 据的能力,告诉学生如何編写2,从 率高、结构好的程序。本书作为 和队列 计算机大专系列教材之一,在内 第四章”串 容的选取、概念的引入、文字的第五章 叙述以及例题和司题的选等方多维数红义表 结构简明合理、由浅入深、深入。第氏 面,都力求遵循面向应用、逻辑 树 浅出、循序渐进、便于自学的原「第七♀一 则,突出其实用性与应用性。全「八、3 找 书共分十章。书中,安排了相当 的篇幅来介绐这些基本数据结构「第九章排序 的实际应用。 第十章文件
数据结构是程序设计的中级课程， 主要培养学生分析数据、组织数 据的能力，告诉学生如何编写效 率高、结构好的程序。本书作为 计算机大专系列教材之一，在内 容的选取、概念的引入、文字的 叙述以及例题和习题的选择等方 面，都力求遵循面向应用、逻辑 结构简明合理、由浅入深、深入 浅出、循序渐进、便于自学的原 则，突出其实用性与应用性。全 书共分十章。书中，安排了相当 的篇幅来介绍这些基本数据结构 的实际应用。 进 入 章 节
第一章绪论 543中史21 所及 本章介绍了数 科 发展历 机 处黑藏 的在 据 重点介绍子数据灼 地计 结 有关的概念语 读者学习本薰后应能 掌握数据、据元素、 的 逻辑结构储结构 盆算为 机 数据处理据居结构 发 并了解如何八 算法设计 苗倍 算法的好坏。 学 简
1引言 2数据结构的发展简 史及其在计算机科学 中所处的地位 3什么是数据结构 4基本概念和术语 5算法和算法的描述 第一章 绪论 本章介绍了数据结构 这门学科诞生的背景、 发展历史以及在计算 机科学中所处的地位， 重点介绍了数据结构 有关的概念和术语， 读者学习本章后应能 掌握数据、数据元素、 逻辑结构、存储结构、 数据处理、数据结构、 算法设计等基本概念， 并了解如何评价一个 算法的好坏
11引言 众所周知,二十世纪四十年代,电子数字计算机问世的直接原因 是解决弹道学的计算问题。早期,电子计算机的应用范围,几乎 只局限于科学和工程的计算,其处理的对象是纯数值性的信息, 通常,人们把这类问题称为数值计算 近三十年来,电子计算机的发展异常迅猛,这不仅表现在计算机 本身运算速度不断提高、信息存储量日益扩大、价格逐步下降, 更重要的是计算机广泛地应用于情报检索、企业管理、系统工程 等方面,已远远超出了科技计算的范围,而渗透到人类社会活动 的一切领域。与此相应,计算机的处理对象也从简单的纯数值性 信息发展到非数值性的和具有一定结构的信息
1.1 引言 众所周知，二十世纪四十年代，电子数字计算机问世的直接原因 是解决弹道学的计算问题。早期，电子计算机的应用范围，几乎 只局限于科学和工程的计算，其处理的对象是纯数值性的信息， 通常，人们把这类问题称为数值计算。 近三十年来，电子计算机的发展异常迅猛，这不仅表现在计算机 本身运算速度不断提高、信息存储量日益扩大、价格逐步下降， 更重要的是计算机广泛地应用于情报检索、企业管理、系统工程 等方面，已远远超出了科技计算的范围，而渗透到人类社会活动 的一切领域。与此相应，计算机的处理对象也从简单的纯数值性 信息发展到非数值性的和具有一定结构的信息
因此,再把电子数字计算机简单地看作是进行数值计算的工具, 把数据仅理解为纯数值性的信息,就显得太狭隘了。现代计算机 科学的观点,是把计算机程序处理的一切数值的、非数值的信息, 乃至程序统称为数据(Data),而电子计算机则是加工处理数据 (信息)的工具 由于数据的表示方法和组织形式直接关系到程序对数据的处理效 率,而系统程序和许多应用程序的规模很大,结构相当复杂,处 理对象又多为非数值性数据。因此,单凭程序设计人员的经验和 技巧已难以设计出效率高、可靠性强的程序。于是,就要求人们 对计算机程序加工的对象进行系统的研究,即研究数据的特性以 及数据之间存在的关系——数据结构( Date structure)
因此，再把电子数字计算机简单地看作是进行数值计算的工具， 把数据仅理解为纯数值性的信息，就显得太狭隘了。现代计算机 科学的观点，是把计算机程序处理的一切数值的、非数值的信息， 乃至程序统称为数据（Data），而电子计算机则是加工处理数据 （信息）的工具。 由于数据的表示方法和组织形式直接关系到程序对数据的处理效 率，而系统程序和许多应用程序的规模很大，结构相当复杂，处 理对象又多为非数值性数据。因此，单凭程序设计人员的经验和 技巧已难以设计出效率高、可靠性强的程序。于是，就要求人们 对计算机程序加工的对象进行系统的研究，即研究数据的特性以 及数据之间存在的关系——数据结构（Date Structure）
1.2数据结构的发展简史及其 在计算机科学中所处的地位 发展史: 1、“数据结构”作为一门独立的课程在国外是从1968年才开始 设立的。 2、1968年美国唐·欧·克努特教授开创了数据结构的最初体系,他 所著的《计算机程序设计技巧》第一卷《基本算法》是第一本 较系统地阐述数据的逻辑结构和存储结构及其操作的著作
1.2 数据结构的发展简史及其 在计算机科学中所处的地位 发展史： 1、 “数据结构”作为一门独立的课程在国外是从1968年才开始 设立的。 2、 1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他 所著的《计算机程序设计技巧》第一卷《基本算法》是第一本 较系统地阐述数据的逻辑结构和存储结构及其操作的著作
地位 1.“数据结构”在计算机科学中是一门综合性的专业 基础课 2.数据结构是介于数学、计算机硬件和计算机软件三 者之间的一门核心课程。 3.数据结构这一门课的内容不仅是一般程序设计(特 别是非数值性程序设计)的基础,而且是设计和实 现编译程序、操作系统、数据库系统及其他系统程 序的重要基础
地位： 1. “数据结构”在计算机科学中是一门综合性的专业 基础课。 2. 数据结构是介于数学、计算机硬件和计算机软件三 者之间的一门核心课程。 3. 数据结构这一门课的内容不仅是一般程序设计（特 别是非数值性程序设计）的基础，而且是设计和实 现编译程序、操作系统、数据库系统及其他系统程 序的重要基础
1.3什么是数据结构 计算机解决一个具体问题时,大致需要经过下列几个步骤:首先 要从具体问题中抽象出一个适当的数学模型,然后设计一个解此 数学模型的算法( Algorithm),最后编岀程序、进行测试、调整 直至得到最终解答。寻求数学模型的实质是分析问题,从中提取 操作的对象,并找出这些操作对象之间含有的关系,然后用数学 的语言加以描述 计算机算法与数据的结构密切相关,算法无不依附于具体的数据 结构,数据结构直接关系到算法的选择和效率。 运算是由计算机来完成,这就要设计相应的插入、删除和修改的 算法。也就是说,数据结构还需要给出每种结构类型所定义的各 种运算的算法。 直观定义:数据结构是研究程序设计中计算机操作的对象以及它 们之间的关系和运算的一门学科
1.3 什么是数据结构 计算机解决一个具体问题时，大致需要经过下列几个步骤：首先 要从具体问题中抽象出一个适当的数学模型，然后设计一个解此 数学模型的算法（Algorithm），最后编出程序、进行测试、调整 直至得到最终解答。寻求数学模型的实质是分析问题，从中提取 操作的对象，并找出这些操作对象之间含有的关系，然后用数学 的语言加以描述。 计算机算法与数据的结构密切相关，算法无不依附于具体的数据 结构，数据结构直接关系到算法的选择和效率。 运算是由计算机来完成，这就要设计相应的插入、删除和修改的 算法 。也就是说，数据结构还需要给出每种结构类型所定义的各 种运算的算法。 直观定义：数据结构是研究程序设计中计算机操作的对象以及它 们之间的关系和运算的一门学科
14基本概念和术语 1.数据 数据是人们利用文字符号、数字符号以及其他规定的符 号对现实世界的事物及其活动所做的描述。在计算机科学中,数 据的含乂非常广泛,我们把一切能够输入到计算机中并被计算机 程序处理的信息,包括文字、表格、图象等,都称为数据。例如, 个个人书库管理程序所要处理的数据可能是一张如表1-1所示的 表格
1.4 基本概念和术语 1．数据 数据是人们利用文字符号、数字符号以及其他规定的符 号对现实世界的事物及其活动所做的描述。在计算机科学中，数 据的含义非常广泛，我们把一切能够输入到计算机中并被计算机 程序处理的信息，包括文字、表格、图象等，都称为数据。例如， 一个个人书库管理程序所要处理的数据可能是一张如表1-1所示的 表格