数据结构-2004-02-01初版

1、软件技术基础软件技术基础教材：教材：数据结构教程，迟乐军等编著，北京航空航天大学出版社，数据结构教程，迟乐军等编著，北京航空航天大学出版社，2003.4软件技术基础软件技术基础 王人骅王人骅 唐梓荣唐梓荣 北京航空航天大学出版社北京航空航天大学出版社参考资料：参考资料：数据结构与算法分析，数据结构与算法分析，美美Clifford A. Shaffer著，电著，电子工业出版社，子工业出版社，2001.2 权威著作：权威著作：The Art of Computer Programming(计算机程序设计技巧计算机程序设计技巧),其中其中的第一卷、第三卷的第一卷、第三卷软件技术基础软件技术基础要求的

2、基础：要求的基础：学习并掌握了一门高级语言，最好完成过一定数量的程学习并掌握了一门高级语言，最好完成过一定数量的程序序目标：目标：提高程序设计的分析能与实际动手能力，掌握一定的数提高程序设计的分析能与实际动手能力，掌握一定的数据处理方法据处理方法理解软件设计与开发的基本概念理解软件设计与开发的基本概念 联系方法：联系方法：姓名：高连生姓名：高连生 电话：电话：82317246Q：525573325eMail: liansheng_软件技术基础软件技术基础第零章第零章 编程的一些问题编程的一些问题第一章第一章 绪绪论论第二章第二章 线线 性性 表表第三章第三章 栈和队列

3、栈和队列第四章第四章 串和数组串和数组第五章第五章 二叉树和树二叉树和树第六章第六章 图和广义表图和广义表第七章第七章 排排序序第八章第八章 查查找找第九章第九章 文文件件适合于软件的开发与设计程序包括：程序，软件开发的步骤-软件工程，程序设计的思维方法，结构化程序设计，O-O程序设计(2)VC环境下的程序设计初步(3)数据结构包括：线性表，链表，栈，队列，树，图等软件技术基础软件技术基础学习方法学习方法讲练结合讲练结合作业：至少完成作业：至少完成6次作业次作业(每次每次布置作业后一周后上交，两周布置作业后一周后上交，两周截止日期，过期减少分数截止日期，过期减少分数-最最后一次除外后一次除外)

4、结业方法结业方法作业：作业：30%,考试考试70%1.考试占考试占100%数据结构在程序设计中是非常实用的一门技术，是前人程序设计的结晶，希望大家能掌握这门技术，为研究工作奠定基础。第零章第零章 程序设计的一些问题程序设计的一些问题程序与软件？程序程序是最终达到一定目的指令序列。例如课程表，会议程序，开学注册程序计算机程序计算机程序：计算机指令的序列，实现预期的目的。软件软件狭义：软件=程序，除了硬件都是软件广义：软件程序软件是一种抽象的、逻辑性的产品，它不仅是在计算机上运行的程序,还包括开发、使用和维护程序所需要的文档。软件可以减轻劳动，提高工作效率，是计算机工作的延伸。第零章第零章 程序设

5、计的一些问题程序设计的一些问题软件和属性计算机运行中不可缺少的预先编好，能为他人使用商品盘和软件盘是软件的载体软件的分类应用软件系统软件第零章第零章 程序设计的一些问题程序设计的一些问题程序设计的几个阶段(软件工程简介)六、七十年代出现了软件危机软件开发周期长软件开发费用大软件的正确性差软件的可靠性差工程化的方法-软件工程据估计，将软件生产由手工方式转变为工程化方式，软件可靠性将提高90%，测试和维护成本大大降低。速度：8行/天-20多行/天第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Det

6、ailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance评评审审（标准：国标，军标，DOD标准）第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance综述：说明问题，明确软件的功能，明确做什么，建立数据流图，数据字典任务：确定软件开发的主要任务功能：确定主要功能输入/处理/输出(IPO)性能：确定主要性能，

7、速度，响应时间，数据转换/传输时间，数据刷新时间接口：与外设，与软件，与人的界面产生：需求规格说明书，数据流程图，数据字典（标准：国标，军标，DOD标准）第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance设计：如何解决问题，可能的解决方案，数据的处理方式，存贮方式，模块的划分、调用关系参考：与系统相关的资料，需求规格说明书，程序设计手册，设备技术手册，支持软件文档第零章

8、第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance综述：设计程序的基本流程，组织结构，输入输出，接口设计及数据结构设计任务：1概要结构设计程序结构，给出程序的分层结构2功能划分分程序与模块的功能3程序的控制流程和数据流4系统间接口，与其他系统的接口5内部接口6算法上列举可能的求解算法产生：概要设计说明，用户手册第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Req

9、uirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance综述：对模块进行过程描述，设计模块内部细节。任务：1结构设计：模块细化，形成程序单元2资源分析及余量大于20%的余量3参数化：设计参数，增加软件的柔性4算法的具体化产生：详细设计说明书第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding &

10、amp; Debug测试-Testing运行与维护-Maintenance综述：根据详细设计说明书，编程实现，并进行调试编程标准：语言结构化，编程格式缩进等，控制结构语言结构化，编程格式缩进等，控制结构三种控制结构，插入或复制程序时要完整从入三种控制结构，插入或复制程序时要完整从入口入，出口出，出口入，出口出，出/ /入口结构唯一，禁止自修改，入口结构唯一，禁止自修改，程序单元的规模程序单元的规模200200行，程序中平均单元行，程序中平均单元的长的长6060行，注意转移，重定位能力，行，注意转移，重定位能力，命名统一，数值约定一致，有效数字，命名统一，数值约定一致，有效数字，注释行注释行20

11、%20%调试后要进行单元测试，先逐步审查代码，后测试，通过测试用例保证每条源代码至少执行一次第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance综述：由专门的测试人员对软件进行测试结果：测试报告1 1测试计划测试计划2 2测试测试条件：编译、链接成功，完成单元测试，walkthrough测试：模块测试：单元问题联合测试：接口问题系统测试：系统问题正确的依据：每条语句执行一

12、次，每个通道执行一次，每个功能正确第零章第零章 程序设计的一些问题程序设计的一些问题需求分析-Requirement Analysis概要设计-Primary Design详细设计-Detailed Design编码调试-Coding & Debug测试-Testing运行与维护-Maintenance综述：记录运行状况，为下一版本升级奠定基础第零章第零章 程序设计的一些问题程序设计的一些问题问题的解决周期：需求36%，设计5%，编码与调试7%，测试15%，运行维护67%工作量费用：需求5%，设计10%，编码调试8%，测试12%，运行维护65%费用可靠性与正确性：步步为营，测试统计数据

13、错误：60%发生在设计阶段，36%发生在编码阶段纠正错误的费用：编制程序的费用为1，则说明阶段的费用为0.5，测试阶段的费用为25，运行阶段的费用为10组织结构：七人小组软件生命周期的概念第零章第零章 程序设计的一些问题程序设计的一些问题讨论软件工程强调开始定型，以后不变，这在实际工作中会有问题吗？快速原型法Prototyping软件工程还是快速原型？第零章第零章 程序设计的思维方法程序设计的思维方法程序设计的本质是实现算法，而算法是计算机解决问题精确描述，有如下特征：入口出口有穷次结束序列化后继唯一抽象法：变量的应用，树的处理枚举法：归纳法：例如求自然数的和公式回朔法：走迷宫子问题法：Han

14、io塔问题，二叉树的遍历反对教条化第零章第零章 如何评价程序如何评价程序正确性：让它干等于程序干的吗？，在不同的环境下的鲁棒性。验证方法：枚举法，归纳法，抽象法，证明时空性：时间越少，空间越小越好时间和空间的定义时空的矛盾解决时间的关键是算法，解决空间的关键是数据结构发展趋势易读性-自己读，别人读，结构清晰，易读易理解，人机界面好，注释语句通用性好可靠性，可移植性-传统的程序方法上：抽象思维，模块化第零章第零章 程序设计方法程序设计方法结构化程序设计方法1968年Dijkstra提出结构化程序设计，主要思想：自上而下，逐步求精-功能结构分层结构与模块结构的程序设计-系统结构，先全局后局部，保证

15、块间不构成圈，块独立，块的层次分明避免GOTO-控制结构采用三种结构主程序员-组织结构GOTO语句的讨论1966年证明三种结构可以表达所需要的程序结构。使用GOTO出现的问题- 程序结构复杂化，阅读时的静态与运行中的动态不统一，无结构形式讨论 *运算是不是一种GOTO？第零章第零章 程序设计方法程序设计方法自顶向下，逐步求精写作文的方式在以后的学习中大量用到VC环境下程序设计初步工程Project面向控制台Console的应用：C语言复习类的概念对话框的应用以及类单文档应用以及类多文档应用以及类第一章第一章 绪绪论论1.1 什么是数据结构？煤气管道铺设问题煤气管道铺设问题ABCDE218163

16、212405020数据结构是一门研究非数值计算的程序设计问题中，计算机的操作对象以及它们之间的关系和操作的学科。第一章第一章 绪绪论论1.2 基本概念与术语数据数据学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004.例例1：学生成绩：学生成绩例例2：声音、图象：声音、图象数据是信息的载体，是对客观事物的符号表示，它被计算机所识别、存储和加工，构成计算机程序的加工原料。 数据元素数据元素 数据元素是数据的基本单位。数据元素是数据的基本单位。 它也可以再由不可分割的数据项组成它也可以再由不可分割的数据项组成 数据对象数据对

17、象性质相同的数据元素的集合性质相同的数据元素的集合 。 例：一个班级的成绩表可以看作一个数据对象。例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音一个图片、声音.数据对象是性质相同的数据元素集合。 数据元素集合（也可称数据对象）数据元素集合（也可称数据对象） 各元素之间的关系，即结构。各元素之间的关系，即结构。数据结构数据结构从三个方面研究数据结构：从三个方面研究数据结构：逻辑结构逻辑结构存储结构存储结构 算法算法数据结构 = 数据 + 结构 数据元素之间具有的逻辑关系数据元素之间具有的逻辑关系(结构结构)。线性关系线性关系( (线性结构线性结构) )： 数据元素间为严格的一对一关系

18、。 树形结构树形结构 ： 数据元素间为严格的一对多关系。逻辑结构逻辑结构图状结构（或网状结构）图状结构（或网状结构）： 数据元素间为多对多关系 非非 线线 性性 结结 构构具有某种逻辑结构的数据在计算机存具有某种逻辑结构的数据在计算机存储器中的存储方式。储器中的存储方式。顺序存储：顺序存储：用一组地址任意的用一组地址任意的存储单元依次存放数据元素，存储单元依次存放数据元素，链式存储：链式存储：数据元素之间的逻数据元素之间的逻辑关系通过指针间接地反映。辑关系通过指针间接地反映。存储结构存储结构存储结构是数据结构在计算机中的表示，也称之为物理结构。计算机内存的模型03000301030203030

19、3040305逻辑结构：逻辑结构： 线性结构线性结构 (线性表线性表)a1a2a3 a30d1 d2 d3 d4 d30a2a1a3a4a30存储结构存储结构:1. 顺序存储结构顺序存储结构:学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004.例：例：2. 链式存储结构链式存储结构:d1 d2 d3 d4 a1a2a3a30lista2a1a4a3d4d1d5d3 算法算法数据的数据的处理方法（算法）处理方法（算法）查找：数学成绩前三名的同学查找：数学成绩前三名的同学学号姓名语文数学C语言6201001张三855492

20、6201002李四9284646201003王五8774736201004.例例：添加：来了一个新同学添加：来了一个新同学 1. 研究数据元素之间的客观联系研究数据元素之间的客观联系。 2. 研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。 3. 研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的) 的基础上对数据实施一系列有效的基本操作。的基础上对数据实施一系列有效的基本操作。 数据结构课程研究的主要内容数据结构课程研究的主要内容(算法算法)(逻辑结构逻辑结构)(存储结构存储结构)为什么研究数据结构 1

21、.4 算法及其描述算法及其描述输入输入 一个完整的算法应该满足下面五个基本标准：一个完整的算法应该满足下面五个基本标准： 有效性有效性 确定性确定性有穷性有穷性输出输出一一. 算法及其性质算法及其性质 (2). 算法算法是指令的有限序列，其中每一条指令表示一是指令的有限序列，其中每一条指令表示一 个或多个操作个或多个操作 。1. .算法的定义算法的定义2. .算法的性质算法的性质 (1). 算法算法是对特定问题求解步骤的一种描述。是对特定问题求解步骤的一种描述。二二. 算法的描述算法的描述 (1) M除以除以N，将余数送中间变量将余数送中间变量R； (2) 测试余数测试余数R是否等于零？是否等

22、于零？ a) 若若R等于零，求得的最大公因子为当前等于零，求得的最大公因子为当前N 的值的值, 算法到此结束。算法到此结束。 b) 若若R不等于零，将不等于零，将N送入送入M，将将R送送N，重重 复算法的复算法的(1)和和(2)。1. 采用自然语言来描述采用自然语言来描述问题：问题：求两个正整数求两个正整数M与与N的最大公因子。的最大公因子。2. 采用程序流程图的形式来描述采用程序流程图的形式来描述M除以N的余数送R余数R为0否？将N送M将R送N输出输出N的值的值结束开始yesnoCOMFACTOR( int M, int N ) int R; while( 1 ) R=M % N; if (

23、R=0) return N; M=N; N=R; 3. 采用某种具体程序语言来描述采用某种具体程序语言来描述 4. 设计一种既脱离某种具体的程序设计语言，设计一种既脱离某种具体的程序设计语言， 又具有各种程序设计语言的共同特点的形又具有各种程序设计语言的共同特点的形 式化语言来描述式化语言来描述类类 C C 语言语言 一一. 算法格式算法格式函数类型函数类型 函数名（形式参数及其说明）函数名（形式参数及其说明） 内部参数说明；内部参数说明； 语句序列；语句序列； 1.3 类类 C 语言简介语言简介二二. 语句语句1. 赋值语句：赋值语句： (1) if 条件表达式条件表达式 语句串；语句串；

24、(2) if 条件表达式条件表达式 语句串语句串1； else 语句串语句串2； 变量名变量名 =表达式表达式 2. . 条件语句条件语句( (两种两种) )3. 循环语句循环语句(三种三种) do 语句串；语句串； while(循环条件循环条件) for (赋初值表达式；条件表达式；修改表达式赋初值表达式；条件表达式；修改表达式) 语句串语句串; while (循环条件循环条件) 语句串；语句串； switch(表达式表达式) case 判定值判定值1：语句串：语句串1； break; case 判定值判定值2：语句串：语句串2； break; . . . . case 判定值判定值n：语句

25、串语句串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+

26、) Ci, j=Ci, j+Ai, k*Bk, j; 例例 1.5 算法分析算法分析 1、正确性、正确性2、可读性、可读性3、健壮性、健壮性4、效率与低存储量需求、效率与低存储量需求 效率效率指的是算法执行时间。指的是算法执行时间。 存储量存储量需求指算法执行过程中所需要的最大存储空间。需求指算法执行过程中所需要的最大存储空间。 两者都与问题的规模有关。两者都与问题的规模有关。是指对算法质量优劣的评价。是指对算法质量优劣的评价。 3其他方面。如算法的可读性、可移植性以其他方面。如算法的可读性、可移植性以 及易测试性的好坏。及易测试性的好坏。 2依据算法编写的程序在计算机中占存储空依据算法编写的程序在计算机中占存储空 间多少的度量，称之为间多少的度量，称之为空间复杂度空间复杂度。 1依据算法编写的程序在计算机中运行时间依据算法编写的程序在计算机中运行时间 多少的度量，称之为多少的度量，称之为时间复杂度时间复杂度。 除正确性外，应从三个方面分析一个算法：除正确性外，应从三个方面分析一个算法：算法分析算法分析