C语言程序设计教程第1章

1、,C语言程序设计,信息与电气工程学院 计算机基础教研室 邮箱：xindian_,第一章 软件开发基础工资管理系统之项目管理,任务一 学习目标 任务二 了解软件工程 任务三 了解数据结构 任务四 了解算法设计 任务五 本章要点汇总 任务六 实力检验,任务一 学习目标,了解软件工程的相关知识 软件工程的概念、三要素 软件生命周期的几个阶段,了解数据结构 数据结构的概念 数据的逻辑结构和存储结构 常用的几种数据结构,了解算法设计 算法的概念、特性 算法的描述方法 算法的复杂度,任务一 学习目标,任务二 了解软件工程,1软件的概念及特点,定义,软件是程序、数据及其相关文档的完整集合。,程序是按事先设计

2、的功能和性能要求执行的指令序列。 数据实施程序能正常操纵信息的数据结构。 文档是与程序开发、维护和使用有关的图文材料。,特点,软件是一种逻辑产品，它以程序和文档的形式出现，保存在计算机存储器的磁盘和光盘介质上，通过计算机的运行体现它的功能和作用。,软件产品的生产主要是研制-脑力劳动。,软件产品不存在磨损、消耗的问题，存在软件维护的问题。,2软件工程,自上世纪60年代以来，软件的应用越来越广泛，需求越来越迫切，规模也越来越大，但是软件的生产率一直得不到提高，出现了种种难以解决的问题，严重影响了软件产业的健康发展，这一系列现象被称为“软件危机”。,软件工程是指导计算机软件开发和维护的一门工程科学，

3、它采用工程的概念、原理、技术和方法来开发、维护以及管理软件。,定义,软件工程的三要素,方法、工具、过程,1968年在NATO（北大西洋公约组织）一次专门讨论软件危机的国际会议上正式提出了“软件工程“这一概念。,工具人类在开发软件的活动中智力和体力的扩展和延伸，它提供了自动或半自动的软件支撑环境。,方法完成软件工程项目的技术手段。包括项目计划与估算、软件需求分析、系统总体结构设计、数据结构设计、算法设计、编写代码、软件测试及维护等。,过程贯穿于软件开发的各个环节，支持软件开发的各个环节的控制、管理。,软件生命周期,指从开发软件概念的提出起，直到该软件使用，失去使用价值而被废弃的整个过程，也可以称

4、作软件生存周期。,包含六个阶段：,可行性研究与计划制定,需求分析,经济可行性、技术可行性、方案的选择等,对软件需要实现的各个功能进行详细分析,软件设计,软件实现,软件测试,运行与维护,系统框架设计、数据库设计等,任务三 了解数据结构,程序=算法+数据结构+程序设计语言,算法：处理问题的策略。,数据结构：问题的数学模型。,程序：为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。,1数据、数据元素和数据项的概念,数据：对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储和加工的符号总称。,数据项：数据结构中讨论的最小单位。,数据元素：数据结构中的基本单位，可由若干个

5、数据项组成，在程序中常作为一个整体进行考虑和处理。,2数据结构的概念及分类,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储、组织数据的方式。,（1）概念,（2）分类,数据结构研究的三个方面： （1）各数据元素之间的逻辑关系-逻辑结构； （2）数据元素在计算机中的存储关系-存储结构； （3）对各种数据结构进行的运算。,1）数据的逻辑结构,数据的逻辑结构是对数据元素之间的逻辑关系的描述，它是数据的组织形式。,集合：集合中任意两个数据元素间没有逻辑关系，组织形式松散。,树形结构：树形结构具有分支、层次特性，数据元素间形成一种一对多的关系。,线性结构：数据元素间顺序的线性关系

6、。,图状结构：数据元素之间存在多对多的关系，也叫网状结构。,2）数据的存储结构,数据结构在计算机中的表示称为数据的存储结构，也称为物理结构。,四种基本的存储映像：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。,顺序存储结构,顺序存储通常用于存储具有线性结构的数据。,链式存储结构,节点在存储器中随意存放，节点之间的物理关系与逻辑关系无关。,常用的几种数据结构,数据元素的位置取决该元素的序号，元素之间的相对位置是线性的。,限定在一端进行插入与删除的线性表， 按照“先进后出或“后进先出组织数据,允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表,各数据结点的存储顺序与数据元素之

7、间的逻辑关系可以不一致，数据元素之间的逻辑关系是由指针域来确定。,任务四 了解算法设计,算法是为解决一个问题而采取的方法和步骤。,1算法的概念,算法分为：数值运算算法和非数值运算算法。,【例1-1】 计算1+2+3+100。,传统算法：先计算1加2，得到3；再将3与3相加，得到6；再将6与4相加，得到10；依此类推。,繁琐！,如何设计一个算法,设变量s初值为0，变量i存放第一个加数，s和i相加后将和重新放在s中，并作为新的第一个加数，变量i的值增1，再与s求和，依此类推，直到i的值大于100。,step1：s=0； step2 ：i=1； step3 ：s+is； step4 ：i+1i； s

8、tep5 ：如果i小于等于100，返回继续执行step3以及之后的步骤；否则，输出s的值，算法结束。,改进的算法：,若要实现：1+3+5+99，如何设计算法呢？,提示：只要将第四步改为：i+2i就可以了。,【例1-2】从键盘输入任意两个不等的整数，输出较大者的值。,step1：从键盘输入两个不相等的整数a和b； step2 ：比较a和b的大小，如果ab，执行第三步，否则执行第四步； step3 ：输出a； step4 ：输出b。,从键盘输入任意两个不等的整数，输出较小者的值，又该如何设计算法呢？,提示：将第二步中的ab改为ab。,step1：从键盘输入两个不相等的整数a和b； step2 ：比

9、较a和b的大小，如果ab，执行第三步，否则执行第四步； step3 ：输出a； step4 ：输出b。,2算法的特性,有穷性,包含有限的操作步骤，在有限的、合理的 时间内完成。,确定性,每一个步骤必须有确切的含义。,有效性,每一个步骤都应当能有效地执行，并得到确定的结果。,有一个或多个输出。,有零个或多个输入,3算法的描述,自然语言。,优点：通俗易懂。 缺点：缺乏直观性和简洁性，易产生歧义。,专用工具,流程图,案例1-1 的算法用流程图来描述如图1-6所示。,案例1-2 的算法用流程图来描述如图1-7所示。,直观形象、结构清晰,缺点：流程随意跳转,N-S图,案例1-1 的算法用流程图来描述如图

10、1-8所示。,案例1-2的算法使用N-S图来描述如图1-9所示：,4算法的复杂度,算法效率的度量，评价算法优劣的重要依据。,算法的复杂度的高低体现在运行该算法所需要的计算机资源的多少 。,时间复杂度,指执行算法所需要的计算工作量。,算法执行所花费的时间和语句执行的次数成正比例。,语句执行的次数称为语句频度或时间频度。所有语句的频度之和构成了该算法的运算时间。,例如，计算下面程序段的时间复杂度 for(i=0;in;i+) for(j=0;jm;j+) aij=1;,语句的频度为n，语句的频度为m，,该程序段的时间复杂度为： T(n)=nm=O(nm)。,空间复杂度,指算法在计算机内执行时所占用

11、的内存开销规模(程序、输入数据和辅助变量所占空间)。,降低算法的空间复杂度，从两方面考虑：一是数据结构，二是从算法。,任务五 本章要点汇总,软件工程基础知识 软件：程序、数据及其相关文档的完整集合 软件工程：是指导计算机软件开发和维护的一门工程科学，它采用工程的概念、原理、技术和方法来开发、维护以及管理软件。软件工程是目前计算机学科中一个年轻并且充满活力的研究领域。 软件工程三要素：方法、工具和过程。,软件的生命周期：是指从开发软件概念的提出起，直到该软件的使用、失去使用价值而被废弃为止的整个过程。包括6个阶段：可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行与维护。 软件开发模型：是软件开发全部过程、活动和任务的结构框架。它能直观表达软件开发全过程，明确规定要完成的主要活动、任务和开发策略。,数据结构基础知识 数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储、组织数据的方式。数据结构主要研究和讨论数据的逻辑结构、存储结构和数据的运算。 数据的逻辑结构：是对数据元素之间的逻辑关系的描述，它是数据的组织形式。包括：集合、线性结构、树形结构和图状结构四种。 数据的存储结构：是数