数据结构-2004--初版.ppt

,软件技术基础,教材： 数据结构教程，迟乐军等编著，北京航空航天大学出版社，2003.4 软件技术基础 王人骅 唐梓荣 北京航空航天大学出版社 参考资料： 数据结构与算法分析，美Clifford A. Shaffer著，电子工业出版社，2001.2 权威著作： The Art of Computer Programming(计算机程序设计技巧),其中的第一卷、第三卷,软件技术基础,要求的基础： 学习并掌握了一门高级语言，最好完成过一定数量的程序 目标： 提高程序设计的分析能与实际动手能力，掌握一定的数据处理方法 理解软件设计与开发的基本概念 联系方法： 姓名：高连生 电话：82317246QQ：525573325 eMail: liansheng_,软件技术基础,第零章 编程的一些问题 第一章 绪 论 第二章 线 性 表 第三章 栈和队列 第四章 串和数组,第五章 二叉树和树 第六章 图和广义表 第七章 排 序 第八章 查 找 第九章 文 件,适合于软件的开发与设计程序 包括：程序，软件开发的步骤-软件工程，程序设计的思维方法，结构化程序设计，O-O程序设计 数据结构 包括：线性表，链表，栈，队列，树，图等,软件技术基础,学习方法 讲练结合 作业：至少完成6次作业(每次布置作业后一周后上交，两周截止日期，过期减少分数-最后一次除外),结业方法 作业：30%,考试70% 考试占100%,数据结构在程序设计中是非常实用的一门技术， 是前人程序设计的结晶，希望大家能掌握这门技术， 为研究工作奠定基础。,第零章 程序设计的一些问题,程序与软件？,程序是最终达到一定目的指令序列。 例如课程表，会议程序，开学注册程序 计算机程序：计算机指令的序列，实现预期的目的。,软件 狭义：软件=程序，除了硬件都是软件 广义：软件程序 软件是一种抽象的、逻辑性的产品，它不仅是在计算机上运行的程序,还包括开发、使用和维护程序所需要的文档。 软件可以减轻劳动，提高工作效率，是计算机工作的延伸。,第零章 程序设计的一些问题,软件和属性 计算机运行中不可缺少的 预先编好，能为他人使用 商品 盘和软件 盘是软件的载体 软件的分类 应用软件 系统软件,第零章 程序设计的一些问题,程序设计的几个阶段(软件工程简介) 六、七十年代出现了软件危机 软件开发周期长 软件开发费用大 软件的正确性差 软件的可靠性差 工程化的方法-软件工程 据估计，将软件生产由手工方式转变为工程化方式，软件可靠性将提高90%，测试和维护成本大大降低。,速度：8行/天-20多行/天,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,评审,（标准：国标，军标，DOD标准）,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：说明问题，明确软件的功能，明确做什么，建立数据流图，数据字典 任务：确定软件开发的主要任务 功能：确定主要功能输入/处理/输出(IPO) 性能：确定主要性能，速度，响应时间，数据转换/传输时间，数据刷新时间 接口：与外设，与软件，与人的界面 产生：需求规格说明书，数据流程图，数据字典 （标准：国标，军标，DOD标准）,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,设计：如何解决问题，可能的解决方案，数据的处理方式，存贮方式，模块的划分、调用关系 参考：与系统相关的资料，需求规格说明书，程序设计手册，设备技术手册，支持软件文档,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：设计程序的基本流程，组织结构，输入输出，接口设计及数据结构设计 任务： 1概要结构设计程序结构，给出程序的分层结构 2功能划分分程序与模块的功能 3程序的控制流程和数据流 4系统间接口，与其他系统的接口 5内部接口 6算法上列举可能的求解算法 产生：概要设计说明，用户手册,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：对模块进行过程描述，设计模块内部细节。 任务： 1结构设计：模块细化，形成程序单元 2资源分析及余量大于20%的余量 3参数化：设计参数，增加软件的柔性 4算法的具体化 产生：详细设计说明书,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：根据详细设计说明书，编程实现，并进行调试 编程标准： 语言结构化，编程格式缩进等，控制结构三种控制结构，插入或复制程序时要完整从入口入，出口出，出/入口结构唯一，禁止自修改，程序单元的规模200行，程序中平均单元的长60行，注意转移，重定位能力，命名统一，数值约定一致，有效数字，注释行20% 调试后要进行单元测试，先逐步审查代码，后测试，通过测试用例保证每条源代码至少执行一次,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：由专门的测试人员对软件进行测试 结果：测试报告 1 测试计划 2 测试 条件：编译、链接成功，完成单元测试，walkthrough 测试： 模块测试：单元问题 联合测试：接口问题 系统测试：系统问题 正确的依据：每条语句执行一次，每个通道执行一次，每个功能正确,第零章 程序设计的一些问题,需求分析-Requirement Analysis 概要设计-Primary Design 详细设计-Detailed Design 编码调试-Coding & Debug 测试-Testing 运行与维护-Maintenance,综述：记录运行状况，为下一版本升级奠定基础,第零章 程序设计的一些问题,问题的解决 周期：需求36%，设计5%，编码与调试7%，测试15%，运行维护67%工作量 费用：需求5%，设计10%，编码调试8%，测试12%，运行维护65%费用 可靠性与正确性：步步为营，测试 统计数据 错误：60%发生在设计阶段，36%发生在编码阶段 纠正错误的费用：编制程序的费用为1，则说明阶段的费用为0.5，测试阶段的费用为25，运行阶段的费用为10 组织结构：七人小组 软件生命周期的概念,第零章 程序设计的一些问题,讨论 软件工程强调开始定型，以后不变，这在实际工作中会有问题吗？ 快速原型法Prototyping 软件工程还是快速原型？,第零章 程序设计的思维方法,程序设计的本质是实现算法，而算法是计算机解决问题精确描述，有如下特征： 入口 出口 有穷次结束 序列化 后继唯一 抽象法：变量的应用，树的处理 枚举法： 归纳法：例如求自然数的和公式 回朔法：走迷宫 子问题法：Hanio塔问题，二叉树的遍历,反对教条化,第零章 如何评价程序,正确性：让它干等于程序干的吗？，在不同的环境下的鲁棒性。 验证方法：枚举法，归纳法，抽象法，证明 时空性：时间越少，空间越小越好 时间和空间的定义 时空的矛盾 解决时间的关键是算法，解决空间的关键是数据结构 发展趋势 易读性-自己读，别人读，结构清晰，易读易理解，人机界面好，注释语句 通用性好 可靠性，可移植性-传统的程序 方法上：抽象思维，模块化,第零章 程序设计方法,结构化程序设计方法 1968年Dijkstra提出结构化程序设计，主要思想： 自上而下，逐步求精-功能结构 分层结构与模块结构的程序设计-系统结构，先全局后局部，保证块间不构成圈，块独立，块的层次分明 避免GOTO-控制结构采用三种结构 主程序员-组织结构 GOTO语句的讨论 1966年证明三种结构可以表达所需要的程序结构。 使用GOTO出现的问题- 程序结构复杂化，阅读时的静态与运行中的动态不统一，无结构形式 讨论 *运算是不是一种GOTO？ 自顶向下，逐步求精 写作文的方式 在以后的学习中大量用到,第零章 程序设计方法,自顶向下，逐步求精 写作文的方式 在以后的学习中大量用到,第一章 绪 论,1.1 什么是数据结构？,数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作的学科。,第一章 绪 论,1.2 基本概念与术语,例1：学生成绩,例2：声音、图象,数据是信息的载体，是对客观事物的符号表示，它被计算机所识别、存储和加工，构成计算机程序的加工原料。,数据元素是数据的基本单位。 它也可以再由不可分割的数据项组成,性质相同的数据元素的集合 。,例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音,数据对象是性质相同的数据元素集合。,数据元素集合（也可称数据对象） 各元素之间的关系，即结构。,从三个方面研究数据结构：,数据结构 = 数据 + 结构,数据元素之间具有的逻辑关系(结构)。,线性关系(线性结构)： 数据元素间为严格的一对一关系。,树形结构 ： 数据元素间为严格的一对多关系。,图状结构（或网状结构）： 数据元素间为多对多关系,非 线 性 结 构,具有某种逻辑结构的数据在计算机存储器中的存储方式。,顺序存储：用一组地址任意的存储单元依次存放数据元素， 链式存储：数据元素之间的逻辑关系通过指针间接地反映。,存储结构是数据结构在计算机中的表示，也称之为物理结构。,计算机内存的模型,逻辑结构： 线性结构 (线性表),a1 a2 a3 a30,存储结构:,1. 顺序存储结构:,例：,2. 链式存储结构:,数据的处理方法（算法）,查找：数学成绩前三名的同学,例：,添加：来了一个新同学,1. 研究数据元素之间的客观联系。,2. 研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。,3. 研究如何在数据的各种结构(逻辑的和物理的) 的基础上对数据实施一系列有效的基本操作。,(算法),(逻辑结构),(存储结构),为什么研究数据结构,1.4 算法及其描述,输入,一个完整的算法应该满足下面五个基本标准：,有效性,确定性,有穷性,输出,一. 算法及其性质,(2). 算法是指令的有限序列，其中每一条指令表示一 个或多个操作 。,1.算法的定义,2.算法的性质,(1). 算法是对特定问题求解步骤的一种描述。,二. 算法的描述,(1) M除以N，将余数送中间变量R； (2) 测试余数R是否等于零？ a) 若R等于零，求得的最大公因子为当前N 的值, 算法到此结束。 b) 若R不等于零，将N送入M，将R送N，重 复算法的(1)和(2)。,1. 采用自然语言来描述,问题：求两个正整数M与N的最大公因子。,2. 采用程序流程图的形式来描述,COMFACTOR( int M, int N ) int R; while( 1 ) R=M % N; if (R=0) return N; M=N; N=R; ,3. 采用某种具体程序语言来描述,4. 设计一种既脱离某种具体的程序设计语言， 又具有各种程序设计语言的共同特点的形 式化语言来描述,类 C 语言,一. 算法格式,1.3 类 C 语言简介,二. 语句,1. 赋值语句：,(1) if 条件表达式 语句串； (2) if 条件表达式 语句串1； else 语句串2； ,变量名 =表达式,2. 条件语句(两种),3. 循环语句(三种),do 语句串； while(循环条件),for (赋初值表达式；条件表达式；修改表达式) 语句串; ,while (循环条件) 语句串； ,switch(表达式) case 判定值1：语句串1； break; case 判定值2：语句串2； break; . . . . case 判定值n：语句串n； default ： 语句串n+1; break; ,4. 情况语句,1、 /* 注释内容 */ 2、/,1、字符：函数getchar()、 putchar()实现 2、其他数据：函数scanf() 、printf()实现表),5. 输入/输出语句,6. 注释,求两个n阶矩阵的乘积： MATRIX( int A ,int B ,int C ,int n ) for (i=1 ; i=n; i+) for ( j=1; j=n; j+ ) Ci, j=0; for ( k=1; k=n; k+ ) Ci, j=Ci, j+Ai, k*Bk, j; ,例,1.5 算法分析,1、正确性 2、可读性 3、健壮性 4、效率与低存储量需求 效率指的是算法执行时间。 存储量需求指算法执行过程中所需要的最大存储空间。 两者都与问题的规模有关。,是指对算法质量优劣的评价。,3其他方面。如算法的可读性、可移植性以 及易测试性的好坏。,2依据算法编写的程序在计算