全国计算机等级考试《二级C语言程序设计》复习全书核心讲义+历年真题详解

全国计算机等级考试《二级C语言程序设计》

复习全书【核心讲义+历年真题详解］最新资料，WORD式，可编辑修改！目录第一部分备考指南第1章考试^^述第2章复习技巧第二部分核心讲义【公共基础知识】第1章数据结构与算法第2章程序设计基础第3章软件工程基础第4章数据库设计基础【C语言程序设计】第1章程序设计基本概念第2章C程序设计的初步知识第3章顺序2g构第4章选择名g构第5章循环名g构第6章字符型数据第7章函数第8章地址和指针第9章数组第10章字符串第11章对函数的进一步讨论第12章C语言中用户标识符的作用域和存储类第13章编译预处理和动态存储分配第14章结构体、共用体和用户定义类型第15章位运算第16章文件第三部分历年真题及详解全国计算机等级考试《二级C语言程序设计》真题及详解（一）全国计算机等级考试《二级C语言程序设计》真题及详解（二）

全国计算机等级考试《二级C语言程序设计》真题及详解（二）.….…全国计算机等级考试《二级C语言程序设计》真题及详解（四）.….…全国计算机等级考试《二级C语言程序设计》真题及详解（五）.….…全国计算机等级考试《二级C语言程序设计》真题及详解（六）.….…第四部分模拟试题及讲解..…全国计算机等级考试《二级C语言程序设计》模拟试题及详解（一）全国计算机等级考试《二级C语言程序设计》模拟试题及详解（二）第一部分备考指南第1章考试概述一、考试简介全国计算机等级考试（NationalComputerRankExamination,简称NCRE,是经原国家教育委员会（现教育部）批准，由教育部考试中心主办，面向社会，用于考查应试人员计算机应用知识与技能的全国性计算机水平考试体系。计算机技术的应用在我国各个领域发展迅速，为了适应知识经济和信息社会发展的需要，操作和应用计算机已成为人们必须掌握的一种基本技能。许多单位、部门已把掌握一定的计算机知识和应用技能作为人员聘用、职务晋升、职称评定、上岗资格的重要依据之一。鉴于社会的客观需求，经原国家教委批准，原国家教委考试中心于1994年面向社会推出了NCRE其目的在于以考促学，向社会推广和普及计算机知识，也为用人部门录用和考核工作人员提供一个统一、客观、公正的标准。二、考试科目级别科目名称科目代码考试时间考核课程代码一级计算机基础及WPSOffice应用1490分钟114计算机基础及MSOffice应用1590分钟115计算机基础及Photoshop应用1690分钟116二级C语言程序设计24120分钟201、224VB语言程序设计26120分钟201、226VFP数据库程序设计27120分钟201、227Java语言程序设计28120分钟201、228Access数据库程序设计29120分钟201、229C++吾言程序设计61120分钟201、261MySQ擞据库程序设计63120分钟201、263Web®序设计64120分钟201、264MSOffice高级应用65120分钟201、265三级网络技术35120分钟335数据库技术36120分钟336软件测试技术37120分钟337信息安全技术38120分钟338嵌入式系统开发技术39120分钟339四级网络工程师4190分钟401、403数据库工程师4290分钟404、405软件测试工程师4390分钟401、405信息安全工程师4490分钟401、403嵌入式系统开发工程师4590分钟401、402说明：同次考试考生可报考多个级别或科目，但不允许重复报考同一个科目，具体要求请向所在省级承办机构进行咨询。报考多个科目时需咨询考点，避免考场安排时冲突。如：考生同时报考了二级C三级网络技术、四级网络工程师三个科目，结果通过了三级网络技术、四级网络工程师考试，但没有通过二级C考试，将不颁发任何证书，三级网络技术、四级网络工程师两个科目成绩，自考试结束之日起可保留半年（按月计算）。下一次考试考生报考二级C并通过，将一次获得三个级别的证书；若没有通过二级C,将不能获得任何证书。同时，三级网络技术、四级网络工程师两个科目成绩自动失效。三、报考条件.考生不受年龄、职业、学历等背景的限制，任何人均可根据自己学习和使用计算机的实际情况，选考不同等级的考试。考生一次只能报考一个科目的考试。考生一次考试只能在一个考点报名。考生可以不参加考前培训，直接报名参加考试。.每次考试报名的具体时间由各省（自治区、直辖市）级承办机构规定。考生按照有关规定到就近考点报名。上次考试的笔试和上机考试仅其中一项成绩合格的，下次考试报名时应出具上次考试成绩单，成绩合格项可以免考，只参加未通过项的考试。.特殊人员报考条件：现役军人可使用军官证报考NCR瑙试，在其军官证号码前后各加入识别码，此办法也适用于没有身份证的未成年人，识别码的编码有统一格式，前6位后4位。国务院和中央军事委员会联合下发的510号令，已经公布《现役军人和人民武装警察居民身份证申领发放办法》，该办法自2008年1月1日起实施，现役军人可以通过团以上单位集中向地方公安机关申请居民身份证。无身份证的学生可携带户口本参加报名，身份证丢失者凭公安机关开具的身份证明，外籍人员凭护照参加报名。四、报考方式分为考点现场报名与网上报名。考生在考点现场报名时，需出示身份证以及缴纳相关的考试费。考生一定要亲自到场，不能由任何单位、个人代劳。考生按要求进行信息采集，并逐一核实报名表上的个人信息：姓名、身份证号、照片、报考科目、报考类别（是否补考）等，发现信息不一致要立刻更改。报名完成后请妥善保管“考生报名登记表”防止阻碍准考证的领取。考生采取网上报名方式，需先在所在省份的网上报名系统注册并填报相关基本信息、上传正面免冠电子近照，然后网上缴费或至指定地点缴费并确认身份信息，完成报名。一般情况下，每次考试每个考生只能在一个考点完成报名。考生报名时缴纳的考试费的具体金额由各省级承办机构根据考试需要和当地物价水平确定，并报当地物价部门核准。考点不得擅自加收费用。

注：报名时依据的身份证明包括：居民身份证、军人的证件、护照、户口本等。五、报考时间考试安排第一场第二场第三场报名时间12月开始5月开始11月10日以后注：各地的报名时间由考生报考所在地的当地考试机构决定。六、考试时间NCREZ往每年开考两次，从2014年开始每年开考次数由两次增为三次。2016年NCR改排三次考试，考试时间分别为3月21日〜24日、9月19日〜22日、12月12日〜13日，其中3月和9月考试开考全部级别全部科目，12月只开考一级和二级，由各省级承办机构根据实际情况确定是否开考12月的考试七、各级别考试介绍一级科目一级WPSOffice一级MSOffice一级Photoshop考试环境NCR1级上机考试环境为Windows7简体中文版考试软件WPSOffice2012办公软件MSOffice2010PhotoshopCS5（典型方式安装）题型及分值比例单项选择题，20题，20分Windows操作系统的使用，10分WP敛字的操作，25分WPS1格的操作，20分WPSM示软件的操作，15分浏览器（IE）的简单使用和电子邮件收发，10分单项选择题，20题，20分Windows操作系统的使用，10分Word操作，25分Excel操作，20分PowerPoint操作，15分浏览器（IE）的简单使用和电子邮件收发，10分.单项选择题，55题，55分（含计算机基础知识部分20分）.Photoshop操作题，45分考核内容.考核内容包括计算机基础知识和操作技能两部分。.各科目对基础知识的要求相同，以考查应知应会为主，题型为选择题，分数占全卷的20%（20分）。.办公软件类考试，操作技能部分包括汉子录入、Windows系统使用、文子排版、电子表格、演示文稿、IE的简单应用及电子邮件收发。3.Photoshop考试，要求了解数字图像的基本知识，熟悉Photoshop的界面与基本操作方法，掌握并熟练运用绘图工具进行图像的绘制、编辑、修饰，会使用图层蒙版、样式以及文字工具。形式［完全采取上机考试形式，各科上机考试时间均为90分钟，满分100分。获证条件总分不低丁60分。备注参力口NCRE计算机基础及Photoshop应用”科目考生，可以在NCRES名时自

愿申请免试取得“AdobePhotoshop产品工程师认证”证书，即：通过NCRE“计算机基础及Photoshop应用”科目考试实现一次考试，可以同时取得全国计算机等级证书与“AdobePhotoshop产品工程师认证”证书，即“一考双证”。二级语言程序设计类数据库程序设计类办公软件高级应用科目C语言C++JavaVBWebVFPAccessMySQL办公软件高级应用考试环境NCRE二级上机考试环境为Windows7简体中文版考试软件VisualC++6.0VisualC++6.0Net-Beans中国教育考试版2007VB6.0简体专业版NetBeans中国教育考试版，IE6.0及以上VFP6.0简体中义专业版MSAccess2010MySQL(Community5.5.16)MSOffice2010题型及分值比例.单项选择题，40题，40分(含公共基础知识部分10分)2.程序填空题，3小空，18分.程序改错题，2个错误，24分.程序设计题，18分.单项选择题，40题，40分(含公共基础知识部分10分).基本操作题，18分.简单应用题，24分.综合应用/操作题，18分.单项选择题，20分(含公共基础知识部分10分).文字处理题(Word),30分.电子表格题(Excel),30分.演小文稿也(PowerPoint),20分考核内容一级定位为程序员，考核内容包括公共基础知识和程序设计。所有科目对基础知识作统一要求，使用统一的公共基础知识考试大纲和教程。一级公共基础知识在各科考试选择题中体现。程序设计部分，主要考查考生对程序设计语言使用和编程调试等基本能力，在选择题和操作题中加以体现。形完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。获

证

条

件总分不低于60分三级科目网络技术数据库技术软件测试技术信息安全技人嵌入式系统开发技人考试环境与软件.NCR三级上机考试环境为Windows7简体中文版.数据库技术考核C语言程序设计，使用VisualC++6.0题型及分值比例1.单选题，40题，40分2.综合题，40分3.应用题，20分考核内容.网络技术。网络规划与设计、局域网组网技术、计算机网络信息服务系统的建立及计算机网络安全与管理。.数据库技术。数据库应用系统分析及规划、数据库设计及实现、数据库存储技术、并发控制技术、数据库管理与维护、数据库技术的发展及新技术。.软件测试技术。软件测试的基本概念、软件测试技术、软件测试过程和管理方法。.信息安全技术。信息安全保障概论、信息安全基础技术与原理、系统安全、网络安全、应用安全、信息安全管理、信息安全标准与法规。.嵌入式系统开发技术。嵌入式系统的概念与基础知识、嵌入式处理器、嵌入式系统硬件组成、嵌入式系统软件、嵌入式系统的开发等相关知识和技能。形式完全采取上机考试形式。各科上机考试时间均为120分钟，满分100分。获证条件.总分不低于60分，并已经（或同时）获得一级相关证书。.三级数据库技术证书要求已经（或同时）获得二级数据库程序设计类证书；网络技术、软件测试技术、信息安全技术、嵌入式系统开发技术等四个证书要求已经（或同时）获得二级语言程序设计类证书。.考生早期获得的证书（如Pascal、FoxBase等），不严格区分语言程序设计和数据库程序设计，可以直接报考并获得证书。备注无四级科目网络工程师数据库工程师软件测试工程师信息安全工程师嵌入式系统开发工程师考试环境NCRE3级上机考试环境为Windows7简体中文版。题型及分值比例.单选题，60题，60分.多选题，20题，40分考核内容.网络工程师。考核计算机网络、操作系统原理两门课程。测试内容包括网络系统规划与设计的基础知识及中小型网络的系统组建、设备配置调试、网络系统现场维护与管理的基本技能。.数据库工程师。考核数据库原理、软件工程两门课程。测试内容包括数据库系统的基本理论以及数据库设计、维护、管理与应用开发的基本能力。.软件测试工程师。考核操作系统原理、软件工程两门课程。测试内容包括软件测试的基本理论、软件测试的规范及标准，以及制定测试计划、设计测试用例、选择测试工具、执行测试并分析评估结果等软件测试的基本技能。.信息安全工程师。考核计算机网络、操作系统原理两门课程。测试内容包括网络攻击与保护的基本理论与技术，以及操作系统、路由设备的安全防范技能。.嵌入式系统开发工程师。考核操作系统原理、计算机组成与接口两门课程。测试内容包括嵌入式系统基本理论、逻辑电路基础以及嵌入式系统中的信息表示与运算、评价方法等基本技能。形式.无纸化考试，考试总时间为90分钟，单课程考试没有时间要求。.四级考试科目由五门专业基础课程中指定的两门课程组成，总分100分，两门课程各占50分。.专业基础课程为计算机专业核心课程，包括：操作系统原理、计算机组成与接口、计算机网络、数据库原理、软件工程。获证条件两门课程分别达到30分及以上，并已经（或同时）获得三级相关证书。2013年3月及以前获得的二级各科目证书，不区分科目，可以作为四级任一科目的获证条件。备注无•2015年NCRE昧续实施2013年版考试大纲，教材参见全国计算机等级考试教材目录（2015年版）。八、考试要求.熟悉VisualC++6.0集成开发环境。.掌握结构化程序设计的方法，具有良好的程序设计风格。.掌握程序设计中简单的数据结构和算法并能阅读简单的程序。.在VisualC++6.0集成环境下，能够编写简单的C程序，并具有基本的纠错和调试程序的能力。九、考试内容（一）C语言程序的结构.程序的构成，main函数和其他函数。.头文件，数据说明，函数的开始和结束标志以及程序中的注释。.源程序的书写格式。.C语言的风格。（二）数据类型及其运算C的数据类型（基本类型，构造类型，指针类型，无值类型）及其定义方法。C运算符的种类、运算优先级和结合性。不同类型数据间的转换与运算。C表达式类型（赋值表达式，算术表达式，关系表达式，逻辑表达式，条件表达式，逗号表达式）和求值规则。（三）基本语句.表达式语句，空语句，复合语句。.输入输出函数的调用，正确输入数据并正确设计输出格式。（四）选择结构程序设计.用if语句实现选择结构。.用switch语句实现多分支选择结构。.选择结构的嵌套。（五）循环结构程序设计for循环结构。while和do-while循环结构。continue语句和break语句。循环的嵌套。（六）数组的定义和引用.一维数组和二维数组的定义、初始化和数组元素的引用。.字符串与字符数组。十、成绩及证书NCR世行百分制计分，但以等第通知考生成绩。等第共分优秀、及格、不及格三等。90〜100分为优秀、60〜89分为及格、0〜59分为不及格。一般在考后30个工作日内由教育部考试中心将成绩处理结果下发给各省级承办机构。考后50个工作日，考生可登录教育部考试中心综合查询网（）进行成绩查询。部分省市如江苏、黑龙江等也可通过省市考试院或者人事考试中心进行查询。NCREK绩在及格以上者，由教育部考t中心颁发合格证书。考后45个工作日教育部考试中心将证书发给各省级承办机构，然后由各省级承办机构逐级转发给考生。考生证书若丢失，可登录教育部考试中心综合查询网补办合格证明书。补办合格证明书收费21元，其中制证、邮寄费用20元，银行收取手续费1元。NCRE^格证书式样按国际通行证书式样设计，用中、英两种文字书写，证书编号全国统一，证书上印有持有人身份证号码。该证书全国通用，是持有人计算机应用能力的证明，也可供用人部门录用和考核工作人员时参考。一级证书表明持有人具有计算机的基础知识和初步应用能力，掌握Office办公自动化软件的使用及因特网应用，或掌握基本图形图像工具软件(Photoshop)的基本技能，可以从事政府机关、企事业单位文秘和办公信息化工作。二级证书表明持有人具有计算机基础知识和基本应用能力，能够使用计算机高级语言编写程序，可以从事计算机程序的编制、初级计算机教学培训以及企业中与信息化有关的业务和营销服务工作。三级证书表明持有人初步掌握与信息技术有关岗位的基本技能，能够参与软硬件系统的开发、运维、管理和服务工作。四级证书表明持有人掌握从事信息技术工作的专业技能，并有系统的计算机理论知识和综合应用能力。第2章复习技巧一、备考指导.勇往直前进入下午考试，也许有疲劳或不好的感觉，自信心就会下降；当看到题干很长，操作较复杂的题时，就有想回避或焦虑、急燥的情绪。这是典型的“两军未战，兵先屈”的败兴思绪。要知道两对手相遇勇者胜，勇者相遇智者胜。抛开所有不必要的想法，相信自己的实力，做到心无旁鹫，勇往直前。.审清题干题干包含了整个题目的条件和要求，若题干比较复杂，就要注意将题干“分段”来阅读，前后注意衔接，必要时在草稿纸上记载下关键点。有时候题干很长，看似很复杂，让很多人望而却步。其实，这种题更好解，因题干长了则提示信息也就多了。主要是考你有没有勇气和耐心。.解读试题首先，要翻阅一下全部试卷，注意试题的时间及分数的分配情况，做到心中有数。其次，要弄清题意，明确题目要求。因为考试要求可能与自己习惯的答题要求有所不同，所以一定要按题意和要求去回答。最后，要特别注意题目中比较隐蔽的条件。一般而言，条件隐蔽的问题难度较大，考生必须看清有关的线索，找出隐蔽条件，问题才能迎刃而解。.相信自己当题做得非常顺利时，心里不要太得意，因为越是看似容易的题目越是错的多，当然也不要逆向思维，觉得这题这么简单是不是做错了，要相信自己，说到底还是要审清题目的意思；二、题型分析.选择题选择题为单选题，是客观性试题，试题覆盖面广，一般情况下考生不可能做到对每个题目都有把握答对。这时，就需要考生学会放弃，即不确定的题目不要在上面花费太多的时间，应该在此题上做上标记，立即转移注意力，作答其他题目。最后有空余的时间再回过头来仔细考虑此题。但要注意，对于那些实在不清楚的题目，就不要浪费时间了，放弃继续思考，不要因小失大。绝大多数选择题的设问是正确观点，称为正面试题；如果设问是错误观点，称为反面试题。考生在作答选择题时可以使用一些答题方法，以提高答题准确率。（1）正选法（顺选法）：如果对题支中的4个选项，一看就能肯定其中的1个是正确的，就可以直接得出答案。注意，必须要有百分之百的把握才行。（2）逆选法（排谬法）：逆选法是将错误答案排除的方法。对题支中的4个选项，一看就知道其中的1个（或2个、3个）是错误的，可以使用逆选法，即排除错误选项。（3）比较法（蒙猜法）：这种办法是没有办法的办法，在有一定知识基础上的蒙猜也是一种方法。.操作题上机考试重点考察考生的基本操作能力，要求考生具有综合运用基础知识进行实际操作的能力。上机操作题综合性强、难度较大。上机考试的评分是以机评为主，人工复查为辅的。机评当然不存在公正性的问题，但却存在呆板的问题，有时还可能因为出题者考虑不周出现错评的情况。考生做题时不充分考虑到这些情况，就有可能吃亏。掌握好上机考试的应试技巧，可以使考生的实际水平在考试时得到充分发挥，从而取得较为理想的成绩。历次考试均有考生因为忽略了这一点，加之较为紧张的考场气氛影响了水平的发挥，致使考试成绩大大低于实际水平。因此每个考生在考试前，都应有充分的准备。总结以下几点供考生在复习和考试时借鉴：(1)对于上机考试的复习，切不可“死记硬背”根据以往考试经验，有部分考生能够通过笔试，而上机考试却不能通过，主要原因是这部分考生已经习惯于传统考试的“死记硬背”，而对于真正的知识应用，却显得束手无策。为了克服这个弊病，考生一定要在熟记基本知识点的基础上，加强上机训练，从历年试题中寻找解题技巧，理清解题思路，将各类典型试题反复练习。(2)在考前，一定要重视等级考试模拟软件的使用在考试之前，应使用等级考试模拟软件进行实际的上机操作练习，尤其要做一些具有针对性的上机模拟题，以便熟悉考试题型，体验真实的上机环境，减轻考试时的紧张程度。(3)学会并习惯使用帮助系统大部分软件都有较全面的帮助系统，熟练掌握帮助系统，可以使考生减少记忆量，解决解题中的疑难问题。(4)熟悉考试场地及环境尤其是要熟悉考场的硬件情况和所使用的相关软件的情况。考点在正式考试前，会给考生提供一次模拟上机的机会。模拟考试时，考生重点不应放在把题做出来，而是放在熟悉考试环境，相应软件的使用方法，考试系统的使用等方面。(5)做上机题时要不急不燥，认真审题先分析，后操作。明白了问题是什么以后，先把问题在脑海里过一遍，考虑好如何操作后，再依思路从容做答。而不要手忙脚乱、毛毛躁躁、急于作答＜对于十分了解或熟悉的问题，切忌粗心大意、得意忘形、而应认真分析，必须将题目给出的全部内容逐字看清楚后针对具体问题进行操作。常言道“熟能生巧”、“打铁还得本身硬”，再好的方法与技巧若没有基础，是发挥不了作用的；如若有了一定的功底，再差的招式也会产生很大的威力，就像金庸小说中杨过的那柄钝剑。但是如果只看不练，不会有提高。建议大家多做模拟试题和历年试题，锻炼解题的能力与节奏。第二部分核心讲义

【公共基础知识】

第1章数据结构与算法一、算法.算法的基本概念(1)算法的定义算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。它是一组严谨定义运算顺序的规则，且每个规则都是明确有效的，此顺序将在有限的次数下终止。需要注意的是：算法不等于程序，也不等于计算方法。(2)算法的基本特征①可行性a.算法中的每一步骤都必须能够实现；b.算法执行的结果要能够达到预期的目的。②确定性确定性是指算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释，也不允许有多义性。③有穷性有穷性是指算法必须能在有限的时间内做完，即必须能在执行有限个步骤之后终止，且必须有合理的执行时间。④拥有足够的情报算法是否有效，取决于为算法所提供的情报是否足够。一般而言，当算法有足够的情报时，此算法有效，而当提供的情报不够时，算法可能无效。2.算法设计基本方法(1)列举法①基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。常用于解决“是否存在”或“有多少种可能”等类型的问题。②主要特点算法比较简单，但列举情况较多时，算法工作量很大。③注意事项例举算法时，通过对实际问题进行详细分析，将与问题有关的知识条理化、完备化、系统化，并从中找出规律，或对所有可能的情况进行分类，从而引出一些有用的信息，减少列举量。(2)归纳法①基本思想通过列举少量的特殊情况，经过分析，最后找出一般的关系。②主要特点a.比列举法更能反映问题的本质，可解决列举量为无限的问题；b.可操作性低，不易归纳出一个具体数学模型；c.归纳得出的结论只是一种猜测，须对这种猜测加以必要的证明。(3)递推①基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。②主要特点a.初始条件或问题本身已给定，或通过对问题的分析化简得到；b.递推本质上属于归纳法，递推关系式往往是归纳的结果；c.数值型递推算法计算过程中必须注意数值计算的稳定性问题。(4)递归①基本思想将复杂问题逐层分解，归结为一些简单的问题，将简单问题解决掉，再沿着原来分解的逆过程逐步进行综合。②主要特点a.递归的基础是归纳，对问题逐层分解的过程实际上并没有对问题进行求解；b.在可计算性理论和算法设计中占有重要地位；c.递归算法比递推算法清晰易读，结构简练；d.设计递归算法比递推算法容易，但是其执行效率较低。③分类a.直接递归。一个算法P显式地调用自己。b.间接递归。算法P调用另一个算法Q,而算法Q又调用算法P。④递归与递推的区别递归与递推的区别主要在于二者实现方法的不同，表现为：a.递归是从算法本身到达递归的边界的；b.递推是从初始条件出发，逐次推出所需求的结果。(5)减半递推技术减半递推技术是工程上常用的分治法，其中，“减半”指将问题的规模减半，而问题的性质不变；“递推”指重复“减半”的过程。(6)回溯法回溯法是指通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，若试探成功，则问题得到解决，若试探失败，则逐步回退换别的路线再进行试探。3.算法复杂度(1)时间复杂度①定义算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量=f(n)其中，n是问题的规模。②在同一问题规模下，若算法的基本运算次数取决于某一特定输入，可用以下两种方法来分析算法的工作量：a.平均性态平均性态分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量。算法的平均性态定义为：其中，x是所有可能输入中的某个特定输入，p(x)是x出现的概率，即输入为x的概率，t(x)是算法在输入为x时所执行的基本运算次数，Dn表示当规模为n时，算法执行时所有可能输入的集合。b.最坏情况复杂性最坏情况分析是指规模为n时，算法所执行的基本运算的最大次数。其定义为：(2)空间复杂度①定义算法的空间复杂度一般是指执行这个算法所需要的内存空间。②存储空间组成一个算法的存储空间包括以下几种：a.算法程序占用的空间；b.输入的初始数据占用的存储空间；c.算法执行过程中所需要的额外空间。额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间，若额外空间相对于问题规模来说是常数，则称该算法是原地工作的。二、数据结构的基本概念.概述(1)数据处理概述①定义数据处理是指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。②关键问题大量数据元素在计算机中如何组织，以便提高数据处理的效率，从而节省计算机的存储空间，这是进行数据结构处理的关键问题。(2)数据结构研究概述①研究问题a.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；b.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；c.对各种数据结构进行的运算。②研究目的数据结构研究和讨论上述3个问题的主要目的在于提高数据处理效率，包括：a.提高数据处理的速度；b.尽量节省在数据处理过程中所占用的计算机存储空间。.数据结构的概念(1)数据结构的定义数据结构是指相互有关联的数据元素的集合，即它是反映数据元素之间关系的数据元素集合的表示。简言之，数据结构是指带有结构的数据元素的集合，这里的“结构”指数据元素之间的前后件关系。一个数据结构应包含以下两方面内容：①表述数据元素的信息；②表示各数据元素之间的前后件关系。(2)数据的逻辑结构①定义数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。②要素：a.数据元素的集合，通常记为D;b.D上的关系，通常记为R,它反映了D中各数据元素之间的前后件关系。③表示一个数据结构B可表示为：B=(D,R)为反映D中个数据元素之间的前后件关系，一般用二元组来表示。(3)数据的存储结构①定义数据的存储结构，也称数据的物理结构，是指数据逻辑结构在计算机存储空间中的存放形式。在数据的存储结构中，不仅要存放各数据元素的信息，而且要存放各数据元素之间的前后件信息。②常用的存储结构：a.顺序；b.链接；c.索引。采用不同的存储结构，数据处理的效率是不同的。.数据结构的图形表示(1)在数据结构的图形表示中，数据集合D中每个元素用中间标有元素值的方框表示，称为数据结点(简称结点)；对关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点。(2)在数据结构中，没有前件的结点称为根结点，没有后件的结点称为终端结点(也称叶子结点)，其余结点都称为内部结点。(3)数据结构中的元素结点可能是在动态变化的，这种变化体现在结点数量的增减以及各结点之间的前后件关系的动态变化上。.线性结构与非线性结构根据数据结构中各数据元素之间的前后件关系的复杂程度，可将数据结构分为：(1)线性结构(线性表)一个非空的数据结构满足下列两个条件时，称其为线性结构：①有且只有一个根结点；②每个结点最多只有一个前件，也最多只有一个后件。线性结构中插入或删除任何一个结点还应是线性结构，如果不满足这个条件就不能称之为线性结构。(2)非线性结构如果一个数据结构不是线性结构，则称之为非线性结构。注：线性结构与非线性结构都可以是空的数据结构。一个空的数据结构属于线性结构还是非线性结构，需要根据对该数据结构的运算是否按照线性结构的规则来处理进行判断。三、线性表及其顺序存储结构.线性表的基本概念(1)线性表是一种最常见最简单的数据结构，由一组数据元素构成。数据元素在线性表中的位置值只取决于它们自己的序号，即数据元素之间的相对位置是线性的。(2)非空线性表的结构特征：①有且只有一个根结点ai,它无前件；②有且只有一个终端结点an,它无后件；③除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有*个后件。线性表中结点的个数n称为线性表的长度。当n=0时，称为空表。.线性表的顺序存储结构(1)概述顺序存储是一种最简单的在计算机中存放线性表的方法，也称顺序分配。(2)特点：①线性表中所有元素所占的存储空间是连续的；②线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。(3)运算在线性表的顺序存储结构下，可对线性表进行以下运算：①插入：在线性表的指定位置处加入一个新的元素；②删除：在线性表中删除指定的元素；③查找：在线性表中查找某个(或某些)特定的元素；④排序：对线性表中的元素进行整序；⑤分解：按要求将一个线性表分解成多个线性表；⑥合并：按要求将多个线性表合并成一个线性表；⑦复制：复制一个线性表；⑧逆转：逆转一个线性表等。.顺序表的插入运算假设线性表的存储空间为V(1:m),线性表的长度为n(n<mj),插入的位置为i(表示在第i个位置插入元素)，则顺序表插入新元素过程如下：(1)首先处理以下三种异常情况：①当存储空间已满(即n=m)时为“上溢”错误，不能进行插入，算法结束；②当i>n时，认为在最后一个元素之后(即第n+1个元素之前)插入；③当i<1时，认为在第1个元素之前插入。(2)从最后一个元素开始，直到第i个元素，其中每一个元素均往后移动一个位置。(3)最后将新元素插入到第i个位置，并且将线性表的长度增加1。4.顺序表的删除运算假设线性表的存储空间为V(1:m),线性表的长度为n(n<mj),删除的位置为i(表示删除第i个元素)，则顺序表删除元素的过程如下：(1)首先处理以下两种异常情况：①当线性表为空(即n=0)时为“上溢”错误，不能进行插入，算法结束；②当i<1或i>n时，认为在最后一个元素之后(即第n+1个元素之前)插入。(2)然后从第i+1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。(3)最后将线性表的长度减小1。四、栈和队列.栈及其基本运算(1)栈的定义栈是限定在一端进行插入与删除的线性表。(2)栈的特点：①允许插入和删除的一端称为栈顶，不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入也是最后被删除的。②栈遵循“先进后出”或“后进先出”的原则，具有记忆功能。③通常用指针top来指示栈顶位置，用指针bottom指向栈底，栈顶指针top动态反映了栈中元素的变化情况。(3)栈的顺序存储及其运算在栈的顺序存储空间S(1:m)中，top=0表示栈空；top=m表示栈满。栈的三种运算：①入栈运算人栈运算是指在栈顶位置插入一个新元素。操作过程如下：a.首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作(这种情况称为栈“上溢”错误)，算法结束。b.然后将栈顶指针进一(即top加1)。c.最后将新元素x插入栈顶指针指向的位置。②退栈运算退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：a.首先判断栈顶指针是否为00如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。b.然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。c.最后将栈顶指针退一（即top减1）。③读栈顶元素读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：a.首先判断栈顶指针是否为00如果是，则说明栈空，读不到栈顶元素，算法结束。b.然后将栈顶元素赋给指定的变量y。这个运算不删除栈顶元素，只是将它的值赋给一个变量，栈顶指针不会变。.队列及其基本运算（1）什么是队列队列（Queued是指允许在一端进行插入、而在另一端进行删除的线性表。（2）队列的特点①允许插入的一端称为队尾，用队尾指针指向队尾元素；允许删除的一端称为队头，用排头指针指向排头元素的前一个位置。②最先插入的元素最先被删除，最后插入的元素最后被删除，遵循“先进先出”或“后进后出”原则。③队尾指针rear和排头指针front共同反映队列中元素变动情况。④入队运算指只涉及队尾指针rear变化，退队运算只涉及排头指针front变化。（3）循环队列及其运算循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队尾元素，用排头指针front指向排头元素的前一个位置，从排头指针front指向的后一个位置到队尾指针rear指向的位置均是队列中元素。队列空的条件是s=0;队列满的条件是s=1且front=rear。队列的两种运算假设循环队列的初始状态为空，即：s=0,且front=rear=mi①入队运算入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：a.首先判断循环队列是否满。当循环队列非空（S=1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。b.然后将队尾指针进一（即rear=rear+1）,并当rear=mi+1时置rear=1oc.最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。②退队运算退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：a.首先判断循环队列是否为空。当循环队列为空(s=0)时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。b.然后将排头指针进一(即front=front+1),并当front=mVr1时置front=1。c.再将排头指针指向的元素赋给指定的变量。d.最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志(即s=0)o五、线性链表.线性链表的基本概念(1)线性表的顺序存储结构存在的缺陷：①在插入或删除元素时，为保证操作后的线性表仍然是顺序存储，需要大量移动数据元素，效率很低。②在顺序存储结构下，线性表的存储空间不便于扩充，易产生上溢现象。③线性表的顺序存储结构不便于对存储空间的动态分配。(2)链式存储结点组成：①数据域：用于存放数据元素值；②指针域：用于存放指针。指针用于指向该结点的前一个或后一个结点，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式既可用于表示线性结构，也可用于表示非线性结构。在用链式结构表示较复杂的非线性结构时，其指针域的个数要多一些。(3)线性链表①定义：线性链表是线性表的链式存储结构。②特点a.各数据结点的存储序号是不连续的，各结点在存储空间中的位置关系与逻辑关系也不一致；b.各数据元素之间的前后件关系是由各结点的指针域来指示的；c.每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前件结点，只能顺指针向链尾进行扫描。为了弥补线性单链表的缺陷，在某些应用中为线性链表每个结点设置两个指针，左指针用以指向其前件结点，右指针指向其后件结点。(4)带链的栈带链的栈可以用来收集计算机存储空间中所有空闲的存储结点。与顺序栈一样，带链栈的基本操作有以下几个：①栈的初始化：建立一个空栈的顺序存储空间；②入栈运算：在栈顶位置插入一个新元素；③退栈运算：取出栈顶元素并赋给一个指定的变量；④读栈顶元素：将栈顶元素赋给一个指定的变量。(5)带链的队列与顺序队列一样，带链队列的基本操作有以下几个：①队列的初始化：建立一个空队列的顺序存储空间；②入队运算：在循环队列的队尾加入一个新元素；③退队运算：在循环队列的排头位置退出一个元素并赋给指定的变量。.线性链表的基本运算(1)常见的线性表的运算线性链表的运算主要有以下几个：①在线性链表中包含指定元素的结点之前插入一个新元素；②在线性链表中删除包含指定元素的结点；③将两个线性链表按要求合并成一个线性链表；④将一个线性链表按要求进行分解；⑤逆转线性链表；⑥复制线性链表；⑦线性链表的排序；⑧线性链表的查找。(2)在线性链表中查找指定元素非空线性链表中寻找包含指定元素值x的前一个结点p的基本方法：从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。因此，由这种方法找到的结点p有两种可能：当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。(3)线性链表的插入①定义：线性链表的插入是指在链式储存结构下的线性表中插入一个新元素。②插入过程：在线性链表中包含元素x的结点之前插入一个新元素boa.从可利用栈取得一个结点，设该结点号为p,并置结点p的数据域为插入的元素值bob.在线性链表中寻找包含元素x的前一个结点，设该结点的存储序号为q。c.最后将结点p插入到结点q之后。为了实现这一步，只要改变以下两个结点的指针域内容：第一，使结点P指向包含元素x的结点；第二，使结点q的指针域内容改为指向结点p。③插入特点：a.不会发生上溢现象；b.可方便实现存储空间动态分配；c.不发生数据元素移动现象，只改变结点指针，提高插入效率。(4)线性链表的删除①定义：线性链表的删除是指在链式储存结构下的线性表中删除包含指定元素的结点。②删除过程：在线性链表中删除包含元素x的结点。a.在线性链表中寻找包含元素x的前一个结点，设该结点序号为q;b.将结点q后的结点p从线性链表中删除，即让结点q的指针指向包含元素x的结点p的指针指向的结点；c.将包含元素x的结点p送回可利用栈。在线性链表中删除一个元素后，不需要移动表的数据元素，只需改变被删除元素所在结点的前一个结点的指针域即可。.循环链表(1)与线性链表相比，循环链表具有的特点：①在循环链表中增加了一个表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。②循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。(2)与线性单链表相比，循环链表具有两方面优点：①在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。而线性单链表做不到这一点。②由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。循环链表的插入与删除运算要比一般单链表简单，不用考虑在空链表和在第一个结点前插入以及空链表的删除等特殊情况，从而实现了空表与非空表运算的统一。六、树与二叉树.树的基本概念(1)树是一种简单的非线性结构，在这种结构中，所有数据元素之间的关系具有明显的层次特性。在树的图形表示中，上端结点是前件，下端结点是后件。(2)在树结构中，每个结点只有一个前件(父结点)，没有前件的结点只有一个，称为树的根结点。每个结点都可以有多个后件(子结点)，没有后件的结点称为叶子结点。(3)一个结点拥有的后件个数称为i^结点的度。某结点的度为n,表示该结点有n个分支，每个分支指向一个后件，除根结点外，每个结点都有一个唯一的分支指向它。树中的结点数为树中所有结点的度之和再加1。(4)根结点在第1层，同一层上所有结点的所有子结点都在下一层，树的最大层次称为树的深度(5)在树中，叶子结点没有子树。(6)用树来表示算术表达式的原则：①表达式中的每一个运算符在树中对应一个结点，称为运算符结点；②运算符的每一个运算对象在树中为该运算符结点的子树(在树中的顺序为从左到右)；③运算对象中的单变量均为叶子结点。在树中，叶子结点没有子树。.二叉树及其基本性质(1)二叉树定义二叉树是一种很有用的非线性结构，与树结构很相似，树结构的所有术语都可以用到叉树这种数据结构上。(2)二叉树的两个特点①非空二叉树只有一个根结点；②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。(3)二叉树的基本性质①在二叉树的第k层上，最多有2k-1(k>1)个结点。②深度为m的二叉树最多有2m-1个结点。③在任意一棵二叉树中，度为0的结点(即叶子结点)总是比度为2的结点多一个。④具有n个结点的二叉树，其深度至少为［log2n］十1,其中［［log2n］表示取log2n的整数部分。(4)满二叉树与完全二叉树满二叉树与完全二叉树是两种特殊形态的二叉树。①满二叉树除最后一层外，每一层上的所有结点都有两个子结点。②完全二叉树a.除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。b.更确切地说，如果从根结点起，对二叉树的结点自上而下、自左至右用自然数进行连续编号，则深度为m且有n个结点的二叉树，当且仅当其每一个结点都与深度为m的满二叉树中编号从1到n的结点一一对应时，称之为完全二叉树。对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现；对于任何一个结点，若其右分支下的子孙结点的最大层次为P,则其左分支下的子孙结点的最大层次或为P,或为p+1oc.满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。完全二叉树具有以下两个性质：a.具有n个结点的完全二叉树的深度为［log2n］+1。b.设完全二叉树共有n个结点。如果从根结点开始，按层序(每一层从左到右)用自然数1,2,…，n给结点进行编号，则对于编号为k(k=1,2,…,n)的结点有以下结论：第一，若k=1,则该结点为根结点，它没有父结点；若k>1,则该结点的父结点编号为INT(k/2)o第二，若2k<n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(显然也没有右子结点)。第三，若2k+1<n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。根据完全二叉树的这个性质，如果按从上到下、从左到右顺序存储完全二叉树的各结点，则很容易确定每一个结点的父结点、左子结点和右子结点的位置。.二叉树的存储结构(1)在计算机中，二叉树采用链式存储结构。(2)用于存储二叉树中各元素的存储结点由两部分组成：①数据域②指针域a.左指针：用于指向该结点的左子结点的存储地址；b.右指针：指向该结点的右指结点的存储地址。.二叉树的遍历二叉树的遍历是指不重复地访问二叉树中的所有结点。在遍历二叉树结点中遵循先左后右的原则。二叉树的遍历可分为三种：(1)前序遍历(DLR)在访问根结点、遍历左子树与遍历右子树这三者中，首先访问根结点，然后遍历左子树，最后遍历右子树；并且，在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。该过程是一个递归的过程。(2)中序遍历(LDR)在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。因此，中序遍历二叉树的过程也是一个递归的过程。(3)后序遍历(LRD在访问根结点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根结点，并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。因此，后序遍历二叉树的过程也是一个递归的过程。如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树,如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。但如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。七、查找技术.顺序查找(顺序搜索)(1)基本方法从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较,若相等则表示找到(即查找成功)；若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素(即查找失败)。(2)以下两种情况只能采用顺序查找：①线性表为无序表(即表中元素的排列是无序的)，则不管是顺序存储结构还是链式存储结构，都只能用顺序查找。②即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。(3)顺序查找的缺陷：效率太低.二分法查找(对分查找)(1)适用范围只适用于顺序存储的有序表，在此所说的有序表是指线性表中元素按值非递减排列。(2)具体方法设有序线性表的长度为n,被查元素为x,则：①将x与线性表的中间项进行比较：若中间项的值等于x,则说明查到，查找结束；②若x小于中间项的值，则在线性表的前半部分(即中间项以前的部分)以相同的方法进行查找③若x大于中间项的值，则在线性表的后半部分(即中间项以后的部分)以相同的方法进行查找④这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。八、排序技术.交换类排序法(1)冒泡排序法①定义：冒泡排序法是一种最简单的交换类排序方法，通过相邻数据元素的交换逐步将线性表变成有序。②基本过程：a.从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。b.从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。c.对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。③在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者像气泡一样冒到表的前头。冒泡排序由此而得名，且冒泡排序又称下沉排序。假设线性表的长度为n,则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n-1)12。(2)快速排序法①基本思想从线性表中选取一个元素T,将线性表后面小于T的元素移到前面，前面大于T的元素移到后面，这样就以T为分割线将线性表分割成前后两个子表。再将得到的子表按照这个过程继续下去，直到所有子表为空为止。②快速排序在最坏情况下需要进行n(n-1)12次比较，但实际的排序效率要比冒泡排序高得多。.插入类排序法

(1)简单插入排序法①定义：所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。②插入过程：将第j个元素放到一个变量T中，然后从有序子表的最后一个元素(即线性表中第j-1个元素)开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T(即原线性表中的第j个元素)插入到刚移出的空位置上，有序子表的长度就变为j了。③这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。(2)希尔排序法①基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序。②子序列的分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。增量序列一般取ht=n/2k(k=1,2,…，[log2n]),其中n为待排序序列的长度。③如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为0(n1.5)o.选择类排序法(1)简单选择排序法①基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面(这是它应有的位置)；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。②简单选择排序法在最坏情况下需要比较n(n-1)/2次。(2)堆排序法①堆的定义具有n个元素的序列(h,h2,…，hn),当且仅当满足(i=1,2,…，n/2)时称之为堆。②堆排序的方法：a.将一个无序序列建成堆；b.将堆顶元素(序列中的最大项)与堆中最后一个元素交换(最大项应该在序列的最后)；c.反复做上一步，直到剩下的子序列为空为止。③在最坏情况下，堆排序需要比较的次数为③在最坏情况下，堆排序需要比较的次数为0(nlog2n)第2章程序设计基础一、程序设计方法与风格.程序设计发展阶段就程序设计方法和技术的发展而言，主要经过了结构化程序设计和面向对象的程序设计阶段。.程序设计方格程序设计风格会影响软件的质量和可维护性，良好的程序设计风格可以使结构清晰合理，程序代码便于维护，程序设计风格总体强调简明清晰，易读易懂，程序必须是可理解的，总体遵循“清晰第一，效率第二”的原则。.良好的程序设计风格应考虑的因素(1)源程序文档化①符号名的命名符号名的命名应具有一定的实际含义，以便于对程序功能的理解。②程序注释a.序言性注释位于每个程序的开头部分，给出程序的整体说明，主要描述内容可以包括:程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序设计者、复审者、复审日期、修改日期等。b.功能性注释嵌在源程序体之中，主要描述其后的语句或程序做什么。③视觉组织在程序中利用空格、空行、缩进等技巧可以使层次清晰，便于阅读。(2)数据说明的方法为使程序中的数据说明更易于理解和维护，应注意以下几点：①数据说明的次序规范化数据说明次序固定，可以使数据的属性容易查找，也有利于测试、排错和维护。②说明语句中变量安排有序化当一个说明语句说明多个变量时，变量按照字母顺序排序为好。③使用注释来说明复杂数据的结构。(3)语句的结构程序应该简单易懂，语句构造应该简单直接，不为提高效率而把语句复杂化。①在一行内只写一条语句；②程序编写应优先考虑清晰性；③除非对效率有特殊要求，程序编写要做到清晰第一，效率第二；④首先要保证程序正确，然后才要求提高速度；⑤避免使用临时变量而使程序的可读性下降；⑥避免不必要的转移；⑦尽可能使用库函数；⑧避免采用复杂的条件语句；⑨尽量减少使用“否定”条件的条件语句；⑩数据结构要有利于程序的简化；?要模块化，使模块功能尽可能单一化；?利用信息隐蔽，确保每一个模块的独立性；?从数据出发去构造程序；?不要修补不好的程序，要重新编写；(4)输入和输出输入输出的方式和格式应当尽量方便用户使用，在设计和编程时应遵循以下原则：①对所有的输入数据都要检验数据的合法性；②检查输入项的各种重要组合的合理性；③输入格式要简单，以使得输入的步骤和操作尽可能简单；④输入数据时，应允许使用自由格式；⑤应允许缺省值；⑥输入一批数据时，最好使用输入结束标志；⑦在以交互式输入/输出方式进行输入时，要在屏幕上使用提示符明确提示输入的请求，同时在数据输入过程中和输入结束时，应在屏幕上给出状态信息；⑧当程序设计语言对输入格式有严格要求时，应保持输入格式与输入语句的一致性；给所有的输出加注释，并设计输出报表格式。二、结构化程序设计1.结构化程序设计的原则结构化程序设计方法的主要原则可以概括为自顶向下，逐步求精，模块化，限制使用goto语句。(1)自顶向下先考虑总体后考虑细节，先考虑全局目标，后考虑局部目标。先从最上层总目标开始设计，逐步使问题具体化。(2)逐步求精对复杂问题，应设计一些子目标作过渡，逐步细化。(3)模块化把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块。(4)限制使用goto语句①滥用GOTOg句确实有害，应尽量避免；②完全避免使用GOT薪句也并非是个明智的方法，有些地方使用GOTCM句，会使程序流程更清楚、效率更高；③争论的焦点不应该放在是否取消GOTO®句，而应该放在用什么样的程序结构上。其中最关键的是，肯定以提高程序清晰性为目标的结构化方法。2.结构化程序的基本结构与特点(1)基本结构①顺序结构顺序结构是一种简单的程序设计，它是最基本、最常用的结构，按照程序语句行的自然顺序，一条语句一条语句地执行程序。②选择结构(分支结构)选择结构包括简单悬着多分枝选择，可根据设定条件，判断应该选择哪一个分支来执行相应的语句序列。③循环结构根据给定的条件，判断是否重复执行某一个相同的或类似的程序段，利用循环可以大大简化大量的程序行。a.当型循环结构：先判断后执行循环体；b.直到型循环结构：先执行循环体后判断。(2)结构化程序设计方法的优点①程序易于理解、使用和维护，便于控制、降低程序的复杂性，可理解性好；②提高了编程工作的效率，降低了软件开发成本。3.结构化程序设计原则和方法的应用在结构化程序设计中应把握以下要素：(1)使用程序设计语言中的顺序、选择、循环等有限的控制结构表示程序的控制逻辑；(2)选用的控制结构只准许有一个入口和一个出口；(3)程序语句组成容易识别的块，每块只有一个入口和一个出口；(4)复杂结构应该用嵌套的基本控制结构进行组合嵌套来实现；(5)语言中所没有的控制结构，应该采用前后一致的方法来模拟；(6)严格控制GOTO®句的使用。其意思是指：①用一个非结构化的程序设计语言去实现一个结构化的构造；②若不使用GOTOg句会使功能模糊；③在某种可以改善而不是损害程序可读性的情况下。三、面向对象的程序设计.关于面向对象方法(1)面向对象的本质从客观世界固有的事物出发来构造系统，提倡用人类在现实生活中常用的思维方法来认识、理解和描述客观事物，强调最终建立的系统能够映射问题域，即系统中的对象以及对象之间的关系能够如实地反映问题域中固有事物及其关系。(2)面向对象的主要优点①与人类习惯的思维方法一致面向对象的设计和技术以对象为核心，与客观实体有直接的对应关系，对象之间传递信息互相联系，以模拟现实世界中不同事物彼此之间的联系。强调模拟现实世界中的概念而不是强调算法，鼓励开发者在软件开发的绝大部分过程中都应用领域的概念去思考。②稳定性好面向对象的软件系统结构是根据问题领域的模型建立起来，而不是基于对系统应完成功能的分解，当对系统的功能需求变化时不会引起软件结构的整体变化，仅需要做一些局部性的修改。③可重用性好a.面向对象方法中使用的对象和数据是作为平等地位出现的。对象有很强的自含性，且对象固有的封装性使得对象的内部实现与外界隔离，具有较强的独立性。b.重复使用一个对象的两种方法：第一，创建该类的实例，直接使用它；第二，从它派生出一个满足当前需要的新类。④易于开发大型软件产品用面向对象范型开发软件时，可以把一个大型产品看作是一系列本质上相产独立的小产品来处理，这就不仅降低了开发的技术难度，而且也使得对开发工作的管理变得容易。⑤可维护性好软件的可维护性是长期困扰人们的一个严重问题，是软件危机的突出表现。(3)面向对象设计软件可维护性好的主要表现①用面向对象的方法开发的软件稳定性比较好功能或性能的要求发生变化时，不会引起软件整体变化，只需要对局部做修改，容易实现。②用面向对象的方法开发的软件比较容易修改对象具有理想的模块机制，独立性好，修改一个类很少会牵扯到其它类，特有的继承机制使得对开发的软件的修改和扩充比较容易实现。③用面向对象的方法开发的软件比较容易理解面向对象的技术符合人们习惯的思维方式，用这种方法所建立的软件系统的结构与问题空间的结构基本一致。因此，面向对象的软件系统比较容易理解。对面向对象软件系统进行修改和扩充，通常是通过在原有类的基础上派生出一些新类来实现。④易于测试和调试面向对象设计的软件在维护后的测试和调试工作主要是围绕新派生出来的类进行。类是独立性很强的模块，因此软件的测试和调试就很容易实现。.面向对象方法的基本概念1)对象①概念对象用来表示客观世界中的任何实体，在应用领域中，有意义的、与所要解决的问题有关系的任何事物都可以作为对象。②面对对象的程序设计方法中的对象该对象是系统中用来描述客观事物的一个实体，是构成系统的一个基本单位，由一组表示其静态特征的属性和它可执行的一组操作组成。③对象的属性和操作a.属性属性即对象包含的信息，在设计对象时确定，一般只能通过执行对象的操作来改变。b.操作描述了对象执行的功能，通过消息传递还可以为其他对象使用，操作的过程对外是封闭的，用户只能看到操作实施的结果，所有的操作过程都封装在对象中。④对象具有的特点：a.标识唯一性对象是可区分的，且这种区分是通过对象的内在本质，而不是通过描述来区分。b.分类性可以将具有相同属性和操作的对象抽象成类。c.多态性同一个操作可以是不同对象的行为。d.封装性从外面只能看到对象的外部特征，只知道数值的取值范围和可以对数据施加的操作，无法知道数据的具体结构及实现操作的算法。对象的处理能力对外不可见，从外面不能直接使用对象的处理能力，无法修改其内部状态，其内部状态只能由其自身改变。e.模块独立性好对象是面向对象的软件的基本模块，它是由数据及可以对这些数据施加的操作所组成的统一体，而且对象是以数据为中心的，操作围绕对其数据所需做的处理来设置，没有无关的操作。从模块的独立性考虑，对象内部各种元素彼此结合得很紧密，内聚性强。2)类和实例①类是具有相同属性，共同方法的对象的集合，它描述了属于该对象类型的所有对象的性质，一个对象是其对应类的一个实例。②使用“对象”这个术语时，可以指一个具体的对象，也可以泛指一般的对象。当使用“实例”这个术语时，必然是指一个具体的对象。③类是关于对象性质的描述，它同对象一样，包括一组数据属性和在数据上的一组合法操作。(3)消息①消息是一个实例与另一个实例之间传递的信息，它请求对象执行某一处理或回答某一要求的信息，它统一了数据流和控制流。②消息中只包含传递者的要求，告诉接收者应该做哪些处理，但不指示接收者应该怎样完成这些处理。接收者独立决定采用什么样的方式完成所需的处理。③一个对象能够接收不同形式，不同内容的多个消息；相同形式的消息可以送往不同的对象，不同对象对于形式相同的消息可以有不同的解释，作出不同反应。④一个消息由下述三部分组成：a.接收消息的对象的名称；b.消息标识符(也称为消息名)；c.零个或多个参数。(4)继承①定义：继承是使用已有的类定义作为基础建立新类的定义技术，已有的类可当做基类来引用，新类当做派生类来引用。②面对对象软件技术的许多功能和优点来源于将类组成一个层次结构的系统：一个类的上层可以有父类下层可以有子类，这种系统的重要性质是继承性；一个类直接继承父类的特性，子类自动地共享基类中定义的数据和方法。③继承的分类：a.单继承一个类只允许有一个父类，类等级为树状结构。b.多继承一个类允许有多个父类，可以组合多个父类的性质构成所需要的性质。功能更强，使用更方便；注意避免二义性。④继承性的优点：a.相似的对象可以共享程序代码和数据结构，从而大大减少了程序中的冗余信息，提高软件的可重用性，便于软件修改维护。b.用户在开发新的应用系统时不必完全从零开始，可以继承原有的相似系统的功能或者从类库中选取需要的类，再派生出新的类以实现所需要的功能。(5)多态性①多态性是指对象根据所接收的消息而做出动作，同样的消息被不同的对象接收时可导致完全不同的行动的一种现象。②在面向对象的软件技术中，多态性是指子类对象可以像父类对象那样使用，同样的消息既可以发送给父类对象也可以发送给子类对象。③多态性机制增加了面向对象软件系统的灵活性，进一步减少了信息冗余,显着地提高了软件的可重用性和可扩充性。第3章软件工程基础一、软件工程基本概念1.软件定义与软件特点(1)软件的定义计算机软件(Software)是计算机系统中与硬件相互依存的另一部分，是包括程序、数据及相关文档的完整集合。(2)软件的组成①机器可以执行的程序和数据；②机器不可执行的，与软件开发、运行、维护、使用等有关的文档。(3)软件的特点①软件是一种逻辑实体，而不是物理实体，具有抽象性。可记录在纸上或存储介质上，无法看到其本身形态，必须通过观察、分析、思考、判断才能了解其功能和特性。②软件的生产与硬件不同，它没有明显的制作过程。开发成功可以大量复制，所以对软件的质量控制主要集中在开发方面。③软件在运行、使用期间不存在磨损、老化问题。软件虽然在生存周期后期不会因为磨损而老化，但为适应硬件等变化，必要时要做出修改。修改可能会引入错误，导致软件失效率升高，软件退化。④软件的开发、运行对计算机系统有很大依赖性，导致软件出现移植问题。⑤软件复杂性高，成本昂贵。软件开发涉及各行业的专业知识，需要投入大量、高强度的脑力劳动，成本高，风险大。⑥软件开发涉及诸多的社会因素。许多软件的开发和运行涉及软件用户的机构设置，体制问题以及管理方式等，甚至涉及人们的观念和心理，软件知识产权及法律等问题。(4)软件的分类软件按照应用功能划分，可分为：①应用软件应用软件是为解决特定领域的应用而开发的软件。常用的应用软件：事务处理软件，工程与科学计算软件，实时处理软件等。②系统软件系统软件是计算机管理自身资源，提高计算机使用效率并服务于其他程序的软件。常用的系统软件：操作系统，编译程序，汇编程序，网络软件，数据库管理系统等③支撑软件支撑软件是介于系统软件和应用软件之间，协助用户开发软件的工具性软件，包括辅助和支持开发和维护应用软件的工具软件。常用的支撑软件：需求分析工具软件，设计工具软件，编码工具软件，测试工具软件等。.软件危机与软件工程(1)软件危机①定义软件危机泛指计算机软件的开发和维护过程中所遇到的一系列严重问题。②主要表现a.软件需求的增长得不到满足，用户对系统不满意的情况经常发生；b.软件开发成本和进度无法控制，开发成本超出预算，开发周期大大超过规定日期的情况经常发生；c.软件质量难以保证；d.软件不可维护或维护程度非常低；e.软件的成本不断提高；f.软件开发生产率的提高赶不上硬件的发展和应用需求的增长。③产生原因a.对软件需求速度大大超过了技术进步带来的软件生产率的提高；b.软件工程所面临的任务和其他工程之间的差异以及软件和其他工业产品的不同。(2)软件工程①定义IEEE给出一个综合的定义是：将系统化的、规范的、可度量的方法应用于软件的开发、运行和维护的过程，即将工程化应用于软件中。②三要素a.方法：完成软件工程项目的技术手段。b.工具：支持软件的开发、管理、文档生成。c.过程：支持软件开发的各个环节的控制、管理。③核心把软件产品当作工程产品来处理，把需求计划、可行性研究、工程审核、质量监督等工程化的概念引入到软件生产当中，以期达到工程项目的三个基本要素：进度、经费和质量的目标。同时，也注重研究不同于其他工业产品生产的一些独特特性，并针对软件的特点提出了许多有别于一般工业工程技术的一些技术方法。代表性的有结构化的方法、面向对象方法和软件开发模型及软件开发过程等。.软件过程与软件生命周期(1)软件过程①定义ISO9000定义：软件过程是把输入转化为输出的一组彼此相关的资源和活动。②内涵a.为获得软件产品，在软件工具支持下由软件工程师完成的一系列软件工程活动。通常包括四方面活动：第一，P(Plan)——软件规格说明。规定软件的功能及其运行时的限制；第二，D(Do)——软件开发或软件设计与实现。生产满足规格说明的软件;第三，C(Cheek)——软件确认。确认软件能够满足客户提出的要求；第四，A(Action)软件演进。为满足客户的变更要求，软件必须在使用的过程中演进。b.使用适当的资源，为开发软件进行的一组开发活动，在过程结束时将输入(用户要求)转化为输出(软件产品)。(2)软件生命周期①定义软件生命周期是指软件产品从提出、实现、使用维护到停止使用退役的过程。②阶段a.软件定义软件定义阶段包括可行性研究初步项目计划和需求分析阶段。主要任务：确定软件开发工作必须完成的目标，确定工程可行性b.软件开发软件开发阶段包括总体设计、详细设计、编码与测试阶段。主要任务：具体完成设计和实现定义阶段所定义的软件，总体设计和详细设计又称为系统设计，编码和测试又称为系统实现。c.软件运行维护软件运行维护阶段包括使用、维护和退役阶段。主要任务：使软件在运行中持久地满足用户的需要，及时改正软件在使用中发生的错误，修改软件以适应不同的使用环境。③各阶段的基本任务a.可行性研究与计划制定确定待开发软件系统的开发目标和总的要求，给出它的功能、性能、可靠性以及接口等方面的可能方案，制定完成开发任务的实施计划。b.需求分析对待开发软件提出的需求进行分析并给出详细定义。编写软件规格说明书及初步的用户手册，提交评审。c.软件设计系统设计人员和程序设计人员应该在反复理解软件需求的基础上，给出软件的结构、模块的划分、功能的分配以及处理流程。在系统比较复杂的情况下，设计阶段可分解成概要设计阶段和详