西电软件技术基础课件1 概述

1、软件技术基础（一）西安电子科技大学电子工程学院林杰1先修课程：C语言程序设计教材：软件技术基础周大为等西安电子科技大学出版社2学时安排：上课40学时+上机16学时考核：80% 期末考试成绩，闭卷20%的上机、平时作业，考勤教师：林杰 Cell phone:Email: 3软件的基本概念软件技术程序设计技术及程序性能数据结构的概念与算法的性质设计程序所需的基础知识和基本能力4问题：软件=计算机程序?软件的定义：计算机程序计算机程序是能够完成预定功能和性能的可执行的指令5生产过程不同：软件是开发或工程化形成，没有明显的制作过程6故障率变化不同硬件有零件可替换，软件无备用零

2、件，软件的维护更加麻烦7软件复用性差：软件大部分都是自定义硬件可以通过已有的构件组装而成8 软件软件系统软件系统软件应用软件应用软件操作系统操作系统网络系统网络系统语言编译器语言编译器工具软件工具软件管理软件管理软件实时软件实时软件科学计算、数据处理科学计算、数据处理嵌入式软件嵌入式软件人工智能软件人工智能软件专用领域专用领域软件软件9包括操作系统、编译程序、诊断程序、系统服务程序、语言处理程序、数据库管理系统和网络管理系统等系统软件的主要特征是：与硬件有很强的交互性能对资源共享进行调度管理能解决并发操作处理中存在的协调问题其中的数据结构复杂，外部接口多样化，便于用户反复使用10它可以拓宽计算

3、机系统的应用领域，放大硬件的功能。应用软件具有无限丰富和美好的开发前景。如：电路仿真软件Pspice、Matlab等均属于应用软件。11第一阶段：20世纪60年代中期以前，早期阶段软件开发无计划、无管理无计划、无管理；每类应用自行设计，应用的范围有限；编写者负责修改，无文档无文档第二阶段：20世纪60年代中期到20世纪70年代多道程序设计、多用户系统引入人机交互的新概念，打开了软件和硬件配合的新层次；实时系统大大提升软件系统的速度在线存储的发展导致第一代数据库管理系统的出现软件作坊的出现和软件产品的使用，产生了巨大的经济效益软件危机的出现软件危机的出现“三无”12第三阶段：20世纪70年代中期

4、后的10年分布式系统对软件开发提出了更高的要求微处理器的出现和广泛应用，使得智能产品纷纷面世，计算机的应用真正成为大众化的应用。第四阶段：20世纪80年代后计算机体系结构从主机环境转变为分布的客户机/服务器环境。软件产业在国民经济中举足轻重的作用面向对象技术取代了传统软件开发方法专家系统和人工智能软件进入实际应用13软件危机出现于20 世纪60 年代末1968年北大西洋公约组织的计算机科学家在联邦德国召开的国际学术会议上第一次提出了“软件危机”(software crisis)这个名词。 ，包含两个方面问题：如何如何开发开发软件，以满足不断增长，日趋复杂的软件，以满足不断增长，日趋复杂的需求需

5、求？如何如何维护维护数量不断膨胀的已有数量不断膨胀的已有软件？软件？14151对对软件开发成本和进度的软件开发成本和进度的估计常常很不准确估计常常很不准确。开发成本超开发成本超出预算，实际进度比预定计划一再拖延的现象并不罕见。出预算，实际进度比预定计划一再拖延的现象并不罕见。 2用户用户对对“已完成的已完成的”软件系统不满意软件系统不满意的现象经常发生的现象经常发生。3 软件产品的软件产品的质量往往靠不住质量往往靠不住。 Bug一大堆，一大堆，Patch一个接一个接一个。一个。4软件软件常常是常常是不可维护的不可维护的。5 软件通常软件通常没有适当的文档资料没有适当的文档资料。计算机软件不仅仅

6、是。计算机软件不仅仅是程序程序，还应该有一整套文档资料。还应该有一整套文档资料。 6软件软件成本成本在计算机系统总成本中在计算机系统总成本中所占的比例逐年上升所占的比例逐年上升。7软件开发软件开发生产率提高的速度生产率提高的速度，远远，远远跟不上跟不上计算机应用迅速计算机应用迅速普及深入的趋势普及深入的趋势。软件成本在计算机系统总成本中所占的比例1617客观原因客观原因：软件本身软件本身特点，软件的规模庞大、复特点，软件的规模庞大、复杂性高杂性高实际实际问题的问题的复杂性复杂性程序逻辑程序逻辑结构的复杂性结构的复杂性 主观原因主观原因：与与软件开发软件开发和维护的方法不正确有关和维护的方法不正

7、确有关，主要主要表现表现为：为：忽视忽视软件开发前期的软件开发前期的需求分析需求分析；开发过程开发过程没有统一的、规范的方法论的没有统一的、规范的方法论的指导指导，文档资料文档资料不齐全，忽视不齐全，忽视人与人的交流人与人的交流；忽视忽视测试阶段测试阶段的工作，提交用户的软件质量差的工作，提交用户的软件质量差；轻视轻视软件的软件的维护维护。这些这些大多数都是软件开发过程大多数都是软件开发过程管理上的原因管理上的原因。欧洲航天局欧洲航天局ARIANE 5 火箭1996 年6 月，耗资70 亿美元，发射后大约40 秒爆炸发射失败的原因在于软件错误，64位浮点数转换为16位有符号整数（32,767）

8、爱国者导弹1991 年2 月，海湾战争期间，未能成功拦截伊拉克飞毛腿导弹，28 名美国士兵丧生问题的症结在于导弹软件包含一个累加计时误差18Therac 25 型放射医疗仪事故1985.06-1987.01 ，由于软件错误导致放射过量，6人受伤，3 人死亡配置错误是导致问题的主要原因千年虫千年虫问题问题迫于计算机存储空间的限制，程序员将日期缩减为2 位数世界各地更换或升级2000 年问题软件的花费超过数亿美元19技术技术措施措施使用更好的软件开发方法和开发软件开发方法和开发工具工具组织管理组织管理措施措施软件开发不是某种个体劳动的神秘技巧，而应该是一种组织良好、管理严密、各类人员协同一种组织良

9、好、管理严密、各类人员协同配合、共同完成的工程项目配合、共同完成的工程项目。20软件的基本概念软件技术程序设计技术及程序性能数据结构的概念与算法的性质设计程序所需的基础知识和基本能力2122包括：1 软件工程技术2 程序设计技术 3 软件工具环境技术 4 系统软件技术 5 数据库技术 6 实时软件技术7 网络软件技术8与实际工作相关的软件技术软件的基本概念软件技术程序设计技术及程序性能数据结构的概念与算法的性质设计程序所需的基础知识和基本能力2324程序设计技术主要包括以下方面：程序的结构与算法设计程序设计的风格程序设计语言程序设计方法程序设计自动化程序的正确性证明程序的变换程序设计技术的关键

10、： 数据结构数据结构和算法和算法设计设计1.程序设计技术的目标 是提高程序的质量与生产率质量与生产率，最终实现程序的工业化生产。2.影响程序质量的因素 正确性、性能、可靠性、容错性、易用性、灵活性、可扩充性、可理解性、可维护性和复用性等等。有些因素相互重叠，有些则相抵触，提高质量可不容易。矛盾矛盾253.本课程介绍的程序设计技术主要针对规模小且一个人能够独立完成的程序的设计技术。4. 程序设计的主要环节有：明确要求、设计、实现（编码）、测试等，如图所示。 程序设计程序设计的主要环节的主要环节明确要求设计实现测试26它包括它包括可维护性、可靠性和可维护性、可靠性和效率效率。维护性是指程序能够被理

11、解、改正、改进和完善以适维护性是指程序能够被理解、改正、改进和完善以适应新的环境的难易程度应新的环境的难易程度。可理解性可理解性是可维护性的是可维护性的首要首要要求要求，具有可理解性的程序必须具有，具有可理解性的程序必须具有可读性、简单性可读性、简单性和清晰性和清晰性等。等。可修改性和可测试性可修改性和可测试性也是可维护性的重也是可维护性的重要衡量指标要衡量指标。可靠性是程序在规定的时间内及规定的环境条件下，可靠性是程序在规定的时间内及规定的环境条件下，完成规定功能的能力完成规定功能的能力，包括，包括正确性和健壮性正确性和健壮性。效率是指系统能否有效地使用计算机资源效率是指系统能否有效地使用计

12、算机资源，如，如时间和时间和空间空间等。等。 27软件的基本概念软件技术程序设计技术及程序性能数据结构的概念与算法的性质设计程序所需的基础知识和基本能力28长30.48m宽1m占地170 平方米30个操作台重30吨耗电150千瓦造价48万美元每秒执行5000次加法或400次乘法数据结构的产生背景1946年，第一台计算机ENIAC（埃尼阿克）诞生。早期的计算机主要用于数值计算。现在计算机的功能主要是用于数据处理。据不完全统计，目前全球有超过80%的计算机用于数据处理。近三十年来，计算机加工处理的对象由纯粹的数值型发展到字符、表格、声音、文字和图像等具有一定结构的数据。为了编写一个好的程序，必须分

13、析待处理的对象的特性以及各处理对象之间存在的关系。 2930Donald E. Knuth计算机程序设计艺术1968,在第一卷基本算法中较系统地阐述了数据的逻辑结构和存储结构及其操作，开创了数据结构的课程体系。同年，数据结构作为一门独立的课程在计算机科学的学位课程中开始出现。1974年，因在算法分析和编程语言设计方面的突出贡献，荣获美国计算机协会图灵奖，是历史上最年轻的获奖者(36岁)。图灵奖被称为计算机界的诺贝尔奖。计算机程序计算机程序设计艺术设计艺术一书与牛顿的自然哲学的数学原理等书一起，被评为“世界历史上最伟大的十种科学著作”之一。按学号顺序，除第一个学生外，每个学生前面(指学号相邻)只

14、有一个学生；除最后一个学生外，每个学生后面(指学号相邻)也只有一个学生；线性结构 31一个文件夹可以包含多个子文件夹。每个文件夹只能有一个上一级文件夹。树形结构。(可以画成更形象的“树”形)32 树形结构生产计划科生产计划科 技术科技术科 设计组设计组 工艺组工艺组 供销科供销科 供应组供应组 销售组销售组 厂长厂长 财务科财务科 人事科人事科 一车间一车间 二车间二车间 铸造工段铸造工段 锻压工段锻压工段 三车间三车间 行政副行政副厂长厂长生产副生产副厂长厂长3334数据数据（Data）：）：是是对信息的一种符号对信息的一种符号表示表示，描述客观事，描述客观事物的数字、字符以及所有能输入到计

15、算机中并被计算机物的数字、字符以及所有能输入到计算机中并被计算机程序处理的字符的集合。程序处理的字符的集合。数据元素数据元素（Data Element）：是）：是数据的基本单位，在计数据的基本单位，在计算机程序中算机程序中通常通常作为一作为一个整体进行考虑和处理个整体进行考虑和处理。一个数。一个数据元素可由据元素可由若干个若干个数据项数据项(data item)组成组成。数据项是数。数据项是数据的不可分割的最小据的不可分割的最小单位。单位。数据数据对象对象(Data Object)：是性质相同的是性质相同的数据元素的集合数据元素的集合。是数据的是数据的一个一个子集子集。数据类型数据类型（Dat

16、a Type）:用以描述程序操作对象的用以描述程序操作对象的特性。特性。原子类型原子类型：其值不可分解。例如整型，实型，字符型：其值不可分解。例如整型，实型，字符型结构类型结构类型：其值可以分解为若干个成分。例如：数组，结构：其值可以分解为若干个成分。例如：数组，结构体体35数据结构数据结构是指是指数据之间的相互关系数据之间的相互关系，即，即数据的组数据的组织形式织形式。从集合的观点形式化描述为一个二元组： Data_Structure =（D, R） 其中：D是数据元素的集合，R是D上关系的集合36数据数据的的“结构结构”：包括：包括逻辑结构逻辑结构和和存储结构存储结构。数据结构研究以下三个

17、方面的内容：数据的逻辑数据的逻辑结构结构：是数据本身所固有的，独立于计算机。数据的存储数据的存储结构结构：逻辑结构用计算机语言的实现，必须依赖于计算机。数据的数据的运算运算：运算的运算的定义定义直接依赖于逻辑结构，但运算直接依赖于逻辑结构，但运算的实现必须依赖的实现必须依赖于于存储存储结构结构。数据结构 数据元素 数据项 直接前趋 直接后继 开始结点 终端结点结点间的关系构成了学生成绩表的逻辑结构这种逻辑关系的表在计算机中如何进行存储表示则是存储结构研究的内容。进行查找、插入和删除就是数据的运算问题。学号学号 姓姓 名名 性性别别 课名课名 成绩成绩 22001 22001 王王 丽丽 女女

18、物理物理 81 81 22002 22002 刘建东刘建东 男男 物理物理 76 76 22031 22031 陈立平陈立平 男男 物理物理 92 92 学生成绩表37线性结构逻辑特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前趋和一个直接后继。线性表，栈，队，字符串，数组，广义表非线性结构逻辑特征是：一个结点可能有多个直接前趋和直接后继。图，树1573246abcdefhgi3839类比1：牌的大小和牌的位置牌的大小关系：4比5小、比3大等，相当于牌的逻辑关系(线性结构)。牌的实际顺序：洗完牌后，每张牌的实际位置相当于牌的存储结构。40类比2：银行排队旧的排队方法：

19、储户按到来的顺序站着排队，银行按排队顺序依次为储户服务。新的排队方法：银行引入排队机后，储户不再需要站着排队，而是先在排队机上取号，银行根据储户号码的顺序依次为储户服务，储户可以分散在银行的等候区等候排队机叫号。41采用排队机的排队方式 与 逻辑结构/存储结构的对应关系：储户取到的号码，相当于储户们之间的逻辑关系。银行根据储户号码的顺序依次为他们服务。储户在等候时，分散在等候区的各个位置，此时每个储户的实际位置相当于储户的存储结构。42存储器描述1：存储空间中每个存储单元(字节)都有唯一的地址，存储空间在地址上是连续的，而且按地址从低到高排列。描述2：其存储空间提供了一种具有非负整数地址编码的

20、、在存储空间上相邻的单元集合，其基本的存储单元是字节。数据的存储结构：建立一种从逻辑结构逻辑结构到存存储空间储空间的映射。43顺序存储由此得到的存储表示称为顺序存储结构。 特点 (1) 连续连续存放，逻辑存放，逻辑上上相邻，物理相邻，物理上也相邻。上也相邻。 (2) 结构简单，易实现。结构简单，易实现。 (3) 插入、删除操作不便（需大量移动元素）插入、删除操作不便（需大量移动元素）。该方法主要应用于线性的数据结构，也可用于非线性的数据结构。 44元素元素n n.元素元素i i.元素元素2 2元素元素1 1L Lo oL Lo o+m+mL Lo o+(i-1)+(i-1)* *m mL Lo

21、 o+ +（n-1)n-1)* *m m存储地址存储地址存储内容存储内容顺序存储顺序存储LocLoc( (元素元素i i)=Lo+)=Lo+（i-1)i-1)* *m m45链接存储由此得到的存储表示称为链式存储结构。 特点:(1)非连续非连续存放，借助存放，借助指针来表示元素间的指针来表示元素间的关系；关系；(2)插入、删除操作简单，只要修改指针即可插入、删除操作简单，只要修改指针即可；(3)结构较复杂，需要额外存储空间结构较复杂，需要额外存储空间。该方法主要应用于线性的数据结构，也可用于非线性的数据结构。 4615361536元素元素2 214001400元素元素1 113461346元素

22、元素3 3 元素元素4 413451345存储地址存储地址 存储内容存储内容 指针指针 1345 1345 元素元素1 1 14001400 1346 1346 元素元素4 4 . . . . . . 14001400 元素元素2 2 1536 1536 . . . . . . 1536 1536 元素元素3 3 1346 1346 链式存储链式存储 h h47索引存储方法 索引表中的每一项称为索引项，一般形式是： （关键字，地址）关键字，地址） 关键字是关键字是能唯一标识能唯一标识一个结点或一组结点的那些数据项一个结点或一组结点的那些数据项 地址是存储数据的位置地址是存储数据的位置 稠密索引

23、：每个结点在索引表中都有一个索引项。稀疏索引：一组结点在索引表中只对应一个索引项。特点: (1)非连续存放非连续存放；(2)检索速度快检索速度快；(3)插入、删除操作插入、删除操作简单。简单。48索引存储王2王1张2张1李2李1地址姓名王张李地址姓49散列存储Address=H(KeyWord)散列存储结构在数据元素与存储位置之间建立一种存储关系F，根据这种关系F，已知元素E，就可以得到它的存储地址，即D=F(E)。哈希查找中的哈希表就是这样一种存储结构。特点:(1)数据元素间无内在联系数据元素间无内在联系；(2)存储形式不定。存储形式不定。 50算法(Algorithm)的定义算法须满足以下

24、性质： 输入输入性性：具有零个或多个输入量，即算法开始前对算法给出的初始量； 输出输出性性：至少产生一个输出； 有有穷性穷性：每条指令的执行次数必须是有限的； 确定性确定性：每条指令的含义必须明确，无二义性； 可行性可行性：每条指令都应在有限的时间内完成。 程序可以不满足第(3)个条件(有穷性)，例如操作系统，启动后如果不关闭，它永远也不会结束。51判断一个算法的优劣，主要有以下几个标准：(1) 正确性：要求算法能正确地执行预先规定的功能和性能要求。(2) 可实用性：要求算法能够很方便地使用。(3) 可读性：算法应该是可读的，这是理解、测试和修改算法的需要。(4) 效率：算法的效率主要指算法执

25、行时对计算机资源的消耗，包括存储空间和运行时间的开销，前者称为算法的空间代价，后者叫做算法的时间代价。(5) 健壮性：对不合理的数据进行检查，要求在算法中加入对输入参数、打开文件、读文件记录等进行自动检查、报错并通过用户对话来纠错的功能，也称为容错性处理。52算法效率度量分为事前估计和后期测试。算法的后期算法的后期测试测试算法设计完毕后，在运行时通过在算法的某些位置加入时间函数(如time( )、clock( )等)来测定算法完成某一功能所需的时间。算法的事前估计：算法的事前估计：不需运行算法，通过度量算法所需时间、存储空间与问题规模的关系来测定算法的效率。所测定出来的关系称为算法的复杂度，分

26、为时间复杂度和空间复杂度。5354算法的后期测试对评定算法的效率有什么优缺点？#include #include int main( )freopen( out3.txt, w, stdout );int n = 100;int i, j;double F;time_t time, start, end;/程序运行总时间、程序运行开始时刻、结束时刻程序运行总时间、程序运行开始时刻、结束时刻start = clock( );/取得系统当前时刻取得系统当前时刻for( i=1; i=n; i+ )F = 1;for( j=1; j=i; j+ )F = F*j;printf( %.fn, F );

27、end = clock( );/取得系统当前时刻取得系统当前时刻time = end - start;printf( %dn, time );return 0;算法的事前估计算法的事前估计：不需运行算法，通过度量算法所需时间、存储空间与问题规模的关系来测定算法的效率。所测定出来的关系称为算法的复杂度，分为时间复杂度和空间复杂度。时间复杂度时间复杂度(Time Complexity)：指当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所需时间也以某种单位由1增加到t(n)。空间复杂度空间复杂度(Space Complexity)：指当问题的规模以某种单位从1增加到n时，解决这个问

28、题的算法在执行时所占用的存储空间也以某种单位由1增加到f(n)。55求两个n阶方阵的乘积，算法描述如下：算法的时间特性是： T(n)=2nT(n)=2n3 3+3n+3n2 2+2n+1 +2n+1 ，T(n)也称为算法的时间复杂度，简记为：O(O(n n3 3) )“O”的形式定义为：若f(n)是正整数n的一个函数，则xnO(f(n)表示存在一个正的常数M，使得当nn0时，满足|xn|M|f(n)|。n+1n(n+1)n*nn*n*(n+1)n*n*n问题的规模为n56算法时间复杂度的：在时间复杂度T(n)中，经过这样处理得到的函数是T(n)的近似效率值，但这个近似值与原函数已经足够接近，当问题规模很大时尤其如此。这种效率的度量就称为。(在不引起混淆的情况下，也可简称)：找出算法中最重要、执行最频繁的操作，找出算法中最重要、执行最频繁的操作，即所谓的即所谓的。并。算法的基本操作。57关于时间复杂度的三个例子(1) +x；s = 0；(2) for ( i = 1；i=n；+i ) +x；s += x；(3) for ( j = 1；j=n；+j ) for ( k = 1；k=n；+k ) +x；s +=x；含基本操作+x的语句的频度分别为1、n、n2，时间复杂度分别为O(1)、 O