当前位置:首页 >> 工学 >>

第一章 数据结构----绪论


数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

课程导入
课程性质:专业必修课 总学时数:20*3=60 学时 上机学时:18*2=36 学时 假设前提:已有程序设计基础(C/C++基础,尤其是 C 语言程序设计基础) 学习目标:培养数据抽象能力(Data Abstraction Ability) 。注:C 程序设计 课则是培养结构化程序设计的能力。 具体涉及两个方面内容的学习和训练: 1) 学会分析研究计算机加工数据结构的特征,以便学会针对不同的应用问 题,选择合适的逻辑结构、存储结构及相应的算法描述。并做相应的时间复杂 度和空间复杂度的分析。 2) 复杂程序设计方法的训练过程。学会将问题求解的程序设计成结构清楚、 正确、符合软件工程规范的系统。 学习方法:勤奋练习,积极上机实践。(熟悉各种数据结构的基本思想和算 法描述,并不断尝试结合教材内容和课外训练的数据抽象能力的培养) 教学步骤:整体上分为两个部分内容,一是数据结构的基本思想、方法与应 用技巧,二是上机实践。 具体内容: 第一章 绪论 第二、三、四、五、六、七章 基础(强调从 ADT 的角度进行描述的思想) 第八章 OS/Compiler 中的动态存储管理技术(×) 第九、十章 查找/内排序 第十一章 外排序(×) 第十二章 文件结构(×) 注:由于学时数的限制,第八章、第十一章和第十二章暂时不做要求。其它 章节中,带**号的章节不做要求或不做考试要求。

课程教材
《数据结构》 ,严蔚敏,吴伟民 编著,北京:清华大学出版社,2003 年 3 月

参考书目
(1) 《计算机算法:设计和分析引论》 ,[美] S 巴斯, 朱洪 等译,上海:复旦 大学出版社,1985 (2) 《Data Structures with C++》,[美] William Ford, William Topp, 北京:清华 大 学 出 版 社 , Printice-Hall International, inc. 1998 年 4 月 , ISBN 7-302-02413-8 (3) 《数据结构、算法与应用----C++语言描述》 ,[美] Sartaj Sahni 著,汪诗林,
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

孙小东 译,北京:机械工业出版社,2002 年 10 月,ISBN 7-111-07654-1 (4) 《计算机程序设计艺术》 (第 2 版) ,第 3 卷,[美]Donald E.Knuth 著,北 京:清华大学出版社,2002 年 9 月,ISBN 7-302-05816-4 (5) 《算法设计技巧与分析》(沙特)M.H. Alsuwaiyel 著,北京:电子工业出 , 版社,2004 年 8 月,ISBN 7-121-00108-X 注:其它很好的学习类参考书籍,请咨询高年级学长或光临书店!

习题及实验参考书
(1) 《数据结构实验教程》(C 语言版),王玲 主编,成都:四川大学出版社, 2003 年 7 月 (2) 《数据结构习题集》(C 语言版),严蔚敏,吴伟民 编著,北京:清华大 学出版社,2003 年 1 月

第一章 绪论
需要对程序的处理对象进行组织研究的两大主要原因: 一是计算机领域的渗透早已使其应用不再局限于早期的科学计算领域?其加工处理对 象由纯粹的数值类发展到具有一定结构的数据类型,如字符、表、图形、图像、声音等, 使得程序设计活动面临了许多新的问题需要解决。 二是要编写出好的程序系统,人们发现,必须要对待处理对象的数据特性、各处理对象 之间的关系进行分析、组织,使编写出的程序能够有效地处理和解决它们。 它们构成了数据结构的研究动力和研究内容。

1-1 什么是数据结构?
Data Structure (DS): Data---- (1) facts; (2) Information prepared for or stored by a computer; Structure---- way in which something is put together, organized, built, etc.

1-1-1 不同问题的数据结构模型构建实例分析
用计算机解决问题的步骤: 抽象其数学模型?求解该模型的算法?编制程序?测试或调 试?得解 (1) 对数值计算问题 例 1-1 求解梁架结构中应力的数学模型;预报人口增长的微分方程模型。 其关键在于分析问题,提取或寻找对象之间的结构关系,然后用数学语言加以描述。 (2) 对无法用数学模型描述的非数值计算问题 其数学模型集中在数据结构的建立中。 例 1-2 图书馆书目检索系统自动化问题。 按书名的索引表、按作者名的索引表、按分类号的索引表、按登录号排列的书目表表示

作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

结构就是其检索问题中的基本数据关系的数学模型(此为线性的结构关系模型)。(见教材 P1-2) 例 1-3 人机对弈问题。 其对弈策略、规则驱动、棋盘状态、前景预测方法等模型的建立,同时,棋盘状态描述 模型是对弈问题的关键性数据描述模型, 但棋局之间的关系往往不是线性的, 需要用非数值 型结构来描述。例如:#字游戏问题(见教材 P2)。需要用到所谓“树结构”来描述这些棋盘 状态之间转换过程。 例 1-4 多叉路口交通灯的管理问题(在多叉路口需要设多少颜色的灯,使得车辆之间互 不碰撞,同时车流量最大) (见教材 P2-3) ??对图的顶点作图的问题。 与此相关的还有如哥黎斯堡七桥问题、逻辑电路设计问题等,用传统的数学模型是无法 描述的。必须用新型的所谓“图结构”进行描述。

1-1-2 DS 课程的研究内容及课程历史
DS 研究内容:研究非数值计算的程序设计问题中计算机的操作对象以及它们之间关系 和操作的一门学科课程。 DS 作为一门独立课程的发展历史: 1968 年,DS 与图论、表、树为“同义语” 。后来,扩充到了网络、集合代数、格、关系 等(它们又构成了“离散数学”的基础内容)。再后来,将大型数据库系统中的文件管理以及 内 存管理等技术也纳入了本课程中来。 《计算机程序设计艺术》(第一卷) ,Donald Knuth1 (Turing 奖获得者)(开创 了最初的 DS 体系, 是第一本系统阐述数据的逻辑结构、 存储结构及其操作的著作) 目前,DS 是许多专业的选修或必修课。 DS 课程的地位(综合性非常强)(见教材 P4 图 1.4):界于数学、计算机软件和 计算机硬件之间的核心课程。既是一般程序设计的基础,更是编译程序、OS、DBS 及其它大 型的系统程序和应用程序设计与实现的重要基础。 发展方向: 1) 向各专门领域中的特殊问题之数据结构研究发展; 2) 从 ADT 观点来研究。

1-2 数据结构中涉及的基本概念与术语 1-2-1 基本概念和术语
(1) Data----(facts/information)能被计算机处理的符号总称,是待加工的“原料” 例如:求解代数方程组时的 Data 为 integer/real 型的系数或根等; 编译器的 Data 为:程序代码或字符序列; 文字编辑器的 Data 为:字符、图形等。 (2) Data Element----对数据进行处理的基本单位 例如:前述的棋盘之格局;图中的顶点等。 注:数据元素一般由若干数据项(Data Item)组成。
1

作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

又如:前述图书书目中的书卡数据由作者姓名、书名、书号等数据项构成。 (3) Data Object----相同性质的数据元素之集合 例如:整数数据对象即集合 N ? { 0 , ? 1, ? 2 ,...} ;字母字符对象即 C ? {' A ' , ' B ' ,...} ;计 算机信息与计算科学专业 2003 级学生对象即全体该班的学生集合等。 (4) Data Structure----相互之间存在某种特定关系的数据元素之集合(从操作对象抽象出 来的数学模型) 注 1:DS 中的数据元素不是孤立存在的; 注 2:数据元素之间的关系即可称为“结构” ; 注 3:数据元素之间的关系有 4 种基本结构: 集合(set)关系----无序的松散关系; 线性(linear)关系----一一对应关系(one-one); 树(tree)关系----一对多关系(one-many); 图(graph)关系或者网(net)关系----多对多关系(many-many)。 (如教材 P5 图 1.5 所示) 注 4:DS 的形式定义为:D_S=(D,S)。其中,D 为数据对象有限集合,S 为 D 上的关 系有限集合。 注 5:一般而言,DS 要表达的是一组具有相同结构的数据对象之值的集合。

1-2-2 实例分析
例 1-4 复数关系的定义。 数据结构:Complex=(C,R)。 其中,C 是两个实数集合{c1,c2};R 是定义在 C 上的一种关系,即 R={P}={<c1,c2>}。其 中,序偶< c1,c2>中的 c1 表示复数的实部,c2 表示复数的虚部。 例 1-5 事务管理程序中的课题小组信息的数据结构。假设 1 位老师带 1~3 名研究生,1 位研究生带 1~2 位学生,则数据结构如下:Group=(P,R)。 其中,P={T,G1,…,Gn,S11,…Snm,1<=n<=3, 1<= m<=2} R={R1, R2} R1={<T, Gi>|1<=i<=n,1<=n<=3} R2={<Gi,Sij>|1<=i<=n, 1<=j<=m, 1<=n<=3, 1<=m<=2}

1-2-3 其它概念与术语
(1) 逻辑结构(Logical Structure)---描述数据元素之间的逻辑关系的结构。 (2) 物理结构(Physical Structure)----描述数据元素在计算机中的实际存储映射关系的 结构,又称存储结构。 存储结构一般包含两个部分的内容:一是数据元素的存储,二是数据元素之间关系的 存储。 (3) 容量单位问题 Byte, bit, KB, MB, GB, TB (4) 数据域(Data Field)----当数据元素由若干个数据项组成时,各数据项位串被称为数 据域。 (5) 数据节点(Node)----数据元素。
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

(6) 数据元素之间关系的两种映射方法 顺序映射----顺序存储结构。 借助元素在存储器中存储的相对位置关系来表示数据元素 之间的逻辑关系。 非顺序映射----链式存储结构。 借助指示元素存储地址的指针来表示元素之间的逻辑关 系。 注:数据的逻辑结构与物理结构是紧密相关的。一般来讲,任何一个算法的设计取决 于其数据的逻辑结构,而算法的实现取决于其数据的存储结构。 (7) 虚拟存储结构----存储结构的基于高级程序设计语言的描述方法 通过高级语言的数据类型来描述。 例如:一维数组用于描述顺序存储结构;指 DS 针用于描述链式存储结构;struct, union 等用来表 C 语言 虚拟存储结构 示复杂问题的数据结构。 DS 中的虚拟存储结构在计算机系统中的层 OS 次位置如图 1-3 所示。 物理存储结构 Hardware (8) 数据类型(Data Type)----用于刻画程序中的 操作对象之值的集合及定义在其上的一组相应操 图 1-3 数据结构的虚拟存储结构的系统 作的抽象总称。 层次定位 注 1:每个变量、常量或表达式都有一个属 于它的数据类型。 显式地或者隐含地规定了变量等在程序执行期间的所有可能取值, 及其上 允许的一组操作。 注 2: 数据类型一般分为原子类型(Atom Data Type)和结构类型(Structure Data Type)。 前者即基本数据类型,后者即复杂结构类型。 注 3:数据类型的作用:从硬件的角度,它是解释计算机内存信息含义的手段;从用 户的角度,它实现的信息的隐藏,将用户不必了解的细节隐藏了起来。 (9) 抽象数据类型(Abstract Data Type)----一个数学模型及定义在其上的一组操作。 注 1:其定义仅取决于其逻辑结构特性,与机器内部的表示与实现无关。只要其数学 特性不变,则其外部的使用将不受影响。 注 2:本质上跟数据类型概念一致。但 ADT 比之更广泛,不再局限于处理器已经定义 的类型(固定数据类型),还包含用户设计软件时的自定义数据类型。 注 3:程序设计方法学:软件系统框架应建立在数据之上,而不是建立在操作之上。 其目的是为了提高软件的复用程度。具体而言,即:在软件系统每个相对独立的模块上, 建立起一组数据和施加于这些数据的一组操作,并在模块内部给出这些数据的表示及相应 的操作细节,但在外部的使用只是其抽象的数据和抽象的操作。

1-2-4 ADT 的结构及定义方法
抽象数据类型的形式定义(三元组):ADT=(D,S,P) 其中,D----Data, S----Relations on D, P----Operations on D。 本书对抽象数据类型的定义形式: ADT 抽象数据类型名 { 数据对象:<数据对象的定义> 数据关系:<数据关系的定义> 基本操作:<基本操作的定义> } ADT 抽象数据类型名
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

其中数据对象和数据关系用伪码描述。 基本操作的一般定义格式为: 基本操作名(参数表) 初始条件:<初始条件描述> 操作结果:<操作结果描述> 其中, 参数表中的参数有赋值参数(只负责提供操作用的输入值)和引用参数(&)(既可输 入值,也返回操作结果值)。 初始条件描述了操作执行之前,数据结构和参数应当满足的要求,若不满足,操作将失 败,并应返回相应出错信息。如没有初始条件,则初始条件为空。 操作结果是指在正常操作完成之后,数据结构的变化及其它应该返回的结果。 例 1-6 对抽象数据类型三元组的定义。 ADT Triplet { 数据对象:D={e1,e2,e3|e1,e2,e3 ? ElemSet} 数据关系:R1={<e1,e2>,<e2,e3>} 基本操作: InitTriplet(&T,v1,v2,v3) 操作结果:构造三元组 T,v1,v2,v3 分别赋给元素 e1,e2,e3。 DestroyTriplet(&T) 操作结果:三元组 T 被销毁。 Get(T,i,&e) 初始条件:三元组 T 已经存在,且 1<=i<=3 操作结果:用 e 返回 T 的第 i 个元素 Put(&T,i,e) 初始条件:三元组 T 已经存在,且 1<=i<=3 操作结果:改变 T 的第 i 个元素的值为 e IsAscending(T) 初始条件:三元组 T 已经存在 操作结果:如果 T 的三个元素按升序排列,则返回 true,否则,返回 false IsDescending(T) 初始条件:三元组 T 已经存在 操作结果:如果 T 的三个元素按降序排列,则返回 true,否则,返回 false Max(T,&e) 初始条件:三元组 T 已经存在 操作结果:用 e 返回 T 的三个元素中的最大者的值 Min(T,&e) 初始条件:三元组 T 已经存在 操作结果:用 e 返回 T 的三个元素中的最小者的值 } ADT Triplet 多形数据类型(Polymorphic Data Type)----具有相同的数学抽象特性的类型,即不论元 素的特性如何,元素之间的关系及对元素的操作都相同。 注 1:多形数据类型由 C++类 OOPL 语言实现之。即 C++中的多态技术。 注 2:本书以 C 为背景描述算法,所以,都假定其数据元素的成分是确定的。其在上机 实践时需要由程序设计者确定或自行定义。

作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

1-3 ADT 的表示与实现
基本原则:通过高级语言中固有的 DT 来表示和实现。(本书)介于伪代码与 C 语言之间 的类 C 描述,以便于转成 C 或 C++程序实现之。 为什么选择 C?C 语言并不是描述抽象数据类型(即数据结构)的理想工具。但鉴于如 下理由: “面向对象的程序设计”并非程序设计的入门课程或“数据结构”课程的先修课程。 同时,由于 C/C++又是目前计算机软件程序设计实现中的主流环境工具。 解决的办法:本书精选了一个 C 语言的核心子集, 并增添了 C++的引用调用参数传递方 式,构成了数据结构和算法描述的 C 描述语言。其特点:不拘泥于 C 的细节,又容易转换 成 C/C++程序。 本书的类 C 工具核心子集说明:(教材 P10-13) (1) 预定义常量 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status /*Status 表示函数的类型,其值是函数结果的状态编码*/ (2) DS 的表示 数据结构的表示或存储结构都用“类型定义”进行描述,即 typedef。数据元素的用 Elem Type 表示,其具体类型由用户在实现时定义。 (3) 基本操作或算法都以函数的形式描述 一般的函数格式: 函数类型 函数名(函数参数表) { /*算法说明部分*/ 算法实现的语句序列 }//函数名 注 1:参数类型要说明。算法内部使用的辅助变量可以不说明,或做简要注释即可。 注 2:约定符号含义: 1) a,b,c,d,e 等表示数据元素的名; 2) i,j,k,l,m,n 表示整型变量名; 3) p,q,r 等表示指针变量名; 4) 当函数返回值为结果状态时,函数类型用 Status 说明; 5) 函数调用有两种: 值调用; 引用(C++概念, 用?&?表示在 C 中用指针的形式表示)。 (4) 赋值语句的形式 简单赋值、串联赋值和条件赋值与 C 相似; 成组赋值形式:(变量名 1,…,变量名 n)=(表达式 1,…,表达式 n) 结构名=结构名; 变量名[]=表达式; 变量名[起始下标..终止下标]=变量名[起始下标..终止下标]; 交换赋值形式:变量名??变量名; (5) 选择语句(if/switch)

作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

(6) 循环语句(for/while/do-while) (7) 结束语句(return/break/exit(异常代码)) (8) I/O 语句(scanf()/printf()) (9) 注释(//) (10) 基本函数 max(表达式 1,…,表达式 n) min(表达式 1,…,表达式 n) abs(表达式) floor(表达式)----求不足整数值 ceil(表达式)----求进位整数值 eof(文件变量)----判定文件是否结束 eoln(文件变量)----判定行是否结束 (11) 逻辑运算约定(&&, ||, !等) 例 1-7 抽象数据类型 Triplet 的表示与实现。 //----------采用动态分配的顺序存储结构---------typedef ElemType *Triplet; //三元组元素的数据类型,ElemType 需要自 us 定义 //----------基本函数的原型说明---------Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3); //操作结果:用 v1,v2,v3 构造三元组 T Status DestroyTriplet(Triplet &T); //操作结果:销毁三元组 T Status Get(Triplet T,int i, ElemType &e); //初始条件:三元组 T 已经存在,i 的取值为 1-3 //操作结果:将 T 的第 i 个元素取出来,用 e 返回之 Status Put(Triplet &T, int i, ElemType e); //初始条件:三元组已经存在,i 的取值为 1-3 //操作结果:用 e 作为 T 的第 i 个元素的值 … //----------基本操作的实现---------Status InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3) { //用 v1,v2,v3 构造三元组 T T=(ElemType*)malloc(3*sizeof(ElemType)); //分配三个元素空间 if (!T) exit(OVERFLOW); //分配失败时,退出程序执行 T[0]=v1; T[1]=v2; T[2]=v3; return OK; } // InitTriplet Status DestroyTriplet(Triplet &T) { //销毁三元组 T free(T); t=NULL; Return OK; } // DestroyTriplet
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

Status Get(Triplet T,int i, ElemType &e) { //将 T 的第 i 个元素取出来,用 e 返回之 if (i<1 || i>3) return ERROR; //下标值不合法时,直接退出 e=T[i-1]; return OK; } // Get …

1-4 算法与算法分析方法 1-4-1 算法及其特征
算法(Algorithm):对特定问题求解步骤的描述指令操作的有限序列。 (Set of rules or procedures that must be followed in solving a problem) 基本特征: 1) 有穷(Finite) 对任何合法的输入值,算法必须在有限步骤之内停止或完成或结束。 注:这种“有穷性”使得算法不必保证一定得解。其结果有如下几中情形:有解;无解; 有理论解,但算法的运行没有得到之;不知有无解,且算法的有穷执行中也没有得到解。 2) 确定性(Definite) 算法中的每一条指令必须有确切的含义,不会产生理解上的偏差。 算法在任何时候只有唯一的一条执行路径。即相同输入,得相同输出。 3) 可行性(Feasibility) 算法是可行的。其描述的操作都是可以通过基本运算的有限次运算来实现的。 4) 输入(Input) 有 0 个或多个输入。 5) 输入(Output) 有 1 个或多个输出。

1-4-2 算法设计的要求
好算法的主要特性: 1) 正确性(Correctness):满足具体问题的要求。 四种级别要求: 无语法错误?(2) 对几组输入数据可得到符合要求的解?(3) 对精选 (1) 的、典型的、苛刻的输入能得到符合要求的解?(4) 对一切合法的输入都可以得到符合要求 的解。 2) 可读性(Readability):好(易于阅读、理解、交流) 3) 健壮性(Robustness):对非法输入数据或操作,能从容应对并给出提示,不影响结果。 4) 时空效率(Time-Space Efficiency):高时、空效率。

作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

1-4-3 算法(时间)效率的度量方法
两种度量方法: 1) 事后统计法 其依赖的因素是算法的实现和具体的计算机软/硬环境情况。 2) 事先估计法 程序执行过程的耗时分析:(1) 算法策略;(2) 问题规模;(3) 程序代码实现的语言种类 (语言级别越高,时间效率越低);(4) 编译器的质量;(5) 机器的执行速度等。 结论 1:绝对的时间单位来衡量算法的效率是不合适的。 结论 2:除开软、硬件因素外,效率或工作量主要决定于问题的规模大小。 算法的渐进时间复杂度(Asymptotic time complexity)或时间复杂度: (1) 一个算法取决于控制结构(顺序、选择、循环)和原操作的综合效果。因此,可以用关 于问题规模的函数来表示算法的“原操作”时间为单位的效率度量。一般表示为:
T ( n ) ? O ( f ( n ))

例如:N*N 矩阵乘法中, “乘法”是该问题的基本操作或原操作,所以: for (i=1;i<=n;++i) { for (j=1;j<=n;++j) { c[i][j]=0; for (k=1;k<=n;++k) { c[i][j]+=a[i][k]*b[k][j]; } } } 以上算法的乘法是基本操作,其次数与 n3 成正比,记作 T(n)=O(n3)。 (2) 原操作的频度(Frequency count):即原操作的重复执行次数。 例如:(a) {++x;s=0} (b) for (j=1;j<=n; j++) {++x;s+=x;} (c) for(j=1;j<=n;j++) for(k=1;k<=n;k++) {++x;s+=x;} 以上例中,(a), (b), (c)中“++x”的执行频度分别是 1,n,n*n。其复杂度可表示为 O(1), O(n), 2 O(n )。

1-4-4 常见的时间复杂度函数增长率分析
常见的时间复杂度:O(1)----常量阶;O(n)----线性阶;O(n2)----平方阶;O(logn)----对数 阶;O(2n)----指数阶;O(nk)----多项式阶。 注 1:应尽量用多项式阶的算法,少用指数阶的算法。 注 2:时间复杂度往往只考虑问题的规模 n 的关系。
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

注 3:除特别说明,一般指的是最坏情形之值。 增长率的分析(见教材 P16 图 1.7)。 结论:尽可能选 O(nk)型算法或 log(n)型算法。 复杂度的确定的一般原则:一个问题选一个基本操作,也可选几个基本操作。根据具体 问题,复杂度可以选增长率、平均值、执行次数等作为标准。

1-4-5 算法的空间复杂度(Space Complexity)
所需存储空间主要有两类: 1) 常量、指令、变量、输入输出数据空间等; 2) 对数据进行加工的工作单元和中间存储用的辅助空间。 注 1:若额外空间对输入数据量来将是常数的,则可称之为原地工作。 注 2:所占空间量依赖于特定输入,除特别说明外,均指最坏情形。

算法书写规范
(1) 算法说明 又称算法的规格说明。是完整算法描述的不可或缺的部分。 说明内容: 1) 算法要完成的功能; 2) 算法中各个参数的含义和输入、输出意义说明; 3) 算法中引用的全局变量和外部定义变量的说明,其作用和使用方法,入口的初始 值及其应当满足的条件如何。例如:链表是否带有头结点、表中元素是否有序、是升序 还是降序等。 算法说明的时间:在算法设计的开始就应当明确,并在设计过程中补充。 算法说明的作用:用于判别一个算法是否正确的基础。 注意事项:算法规格说明中,应当假定所划分出来的子问题是能够实现的,而如何实现 是算法要完成的工作。 (2) 注释和断言 对算法描述中的难以理解的和关键性的语句或描述段落,应当加上相应的注释以提高算 法的可读性。注释不是越多越好,但其抽象程度应略高于算法语句所表达的含义。 注意事项:多些断言式注释,是增强算法可读性的重要途径。以断言式描述作为算法描 述的手段,是提高结构化算法描述的手段。 (3) 输入和输出 一般通过参数、输入输出语句或全局变量或外部变量形式传递算法所需要的信息。 (4) 错误处理 尽量使用算法中的函数返回值形式返回执行状态,以便实际实现时的异常处理。 (5) 语句选用 尽量使用类 C 结构的语句,如 if else,while,for ,do while 等。 (6) 其它建议 建议尽量能够以图的形式说明算法过程或思想; 建议在算法书写完后,要用边界条件输入参数值进行验证,以便察看算法是否能够顺利 执行。
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

算法书写的说明实例: 例 1 从线性表中删除 k 个元素的算法 Status Delete(SqList a,int i,int k) //本算法从顺序存储的线性表 a 中删除第 i 个元素开始的 k 个元素 例 2 多一元多项式求值的算法 float Evaluate(SqPoly pn,float x) //本算法计算多项式 pn 中 x 的确定后的值,算法不判别计算是否溢出 //算法的计算公式是: ?
m

ai x

ei

i ?1

//pn 为以结构体形式存放每项值的顺序存储结构, 其中 pn.data[i].coef 和 pn.data[i].exp 分 别存放第 i 项的系数 a i 和指数 e i 。 //要求多项式 pn 中的各项按指数升序排列,即满足 0 ? e1 ? e 2 ? ... ? e m ,且指数非负。 例 3 入栈操作 push 的算法 void push(TwoWayStack &tws, int i, ElemType x, bool &overflow) //两栈共享一个大小为 m 的空间,其存储空间表示为 tws.elem[0..m-1],其中,两个栈的 栈顶分别在存储空间的两端,分别用 tws.top[0]和 tws.top[1]表示其指针。 //两栈的表示范围如下:tws.data[0..tws.top[0]]为第一个栈的范围; // tws.data[tws.top[1]..m-1]为第二个栈的范围。 //本算法的功能是:将元素 x 放入栈 i,其中,i 表示将操作的栈序号 //如果 push 操作时,栈 i 已经满,则不改变栈指针和栈内容,且返回 overflow 为 TRUE 表示栈溢出。

课外习题
1-1 简述下列术语:数据(data)、数据元素(data element)、数据对象(data object)、数据结 构(data structure)、 存储结构(Store Structure)、 逻辑结构(Logic Structure)、 数据类型(data type)、 抽象数据类型(abstract data type) 1-2 试个给出数据结构、抽象数据类型和程序设计语言中的数据类型之间的区别。 1-3 有数据结构(D,R),其中: D ? { d 1, d 2, d 3, d 4} , R ? { r } , r ? { ( d 1, d 2 ), ( d 2, d 3), ( d 3, d 4 )} , 试给出其逻辑结构图。 1-4 请给出以下程序段的流程图描述: (1) product=1;i=1;while (i<=n) {product*=i;i++} (2)i=0;do {i++;} while ((i!=0) && (a[i]!=x)); 1-5** 设 n 为正整数。试确定下列程序段中前面有@的语句的执行频度。 (1) i=1;k=0; while (i<=n-1) { @ k+=10*i; i++; } (2) i=1;k=0; do { @ k+=10*i; i++ } while (i<=n-1);
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班

(3) k=0; for (i=1;i<=n;i++) for (j=i;j<=n;j++) @ k++; (4) x=91;y=100; while (y>0) { @ if (x>100) {x-=10;y--;} else x++; } 1-6* 假设 n 为 2 的乘幂,且 n>2,试求以下算法的时间复杂度及变量 count 的值(以 n 的 函数的形式表示)。 int Time(int n) { count=0;x=2; while (x<n/2) { x*=2;count++; } return (count); }//Time 1-7* 已知有实现同一功能的两个算法, 其时间复杂度分别为 O ( 2 n ) 和 O ( n 1 0 ) ,假设计算机 可连续运算的时间为 1 0 7 秒(100 多天),每秒的基本操作为 1 0 5 次。试问两个算法可解问题的 规模各是多少?哪个算法更合适?为什么? 1-8* 试用数学归纳法证明: (1) ? i 2
i ?1 n

? n ( n ? 1)( 2 n ? 1) / 6 ( n ? 0 )

(2) ?
i?0

n

x ? (x
i

n ?1

? 1) /( x ? 1)( x ? 1, n ? 0 )

(3) ?
i ?1

n

2

i ?1

? 2 ? 1( n ? 1)
n

(4) ?
i ?1

n

( 2 i ? 1) ? n ( n ? 1)
2

1-8* 假设有 A,B,C,D,E 五个高校进行田径对抗赛, 各院校的单项成绩均存入计算机,并 构成一张表,表中每一行如下: 项目名称 性别 校名 成绩 得分 试编写算法,以处理以上表格,统计各个院校的男女总分和团体总分,并输出结果。 1-9** 试编写算法, 计算 i !? 2 i ( i
? 0,1, ...., n ? 1)

的值, 并分别存入数组 a[arrsize]的各个分量
k ? n ?1

中。假设计算机中允许的整数最大值为 MAXINT,则当 n>arrsize 或对某个 k( 0 ? 使得 k !? 2 k ? M A X IN T 时,应按出错处理。注意选择你认为较好的出错处理方法。 1-10** 试编写算法求一元多项式 Pn ( x ) ? ?
i?0 n

)

ai x

i

的值, 并确定算法中每一语句的执行次数

和 整个 算法的 时间 复杂度 。注 意选择 你认为 较 好 的输 入和输 出方法 。本 题的 输入为
作者:冯山

数学与软件科学学院信息与计算科学专业 2006-2007 年第 1 学期《数据结构》教案-详案-2004 级 6 班
a i ( i ? 0,1, ..., n )

和 x 0 、n,输出为 Pn ( x 0 ) 。

作者:冯山


相关文章:
《数据结构》吕云翔编著第1章绪论习题解答
数据结构》吕云翔编著第1章绪论习题解答_工学_高等教育_教育专区。《数据结构》吕云翔 郭颖美编著第1章绪论习题解答 数据结构第一章绪论习题一、 【单选题】 1...
通信数据结构第一章绪论习题
通信数据结构第一章绪论习题 - 第一章 绪论 一、选择题 1.以下数据结构中哪一个是非线性结构?( ) D. 二叉树 A. 队列 B. 栈 C. 线性表 2.设某数据...
数据结构 第1章绪论习题答案
数据结构 第1章绪论习题答案 - 第一章 绪论参考答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 和运算等的学科。 2. 数据结构被...
《数据结构》习题汇编01 第一章 绪论 试题
数据结构》习题汇编01 第一章 绪论 试题 - 《数据结构与算法设计》习题册 第一章 绪论 一、单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中...
第一章 绪论
第一章 绪论 - 第一章 绪论 一.填空题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的___ 以及它们之 间的___ 和操作...
数据结构第1章绪论习题解析
数据结构第1章绪论习题解析 - 《数据结构第一章绪论部分习题 数据结构》 一、选择题 1. 下面说法错误的是 。 (1)算法原地工作的含义是指不需要任何额外的...
数据结构作业1-第1章 绪论
数据结构作业1-第1章 绪论 - 第一章概论 一、填空题 自测题答案 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 等的学科。 2. 数据结构被形式...
数据结构第1章绪论
数据结构第1章绪论_理学_高等教育_教育专区。第一章 习题 判断题 1. 数据元素是数据的最小单位。(× ) 2. 记录是数据处理的最小单位。 (× ) 3. 数据的...
第一章绪论
第一章绪论 - 定义与名词解释: 数据结构、数据元素、逻辑结构、存储结构、算法。 一、 判断题 1.数据的逻辑结构是数据的机外表示,数据的存储结构是数据的机内...
数据结构(Java)复习题及答案 1绪论
数据结构(Java)复习题及答案 1绪论 - 一、单项选择题 ( B )1. 计算机算法必须具备输入、输出和 等 5 个特性。 A) 可行性、可移植性和可扩充性 C) 确定...
更多相关标签: