软件技术基础幻灯片.ppt

《软件技术基础幻灯片.ppt》由会员分享，可在线阅读，更多相关《软件技术基础幻灯片.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、软件技术基础第1页，共44页，编辑于2022年，星期三计算机领域的知识需求第2页，共44页，编辑于2022年，星期三课程目的本课程以非计算机专业的本、专科学生为本课程以非计算机专业的本、专科学生为对象，通过本课程的学习，使其掌握有关对象，通过本课程的学习，使其掌握有关计算机软件技术的基础关知识和方法，培计算机软件技术的基础关知识和方法，培养学生利用计算机解决问题的意识和能力，养学生利用计算机解决问题的意识和能力，为计算机在其专业应用中奠定基础，同时为计算机在其专业应用中奠定基础，同时也为其深入学习计算机知识打下良好的基也为其深入学习计算机知识打下良好的基础。础。第3页，共44页，编辑于2022

2、年，星期三参考资料1 1、严蔚敏等，数据结构（、严蔚敏等，数据结构（C C语言版），清华大学语言版），清华大学2 2、徐孝凯，数据结构实用教程，清华大学出版社，、徐孝凯，数据结构实用教程，清华大学出版社，19991999，10.10.3 3、李平等，数据结构，电子工业出版社，、李平等，数据结构，电子工业出版社，20002000，1.1.4 4、郑人杰等，实用软件工程，清华大学出版社，、郑人杰等，实用软件工程，清华大学出版社，19971997，4.4.5 5、江正战、江正战 主编，三级偏软考试教程，东南大学出版社，主编，三级偏软考试教程，东南大学出版社，20022002，6 6第4页，共44页，

3、编辑于2022年，星期三本课程主要教学内容本课程主要教学内容理论教学理论教学(32(32学时学时):):1 1、数据结构（第、数据结构（第1-51-5章）章）2 2、软件工程（第、软件工程（第6 6章：软件的设计与开发）章：软件的设计与开发）上机实践上机实践(10(10学时学时):):1 1、地点、地点-计算中心计算中心2 2、上机参考教材、上机参考教材(电子版电子版)-)-软件应用技软件应用技术基础实验指导书术基础实验指导书第5页，共44页，编辑于2022年，星期三实验参考教材实验参考教材实验参考教材实验参考教材:(1)宁正元宁正元,易金聪等易金聪等,数据结构习题解析与上数据结构习题解析与上

4、机实验指导机实验指导,2000,9(2)李春葆李春葆,数据结构习题与解析数据结构习题与解析,1999,4第6页，共44页，编辑于2022年，星期三计算机领域的知识需求第7页，共44页，编辑于2022年，星期三计算机领域的知识需求第8页，共44页，编辑于2022年，星期三计算机领域的知识需求第9页，共44页，编辑于2022年，星期三第一章：软件基础相关知识概述第一章：软件基础相关知识概述计算机基础知识（计算机基础知识（已学习已学习）程序设计、计算方法（程序设计、计算方法（已学习已学习）数据处理基本知识数据处理基本知识（数据结构、算法）（数据结构、算法）（本课程本课程）数据库技术（数据库技术（相关

5、课程相关课程）操作系统操作系统编译原理编译原理网络系统（网络系统（相关课程相关课程）软件工程软件工程（本课程本课程）第10页，共44页，编辑于2022年，星期三软件基础相关知识概述软件基础相关知识概述讨论：什么是程序？什么是程序？什么是软件？什么是软件？第11页，共44页，编辑于2022年，星期三程序与软件程序与软件 程序是计算机指令序列，这些指令由非常简单的程序是计算机指令序列，这些指令由非常简单的程序是计算机指令序列，这些指令由非常简单的程序是计算机指令序列，这些指令由非常简单的四则运算、逻辑运算、数据传送及跳转指令组合而四则运算、逻辑运算、数据传送及跳转指令组合而四则运算、逻辑运算、数据

6、传送及跳转指令组合而四则运算、逻辑运算、数据传送及跳转指令组合而成。程序实质上是用某种计算机语言描述的某一问成。程序实质上是用某种计算机语言描述的某一问成。程序实质上是用某种计算机语言描述的某一问成。程序实质上是用某种计算机语言描述的某一问题的解决步骤。题的解决步骤。题的解决步骤。题的解决步骤。1、程序的静态与动态属性、程序的静态与动态属性2、程序语言的抽象符号表达、程序语言的抽象符号表达3、对数据施行算法的过程、对数据施行算法的过程4、分层嵌套、分层嵌套第12页，共44页，编辑于2022年，星期三程序与软件程序与软件 1983 1983年，年，年，年，IEEEIEEE组织明确地给软件作了定义

7、：组织明确地给软件作了定义：组织明确地给软件作了定义：组织明确地给软件作了定义：软件软件软件软件是计算机程序、方法和规则相关的文档以及在计算是计算机程序、方法和规则相关的文档以及在计算是计算机程序、方法和规则相关的文档以及在计算是计算机程序、方法和规则相关的文档以及在计算机上运行它时所必需的数据。机上运行它时所必需的数据。机上运行它时所必需的数据。机上运行它时所必需的数据。软件的特性软件的特性1、功能、性能相对完备、功能、性能相对完备2、具有使用性能的软设备、具有使用性能的软设备3、信息商品、信息商品4、只有过时而无、只有过时而无“磨损磨损”软件软件程序程序第13页，共44页，编辑于2022年

8、，星期三软件分类软件分类系统软件系统软件系统软件系统软件应用软件应用软件应用软件应用软件（为释放硬件潜能、方便使用而配备的软件）（为释放硬件潜能、方便使用而配备的软件）操作系统操作系统操作系统操作系统编译编译编译编译/解释系统解释系统解释系统解释系统数据库管理软件数据库管理软件数据库管理软件数据库管理软件各种各种服务程序服务程序服务程序服务程序办公软件套件办公软件套件办公软件套件办公软件套件多媒体处理软件多媒体处理软件多媒体处理软件多媒体处理软件程序开发工具环境程序开发工具环境程序开发工具环境程序开发工具环境计算机辅助设计计算机辅助设计计算机辅助设计计算机辅助设计/制造软件制造软件制造软件制造

9、软件（解决某一应用领域问题的软件）（解决某一应用领域问题的软件）第14页，共44页，编辑于2022年，星期三 算法算法+数据结构数据结构=程序程序(Niklaus Wirth)(Algorithm+Data structure=Program)程序：程序：程序：程序：为计算机处理问题编写的一组指令。为计算机处理问题编写的一组指令。为计算机处理问题编写的一组指令。为计算机处理问题编写的一组指令。算法：算法：处理问题的策略。处理问题的策略。数据结构：数据结构：问题的数学模型。问题的数学模型。程序设计的实质是数据的表示和数据处理程序设计的实质是数据的表示和数据处理,为此为此 应提出问题的数学模型和设

10、计相应的算法。应提出问题的数学模型和设计相应的算法。第15页，共44页，编辑于2022年，星期三 1.研究数据之间的客观联系研究数据之间的客观联系。2.研究具有某种逻辑关系的数据在计算机存储研究具有某种逻辑关系的数据在计算机存储 器内的存储方式。器内的存储方式。3.研究如何在数据的各种结构研究如何在数据的各种结构(逻辑的和物理的逻辑的和物理的)的基础上对数据实施一系列有效的的基础上对数据实施一系列有效的基本操作基本操作。逻辑结构逻辑结构存储结构存储结构数据结构研究的主要内容数据结构研究的主要内容算法算法什么是数据结构？什么是数据结构？第16页，共44页，编辑于2022年，星期三基本操作（基本操

11、作（对数据的处理），通常包含四对数据的处理），通常包含四方面的内容：方面的内容：（1 1）查找数据；）查找数据；（2 2）插入数据；）插入数据；（3 3）删除数据；）删除数据；（4 4）数据排序；）数据排序；第17页，共44页，编辑于2022年，星期三是是相相互互之之间间存存在在一一种种或或多多种种特特定定关关系系的的数数据据元素的集合，表示为：元素的集合，表示为：（数值或非数值数值或非数值）Data_Structure=（D,R）是指同一数据元素类型中各元素之间存在的关系。是指同一数据元素类型中各元素之间存在的关系。元素有限集元素有限集关系有限集关系有限集数据结构数据结构第18页，共44页，

12、编辑于2022年，星期三例如：图书馆的书目检索问题例如：图书馆的书目检索问题登录号登录号书名书名作者作者分类号分类号172832离散数学离散数学樊映川樊映川S01172833理论力学理论力学罗远祥罗远祥S01172834高等数学高等数学华罗庚华罗庚S01172835线性代数线性代数滦汝书滦汝书S02书名书名登录号登录号高等数学高等数学172832,172834理论力学理论力学172833线性代数线性代数172835作者作者登录号登录号樊映川樊映川172832华罗庚华罗庚172834滦汝书滦汝书172835类别类别登录号登录号L172833S172832,172834第19页，共44页，编辑于2

13、022年，星期三数据是描述客观事物的数、字符以及数据是描述客观事物的数、字符以及数据是描述客观事物的数、字符以及数据是描述客观事物的数、字符以及所有所有所有所有能输入到计算机中并为计算机程序能输入到计算机中并为计算机程序能输入到计算机中并为计算机程序能输入到计算机中并为计算机程序处理的处理的处理的处理的对象的集合对象的集合对象的集合对象的集合。数据的基本单位，数据的基本单位，数据的基本单位，数据的基本单位，有时一个数据元素也可有时一个数据元素也可有时一个数据元素也可有时一个数据元素也可以由若干个数据项组成。以由若干个数据项组成。以由若干个数据项组成。以由若干个数据项组成。数据结构的基本概念数据

14、结构的基本概念1.1.1.1.数据数据数据数据2.2.2.2.数据数据数据数据元素元素元素元素例如：例如：描述一年四季的季节名：春、夏、秋、冬描述一年四季的季节名：春、夏、秋、冬描述一年四季的季节名：春、夏、秋、冬描述一年四季的季节名：春、夏、秋、冬表示数值的各个数：表示数值的各个数：表示数值的各个数：表示数值的各个数：1818、1111、3535、2323、1616、表示家庭成员的各成员名：父亲、儿子、女儿表示家庭成员的各成员名：父亲、儿子、女儿表示家庭成员的各成员名：父亲、儿子、女儿表示家庭成员的各成员名：父亲、儿子、女儿数据元素一般具有某种共同特征数据元素一般具有某种共同特征第20页，共

15、44页，编辑于2022年，星期三对数据元素之间逻辑关系的描述。它对数据元素之间逻辑关系的描述。它对数据元素之间逻辑关系的描述。它对数据元素之间逻辑关系的描述。它可以用一个数据元素的集合和定义在可以用一个数据元素的集合和定义在可以用一个数据元素的集合和定义在可以用一个数据元素的集合和定义在这个集合上的若干关系来表示。这个集合上的若干关系来表示。这个集合上的若干关系来表示。这个集合上的若干关系来表示。4.4.4.4.数据数据数据数据的逻辑结构的逻辑结构的逻辑结构的逻辑结构数据结构的基本概念数据结构的基本概念具有相同特性的数据元素的集合，具有相同特性的数据元素的集合，具有相同特性的数据元素的集合，具

16、有相同特性的数据元素的集合，为数据的一个子集。为数据的一个子集。为数据的一个子集。为数据的一个子集。3.3.3.3.数据对象数据对象数据对象数据对象第21页，共44页，编辑于2022年，星期三数据结构的基本概念数据结构的基本概念一个数据结构通常应包含两方面的信息一个数据结构通常应包含两方面的信息表示数据元素的信息表示数据元素的信息表示各数据元素之间的前后件关系表示各数据元素之间的前后件关系例如：例如：“春春春春”是是是是“夏夏夏夏”的前件（直接前驱）的前件（直接前驱）的前件（直接前驱）的前件（直接前驱）“夏夏夏夏”是是是是“春春春春”的后件（直接后继）的后件（直接后继）的后件（直接后继）的后件

17、（直接后继）“父亲父亲父亲父亲”是是是是“儿子儿子儿子儿子”和和和和“女儿女儿女儿女儿”的前件（直接前驱）的前件（直接前驱）的前件（直接前驱）的前件（直接前驱）“儿子儿子儿子儿子”和和和和“女儿女儿女儿女儿”是是是是“父亲父亲父亲父亲”的后件（直接后继）的后件（直接后继）的后件（直接后继）的后件（直接后继）第22页，共44页，编辑于2022年，星期三B=(D,R)B=(D,R)B:B:数据结构数据结构数据结构数据结构D:D:数据元素的集合数据元素的集合数据元素的集合数据元素的集合;R:D;R:D上关系的集合上关系的集合上关系的集合上关系的集合D D中各数据元素之间的前后件关系一般用中各数据元素

18、之间的前后件关系一般用中各数据元素之间的前后件关系一般用中各数据元素之间的前后件关系一般用二元组二元组二元组二元组来来来来表示。例如，表示。例如，表示。例如，表示。例如，a a与与与与b b是是是是D D中的两个数据，则中的两个数据，则中的两个数据，则中的两个数据，则二元组二元组二元组二元组（a a，b b）表示）表示）表示）表示a a是是是是b b的前件，的前件，的前件，的前件，b b是是是是a a的后件的后件的后件的后件。例如：例如：B=(D,R)B=(D,R)D=D=春、夏、秋、冬春、夏、秋、冬春、夏、秋、冬春、夏、秋、冬 R=(R=(春、夏春、夏春、夏春、夏),(),(夏、秋夏、秋夏、

19、秋夏、秋),(),(秋、冬秋、冬秋、冬秋、冬)B=(D,R)B=(D,R)D=D=父亲、儿子、女儿父亲、儿子、女儿父亲、儿子、女儿父亲、儿子、女儿 R=(R=(父亲、儿子父亲、儿子父亲、儿子父亲、儿子),(),(父亲、女儿父亲、女儿父亲、女儿父亲、女儿)第23页，共44页，编辑于2022年，星期三数据结构还可以直观地用图来表示数据结构还可以直观地用图来表示春春夏夏秋秋冬冬结点结点结点结点前后件关系前后件关系前后件关系前后件关系父亲父亲儿子儿子女儿女儿根结点根结点根结点根结点叶子结点叶子结点叶子结点叶子结点孙子孙子内部结点内部结点内部结点内部结点第24页，共44页，编辑于2022年，星期三 1）

20、集合：集合中任何两个结点之间都没有逻）集合：集合中任何两个结点之间都没有逻 辑关系，组织形式松散。辑关系，组织形式松散。数据结构的基本概念数据结构的基本概念2）线性结构：元素之间存在着一对一的关）线性结构：元素之间存在着一对一的关系。依次排列形成一条系。依次排列形成一条“锁链锁链”。3）树形结构：数据元素之间存在着一对）树形结构：数据元素之间存在着一对 多的关系，具有分支、层次特性。多的关系，具有分支、层次特性。4）图状结构：数据元素之间存在多对多）图状结构：数据元素之间存在多对多 的关系，元素之间互相缠绕，具有分支、层次特的关系，元素之间互相缠绕，具有分支、层次特性。性。第25页，共44页，

21、编辑于2022年，星期三数据在计算机中的表示，包括数据数据在计算机中的表示，包括数据数据在计算机中的表示，包括数据数据在计算机中的表示，包括数据元素的表示和关系的表示。元素的表示和关系的表示。元素的表示和关系的表示。元素的表示和关系的表示。1 1）顺序存储方式（向量存储）顺序存储方式（向量存储）顺序存储方式（向量存储）顺序存储方式（向量存储）2 2）链式存储方式）链式存储方式）链式存储方式）链式存储方式3 3）索引存储方式）索引存储方式）索引存储方式）索引存储方式4 4）散列存储方式）散列存储方式）散列存储方式）散列存储方式5.5.5.5.数据数据数据数据的存储结构的存储结构的存储结构的存储结

22、构6.6.6.6.数据结构数据结构数据结构数据结构按照某种逻辑结构组织的一组数据按照某种逻辑结构组织的一组数据按照某种逻辑结构组织的一组数据按照某种逻辑结构组织的一组数据,按一定的存储方式将它们映射到计按一定的存储方式将它们映射到计按一定的存储方式将它们映射到计按一定的存储方式将它们映射到计算机的存储器中，并且在这些数据算机的存储器中，并且在这些数据算机的存储器中，并且在这些数据算机的存储器中，并且在这些数据上定义了一个运算的集合，运算的上定义了一个运算的集合，运算的上定义了一个运算的集合，运算的上定义了一个运算的集合，运算的结果保持原来的结构。结果保持原来的结构。结果保持原来的结构。结果保持

23、原来的结构。数据结构的基本概念数据结构的基本概念第26页，共44页，编辑于2022年，星期三数据结构涵盖的内容数据结构涵盖的内容第27页，共44页，编辑于2022年，星期三算法：是对特定问题求解步骤的一种描述。算法：是对特定问题求解步骤的一种描述。算法的基本特征：算法的基本特征：可行性可行性：算法的每一步都是能够实现的，即可操算法的每一步都是能够实现的，即可操作的。作的。确定性确定性：算法的每一步必须是确切定义的。对于相同：算法的每一步必须是确切定义的。对于相同输入必须得到相同结果输入必须得到相同结果。有穷性有穷性：一个算法必须在执行有穷步之后结束。：一个算法必须在执行有穷步之后结束。有输出有

24、输出：算法执行完毕，必须有一个或若干个输出算法执行完毕，必须有一个或若干个输出结果。结果。算法的基本概念算法的基本概念第28页，共44页，编辑于2022年，星期三算法描述语言算法描述语言采用类C语言来描述一、符号与表达式二、赋值语句三、控制转移语句如：go,if等语句 四、循环五、其他语句：exit、ruturn、设计一种既脱离某种具体的程序设计设计一种既脱离某种具体的程序设计 语言，又具有各种程序设计语言的共语言，又具有各种程序设计语言的共 同特点的形式化语言来描述同特点的形式化语言来描述第29页，共44页，编辑于2022年，星期三1.3 算法设计基本方法常用算法算法设计基本方法常用算法一、

25、枚举法一、枚举法例：百元买百鸡（例：百元买百鸡（P12）强力攻击强力攻击二、归纳法二、归纳法找规律找规律第30页，共44页，编辑于2022年，星期三三、递推法三、递推法例例1：阶乘函数：阶乘函数Fn=N*Fn-1已知：已知：F0=1;四、递归法四、递归法例例1：阶乘函数：阶乘函数例例2：hano塔塔第31页，共44页，编辑于2022年，星期三递归函数的经典问题递归函数的经典问题汉诺塔问题汉诺塔问题在在世世界界刚刚被被创创建建的的时时候候有有一一座座钻钻石石宝宝塔塔（塔塔A），其其上上有有64个个金金碟碟。所所有有碟碟子子按按从从大大到到小小的的次次序序从从塔塔底底堆堆放放至至塔塔顶顶。紧紧挨挨

26、着着这这座座塔塔有有另另外外两两个个钻钻石石宝宝塔塔（塔塔B和和塔塔C）。从从世世界界创创始始之之日日起起，婆婆罗罗门门的的牧牧师师们们就就一一直直在在试试图图把把塔塔A上上的的碟碟子子移移动动到到塔塔C上上去去，其其间间借借助助于于塔塔B的的帮帮助助。每每次次只只能能移移动动一一个个碟碟子子，任任何何时时候候都都不不能能把把一一个个碟碟子子放放在在比比它它小小的的碟碟子子上上面面。当当牧师们完成任务时，世界末日也就到了。牧师们完成任务时，世界末日也就到了。第32页，共44页，编辑于2022年，星期三汉诺塔问题可以通过以下三个步骤实现：汉诺塔问题可以通过以下三个步骤实现：（1）将塔）将塔A上的

27、上的n-1个碟子借助塔个碟子借助塔C先移到塔先移到塔B上。上。（2）把塔）把塔A上剩下的一个碟子移到塔上剩下的一个碟子移到塔C上。上。（3）将）将n-1个碟子从塔个碟子从塔B借助塔借助塔A移到塔移到塔C上。上。显然，这是一个递归求解的过程显然，这是一个递归求解的过程第33页，共44页，编辑于2022年，星期三第34页，共44页，编辑于2022年，星期三算法4.2汉诺塔算法 1 void Hanoi(int n,char A,char B,char C)/第一列为语句行号第一列为语句行号 2 3 if(n=1)Move(A,C);/Move是一个抽象操作，表示将碟子从是一个抽象操作，表示将碟子从

28、A移到移到C上上 4 else 5 Hanoi(n-1,A,C,B);6 Move(A,C);7 Hanoi(n-1,B,A,C);8 9 C+描述第35页，共44页，编辑于2022年，星期三Hanio(3,A,B,C)Hanio(2,A,C,B)Hanio(1,A,B,C)Move(A,C)Move(A,B)Hanio(1,C,A,B)Hanio(1,A,B,C)Hanio(2,A,C,B)Move(C,B)Hanio(1,C,A,B)Move(A,C)Hanio(2,B,A,C)Hanio(1,B,C,A)Move(B,C)Hanio(1,A,B,C)Hanio(1,B,C,A)Move(

29、A,C)Hanio(2,B,A,C)Move(B,A)Hanio(1,A,B,C)结束结束第36页，共44页，编辑于2022年，星期三五、分治法五、分治法例：折半查找例：折半查找六、回溯法（高级算法）六、回溯法（高级算法）例例1：8皇后问题皇后问题七七、迭代法、迭代法例：求例：求X3-X-1=0在在x=1.5附近的一个根附近的一个根第37页，共44页，编辑于2022年，星期三算法算法频度统计法频度统计法以语句执行的次数的多少作为算法的时间量度的分析方法称为以语句执行的次数的多少作为算法的时间量度的分析方法称为频频度统计法度统计法。一条一条语句的频度语句的频度是指该语句被执行的次数，而整个是指该

30、语句被执行的次数，而整个算法的频算法的频度度是指算法中所有语句的频度之和。是指算法中所有语句的频度之和。假如随着问题规模假如随着问题规模n的增长，算法执行时间的增长率和的增长，算法执行时间的增长率和f(n)的增长率相同，则记作的增长率相同，则记作T(n)=O(f(n)，称，称T(n)为算法的时间复杂为算法的时间复杂性。性。时间复杂度时间复杂度第38页，共44页，编辑于2022年，星期三时间复杂度第39页，共44页，编辑于2022年，星期三时间复杂度第40页，共44页，编辑于2022年，星期三例如例如：1）x:=x+1;2）For i:=1 To n Do x:=x+1;3)For i:=1 T

31、o n Do For j:=1 To n Do x:=x+1；l机器只执行一次机器只执行一次,则它的频度为一则它的频度为一次，即次，即f(n)=1,执行时间复杂度为执行时间复杂度为O(1)。l其语句执行其语句执行n次次,频度为频度为n次次,执执行时间与行时间与n成正比成正比,f(n)=n,复杂度复杂度为为O(n)。l 其语句执行其语句执行n2次次,频度为频度为n2次次,执行时间与执行时间与n2成正比成正比,f(n)=n2,复杂度为复杂度为O(n2)。第41页，共44页，编辑于2022年，星期三值得一提的是：复杂度与输入量相关。在某个数组中查找某值。平均复杂度平均复杂度最坏情况复杂度最坏情况复杂

32、度第42页，共44页，编辑于2022年，星期三空间复杂度空间复杂度度量空间复杂度度量存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、程序指令代码的空间，常数、简单变量、定长成分定长成分(如数组元素、结构成分、对象的如数组元素、结构成分、对象的数据成员等数据成员等)变量所占空间变量所占空间可变部分可变部分尺寸与实例特性有关的成分变量所占空间、尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用空间、通引用变量所占空间、递归栈所用空间、通过过new和和delete命令动态使用空间命令动态使用空间第43页，共44页，编辑于2022年，星期三什么是软件数据结构和算法的确立程序软件应用软件数据库操作系统、网络系统服务软件软件工程软件开发管理方法第44页，共44页，编辑于2022年，星期三