本章主要介绍以下内容

《本章主要介绍以下内容》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论本章主要介绍以下内容1、数据结构中涉及的基本概念、术语及所研究的主要内容2、本教材使用的描述工具本章重点和难点：1、数据结构、数据类型、ADT、算法等重要概念。　　　用计算机求解任何问题都离不开程序设计，而程序设计的实质是数据表示和数据处理。数据要能被计算机处理，首先必须能够存储在计算机的内存中，这项任务称为数据表示，数据表示的核心任务是数据结构的设计；一个实际问题的求解必须满足各项处理要求，这项任务称为数据处理，数据处理的核心任务是算法设计。数据结构课程主要讨论数据表示和数据处理的基本问题。本章将概括地介绍数据结构的基本

2、概念、基本思想和基本方法。1.1数据结构的兴起和发展　　　数据结构起源于程序设计。随着计算机科学与技术的不断发展，计算机的应用领域已不再局限于科学计算，而更多地应用于控制、管理等非数值处理领域。与此相应，计算机处理的数据也由纯粹的数值发展到字符、表格、图形、图象、声音等具有一定结构的数据，处理的数据量也越来越大，这就给程序设计带来一个问题：应如何组织待处理的数据以及数据之间的关系（结构）。　　　1968年克努思教授[1]开创了数据结构的最初体系，他所著的《计算机程序设计艺术》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储

3、结构及其操作的著作。70年代初，数据结构作为一门独立的课程开始进入大学课堂。　　　数据结构随着程序设计的发展而发展。程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：⑴无结构阶段。　　　40~60年代，计算机的应用主要针对科学计算，程序设计技术以机器语言/汇编语言为主，程序处理的数据是纯粹的数值，数据之间的关系主要是数学公式或数学模型。这一阶段，在人类的自然语言与计算机编程语言之间存在着巨大的鸿沟，程序设计属于面向计算机的程序设计，设计人员关注的重心是使程序尽可能地被计算机接受并按

4、指令正确执行，至于程序能否让人理解并不重要。⑵结构化阶段。　　　60~80年代，计算机开始广泛应用于非数值处理领域，数据表示成为程序设计的重要问题，人们认识到程序设计规范化的重要性，提出了程序结构模块化，并开始注意数据表示与操作的结构化。数据结构及抽象数据类型就是在这种情况下形成的。数据结构概念的引入，对程序设计的规范化起到了重大作用。图灵[2]奖获得者沃思[3]给出了一个著名的公式：数据结构+算法=程序。从这个公式可以看到，数据结构和算法是构成程序的两个重要的组成部分，一个软件系统通常是以一个或几个关键数据结构为核心而组织的。　　

5、　随着软件系统的规模越来越大、复杂性不断增加，人们不得不对结构化技术重新评价。由于软件系统的实现依赖于关键数据结构，如果这些关键数据结构的一个或几个有所改变，则涉及到整个系统，甚至导致整个系统彻底崩溃。⑶面向对象阶段。　　　面向对象技术（首先是面向对象程序设计）始于80年代初，是目前最流行的程序设计技术。在面向对象技术中，问题世界的相关实体被视为一个对象，对象由属性和方法构成，属性用以描述实体的状态或特征，方法用以改变实体的状态或描述实体的行为。一组具有相同属性和方法的对象的集合抽象为类，每个具体的对象都是类的一个实例。例如，“教师

6、”是一个类，“王老师”、“李老师”等对象都是“教师”类的实例。　　　由于对象（类）将密切相关的属性（数据）和方法（操作）定义为一个整体，从而实现了封装和信息隐藏。使用类时，无需了解其内部的实现细节，一旦数据（结构）修改了，只需修改类内部的局部代码，软件系统的其余部分无需修改。　　　数据结构主要强调两个方面的内容：①数据之间的关系；②针对这些关系的基本操作。这两个方面实际上蕴涵着面向对象的思想：类重点描述实体的状态与行为，而数据结构重点描述数据之间的关系及其基本操作，数据及其相互关系构成了对实体状态的描述，针对数据元素之间关系的操作构

7、成了对实体行为的描述。由此可见，类与数据结构之间具有对应关系，如图1-1所示。　　　“数据结构+算法=程序”这个公式在软件开发的进程中曾产生了深远的影响，但是，它并没有强调数据结构与解决问题的算法是一个整体，因此有人主张将它修改为“（数据结构+算法）=程序”，以体现面向对象的思想。　　　值得注意的是，数据结构的发展并未终结。一方面，数据结构将继续随着程序设计的发展而发展；另一方面，面向各专门领域的数据结构得到研究和发展，各种实用的高级数据结构被研究出来，各种空间数据结构也在探索中。[1]克努思（Donald.E.Knuth，1938

8、年生）从小就是个优秀的学生，多次获得学业成就奖。1963年担任加利福尼亚理工学院的教师，1968年担任斯坦福大学教授。1992年为集中精力写作而荣誉退休，保留教授头衔。他特别感兴趣的是为《计算机程序设计艺术》丛书完成新卷并更新旧卷。这