软件技术基础课件版

计算机软件技术基础主讲：刘海明Email：Office:三号楼210第2页关于本课程选修课、双语课（2学分）英文教材、中英文课件（PPT），中文讲述基础理论课以理论介绍为主，辅以适当的实例讲解和实用技术介绍；目的：学习软件技术的基本概念、基本原理，作为将来深入学习、研究和应用的基础。学完这门课，我就会编程、能够开发软件了吗？第3页课程内容和学时安排课程内容学时数主要学习内容1.概述3软件技术简介2.数据结构与算法151、数据的逻辑结构、存储结构和定义在存储结构上的运算；2、查找和排序算法3.操作系统原理9操作系统概念及其主要功能的实现原理4.数据库系统9关系型数据库、SQL语言应用以及数据库应用程序的开发合计36详细课时安排见另一文档第4页教材英文教材：数据结构与程序设计——C++语言描述（影印版），RobertK.Cruse等编，高等教育出版社操作系统概念（第六版影印版），AbrahamSilberschatz编，高等教育出版社数据库系统概念（第四版影印版），AbrahamSilberschatz编，高等教育出版社中文参考教材：计算机软件技术导论，庞丽萍等编，高等教育出版社（旧版书名为“计算机软件技术基础”，华中理工大学出版社）其它“计算机软件技术基础”类教材（见下页）第5页其它中文参考教材计算机软件技术基础（第二版），麦中凡等编，高等教育出版社计算机软件技术基础，陈建铎编，高等教育出版社计算机软件技术基础，徐士良编，清华大学出版社计算机软件技术及应用基础，冯萍编，清华大学出版社……第6页教学内容和教材关系三个重要章节对应三本英文教材内容范畴；教材内容节选自三本英文教材（详细内容见另一专门文档），并结合中文教材进行增补和删减，相关知识点难易程度作适当调整；实际教学内容以PPT课件内容为准。请复印节选的英文教材进行阅读和学习。第7页相关知识基础计算机基础编程语言基础（C++）专业英语基础（计算机专业词汇）第8页关于教学方式教学方式：课堂讲授、随机提问、课堂测验、课后作业上机练习课件：Powerpoint讲义；可到学校教务处网页的“教学在线”网站下载课件、作业及其它有关文档；Tips：课堂学习、消化是关键，课堂测验、课后作业是检验、反馈和保证。第9页“教学在线”的使用“华工主页”－>“教务处”－>“教学在线”（链接在教务处主页左边栏底部）进入；页面左上角登录栏中（如右图），用学号作为帐号和密码登录（首次登录后最好修改个人密码）；在同一位置出现欢迎窗口时点击“进入”按钮进入“教学在线”平台（如右下图）。在网页左上方选择“软件技术基础”课程可进入本课程教学资源网页，所有课件、作业及相关文档均放在“教学材料”目录下。第10页关于课程考核总评成绩＝平时成绩（20％）＋考试成绩（80％）平时成绩：考勤、课堂测验、课后作业课堂测验：课堂完成、即时提交，即时讲解。作业（2~3次）：纸版，课后独立完成，按时提交，批改后再安排课时讲解。注意：测验内容、答案及作业答案均不下发！考试成绩＝卷面成绩×80％考试方式：闭卷考试作业和测验题型及知识点50％为英语题型（其中至少一半要用英文作答）缺勤一半以上或缺交作业半数以上者取消考试资格！计算机软件技术基础第1章软件技术概述第12页第1章软件技术概述1.计算机系统2.软件技术概述2.1程序设计语言2.2数据结构与算法2.3操作系统2.4数据库技术2.5软件工程2.6软件开发方法第13页学习内容和学习目标了解软件技术所涵盖的主要分支及其研究内容；学习和掌握软件、程序、软件工程、软件生命周期等基本概念。第14页1.计算机系统什么是计算机？

计算机是接收、处理和提供数据的装置，它由硬件和软件两大部分组成。计算机就是我们平时常用的PC机吗？

PC机只是计算机的一种，计算机家族中还有很多其他的成员。第15页养在深闺的巨型计算机超过100万个处理器每个处理器每秒可运算10亿次，运算能力相当于击败国际象棋世界级棋手的超级电脑“深蓝”的1000倍；占地达两个篮球场之大，重达106吨。IBM的BlueGene/L巨型计算机国产银河、曙光第16页无处不在的嵌入式家族第17页第18页（1）计算机硬件及其发展什么是硬件？ 硬件是组成计算机系统的所有电子的、机械的、磁性的、光学的装置和部件。配置一台个人计算机需要购买哪些东西？CPU、内存、硬盘、主板、键鼠、显示器…冯·诺依曼：1945年，“存储程序式计算机”5大部件构成：

运算器＋控制器＋存储器＋输入设备＋输出设备CPUIO设备第19页计算机硬件的发展发展历史逻辑元件：电子管→晶体管→集成电路发展规律及特点速度慢→速度快体积大容量小→体积小容量大外设少、简单→外设繁多、复杂外设速度发展慢于CPU速度的发展摩尔定律（假设价格保持不变，处理器芯片上的晶体管数每18个月翻一番）第20页世界上第一台电子计算机ENIAC诞生于1946年18800个晶体管70000个电阻器18000个电容器5百万个焊接点重量30吨耗电174千瓦/h5000次加法/s第21页PentiumIV（2000）42,000,000个晶体管时钟频率1.5GHz运算速度为1700MIPS（MIPS代表‘百万指令集每秒’）第22页双核处理器（2005）IntelPentium双核处理器AMDAthlon64X2双核处理器第23页三核、四核、六核处理器AMD三核处理器Intel四核处理器AMD六核处理器Intel六核处理器第24页（2）计算机软件软件＝程序？开发软件＝写程序？认识的误区！程序只是软件的一个组成部分；写程序只是软件开发的过程中的一个步骤。软件是程序、数据以及有关文档资料的集合。软件是（可运行的）思想和内容的数字化思想：算法、规律、方法→程序内容：图形、图像、数据、声音、文字等→数据第25页软件的两方面含义个体含义，表示计算机系统中具体的程序、数据和有关文档，例如操作系统软件“WindowsXP”，是从个体含义上讲的；整体含义，它相对于硬件而言，是对计算机系统中所有程序、数据及相关文档的概括。第26页软件的静态和动态属性软件有两种属性：静态属性：它由程序、数据及相关文档组成，可以存储，也可供人们阅读和交流；动态属性：它是可运行的，蕴涵着一定的操作内容和步骤，由计算机执行而产生特定的结果或动态效应。第27页软件的特征从软件的属性来看，它是一种特殊的事物，具有自身的特性，可概括如下：（1）智能性（6）依附性（2）无形性（7）非损性（3）抽象性（8）复制性（4）系统性（9）演化性（5）泛域性第28页软件的分类所有的硬件都是相似的，软件则各有各的不同。但是软件的开发过程存在很多规律和共性，找到并利用这些规律来帮助和指导软件的开发，这正是各类软件技术所研究的内容。操作系统、语言编译器、数据库管理系统文字处理软件、财务软件、用户自己开发的软件等硬件系统软件应用软件用户第29页常见软件介绍1.操作系统操作系统是对硬件的首次扩充，它管理着计算机系统的软、硬件资源，其它软件都是在操作系统的基础上运行的。2.数据库管理系统信息管理是计算机的一个重要应用领域，而信息管理的核心就是数据库管理系统。3.群件系统群件拓宽了电子邮件的内涵，涵盖很多通信协调功能，如制定会议的计划、共享项目进度表等。第30页4.办公软件组件文字处理软件、电子表格处理软件、演示制作软件、个人数据库、个人信息管理软件等。5.多媒体处理软件多媒体处理软件主要包括图形、图像处理、动画制作、音频视频处理、桌面排版等。6.程序开发工具环境集成的环境中，包含了语言编辑器（有的还包括界面和外观的编辑）、调试工具、编译工具、运行工具、图标图像制作工具等。第31页7.Internet工具软件主要有Web服务器软件，Web浏览器，文件传送工具、远程访问工具、邮件软件、新闻阅读工具、信息检索、多媒体、Web页创作工具等。8.系统工具软件帮助操作系统更有效地完成系统的管理和维护。包括杀病毒软件、文件压缩、快速复制工具、磁盘维护与诊断工具、实用工具软件等。9.其它一些常见软件学习、游戏软件、电子字典、各种小工具软件第32页（3）硬件与软件的关系软硬件独立原理和互动原理独立原理：软件理论上能实现的功能本质上与硬件是独立的（不管硬件是何种形式）互动原理：软件实际能实现的功能受制于硬件，硬件发展一个台阶，软件就能前进一大步软硬件等效定律简单的硬件+复杂的软件简单的软件+复杂的硬件最终都可以完成同一个任务，不同的只是开发时间和成本！第33页硬件是计算机系统的物质基础；软件是提高计算机系统效率和方便用户使用计算机的程序扩展；它们二者相互依赖、相互促进、共同发展。好的软件能充分发挥硬件的性能，提升计算机的价值。各类软件技术的最终目的就是设计出好的软件，以便最大限度地合理利用和发挥硬件的能力，使计算机系统更好地为用户服务。“没有软件的硬件是僵尸，没有硬件的软件是幽灵”第34页2.软件技术概述软件技术发展历程（1）程序设计时代（1946年~1955年）以硬件为中心，编程处于从属地位（2）软件行业化时代（1955年~1970年）程序需求增加；软件概念的提出；软件行业诞生（3）软件工程时代（1970年至现在）软件危机；软件工程领域的出现第一代软件技术：模块化、自顶而下结构化设计第二代软件技术：软件测试方法、技术、原理、理论第三代软件技术：软件需求定义技术软件开发集成环境——第四代软件技术？第35页软件技术的研究领域

软件本质上是一种思想：利用计算机来解决某个问题的思想！软件的实现就是将这个思想数字化的过程！在这个过程中要用到各种各样的软件技术，有的是抽象的指导理论，有的是具体的实现工具。程序设计语言编译技术软件及实现技术操作系统及实用程序计算机数据库技术软件技术软件工具软件工程软件开发方法与技术程序设计方法

数据结构和算法第36页2.1程序与程序设计语言

程序:是使计算机完成某种任务的一组有序命令（指令语句）的集合。

程序设计语言发展的三个阶段：

机器语言→汇编语言→高级语言写程序就像写文章，要解决两个问题：1.明确自己要表达的是什么2.用一种语言把它表达出来程序设计语言是编写计算机程序所用的语言。第37页程序设计语言机器语言

是机器指令的集合，其代码由0、1组成的二进制串表示，不需翻译可直接为机器所接受。汇编语言

为符号化的机器语言。它用助记符和标识符代替机器指令的操作码和地址码。高级语言

是一种与具体的计算机指令系统无关、独立于计算机类型、且表达方式接近于自然语言或数学语言、容易被人们掌握和书写的语言。如C，Pascal，java等。第38页举例任务：x＋1→x机器语言

001111100000100100111111B或3E093FH汇编语言

MOVAX,XINCAXMOVX,AXC语言x=x+1 或x++ 或++x第39页高级语言的优点比机器语言或汇编语言更易于学习；程序更易于编写和调试（程序更为短小；记号本身更自然，因此更多注意力可放在程序逻辑而非语法细节上）；程序可读性更强；较好的平台无关性；上述原因使得解决问题的时间和成本减少。第40页语言翻译翻译程序是把甲种语言程序翻译为等价的乙种语言程序的程序。其中，甲种语言称为源语言。乙种语言称为目标语言。汇编程序若源语言是汇编语言，目标语言是机器语言，则该翻译程序被称为汇编程序。编译程序若源语言是高级语言，目标语言是汇编语言或机器语言，则该翻译程序被称为编译程序。解释程序是翻译程序的另一种形式，它对源程序的语句边解释边执行，不产生目标程序。第41页2.2数据结构与算法程序中往往要处理大量的数据，这些数据采用什么样的方式来组织、存放才能最大限度地方便应用处理，提高程序效率呢？数据结构研究数据的组织形式，包括数据的逻辑结构、物理结构以及在该数据结构上所施加的运算。数据结构是算法设计的基础。第42页算法算法是对解题方法的精确描述。描述的方式可以是各种各样的。如自然语言、流程图、伪代码、程序设计语言等。算法必须具有有穷性、确定性、能行性、输入和输出。一个问题可以有多种解题方法，那么就有多个对应的算法。算法的优劣由算法的时间复杂度和空间复杂度来衡量。第43页2.3操作系统裸机：没有安装任何软件的计算机。操作系统是直接运行于裸机之上的系统软件，它负责对计算机系统的各种软硬件资源进行管理和分配，为用户提供友好的计算机使用界面和平台。在裸机上配置操作系统之后就构成了操作系统虚拟机。所有其它的软件或程序都在扩充后的机器上运行。第44页应用程序用户程序操作系统虚拟机操作系统裸机第45页2.4数据库技术数据库是一种强大的数据处理技术。它把应用中所有的数据有结构地集中在一起，并提供对这些数据的存储管理、多用户共享、操作、安全保护、完整性控制等强大功能。一个国家的信息化程度是衡量该国国力的重要标准，而信息化是以数据库技术为基础的。现代的银行、金融、证券、保险等各行业的高效运营都依赖于数据库技术。第46页2.5

软件工程产生背景（上个世纪70年代）硬件的发展使得计算机的应用领域迅速扩大，导致软件的规模和复杂度急剧增长。早期手工作坊式的软件开发方式因无法适应这种变化而形成了“软件危机”。主要表现在：开发成本和进度估计不准确，生产效率低。软件产品的质量不可靠。软件常常是不可维护的。缺乏适当的文档资料。用户对软件系统不满意的现象经常发生。第47页软件工程概念什么是“软件工程”？1983年IEEE给出的定义为：“软件工程是开发、运行、维护和修复软件的系统方法”。软件工程是指导计算机软件开发和维护的工程学科，采用工程的概念、原理、技术和方法来开发与维护软件。软件工程是一门交叉学科，用管理学的原理、方法来进行软件生产管理；用工程学的观点来进行费用估算、制定进度和实施方案；用数学方法来建立软件可靠性模型以及分析各种算法。第48页软件工程的基本目标在给定成本、进度的前提下，开发出具有可修改性、有效性、可靠性、可理解性、可维护性、可重用性、可适用性、可移植性、可追踪性、可互操作性和满足用户需求的软件产品。第49页软件生命周期贯穿“软件工程”这一学科的基本线索是软件生命周期学说，它告诉软件开发者和维护者“什么时候做什么以及怎么做”。软件生命周期就象人的寿命一样，从出生算到死亡，从产生开发需求一直到软件报废为止。包括：软件计划、需求分析、软件开发和软件维护四个时期。第50页软件生命周期阶段软件计划（系统定义）用户想解决什么问题？（软件定义）这个问题能否解决？（可行性分析）需求分析（系统分析）目标系统应该做成什么样子？软件开发（系统实现）怎样实现目标系统？（软件设计）系统的具体实现（软件编程）实现的系统与是否符合目标？（软件测试）软件维护（系统维护）如何保持系统正常运行？如何升级或修复错误？第51页软件开发模型软件开发模型是软件开发的全部过程、活动和任务的结构框架。瀑布模型原型模型螺旋模型第52页软件开发模型1．瀑布模型（1）各阶段间具有顺序性和依赖性。即后一阶段工作必须在前一阶段工作完成后才能进行，前一阶段的输出文档是后一阶段的输入文档。（2）质量保证机制的依赖性。即每一步都必须循序渐进，及早消除故障隐患，保证本阶段的工作的质量，从而达到保证整体软件质量的目的。（3）推迟实现原则。前一阶段工作做的越细、越扎实，后一阶段工作进行的就越顺利，强调“宁慢求好”。因此，各阶段工作总是容易一拖再拖，致使整个工期推迟实现。显然瀑布模型不能满足呈爆炸状增长的社会应用需求。

第53页软件开发模型之一：瀑布模型软件计划需求分析软件设计软件编码软件测试软件维护变化的需求第54页2．原型模型也称样品模式，即开始提出一个样品雏形，通过不断改进，完善样品，使得最后得到用户所需要的产品。由于在项目开发初始阶段人们对软件的需求认识常常弄不清楚，原型模型提出分两次开发软件能较好地使用户满意:第一次只是试验开发，其目标在于探索可行性，弄清软件需求。通常把第一次得到的试验性产品称为原型。第二次则在原型基础上获得较满意的软件产品。显然，原型模型在克服瀑布模型缺点，减少由于软件需求不明确而给开发工作带来的风险，有着显著的效果。第55页软件开发模型之二：原型模型

初步需求分析

快速设计

建造原型

用户评估原型（新需求）

开发产品

开始

结束

第56页原型模型的优点：（1）开发人员和用户在原型上达成一致，共同承担因修改原型而造成的风险，用户成了名副其实的开发组成员。可以减少设计中的错误和开发中的风险，从而提高了系统的准确性、正确性以及用户的满意程度。（2）缩短了开发周期，加快了工程进度，降低了成本。原形模型的缺点：原型样品只是一个临时的系统，它没有考虑整体的质量和日后的可维护性等问题。第57页3．螺旋模型螺旋模型将瀑布模型与原型模型结合起来，并且加入风险分析，构成具有特色的模式，可以弥补前两种模型的不足。螺旋模型将工程分为4个主要活动：制定计划，风险分析，实现工程和用户评价。4个活动螺旋式地重复执行，直到最终得到用户认可的产品。螺旋模型的缺点：（1）它很难让用户确信这种研发方法是可控制的；（2）它要求有风险评价的专门技术，如果主要风险不能发现，则问题一定会发生；第58页生命周期计划需求计划风险分析原型1原型2原型3可操作的原型建模模拟评价操作概念软件需求需求确认开发计划组装测试计划风险分析风险分析风险分析软件产品设计设计验证与确认详细设计编码单元测试组装测试验收测试实现成本顺时针为进展方向计划：明确目标、约束条件选择方案风险分析构造原型工程实现用户评价；阶段评审验收测试计划需求精化计划需求评价评审决策实现计划软件开发模型之三：螺旋模型第59页2.6软件开发方法结构化方法自顶向下，逐步细化模块化结构化程序设计面向对象方法第60页自顶向下，逐步细化由于人类思维能力的限制，如果一次面临的因素太多，就无法作出精确的思维。例如：举办一个生日party布置场地准备食物准备节目邀请客人自顶向下，逐步细化就是将复杂的问题分解成若干个子问题，直到所有子问题都简单到能用程序设计语言来表达的方法。第61页示例：选择排序算法设计（1）顶层设计第62页（2）第2层设计第63页（3）第3层设计第64页（4）选择排序法的N-S框图第65页模块化程序设计把一个程序按功能分解成若干彼此具有一定独立性同时也具有一定联系的组成部分，这些组成部分称为模块。每个程序由一个或多个模块组成。方法：按功能划分；自顶而下逐步求精，直到获得单一的功能模块。优点：降低复杂度：若P=P1+P2，则C(P)>C(P1)+C(P2)软件结构清晰容易测试和调试提高软件的可修改性方便开发任务的分配第66页模块化设计示例报表加工任务的模块化设计第67页结构化程序设计强调使用程序的三种基本控制结构（顺序、选择和循环

。第68页结构化程序设计的特点只有一个入口和一个出口；不存在从结构内跳到结构外，也不存在从结构外跳到结构内的情况；程序进入结构后，肯定能到达出口，不会出现“死循环”。有限制地使用Goto语句进行跳转。第69页面向对象技术OO（面向对象）技术：将客观世界的实体看作不同类型的对象，对象的属性和方法对应实体的自然属性和行为特性。面向对象技术主要包括面向对象的分析（OOA）、面向对象的设计（OOD）、面向对象的实现（OOI）三个方面。基本概念：对象、类、方法、消息、继承、封装等面向对象技术特点：可重用性、可维护性、表示方法的一致性面向对象的编程语言：C++，Java等第70页应用软件的开发作为应用软件开发者，一些必须的准备是：熟悉应用开发平台上的常用工具至少掌握一种程序设计语言注重分析、注意写文档软件开发应注意：采用科学的、现代化的组织管理模式；选用先进的设计思想与方法。软件开发经验之谈通过理论学习去理解和掌握基本概念和方法通过实践去加深认识，积累开发经验和提高软件开发能力。第2章数据结构与算法一、数据结构讨论与研究的范畴二、算法第1节概述第72页学习内容与要求学习和了解数据结构所研究的内容；掌握数据的逻辑结构和存储结构的定义和基本分类；学习和掌握与数据结构有关的名词术语（如数据、数据元素、数据对象、数据类型、抽象数据类型ADT等等）；学习和了解算法的概念、特点以及算法的评价标准。第73页DataStructures+Algorithms=Programs——NicklausWirth程序:数据结构:

算法:利用计算机语言编制的一组具有确定功能的指令集合。处理问题的策略。问题或对象的数学模型(如何描述数据的外部表现形式和内部存储结构)。第74页一、数据结构研究和讨论的范畴第75页“学生”数据123456789第76页“课程”数据第77页“选课”数据学号课程编号成绩时间981640240028206.6.10981640240169006.6.15981650240028506.6.10981650240167606.6.15981650240248906.6.139816598164024016024002024024学生课程第78页学生(学号,姓名,性别,籍贯)课程(课程号,课程名,学分)选课(学号,课程号,成绩)“选课”数据包含如下信息:

学号课程编号成绩时间

学生选课系统中“学生”和“课程”这两个实体构成了网状（图状）关系（即“选课”关系）。第79页UNIX文件系统的系统结构图/(root)binlibuseretcmathdsswlintaoxieStack.cppQueue.cppTree.cpp第80页数据结构的研究内容

综合上述例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。简单地说，作为一门学科，数据结构主要研究非数值计算的程序设计问题当中计算机的操作对象（数据）以及它们之间的关系（逻辑结构和物理结构）和操作（算法实现）。第81页若干名词术语数据（data）数据元素（dataelement）数据项（dataitem）数据对象（dataobject）数据结构（datastructure）数据类型（datatype）抽象数据类型（ADT）第82页数据（data）数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中、被计算机程序识别和处理的符号的集合。数值性数据非数值性数据第83页数据元素(dataelement)和

数据项（dataitem）数据元素是数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理。数据元素又可称为元素、结点、记录。有时一个数据元素可以由若干数据项（dataitem）组成。数据项是具有独立含义的最小标识单位。第84页数据对象(dataobject)具有相同性质的数据成员（数据元素）的集合，数据的子集。例：整数数据对象N={0,1,2,…}学生数据对象有穷集和无穷集第85页什么是数据结构定义:

由某一数据对象及该对象中所有数据成员之间的关系组成。

与“数据对象”这一概念的区别？作为术语名词和作为学科名词的区别？第86页数据元素间的逻辑关系，即数据的逻辑结构。数据元素及其关系在计算机存储内的表示，即数据的存储表示（物理结构、物理表示）。数据的运算，即对数据元素施加的操作。作为学科，数据结构研究数据的组织形式，包括以下内容：第87页数据的逻辑结构数据的逻辑结构从数据的逻辑关系上描述数据，与数据的存储无关，与数据元素本身的具体形式、内容无关。数据的逻辑结构可以看作是从具体问题抽象出来的数据模型。第88页数据的逻辑结构可归结为以下四类：线性结构：一对一关系树形结构：一对多关系图状结构：多对多关系集合结构：简单隶属关系第89页数据逻辑结构的描述方式Data_Structure={D,R}

其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。一般表现形式如下：D={d1,d2,…,dn}R={r1,r2,…,rm}关键字：数据元素中可用于标识该数据元素的某个分量（数据项）。通常用关键字区别不同的数据元素。第90页D＝{01,02,03,04,05,06,07,08,09,10}R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06,>,<05,07>,<08,09>,<08,10>}R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}第91页R1={<08,05>,<05,02>,<02,01>,<01,03>,<03,09>,<09,04>,<04,06>,<06,10>,<10,07>}用连线表示数据元素之间的联系第92页R2={<01,02>,<01,05>,<01,08>,<02,03>,<02,04>,<05,06>,<05,07>,<08,09>,<08,10>}第93页R3={<01,04>,<04,01>,<01,05>,<05,01>,<01,08>,<08,01>,<04,07>,<07,04>,<05,06>,<06,05>,<06,04>,<04,06>,<05,08>,<08,05>,<06,09>,<09,06>,<09,02>,<02,09>,<08,10>,<10,08>,<04,03>,<03,04>}第94页由上述数据结构的描述可得出结论：相同数据元素的集合（即同一数据对象），因其关系的不同而构成不同的数据逻辑结构。对一实际应用问题，合理选择数据逻辑结构才能够设计出有效的算法。例：根据下列选课情况安排考试日程，使得在不冲突的情况下用尽可能短的时间安排所有考试。学生姓名选修课1选修课2选修课3甲ABC乙DE丙DCF丁EFA戊BF第95页数据的存储结构数据的存储结构是数据在计算机内部的存储方式，依赖于计算机语言。存储结构分类

顺序存储结构链式存储结构索引结构散列结构第96页顺序存储（矢量存储）结构Contiguousimplementation（vector

implementation）

所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存中其存储地址仍然相邻。

链式存储结构Linkedimplementation

所有元素可以存放在不连续的存储单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后其存储地址不一定是相邻的。第97页顺序和链式存储结构示意图第98页数据类型数据类型

定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称。

C语言中的数据类型charintfloatdoublevoid

字符型整型浮点型双精度型无值

基本数据类型（原子类型）：可以看作是计算机中程序设计语言已实现的数据结构。构造型数据类型：由相同或不同成分的类型构成，如数组、结构体、类等。第99页抽象数据类型

(ADTs:AbstractDataTypes)由用户定义，用以表示实际应用问题的数据模型。由基本的数据类型组成,并包括一组相关的服务（或称操作）。第100页抽象数据类型的描述方法抽象数据类型从形式上可用（D，R，O）三元组表示。其中：D是数据对象，R是D上的关系集，O是对D的基本操作集。一般采用如下格式描述ADT

抽象数据类型名

{

数据对象：〈数据对象的定义〉

数据关系：〈数据关系的定义〉

基本操作：〈基本操作的定义〉}

ADT

抽象数据类型名第101页ADT基本操作的定义格式基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

参数：赋值参数只为操作提供输入值;引用参数以&打头，除可提供输入值外，还将返回操作结果。初始条件：描述操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。若初始条件为空,则省略之。操作结果：说明操作正常完成之后，数据结构的变化状况和应返回的结果。第102页例如，抽象数据类型“复数”的定义：数据对象：D＝{<e1,e2>｜e1,e2∈RealSet}数据关系：R1＝{<e1,e2>|e1是复数的实数部分，

e2是复数的虚数部分}ADTComplex{第103页基本操作：plex(&Z,v1,v2)操作结果：构造一个复数Z，其实部和虚部分别被赋以参数v1和v2的值。plex(&Z)操作结果：复数Z被销毁。

GetReal(Z,&realPart)初始条件：复数已存在。操作结果：用realPart返回复数Z的实部值。第104页

GetImag(Z,&ImagPart)初始条件：复数已存在。操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2,&sum)初始条件：z1,z2是复数。操作结果：用sum返回两个复数z1,z2的和值。}ADTComplex第105页抽象数据类型的实现

抽象数据类型描述的是抽象的数据模型及其操作，需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。引入抽象数据类型的意义

通常研究一个数据结构的实现问题可以从研究其抽象数据类型着手，例如通过对抽象数据类型的加工来用C++类实现该数据结构：类的数据成员对应于ADT所描述的数据结构，类的方法对应于ADT所描述的操作。第106页二、算法第107页关于算法

算法是为了解决某类问题而设计的一个有限长的操作序列。算法特性有穷性、确定性、可行性、有输入、有输出第108页有穷性：对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行；并且在任何条件下，算法都只有一条执行路径。可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。第109页有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上输入已被嵌入算法之中。有输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。第110页用自然语言描述算法：用我们日常生活中的自然语言也可以描述算法。算法描述方法用流程图描述算法：一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。用其它方式描述算法：我们还可以用数学语言或约定的符号语言（如伪代码）来描述算法。用C++描述算法：在本课程中，我们将采用C++来描述算法，所有算法的描述都用C++中的函数形式。第111页算法和程序的关系

算法≠程序！

算法着重体现思路和方法，程序着重体现计算机的实现。程序不一定满足有穷性（例如死循环情形）；另外，程序中的指令必须是机器可执行的，算法中的指令无此限制。算法用计算机语言来书写时才是程序。第112页算法设计原则正确性可读性健壮性高效率低需求算法评价标准

时间特性：时间复杂度T(n)

空间特性：空间复杂度S(n)算法设计原则与评价标准第113页一个特定算法的运行时间由其“运行工作量”决定。其运行工作量的大小，通常只依赖于问题的规模（通常由问题涉及的数据量决定，用整数量n表示），或者说，它是问题规模的函数。算法的运行时间

假如，随着问题规模n

的增长，算法执行时间的增长率和函数f(n)的增长率相同，则可记作：T(n)=O(f(n))称T(n)为算法的时间复杂度。第114页程序执行时间的计算事后统计法事前分析估算法算法策略问题规模程序设计语言机器代码运行效率机器执行指令的速度第115页如何估算算法的时间复杂度？算法=控制结构+基本操作(基本数据类型的操作)算法的执行时间=∑基本操作的执行次数×基本操作的执行时间算法的执行时间

与

基本操作执行次数之和

成正比。从算法中选取一种对于所研究的问题来说是基本操作的操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。第116页例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){

//以二维数组存储矩阵元素，c为a和b的乘积for(i=1;i<=n;++i)

for(j=1;j<=n;++j){c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作时间复杂度:

O(n3)第117页例二选择排序voidselect_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列

}//select_sort基本操作:数据比较操作时间复杂度:O(n2)for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}j=i;//选择第i个最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j]

)j=k;第118页例三冒泡排序voidbubble_sort(int&a[],intn){

//将a中整数序列重新排列成自小至大有序的整数序列for

(i=n-1,change=TRUE;i>1&&

change;--i)}//冒泡排序基本操作:

赋值操作时间复杂度:

O(n2){

change=FALSE;

//change为元素进行交换标志

for(j=0;j<i;++j)

if(a[j]>a[j+1])

{

a[j]←→a[j+1];

change=TRUE;}}//一趟冒泡排序第119页程序指令本身所占空间常量和变量所占空间数据操作所需的工作单元实现数据计算时所需的辅助空间算法的存储空间需求算法的空间复杂度定义为:

表示随着问题规模n的增大，算法运行所需存储空间的增长率与函数g(n)的增长率相同。S(n)=O(g(n))第2章数据结构与算法Section2

LinearList（线性表）一、基本概念二、顺序表三、链表学习内容和目标1、学习和掌握线性表的定义（逻辑结构）及其特点；2、学习和理解线性表的顺序存储结构（顺序表）的C++类定义和类模板定义方法；掌握顺序表的基本操作的实现原理和方法；3、学习和理解线性表的链式存储结构（链表）的C++类定义和类模板定义方法；掌握单链表、双向链表和循环链表的结构特点以及基本操作的实现原理和方法。Subsection1

BasicConceptDefinitionofList

Alistofelements(数据元素)oftypeTisafinitesequence(有限序列)

ofelementsofTtogetherwiththefollowingoperations(操作):1.Construct(构造)

thelist,leavingitempty.2.Determine(确定)

whetherthelistisemptyornot.3.Determinewhetherthelistisfullornot.4.Findthesizeofthelist.5.Clearthelisttomakeitempty.6.Insert(插入)

anentry(数据元素)ataspecifiedpositionofthelist.7.Remove(删除)anentryfromaspecifiedpositioninthelist.8.Retrieve(检索)theentryfromaspecifiedpositioninthelist.9.Replace(替换)theentryataspecifiedpositioninthelist.10.Traverse(遍历)thelist,performing(执行)agivenoperationoneachentry.

遍历:逐项访问数据元素(每个元素只访问一次)线性表(LinearList)线性表的定义和特点

定义

n（0）个数据元素的有限序列，记作

（a1,a2,…,an）或（a0,a1,…,an-1）

ai

是表中数据元素，n是表长度。数据类型的任意性和一致性直接前驱元素和直接后继元素

线性表的特点除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。相邻数据元素之间存在序偶关系。“序偶”包含两层含义：顺序、配对a1a2a3a4a5a6抽象数据类型线性表的定义如下：ADTList{

数据对象：D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}{称

n

为线性表的表长;

称

n=0

时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{设线性表为(a1，a2,...，ai，...，an),

称i为ai在线性表中的位序。}

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList初始化操作InitList(&L)操作结果：构造一个空线性表L结构销毁操作DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。引用型操作:Empty(L) Length(L)Prior(L,x,&pre)Next(L,x,&next)Get(L,i) Locate(L,x)加工型操作：Clear(&L)PutElem(&L,i,x)Insert(&L,i,x)Delete(&L,i,&x)

线性表的基本操作Empty(L)（判断线性表是否为空）初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。Length(L)（求线性表的长度）初始条件：线性表L已存在。操作结果：返回L中元素个数。引用型操作Prior(L,x,&pre)（求数据元素的前驱）初始条件：线性表L已存在。操作结果：若x是L的元素，但不是第一个，则用pre返回它的前驱，否则操作失败，pre无定义。Next(L,x,&next)（求数据元素的后继）初始条件：线性表L已存在。操作结果：若x是L的元素，但不是最后一个，则用next返回它的后继，否则操作失败，next无定义。Get(L,i)（获取线性表中某个数据元素）初始条件：线性表L已存在，且1≤i≤Length(L)。操作结果：返回L中第i个元素的值。Locate(L,x)（确定元素在表中位置）初始条件：线性表L已存在，x为给定值操作结果：返回L中第1个与x相等的元素的位序。若这样的元素不存在，则返回值为0。Clear(&L)（线性表置空）初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(&L,i,x)（改变数据元素的值）初始条件：线性表L已存在，且1≤i≤Length(L)。操作结果：L中第i个元素赋值为x的值。加工型操作Insert(&L,i,x)（插入数据元素）初始条件：线性表L已存在，且1≤i≤Length(L)+1操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。Delete(&L,i)（删除数据元素）初始条件：线性表L已存在且非空，1≤i≤Length(L)。操作结果：删除L的第i个元素，L的长度减1。线性表的存储结构线性表常用的两种存储结构顺序存储结构（顺序表）链式存储结构（链表）注意：任意一种存储结构，都不仅要存储数据本身，还需要存储（保留）数据与数据之间的逻辑关系，并且在数据操作过程中不破坏这种逻辑关系。逻辑上定义的线性表，在计算机中实现时需要考虑其物理存储结构以及相关操作的实现。Subsection2SequentialList（顺序表）——线性表的顺序存储结构顺序表(SequentialList)顺序表的定义和特点线性表的顺序存储结构：将线性表中的元素相继存放在一个连续的存储空间中。特点：元素存储位置体现逻辑关系如何用程序设计语言实现顺序表？一维数组一维数组实现顺序表数组下标：0123456789data253457164809

需要预先定义数组大小（即线性表的最大长度）；需要跟踪线性表的长度，以便掌握线性表的相关信息以及进行相应的算法操作。或通过记录尾元素的下标来跟踪线性表长度直接记录线性表的长度顺序表(SeqList)的定义（C语言实现）#define

MaxSize

表中最大元素个数Type

SeqList[MaxSize];

//定义数组intlast;

//表中最后一个元素的下标#define为宏定义;如:＃defineMaxSize10数据类型Type可以是原子类型，也可以是已实现的结构类型，但在定义顺序表时必须已经显式定义该数据类型。数组下标有效取值范围?线性表中元素有效下标范围？顺序表长度与Last的关系？空表和满表的判断？0～MaxSize－1表长度=last+10～last顺序表(SeqList)类的定义(C++类实现)classSeqList{protected://SeqList类的数据成员Type*data; //定义数组 intMaxSize; //顺序表允许长度

intlast; //顺序表最后一个元素下标public://SeqList类的函数成员 SeqList(intMaxSize);//构造函数 ~SeqList(){delete[]data;}//析构函数 intLength()const{returnlast+1;}intLocate(

Typex)const; //定位intInsert(inti,Type

x);//插入intDelete(inti); //删除

intNext(Typex,Type

&next);//后继intPrior(Typex,Type

&pre);//前驱intEmpty(){returnlast==-1;

}//判空intFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

（续上页）顺序表(SeqList)类的定义(C++类模板实现)template<classType>

classSeqList{protected://SeqList类的数据成员

Type*data;//顺序表存储数组(指针方式定义) intMaxSize; //最大允许长度(元素个数) intlast; //最后一个元素的下标public://SeqList类的函数成员 SeqList(intListSize);//构造函数 ~SeqList(){delete[]data;}//析构函数 intLength()const{returnlast+1;}intLocate(

Typex)const; //定位intInsert(inti,Type

x);//插入intDelete(inti); //删除

intNext(Typex,Type

&next);//后继intPrior(Typex,Type

&pre);//前驱intEmpty(){returnlast==-1;

}//判空intFull(){returnlast==MaxSize-1;

}TypeGet(inti){//提取

returni<0||i>last？NULL:data[i];}}

（续上页）类模板和模板类类模板是对结构相同但数据类型不同的类的抽象描述；利用类模板创建的实例被称为模板类，是具体的类。利用已定义的类模板可以创建实例，如：SeqList<int>A;上述语句将创建一个线性表实例A（模板类），它具有类模板SeqList所有的特性，同时其数据成员“data数组”的数据类型为整型。使用类模板可以减少重复定义，提高重用性。顺序表部分公共操作的实现

——SeqList类模板的若干函数成员的实现构造函数：线性表的初始化查找函数：根据元素值或序号查找元素插入函数：在指定位置插入一个新元素删除函数：删除指定数值（或位置）的元素注意：在数据操作过程中不能破坏线性表的逻辑关系。

template<classType>

SeqList<Type>::SeqList(intListSize){

//创建一个最大长度为ListSize的空线性表if(ListSize>0){

MaxSize=ListSize;last=-1;

//申请分配内存空间

data=newType[MaxSize];

//空间申请失败处理if(data==NULL){

MaxSize=0;}

}}构造函数（初始化）查找过程示例（查找值为16的元素）253457164809

012345data查找

16i253457164809

i253457164809

i253457164809

i查找成功，返回3查找函数（定位函数）的实现2534571648

01234data查找50i2534571648

i2534571648

i2534571648

i2534571648

i查找失败，返回－1查找过程示例（查找值为50的元素）template<classType> int

SeqList<Type>::Locate(Type

&x)const{//查找函数：在顺序表中从前向后查找元素值//等于给定值x的数据元素,返回所在单元下标

inti=0;

while(i<=last

&&data[i]!=x)i++;

if(i>last)return

-1; //返回-1表示查找失败

elsereturni; }查找函数（定位函数）注意：只需搜索有效元素区域，而不是整个数组。表项（数据元素）的插入操作253457164809630123456data50插入

x253457501648096301234567data50i＝3在进行数据插入操作时，需要注意：插入位置i的有效取值范围：此处为0～last+1线性表为满表(last=Maxsize-1)时，不允许插入操作lastLast——在表中第i个元素前插入一个新元素x

template<classType>int

SeqList<Type>::Insert(inti,Typex){//判断删除位置i是否合理以及表是否已满if(i<0

||

i>last+1

||

last==MaxSize-1)

return0;//插入操作不成功

else{last++;

for(intj=last;j>i;j--)data[j]=data[j-1]; //元素后移

data[i]=x;return1;//操作成功

}}插入函数表项的删除操作253457501648096301234567data16删除位置i2534575048096363

01234567dataLastLast在进行删除操作时，需要注意：删除位置i的有效取值范围：0～Last线性表为空（Last＝－1）时，不允许删除操作——删除表中的第i个元素

template<classType>int

SeqList<Type>::Delete(inti){

//判断插入位置i是否合理,表是否为空表

if(i<0||i>last||last<0)return0;

//数据元素前移for(intj=i+1;j<=last;j++)data[j-1]=data[j];//元素前移(覆盖)last--;

return1; //成功删除

}删除函数顺序表的特点顺序表是随机存取结构，数据元素寻址时间确定；元素最大个数需预先设定，若估计不当会造成空间浪费或空间溢出；插入或删除操作需要耗费较多时间移动数据元素，其时间复杂度为O(n)

，n为线性表长度。顺序表的应用：集合的“并”运算已知两集合A、B，求两集合的并集，结果存放于Avoid

Union(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length

();

intm=B.Length

();

for(inti=0;i<m;i++){ intx=B.Get(i);//在B中取一元素 intk=A.Locate(x);//在A中搜索它 if(k==

-1)//若未找到,插入元素

{A.Insert(n,x);n++;}}}已知两集合A、B，求两集合的交集，结果存放于A

voidIntersection(SeqList<int>

&A,SeqList<int>

&B){

intn=A.Length();

intm=B.Length();inti=0;

while(i<n){intx=A.Get(i);//在A中取一元素

intk=B.Locate(x);//在B中搜索它

if(k==-1){A.Delete(i);n--;}elsei++;//未找到，在A中删除它

}}顺序表的应用：集合的“交”运算Subsection3LinkedList（链表）——线性表的链式存储结构链表特点：用一组地址任意的存储单元存放线性表中的数据元素，用指针反映数据元素之间的线性关系，以“结点的序列”来表示线性表。即：元素(数据元素值的映象)

+指针(指示后继元素存储位置)=