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

语言程序设计C语言程序设计信息与电气工程学院计算机基础教研室邮箱：[e-mail]语言程序设计第一章软件开发基础——工资管理系统之项目管理•任务一学习目标•任务二了解软件工程•任务三了解数据结构•任务四了解算法设计•任务五本章要点汇总•任务六实力检验语言程序设计任务一学习目标了解软件工程的相关知识软件工程的概念、三要素软件生命周期的几个阶段了解数据结构数据结构的概念数据的逻辑结构和存储结构常用的几种数据结构语言程序设计了解算法设计算法的概念、特性算法的描述方法算法的复杂度任务一学习目标语言程序设计任务二了解软件工程1．软件的概念及特点⑴定义软件是程序、数据及其相关文档的完整集合。程序是按事先设计的功能和性能要求执行的指令序列。数据实施程序能正常操纵信息的数据结构。文档是与程序开发、维护和使用有关的图文材料。语言程序设计⑵特点①软件是一种逻辑产品，它以程序和文档的形式出现，保存在计算机存储器的磁盘和光盘介质上，通过计算机的运行体现它的功能和作用。②软件产品的生产主要是研制---脑力劳动。③软件产品不存在磨损、消耗的问题，存在软件维护的问题。语言程序设计失效率时间硬件失效率曲线理想曲线实际曲线失效率时间软件失效率曲线语言程序设计2．软件工程自上世纪60年代以来，软件的应用越来越广泛，需求越来越迫切，规模也越来越大，但是软件的生产率一直得不到提高，出现了种种难以解决的问题，严重影响了软件产业的健康发展，这一系列现象被称为“软件危机”。语言程序设计软件工程是指导计算机软件开发和维护的一门工程科学，它采用工程的概念、原理、技术和方法来开发、维护以及管理软件。⑴定义⑵软件工程的三要素方法、工具、过程1968年在NATO（北大西洋公约组织）一次专门讨论软件危机的国际会议上正式提出了“软件工程“这一概念。语言程序设计工具—人类在开发软件的活动中智力和体力的扩展和延伸，它提供了自动或半自动的软件支撑环境。方法—完成软件工程项目的技术手段。包括项目计划与估算、软件需求分析、系统总体结构设计、数据结构设计、算法设计、编写代码、软件测试及维护等。过程—贯穿于软件开发的各个环节，支持软件开发的各个环节的控制、管理。语言程序设计⑶软件生命周期指从开发软件概念的提出起，直到该软件使用，失去使用价值而被废弃的整个过程，也可以称作软件生存周期。包含六个阶段：①可行性研究与计划制定②需求分析经济可行性、技术可行性、方案的选择等对软件需要实现的各个功能进行详细分析语言程序设计③软件设计④软件实现⑤软件测试⑥运行与维护系统框架设计、数据库设计等语言程序设计任务三了解数据结构程序=算法+数据结构+程序设计语言算法：处理问题的策略。数据结构：问题的数学模型。程序：为实现特定目标或解决特定问题而用计算机语言编写的命令序列的集合。语言程序设计1．数据、数据元素和数据项的概念数据：对客观事物的符号表示，在计算机科学中是指能输入到计算机中并被计算机存储和加工的符号总称。数据项：数据结构中讨论的最小单位。数据元素：数据结构中的基本单位，可由若干个数据项组成，在程序中常作为一个整体进行考虑和处理。工号姓名出生日期工龄基本工资……语言程序设计2．数据结构的概念及分类数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储、组织数据的方式。（1）概念（2）分类栈数据的逻辑结构线性结构非线性结构队线性表图形结构数据的存储结构顺序存储链式存储数据结构树形结构数据结构研究的三个方面：（1）各数据元素之间的逻辑关系-逻辑结构；（2）数据元素在计算机中的存储关系-存储结构；（3）对各种数据结构进行的运算。语言程序设计1）数据的逻辑结构数据的逻辑结构是对数据元素之间的逻辑关系的描述，它是数据的组织形式。①集合：集合中任意两个数据元素间没有逻辑关系，组织形式松散。图1-1集合语言程序设计图1-2线性结构图1-3树型结构③树形结构：树形结构具有分支、层次特性，数据元素间形成一种一对多的关系。②线性结构：数据元素间顺序的线性关系。语言程序设计图1-4图形结构④图状结构：数据元素之间存在多对多的关系，也叫网状结构。语言程序设计2）数据的存储结构数据结构在计算机中的表示称为数据的存储结构，也称为物理结构。四种基本的存储映像：顺序存储结构、链式存储结构、索引存储结构和散列存储结构。①顺序存储结构顺序存储通常用于存储具有线性结构的数据。②链式存储结构节点在存储器中随意存放，节点之间的物理关系与逻辑关系无关。语言程序设计⑷常用的几种数据结构线性表栈队列链表树图数据元素的位置取决该元素的序号，元素之间的相对位置是线性的。限定在一端进行插入与删除的线性表，按照“先进后出或“后进先出组织数据允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，数据元素之间的逻辑关系是由指针域来确定。语言程序设计任务四了解算法设计算法是为解决一个问题而采取的方法和步骤。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+i→s；step4：i+1→i；step5：如果i小于等于100，返回继续执行step3以及之后的步骤；否则，输出s的值，算法结束。改进的算法：语言程序设计若要实现：1+3+5+……+99，如何设计算法呢？提示：只要将第四步改为：i+2→i就可以了。语言程序设计【例1-2】从键盘输入任意两个不等的整数，输出较大者的值。step1：从键盘输入两个不相等的整数a和b；step2：比较a和b的大小，如果ab，执行第三步，否则执行第四步；step3：输出a；step4：输出b。语言程序设计从键盘输入任意两个不等的整数，输出较小者的值，又该如何设计算法呢？提示：将第二步中的ab改为ab。step1：从键盘输入两个不相等的整数a和b；step2：比较a和b的大小，如果ab，执行第三步，否则执行第四步；step3：输出a；step4：输出b。语言程序设计2．算法的特性⑴有穷性包含有限的操作步骤，在有限的、合理的时间内完成。⑵确定性每一个步骤必须有确切的含义。⑶有效性每一个步骤都应当能有效地执行，并得到确定的结果。⑸有一个或多个输出。⑷有零个或多个输入语言程序设计3．算法的描述⑴自然语言。优点：通俗易懂。缺点：缺乏直观性和简洁性，易产生歧义。⑵专用工具①流程图数据处理判断循环上界线循环下界线连接端点注解流线省略图1-5流程图标准化符号语言程序设计案例1-1的算法用流程图来描述如图1-6所示。开始s=0,i=1i≤100s=s+ii=i+1结束YN图1-6语言程序设计YN开始输入a,bab结束输出a输出b图1-7案例1-2的算法用流程图来描述如图1-7所示。直观形象、结构清晰缺点：流程随意跳转语言程序设计②N-S图选择结构条件TFAB当型循环当P为真A直到型循环直到P为假A顺序结构AB语言程序设计0=ss+i=s1=ii+1=i当i≤100输出s图1-8案例1-1的算法用流程图来描述如图1-8所示。语言程序设计图1-9输入a,bab?输出a输出bYN案例1-2的算法使用N-S图来描述如图1-9所示：语言程序设计4．算法的复杂度—算法效率的度量，评价算法优劣的重要依据。算法的复杂度的高低体现在运行该算法所需要的计算机资源的多少。⑴时间复杂度指执行算法所需要的计算工作量。算法执行所花费的时间和语句执行的次数成正比例。语句执行的次数称为语句频度或时间频度。所有语句的频度之和构成了该算法的运算时间。语言程序设计例如，计算下面程序段的时间复杂度for(i=0;in;i++)①for(j=0;jm;j++)②a[i][j]=1;语句①的频度为n，语句②的频度为m，该程序段的时间复杂度为：T(n)=n×m=O(n×m)。语言程序设计⑵空间复杂度指算法在计算机内执行时所占用的内存开销规模(程序、输入数据和辅助变量所占空间)。降低算法的空间复杂度，从两方面考虑：一是数据结构，二是从算法。语言程序设计任务五本章要点汇总软件工程基础知识⑴软件：程序、数据及其相关文档的完整集合⑵软件工程：是指导计算机软件开发和维护的一门工程科学，它采用工程的概念、原理、技术和方法来开发、维护以及管理软件。软件工程是目前计算机学科中一个年轻并且充满活力的研究领域。⑶软件工程三要素：方法、工具和过程。语言程序设计⑷软件的生命周期：是指从开发软件概念的提出起，直到该软件的使用、失去使用价值而被废弃为止的整个过程。包括6个阶段：可行性研究与计划制定、需求分析、软件设计、软件实现、软件测试、运行与维护。⑸软件开发模型：是软件开发全部过程、活动和任务的结构框架。它能直观表达软件开发全过程，明确规定要完成的主要活动、任务和开发策略。语言程序设计数据结构基础知识⑴数据结构：指相互之间存在一种或多种特定关系的数据元素的集合，是计算机存储、组织数据的方式。数据结构主要研究和讨论数据的逻辑结构、存储结构和数据的运算。⑵数据的逻辑结构：是对数据元素之间的逻辑关系的描述，它是数据的组织形式。包括：集合、线性结构、树形结构和图状结构四种。⑶数据的存储结构：是数据的逻辑结构在计算机中的表示。包括：顺序存储结构、链式存储结构、索引存储结构、散列存储结构四种。语言程序设计算法设计基础知识⑴算法：是为解决一个问题而采取的方法和步骤。⑵算法的特性：有穷性、确定性、有效性、有零个或多个输入、有一个或多个输出。⑶算法的描述：自然语言、专用工具——流程图、N-S图。⑷算法复杂度：是算法效率的度量，是评价算法优劣的重要依据，包括时间复杂度和空间复杂度。