数据结构和软硬件的发展, 非数值计算问题显得越来越重要据统计, 当今处理非数值计算问题占用了 90% 以上的机器时间这类问题涉及的处理对象不再是简单的数据类型, 其形式更加多样结构更为复杂, 数据元素之间的相互关系一般无法直接用数学方程式加以描述因此, 解决这类问题的关键不再是数学分析和

Size: px

Start display at page:

Download "数据结构和软硬件的发展, 非数值计算问题显得越来越重要据统计, 当今处理非数值计算问题占用了 90% 以上的机器时间这类问题涉及的处理对象不再是简单的数据类型, 其形式更加多样结构更为复杂, 数据元素之间的相互关系一般无法直接用数学方程式加以描述因此, 解决这类问题的关键不再是数学分析和"

纸译贺
5 years ago
Views:

1 第章绪论随着计算机技术的飞速发展计算机应用的范围越来越广泛从最初的数值计算发展到现在的数据处理自动控制信息处理人工智能情报检索和办公自动化等众多非数值计算领域所处理的数据也从简单的数值发展到复杂的文字图形图像音频视频和动画等具有结构的数据因此要想高效地处理这些数据必须深入研究数据本身的特性数据之间的关系以及如何有效地将数据存储在计算机内这正是数据结构这门课程所要研究的主要问题本章主要介绍数据结构的基本概念数据的逻辑结构存储结构及关系算法及算法时间复杂度的分析. 数据结构的课程地位及研究内容数据结构是计算机及相关专业的一门专业基础课是介于数学计算机硬件和计算机软件之间的一门核心课程是程序设计的后续课程同时也是编译原理操作系统数据库等课程的基础本书较系统地介绍了软件设计及系统开发中经常使用的数据结构及相应的存储结构和算法常用的查找和排序技术并对各种结构和技术进行了比较在计算机发展的初期人们使用计算机的目的主要是处理数值计算问题当我们使用计算机来解决一个具体问题时一般需要经过下列几个步骤首先要从该具体问题抽象出一个适当的数学模型然后设计或选择一个解此数学模型的算法再编写程序进行调试测试最后运行程序并得到答案例如求解梁架结构中应力数学模型的线性方程组可以使用迭代算法来实现求解鸡兔同笼问题可以通过二元一次方程组来实现由于计算机应用初期所涉及的运算对象只是简单的整型实型或布尔型数据所以程序设计者的主要精力集中于程序设计的技巧上而忽略了数据结构随着计算机应用领域的扩大

2 数据结构和软硬件的发展, 非数值计算问题显得越来越重要据统计, 当今处理非数值计算问题占用了 90% 以上的机器时间这类问题涉及的处理对象不再是简单的数据类型, 其形式更加多样结构更为复杂, 数据元素之间的相互关系一般无法直接用数学方程式加以描述因此, 解决这类问题的关键不再是数学分析和计算方法, 而是要设计出合适的数据结构, 以便有效地解决问题下面, 我们先看几个例子例 - 公司员工信息管理系统某公司有一批员工, 现需要用计算机来管理员工信息, 要求能够完成以下操作 : 当招聘新员工时, 能把员工信息添加进来 ; 当有员工辞职时, 能够删除该员工信息 ; 能够修改员工信息 ; 能够以某种方式检索员工信息分析 : 通过对以上问题的描述, 我们可以把公司员工信息用表 -- 表示出来其中, 每个员工的信息由员工号姓名性别年龄等组成, 员工数据按照一定的顺序线性排列这就是解决该问题的模型 ( 线性表 ) 有了模型以后, 就可以围绕该模型设计算法, 即实现员工信息的添加修改删除检索等操作表 -- 员工信息表员工号姓名性别年龄住址电话所属部门 0002 王清男 25 南京路 0 号 3562 财务 0003 李力女 28 甘肃路 6 号 5673 总务 0004 张娟女 30 杭州路 25 号 2345 经理办公室 0005 张爱民男 35 洛阳路 2 号 2436 销售类似地还有学籍管理系统飞机订票系统图书管理系统学生选课系统等, 它们都有一个共同点, 即被处理的对象之间具有简单的线性关系, 这就是一类数据结构线性结构例 -2 计算机和人对弈问题计算机之所以能和人对弈是因为有人将对弈的策略事先已存入计算机, 包括对弈过程中所有可能的情况以及响应的策略由于对弈的过程是在一定的规则下随机进行的, 所以, 为使计算机能灵活对弈就必须对对弈过程中所有可能发生的情况以及对应的策略都考虑周全因此在对弈问题中, 计算机操作的对象是对弈过程中可能出现的棋盘状态称为格局图 -- (a) 所示为井字棋的一个格局, 根据比赛规则, 通常一个格局可以派生出多个格局, 图 -- (b) 所示为从图 --(a) 派生出的 5 个格局, 并且从每个新的格局又可以派生出 4 个可能出现的格局因此, 若将对弈从开始到结束的过程中所有可能出现的格局都画在一张图上, 则可得到一棵倒长的树树根是对弈开始之前的棋盘格局, 而所有的叶子就是可能出现的结局, 对弈的过程就是从树根沿树杈到某个叶子的过程树也是一种数据结构, 常用于表达某些非数值计算问题 2

3 绪论第章 (a) 棋盘格局示例 (b) 对弈树的局部图 -- 井字棋对弈树例 -3 教学计划编排问题一个教学计划包含许多课程, 在教学计划包含的许多课程之间, 有些课程必须按规定的先后次序进行学习, 有些则没有次序要求也就是说, 有些课程之间有先修和后修的关系课程之间先修和后修的次序关系可用一个称作图的数据结构来表示, 如图 --2 所示, 图中的每个顶点表示一门课程, 如果从顶点 v i 到 v j 之间存在有向边 <v i,v j >, 则表示课程 i 必须先于课程 j 进行如何在规定的年限内修完所有的课程, 在哪个学期安排哪个课程, 就是本例要进行的操作课程编号课程名称选修课程 C 计箅机导论无 C 2 数据结构 C,C 4 C 3 汇编语言 C C 4 C 程序设计语言 C C 5 计算机图形学 C 2,C 3,C 4 C 6 接口技术 C 3 C 7 数据库原理 C 2,C 9 C 8 编译原理 C 4 C 9 操作系统 C 2 (a) 计算机专业的课程设置 (b) 表示课程之间优先关系的有向图图 --2 教学计划编排问题的数据结构 3

4 数据结构由以上几个例子可见描述非数值计算问题的数学模型不再是数学方程而是诸如线性表树图之类的数据结构因此数据结构课程是研究非数值计算的程序设计问题中计算机处理对象以及它们之间关系和操作的学科它主要研究 ①数据元素之间的逻辑关系数据的逻辑结构 ②数据元素及关系在计算机内的表示数据的存储结构 ③数据的操作及实现学习数据结构的目的是了解和掌握计算机处理对象的特性将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理同时通过算法训练来提高学生的思维能力通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高.2 基本概念和术语在系统地学习数据结构知识之前首先对一些基本概念和术语赋予确切的定义数据 data 数据是所有能被输入计算机且能被计算机处理的符号的集合是计算机加工处理的对象它可以是数值型数据整数实数复数双精度数等也可以是非数值型数据字符字符串声音图像图片语音等 2 数据元素 data element 数据元素是数据的基本单位在计算机程序中通常作为一个整体来考虑和处理在不同的条件下数据元素又可称为元素结点顶点记录等例如学生信息检索系统中学生信息表中的一个记录教学计划编排问题中的一个顶点等都被称为一个数据元素一个数据元素可由若干个数据项组成 3 数据项 data item 数据项是组成数据元素的单位是数据的不可分割的最小单位图 -2- 以形象的形式指出了数据元素和数据项的关系学号姓名张三李王英语高等数学 C 语言程序设计四五一个数据项一个数据元素图 -2- 学生成绩表 4 数据结构 Data Structure 数据结构指的是数据之间的相互关系即数据的组织形式是互相之间存在着一种或多种关系的数据元素的集合数据结构包括三个方面的内容数据的逻辑结构存储结构和对数 4

5 绪论第章据的运算 ( 或操作 ) () 数据的逻辑结构 (Logical Structure) 在任何问题中, 数据元素之间都不会是孤立的, 在它们之间都存在着这样或那样的关系, 这种数据元素之间存在的关系称为数据的逻辑结构数据的逻辑结构可以看作是从具体问题抽象出来的模型, 它与数据的存储无关逻辑结构可归结为以下四种基本类型 : ) 集合结构 : 结构中的数据元素之间除了同属于一个集合的关系外, 别无其他关系可以用一些离散的圆圈来表示集合的元素比如五个元素的集合如图 -2-2 所示 2) 线性结构 : 结构中的数据元素之间存在一对一的关系图 -2-3 是五个元素的线性结构 3) 树型结构 : 结构中的元素之间存在一对多的关系图 -2-4 是七个元素的树型结构 4) 图状结构 : 结构中的元素之间存在多对多的关系该结构也称作网状结构图 -2-5 是五个元素的图状结构其中树型结构和图状结构是典型的非线性结构图 -2-2 集合图 -2-3 线性结构图 -2-4 树型结构图 -2-5 图状结构在形式上, 数据结构通常可以采用一个二元组来表示 : Data_Structure=(D,R) 其中 D 是数据元素集合,R 是 D 中元素之间关系的集合例 -4 有一种数据结构 Line=(D,R), 其中 D=,2,3,4,5,6,7 R=<3,7>,<7,>,<,5>,<5,2>,<2,4>,<4,6> 这种数据结构的表示如图 -2-6 所示, 显然是一个线性结构图 -2-6 线性结构 5

6 数据结构 2 数据的存储结构 Storage Structure 数据的存储结构是指数据的逻辑结构用计算机语言的实现即数据元素及其关系在计算机存储器内的表示也称为数据的物理结构数据的存储可以采用以下四种基本的存储结构顺序存储链式存储索引存储和散列存储顺序存储是把逻辑上相邻的结点存储在物理位置相邻的存储单元里结点间的逻辑关系由存储单元的邻接关系来体现由此得到的存储表示称为顺序存储结构见图 -2-7 a 2 链式存储结点间的逻辑关系由附加的指针字段表示它不要求逻辑上相邻的结点在物理位置上亦相邻由此得到的存储表示称为链式存储结构见图 -2-7 b a0 a a2 an- a 顺序存储结构 a0 a a2 an- b 链式存储结构图 -2-7 基本存储结构形式 3 索引存储除建立存储结点信息外还建立附加的索引表来标识结点的地址 4 散列存储根据结点的关键字直接计算出该结点的存储地址上述四种基本的存储方法既可以单独使用也可以组合起来对数据结构进行存储映像同一种逻辑结构采用不同的存储方法可以得到不同的存储结构选择何种存储结构来表示相应的逻辑结构要视具体要求而定主要考虑运算方便及算法的时空要求 3 数据的运算数据的运算即对数据施加的操作如插入删除检索等在数据结构中这些运算需要通过算法来实现数据的逻辑结构数据的存储结构及数据的运算这三方面是一个整体孤立地去理解任一个方面而不注意它们之间的联系是不可取的最后通过例子来增加对数据结构三方面内容的感性认识有一张学生成绩表记录了一个班的学生各门课的成绩这个表就是一个数据结构见表 -2- 在表中每一行记录了一个学生的学号姓名和三门课的成绩及平均成绩称为该数据结构中的一个元素或一个结点对于整个表来说只有一个开始结点它的前面无记录和一个终端结点它的后面无记录其他的结点则各有一个也只有一个直接前驱和直接后继它的前面和后面均有且只有一个记录这几个关系就确定了这个表的逻辑结构为线性结构那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢? 是用一片连续的内存单元来存放这些记录如用数组表示还是随机存放各结点数据再 6

7 绪论第章用指针进行链接呢? 这就是存储结构的问题, 我们将从高级语言的层次来讨论这个问题最后, 我们有了这张表 ( 数据结构 ), 肯定要用它, 那么就是要对这张表中的记录进行查询修改删除等操作, 对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题表 -2- 学生成绩表学号姓名数学英语数据结构平均成绩张三李四王五赵六丁一数据结构课程主要研究数据的逻辑结构相应的存储结构以及定义在它们之上的一组运算, 并要求设计出相应的算法, 同时还必须分析算法的效率 5. 数据类型 (Data Type) 数据类型是程序设计语言中所允许使用的变量种类一个数据类型不仅定义了相应变量可以设定的值的集合, 而且还规定了对变量允许进行的一组运算及其规则例如, 在 C 语言中定义的整型 (int) 是 ~32767 范围内所有整数的集合, 以及可以对整数进行的加减乘除求余等运算对用户来说, 只需了解整数的各种运算的抽象特性, 而不必了解计算机实现这些计算的细节, 这样就可以使用高级语言进行程序设计所以通常可以把数据类型看作是程序设计语言中已经实现了的数据结构 6. 抽象数据类型 (Abstract Data Type,ADT) 抽象数据类型是指基于一类逻辑关系的数据类型以及定义在这个类型上的一组操作抽象数据类型的定义取决于它的逻辑特性, 而与在计算机内部如何表示和实现无关在软件设计中, 抽象数据类型的定义可以看作是描述问题的模型, 它独立于具体实现, 一般可以由元素元素之间的关系及操作三种要素来定义抽象数据类型的描述格式如下 : ADT 抽象数据类型名数据对象 :< 数据对象的定义 > 数据关系 :< 数据关系的定义 > 基本操作 :< 基本操作的定义 > ADT 抽象数据类型名其中数据对象和数据关系的定义用伪码描述例 -5 抽象数据类型字符串的定义 ADT String 数据对象 :D=a i a i Character,i=,2, n,n 0 7

8 数据结构数据关系 R=<ai-,ai> ai-,ai D i=2 n 基本操作 StrCopy(&T,S) 将串 S 复制得到串 T StrCompare(S,T) 若 S>T 返回正数若 S==T 返回 0 若 S<T 返回负数 StrLength(S) 返回 S 中元素的个数即串的长度 ClearString(&S) 将 S 清为空串 ConCat(&T,S,S2) 用 T 返回由 S 和 S2 连接而成的新串 SubString(&Sub,S,pos,len) 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串 Index(S,T,pos) 若主串 S 中存在和串 T 值相同的子串则返回它在主串 S 中第 pos 个字符之后第一次出现的位置否则函数值为 0 ADT String 抽象数据类型的定义是软件设计者之间的接口当应用程序中需要用到的各种基本数据结构都有设计好的可重复使用的抽象数据类型时以后的程序设计和程序维护将大大简化.3 算法的描述和分析瑞士计算机科学家 N.Wirth 指出程序=数据结构+算法它描述了计算机程序是由组织信息的数据结构和处理信息的算法组成二者相辅相成不可分割对实际问题的求解就是选择一种好的数据结构加上设计一个好的算法.3. 算法讲算法之前先看一个问题的求解过程例 -6 已知 n 个整数求 n 个整数中的最大数这是一个非常简单的问题下面给出求解过程将第一个数赋给 max 2 初始化计数变量 i 为 3 当 i<n 时执行以下内容比较 a[i]与 max 若 a[i]大于 max 则将 a[i]赋给 max i 自增继续比较 4 返回 max 的值这就是一个求最大数的算法因此算法是对特定问题求解过程的描述是一个能够解决问题的有具体步骤的方法是指令的有限序列算法可以用伪码自然语言和框图等形式描述也可以用程序设计语言描述从易于实现的角度考虑通常用某种程序设计语言来描述算法其优点是直接作为程序语句输入计算机后计算机就能调用和运行从而实现对问题的求解对例 -5 的算法用程序设计语言描述如下 int Max(int a[ ],int n) int i,max; 8

9 绪论 max=a[0]; for(i=;i<=n;i++) if(a[i]>max) return max; 第章 max=a[i]; 一个算法应该具有下列特性有穷性对于任意一组合法输入值在执行有穷步骤之后一定能结束即算法中的每个步骤都能在有限时间内完成 2 确定性对于每种情况下所应执行的操作在算法中都有确切的规定使算法的执行者或阅读者能明确其含义及如何执行并且在任何条件下算法都只有一条执行路径 3 可行性算法中的所有操作都必须足够基本都可以通过已经实现的基本操作运算有限次实现 4 有输入作为算法加工对象的量值通常体现为算法中的一组变量有些输入量需要在算法执行过程中输入而有的算法表面上可以没有输入实际上已被嵌入算法之中 5 有输出一个算法能产生一个或者多个输出它是一组与输入有确定关系的量值是算法进行信息加工后得到的结果这种确定关系即为算法的功能算法的有穷性是算法和程序的分界点程序并不要求在有限的步骤内或有限的时间内结束比如操作系统而算法却有这个要求算法应该有输入和输出主要是希望算法能够解决实际问题能产生有意义的结果.3.2 算法的设计要求算法度量及分析通常对于一个实际问题的解决可以提出若干个算法那么如何从这些可行的算法中找出最有效的算法呢或者有了一个解决实际问题的算法我们如何来评价它的好坏这些问题程序设计的实质是对确定的问题选择一种好结构和好算法一个好的算法应符合以下算法设计要求正确性一个好的算法应当满足具体问题的要求通常包含四层含义不含语法错误对几组输入数据运行正确对精心选择的典型苛刻而带有刁难性的几组输入数据运行正确对一切合法的输入数据都能运行正确 2 可读性算法主要是为了人的阅读与交流其次才是为计算机执行因此算法应该易于人理解另一方面晦涩难读的程序易于隐藏较多错误而难以调试 3 健壮性当输入的数据非法时一个好的算法应能做出适当反应或进行处理而不会产生莫名其妙的输出结果 4 高效率与低存储量需求一个好的算法应能够有效利用计算机的资源执行时间短存储空间小

10 数据结构需要通过算法分析来确定人们一般从两个方面来衡量算法 : 一个是时间效率, 即算法处理数据所花费的时间, 用时间复杂度 (Time Complexity) 来表示 ; 一个是空间效率, 即算法所需的存储量的大小, 用空间复杂度 (Space Complexity) 来表示二者都应尽量得低, 但二者往往不能同时兼顾, 在目前计算机硬件价格大幅度下降的前提下, 算法的时间效率应首先被考虑. 时间复杂度对于解决同一个问题的算法, 执行时间短的显然比执行时间长的效率高, 那么算法执行时间的长短如何度量呢? 当一个算法被转换成程序运行时, 许多因素会影响程序的运行时间, 如同一个算法用不同的语言实现, 或者用不同的编译程序进行编译, 或者在不同的计算机上运行时, 效率均不同, 这表明使用绝对的时间单位衡量算法的效率是不合适的为此, 可以撇开这些与计算机硬件软件有关的因素, 认为一个特定算法运行工作量的大小, 只依赖于问题的规模 ( 通常用整数量 n 表示 ), 或者说, 它是问题规模的函数一个算法的时间复杂度是指该算法的运行时间与问题规模的对应关系为了便于比较同一问题的不同算法, 通常的做法是, 从算法中选出一种对于所研究的问题来说是基本操作的元操作, 以该基本操作重复执行的次数 ( 也称为频度 ) 作为算法的时间度量一般情况下, 算法中基本语句重复执行的次数 T(n) 是问题的规模 n 的某个函数 f(n), 因此, 算法的时间度量可记作 T(n)=O(f(n)) 记号 O 读作大 O, 它表示随着问题规模 n 的增大, 执行时间的增长率和 f(n) 的增长率相同也称作算法的渐进时间复杂度 (Asymptotic Time Complexity), 简称为时间复杂度时间复杂度往往不是精确的执行次数, 而是估算的数量级, 它着重体现的是随着问题规模 n 的增大, 算法执行时间的变化趋势因此, 大 O 表示法通常只关注 T(n) 的最高阶, 而忽略其低次项和常数项例如, 一个程序的实际执行时间为 T(n)=2.7n n , 在这个多项式中随着 n 变大,n 3 项的成长比其他两项的成长速度快得多, 因此这两项可以被忽略, 可以说对于较大的 n 值, 这个子程序基本上是一个 2.7n 3 的处理程序故 T(n)=Ο(n 3 ) 例 -7 求如下两个 NN 矩阵相乘的算法的时间复杂度 for(i=;i<=n;++i) for(j=;j<=n;++j) c[i][j]=0; for(k=;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; 在以上代码中, 乘法运算是矩阵相乘问题的基本操作整个算法的执行时间与该基本操作 ( 乘法 ) 重复执行的次数 n 3 成正比, 记作 : T(n)=O(n 3 ) 显然, 基本操作重复执行次数和算法的执行时间是相同数量级的, 多数情况下它是最深 0

11 绪论第章层循环内的语句中的元操作例 -8 分析下列三个程序段的时间复杂度 a x=x+; b for (i=0; i<n; i++) x=x+; c for (i=0; i<n; i++) for (j=0; j<i; j++) x=x+; 分析上述三个程序段的问题规模均为 n 算法中基本操作 x=x+ 的执行次数分别为 n n(n+l)/2 相应的时间复杂度 T(n)分别为 O() O(n)和 O(n2), 分别称为常数阶线性阶和平方阶常见的时间复杂度按数量级递增排列依次为常数阶 O() 对数阶 O(log2n) 线性阶 O(n) 线性对数阶 O(nlog2n) 平方阶 O(n2) 立方阶 O(n3) k 次方阶 O(nk) 指数阶 O(2n) 且 O() O(log2n) O(n) O(nlog2n) O(n2) O(n3) O(nk) O(2n) 说明当 f(n)为对数函数幂函数或它们的乘积时算法的运行时间是可以接受的称这些算法是有效算法当 f(n)为指数函数或阶乘函数时算法的运行时间是不可接受的称这些 S(n)=O(f(n)) 它也是问题规模或大小 n 的函数一个上机执行的程序除了需要存储空间来寄存本身所用指令常数变量以外也需要一些存储数据操作的工作单元和为实现计算所需信息的辅助空间程序本身所有指令所占空间对不同算法来说一般不会有数量级的差别在比较算法时可以不加考虑若输入数据所占空间只取决于问题本身而和算法无关则在比较算法时也可以不加考虑故对算法空间复杂度的分析通常只需要分析实现计算所需信息的辅助空间.4 应用实践学生管理系统登录模块设计实践目的掌握程序设计的三大结构顺序结构选择结构循环结构 2 掌握结构体的定义和应用 3 掌握指针的定义和应用 4 掌握函数的编写和调用方法的存储空间记作算法是无效算法因此应尽量少用指数阶的算法 2 空间复杂度除了时间以外空间代价也是程序员要经常考虑的计算机资源近年来在计算机运行速度提高的同时其存储能力也大大增强了虽然如此可利用的磁盘或内存空间大小仍是对算法设计者的重要限制类似于时间复杂度一个算法的空间复杂度 S(n)定义为该算法所耗费

12 数据结构 2. 实践内容利用结构体和指针实现学生管理系统登录模块设计, 要求先对多个用户信息进行初始化, 用户信息包括账号和密码两部分, 然后输入当前用户的账号和密码进行验证, 正确则显示登录成功!, 错误则显示账号或者密码错误! 3. 代码清单 #include "stdio.h" #include "string.h" // 用户结构体定义 typedef struct long id; char pwd[6]; user; user users[50];// 数组定义, 用来存储多个用户信息 void init(int n)// 输入用户信息 user *p; int i; p=users;// 指针的应用 printf(" 请管理员输入用户信息 :\n"); for(i=0;i<n;i++) scanf("%ld,%s",&p[i].id,p[i].pwd); main() long stuid; char stupwd[6]; int i; int n; printf(" 请输入用户数量 :"); scanf("%d",&n); init(n);// 调用输入用户信息函数 printf(" 请您输入账号和密码 :"); scanf("%ld,%s",&stuid,stupwd); for(i=0;i<n;i++) if(stuid==users[i].id && strcmp(stupwd,users[i].pwd)==0)// 验证 printf(" 登录成功!\n"); break; if(i==5) printf(" 账号或者密码错误!"); 2

绪论第章 4 结果验证上机实验结果如图 -4- 所示图 -4- 运行结果小结数据结构课程主要讨论非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作本章主要介绍了数据数据元素数据结构等基本概念和抽象数据类型的定义习题一叙述下列概念数据数据结构数据对象存储结构数据类型和算法 2 试举一个数据结构的例子叙述其逻辑结构存储结构和运算三个方面的内容 3

13 绪论第章 4 结果验证上机实验结果如图 -4- 所示图 -4- 运行结果小结数据结构课程主要讨论非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作本章主要介绍了数据数据元素数据结构等基本概念和抽象数据类型的定义习题一叙述下列概念数据数据结构数据对象存储结构数据类型和算法 2 试举一个数据结构的例子叙述其逻辑结构存储结构和运算三个方面的内容 3 什么叫算法评判算法的优劣有哪几种方法 4 什么叫算法的时间复杂度怎样表示算法的时间复杂度 5 分析下列程序段求其时间复杂度 i=; k=0; while (i<=n-) k=k*0*i; i++; 2 i= j=0 while(i+j<=n) if (i>j) j++ 3 性及设计要求掌握计算语句频度和估算算法时间复杂度的方法表示和实现方法并详细阐述了算法设计的要求以及从时间和空间角度分析算法的方法通过本章学习要求同学们熟悉各名词术语的含义掌握数据的逻辑结构和存储结构之间的关系掌握常见的四种逻辑结构和常用的四种存储结构了解抽象数据类型相关内容理解算法的特

14 数据结构 else i++; (3)for (i=0; i<n; i++) for (j=0; j<i; j++) for (k=0; k<j; k++) x=x+; (4)x=n; /* n> */ y=0; while ((x>=(y+)*(y+)) y=y+; 6. 已知输入 x,y,z 三个不相等的整数, 试设计一个算法, 使这三个数按从小到大的顺序输出, 并考虑此算法元素的比较次数和元素的移动次数 7. 编写算法实现猴子吃桃问题 : 猴子第一天摘下若干个桃子, 当即吃了一半, 还不过瘾, 又多吃了一个 ; 第二天早上将剩下的桃子吃掉一半, 又多吃了一个 ; 以后每天早上都吃了前一天剩下的一半零一个, 到第 0 天早上想再吃时, 见只剩下一个桃子了求第一天共摘了多少个桃子 8. 编写算法 : 随机产生 n 个整数, 然后用一种排序算法将它们从小到大排序使用三种不同规模的数据进行试验 :0 个,00 个,0000 个 4

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1

C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1 C++ 程序设计告别 OJ1 - 参考答案 MASTER 2019 年月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出输入输出符合以下范例输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,