第1章绪论 1.1复习提要 本章主要讨论贯穿和应用于整个“数据结构”课程始终的基本慨念和性能分析力法。学 习本章的内容,将为后续章节的学习打下良好的基础 本章复习的要点: 1基本知识点 要求理解的概念包括:数据,数据对象,数据元素或数据成员,数据结构,数据类型, 据抽象,抽象数据类型,数据结构的抽象层次,面向对象,对象与类的系,类的继关系,对 象间的消息通信等。需要对各个概念进行区分与比较。例如,按照而向对象建模技个的要 求,把建立对象类作为一个层次,把建立对象间的关系(即建立结构)作为另外的层次。因 此,在软件开发中做数据结构设计时,不但要设计对象类,类的属性,类的操作,还要建立类 的实例之间的关系。从这个角度考虑,把数据结构定义为数据对象及对象中各数据成员之 间关系的集合是合理的。又例如,类 class或 struct与C中的结构类型 struct的Ⅸ别在于前 者不但有对象的状态描述(数据成员),还加入了操作(成员函数),描述对象的行为,这样叫 以体现一个完整的实体概念,而后者不行。冉例如,传统的数据结构概念从数据结构的逻辑 结构、物理结枃和相关操作等三个方闻进行讨论。它反映了数据结构设计的不冋层次:逻辑 结构属于问题解决范畴,物理结构是逻辑结构在计算枧中的存储方式。但在面向对象廾发 模式中,本课程中涉及的数据结构都属于基本数椐结构,但有的属于应用级的数据结构.如」 稀疏矩阵,字符串,栈与队列,优先级队列,图等;有的属于实现级的数据结构.如数组,链表 堆,索引,散列表等。 2有关算法的概念和简单的算法性能分析方法 算法的五个特性表明算法的实现属于面向过程的开发模式,即传统的“输入-计算-输 出”模式。算法的应用要求明确算法的时间和空间代价。因此,必须理解算法的定义和算法 的五个特性,掌握简单的时间复杂度估计和空间复杂度佔计方法(不讨论程序复杂性)。 3描述语言 要求数据结构的描述既要体现算法的逻辑,又要体现面向对象的概念,需要一种能够兼 有面向对象和面向过程双重特性的描述语言。传统的 Pascal语言和C语言只是面向过程 的语言,不能适应面向对象的开发模式。因此,采用C++许描述。要求学员基本掌握 C十十语言的基本概念和用C++语言编写应用程序的基本技术。例如,用类定义抽象数 据类型的方式,定义模板类、抽象类的方法,函数与参数的定义,建立类(公有、私有)继承的 方法,例外与异常的处理等等都需要掌挥
1.2难点与重点 1基本概念:理解仆么是数据、数捃对象、数据元素、数据结构、数据的逻辑结构与物理结 构、数据结构的抽象层次 2面向对象概念:理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解 什么是面向对象。 (1)抽象数据类型的封装性; (2)Coad与 Yourdon定义:面向对象亠对象十类+继承一通信; (3)面向对象系统结构的稳定性; (4)面向对象方法着眼点在于应用问题所涉及的对象 3算法与算法分析:理解算法的定义、算法的特性、算法的时阃代价、算法的空间代价 (1)算法与程序的不同之处需要从算法的特性来解释 (2)算法的正确性是最主要的要求 (3)算法的可读性是必须考虑的: (4)程序的程序步数的计算与算法的事前估计; (5)程序的时间代价是指算法的渐进时间复杂性度量。 1.3教材中习题的解析 1-1什么是数据?它与信息是什么关系? 【解答】 信息:广义地讲,信息就是消息。信息是宇宙三要素(物质、能量、信息)之一。它是现 实世界各种事物在人们头脑中的反映。此外,人们通过科学仪器能够认识到的也是信息 信息的特征为:可识别、可存储、可变换、可处理、可传递可再生、可压缩,可利用、可共享 数据:因为信息的表现形式十分广泛,许多信息在计算机中不方便存储和处理,例如 一个大楼屮4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等,必 须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此,数据(data)是信息 的载体,是描述客观事物的数、字符,以及所有能输入到计算机中并被计算机程序识别和处 理的符号的集合。在计算机中,信息必须以数据的形式出现 1-2什么是数据结构?有关数据结构的讨论涉及哪二个方面? 【解答】 数据结构是指数据以及数据成员相互之间的关系。记为;数据结构 。其中 D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般沙及以下三方面的内容 ①数据成员以及它们相与之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构 ②数拼成员及其关系在计算机有储器内的存储表示,也称为数据的物理结构,简称为 存储结构; ③施加于该数据结构上的操作
数据的逻辑结构是从逻辑关系上描述数据、它与数据的存储不是…·码事,是与计算机存 储无关。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应 用视图。数据的存储结构是逻辑数据结构在训算机存储器中的实现(亦称为映掾).它是依 赖于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种 数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等 1-3数据的逻辑结构分为线性结构秈‖线性结构两大类。线性结构包括数组、链表、栈 队列、优先级队列等:作线性结构包括树、图等、这两类结构各片的持点是什么? 【解答】 线性结构的特点是:在结构中所有数据成员都处于一个序列中,有且仅有一个开始成 员和-个终端成员,并旦所有数据成员都最多有一个直接前驱和一个直接后继。例如,线性 表就是典型的线性结构 非线性结构的特点是:个数据成员可能有零个、一个或多个直妾前驱和直接后继。 例如,树图或网络等都是典型的非线性结构。 1-4什么是抽象数据类型?试用C++的类声明定义“复数”的抽象数据类型。求 (])在复数内部用浮点数定义它的实部和虚部 (2)实现3个构造函数:缺省的构造函数没有参数;第2个构造凼数将双精度浮点数赋 给复数的实部虚部置为0;第3个构造函数将两个双精度浮点数分别赋给复数的实部和 慮部 3)定义获取和修改复数的实部和虚部,以及一、-、←、/等运算的成员函数 (4)定义重载的流函数来输出一个复数 【解答】 抽象数据类型通常是指由用F定义.用以表示应用问题的数据楔型。抽象数据关型由 基本的数据类型构成,并包括组相关的服务。 在头文件 complex.h中定义的复数类 define_complex h include <iostream. h>> complex(i Re=Im=0; k 不带参数的构造函数 只置实部的构造函数 tomplex(double r, double i)f Rewr: Im=i:) 分别置实部、虚部的构造函数 double get Real)( return Re: 3 取复数实部 取复数虚部 yoid set Real( double r)( Re=r: I 修改复数实部 修改复数虚部 mplex operator=( complex ob){R=oh.Re;Im=b,ln;}:/复数赋值 complex operator +i complex ob) 重载函数:复数叫则运算
友元函数:重载< double re i 复数的实部与虚部 //复数类 complex的相关臘务的实现放在C+-源文件 complex.cpp中 omplex& complex: operator T(eermplex ob)1 重载函数:复数加法运算 sult. Re= Re+ob. Re; result. Im= lm-ob, Im 重载函数:复数减法运算 resu: Re Re- nb. Re; result. Im=Im--obIn operator*(complex oh)I /互载函数:复数乘法运算 result. Re= Re ob. Re-IIm*ob. In: result, Im -In *ob Re-Re x ob.Im complex complex : operator /(complex ob)( 巫载函数:复数除法运算 double d=ob. Re w ob. Redob in oh Im result. Re =(Rc *ob. Re rItu*ub Im)/d; rrsulr Ir=(Im+ob, Re-Re* ob. In)d friend ostream& operator <<(ostream& o9, complex ob)( 友元函数:重载≤∵将复数ob输出到输出流对象Qs中 return os以“0,Re≤(ob.1m∴,=0.0)?"- ∵fabs(cb.lm)
15用归纳法证明: (1) n(m+1) =2(n+1)(2n+1) (3) ,x≠1,n≥0 【证明】略 16什么是箅法?箅法的五个特性是什么?试根据这些特性解释算法与程序的区别 【解答】 通常,定义算法为“为解决某一特定任务而规定的一个指令序列。”个算法应当具有以 下特性 (1)有输入。一个算法必须有0个或多个输人。它们是算法开始运算前给予算法的 量。这些输入取白于特定的对象的集合。它们可以使用输入语句H外部提供,也可以使用 赋值语句在算法内给定 (2)有输出。一个算法应有一个或多个输出,输出的量是算法计算的结果 (3)确定性。算法的每一步都应确切地、无歧义地定义。对于每一种情况,需要执行的 动作都应严格地、清晰抱规定 (4)有穷性。个算法无论在什么情况下都应在执行有穷步后结束。 (5)有效性。算法中毎一条运算都必須是足够基本的。就是说,它们原则上都能精确 地执行,甚全人们仅用笔和纸做有限次运算就能元成 算法和程序不同,程序可以不满足上述的特性(4)。例如:一个操作系统在用户未使用 前一直处于“等待”的循环中,直到出现新的用户事件为止。这样的系统可以无休止地运行 直到系统停工 此外,算法是面向功能的,通常用面向过程的方式描述;程序可以用面向对象方式搭建 它的框架。 1-7设n为干整数,分析下列各程序段中加下划线的语句的程序步数。 (i)for( int i=l; i<=n:i-=.) fort int j=1:j≤=m; for(int k 1: k <=n; k+H ror(int=1;<=i:计+:) r(int k=li k<=j: k+-) x-xTy (3)tnti=1,j=1 while (i<=n&&j<"n)(