《第1章概述》习题解答new.doc
18页
第1章 概 述第1章 概 述本章学习要点◆了解数据结构的相关概念◆了解并掌握数据的4种基本逻辑结构的特点◆了解数据的各种基本存储结构◆了解算法的相关概念，并能分析各种算法的时间复杂度和空间负责度数据结构（Data Structures）是随着计算机科学的发展而逐步形成的一门学科，目前已成为高等院校中计算机类各专业的核心课之一，同时也是统计类、经济类和工程软件设计类各专业的必修课程本章的主要内容是对数据结构的基本概念和基本内容作一概要介绍，为此，简单回顾一下数据结构的发展与形成过程对于理解数据结构的内容和重要性是很有必要的1.1 数据结构的发展概况众所周知，在40年代计算机刚诞生时，计算机所能处理的数据只能是由0或1组成的二进制数，此时还谈不上什么结构后来虽然计算机可以处理十进制整数和十进制实数，也不过是由0到9这十个数字组成的序列，或再加上小数点，其数据的结构非常简单没有研究它的必要由于计算机技术的飞速发展和数据处理能力的不断提高，到60年代中期，各种高级程序设计语言相继出现，所能描述的数据类型逐渐丰富例如，在FORTRAN语言中允许使用复数类型和数组类型数据其中，复数是两个实数的有序对，而数组是同类型数据的一个有限序列，这自然是一种“结构”。
在COBOL语言和PL/1语言中允许使用字符类型和记录类型数据，将计算机的应用领域由数值计算进一步扩充到非数值计算其中，记录就是一种“结构”类型的数据，它把一组相互关联的不同类型的数据看作一个整体构成一种新的“结构类型”数据有了“结构类型”的概念之后，各个数据之间不再孤立，这样便于表示和储存，也便于处理后来，在LISP语言中又定义了一种带有层次性的表结构，并定义了许多相应的运算这种层次结构是一种非线性的树型结构，也是本书中将要着重讨论的内容之一数据结构作为一门课程的形成和发展主要是在60年代后期首先，在1968年由美国计算机协会（ACM）颁发了建议性的计算机教学计划，其中规定数据结构作为一门独立的课程，这在世界上是第一次同一年，美国的计算机科学家D.E.Knuth教授在他的巨著《计算机程序设计的技巧》详细论述了数据的逻辑结构和数据的存储结构，并对各种结构给出了典型算法，为数据结构作为一门课程奠定了理论基础70年代初，随着大型程序以及大规模文件系统的出现，结构程序设计成为程序设计方法学的主要内容在程序设计中，数据结构受到了极大的重视认为程序设计的实质就是对要处理的问题选择一种最为适合的数据结构，同时在此结构上施加一种好的算法。
1976年瑞士著名计算机科学家N.Wirth编著的《算法+数据结构=程序》一书正是这种程序设计思想的具体体现70年代中后期，由于数据库系统和数据检索系统的不断发展，在数据结构中进一步增加了文件管理的内容以及B-树和B+树的知识，使数据结构的内容得以丰富和进一步完善从80年代开始，在我国高等院校的教学计划中已经将数据结构课程列为计算机类各专业的核心课程之一，在许多非计算机专业也把数据结构作为必修课或选修课程数据结构是一门介于数学、计算机硬件和计算机软件三者之间的计算机专业基础课，是程序设计方法学、数据库系统、操作系统、编译原理、软件工程学等课程的先修课程，是设计和实现大型应用软件的基础1.2 数据结构的基本术语和相关概念数据（data）是能输入到计算机中并能被计算机处理的符号的总称，是计算机程序的加工“原料”需要说明的是，这里的“数据”绝对不能狭义地理解为仅仅是数学中的整数或实数而已，必须作广义的理解例如，一个有某种功能源程序，一个文件，一张图画，一段声音等等都可以通过编码而归纳为数据的范畴数据元素（data element）是数据的基本单位，在计算机程序中通常作为一个整体进行处理由于数据的范围非常广泛，因此数据元素可大可小，小到一个字符；大到一本书或一张地图等等。
对于较大的数据元素还能进一步分成若干个“数据项（data item）”，每个数据项也可以是由几个更小的数据项组成，这样的数据项称为“组合项”，不能再分的数据项称为“原子项”例如，一本书的目录信息作为一个数据元素，是由各章的目录组成的，而每章的目录又是由该章中各小节的目录组成各章的目录信息就是组合项，如果每一小节的目录不能再分成更小的单位，则称其为原子项，否则称为组合项关键字（key）是指数据元素中能够起标识作用的数据项其中能够起唯一标识作用的数据项称为“主关键字”，反之称为“次关键字”例如，每个学生的信息可以看成是一个数据元素，其中的数据项有：学号、姓名、性别、年龄和班级等等，由于每个学生都有一个唯一的学号，所以数据项“学号”是主关键字，而姓名可能存在重复所以数据项“姓名”是次关键字数据对象（data object）是具有相同性质的数据元素的集合，是数据的一个子集例如，全体整数的集合N={0,±1,±2,…}就是一个数据对象，全体复数的集合C={
数据关系（dat relation）是数据对象中各元素之间的一种结构（或序），它反映了数据元素之间存在的一种固有联系在数据处理时，通常把一个数据对象中两个元素之间的数据关系简单地用前驱和后继来描述例如，某个数据对象中的两个元素a,b之间存在关系：a是b的前驱（或b是a的后继），则可表示为
数据中各元素之间存在一个对一个的关系，如图1.1(b)所示的数据对象中，其数据的逻辑结构为线性结构3）树型结构（Tree Structure） 在该结构中，除了一个根元素（结点）外，其它各元素（结点）都有唯一的直接前驱；所有数据元素（结点）都可以有多个后继数据中各元素之间存在一个对多个的关系，如图1.1(c)所示的数据对象中，其数据的逻辑结构为树型结构也称为层次结构4）图结构或网结构（Graph Structure） 在该结构中，各元素（顶点）之间可以有多个直接前驱和多个直接后继数据中各元素之间存在多个对多个的关系，如图1.1(d)所示的数据对象中，其数据的逻辑结构就是图结构图结构和树型结构统称为非线性结构数据的物理结构（Data Physical Structure）又称数据的存储结构，它是数据在计算机中的存储表示，包括数据本身在计算机中的存储方式，以及数据之间的逻辑关系在计算机中的表示因此，数据的物理结构是依赖于计算机的根据在存储器中表示数据的不同方法，通常有以下4种物理存储结构：（1）顺序存储结构（Sequential Storage Structure） 将逻辑上相邻的数据元素存储在物理位置上相邻的存储单元中，元素之间的逻辑关系由其相应的存储单元的相邻关系来表示。
2）链式存储结构（Linked Storage Structure） 在存储器中不要求将逻辑上相邻的数据元素存储到相邻的物理存储位置中，而是通过附加指针字段来表示数据元素之间的逻辑关系3）索引存储结构（Index Storage Structure） 在存储数据元素信息的同时，还建立一个附加的索引表，索引表中每一项称为索引项（关键字），它是能够唯一标识一个数据元素的数据项4）哈希存储结构（Hash Storage Structure） 能根据数据元素的关键字直接算出该数据元素的存储地址数据结构（data structure）是具有结构（或关系）特性的数据元素的集合，它研究的是数据的逻辑结构和物理结构以及它们之间的相互关系，并在这种结构上定义相关的运算，设计并实现相应的算法，分析算法的效率数据的逻辑结构和物理结构是数据结构的相互关联的两个方面，同一个逻辑结构可以有几种不同的存储结构算法的设计取决于数据的逻辑结构，而算法的实现依赖于数据的存储结构1.3 应用举例【例1.1】一周中的7天的数据结构是DLS=(D，R)，其中，D={Sun,Mon,Tue,Wed,Thu,Fri,Sat}，R={
可用逻辑图形表示该结构为图1.2（a）；其顺序存储结构可以表示为图1.2（b）；其链式存储结构可以表示成图1.2（c）例1.2】现有下列3种用二元组表示的数据逻辑结构，画出它们对应的逻辑图形表示，并指出它们分别属于何种类型的结构1）A=(K,R），其中：K={a,b,c,d,e,f,g,h},R={
本节将给出算法的定义和算法的各种描述方法，并进一步从运行的时间开销和空间开销两个方面分析算法执行的效率1.4.1 算 法算法（Algorithm）是对特定问题求解步骤的一种描述，是为了解决某个问题给出的一个确定的、有限长的操作序列一个算法应具有以下5个重要特性：（1）有穷性一个算法应该包含有限个操作步骤，而不是无限的对于合法的输入值，算法能在执行有限次操作之后得到结果有限次操作是指操作步骤为有限个，并且每个步骤都能在规定的时间内完成2）确定性算法中的每一个步骤都应当是确定的，而不应当是。
