软件技术基础教学绪论

第一章第一章 软件技术基础软件技术基础软件设计能力是大学生的一种基本能力软件设计能力是大学生的一种基本能力 科研需要：现有工具软件并不总能满足科研需要：现有工具软件并不总能满足要求要求 工作需要：现代工业离不开自动化设备，工作需要：现代工业离不开自动化设备，自动化设备离不开计算机的控制，计算自动化设备离不开计算机的控制，计算机的灵魂是软件。机的灵魂是软件。 对于一个非计算机专业的人来说，对于一个非计算机专业的人来说，“如如何学、学什么何学、学什么”是学习计算机技术的重是学习计算机技术的重要问题。要问题。为什么学习 这门课？如何学、学什么n如何学如何学 兴趣兴趣 +实践实践n学什么学什么 将本专业和计算机的应用联系起来。在学习将本专业和计算机的应用联系起来。在学习中应该掌握尺度，并非每一门课都做到中应该掌握尺度，并非每一门课都做到“完完全透彻全透彻”。但也不能什么都一知半解，要有。但也不能什么都一知半解，要有一个一个“拳头拳头”方向。方向。 n必要的准备必要的准备 熟悉应用开发平台上的常用工具熟悉应用开发平台上的常用工具 至少掌握一种程序设计语言至少掌握一种程序设计语言 注重分析：分析问题、解决问题注重分析：分析问题、解决问题课程内容课程内容1.算法2.数据结构3.查找与排序技术4.操作系统5.数据库技术6.计算机网络7.软件工程课程特点 重点分散 难度集中 广而不深 杂而不乱学习方法 重视基础原理 理解思维方式 实践、实践再实践 善于自学，善于利用电子资源软件改变了我们的生活n工作n生活n娱乐第一章第一章 计算机软件技术基础计算机软件技术基础第一章第一章 计算机软件技术基础计算机软件技术基础软件无所不在软件无所不在第一章第一章 计算机软件技术基础计算机软件技术基础第一章第一章 计算机软件技术基础计算机软件技术基础软件无所不在第一章第一章 计算机软件技术基础计算机软件技术基础软件无所不在第一章第一章 计算机软件技术基础计算机软件技术基础软件无所不在第一章第一章 计算机软件技术基础计算机软件技术基础软件无所不在软件无处不在n电力调度系统n火车调度系统n民航调度系统n天气预报系统n地震预警系统n核试验模拟系统第一章第一章 计算机软件技术基础计算机软件技术基础看不见的软件-嵌入式软件n战斗机飞控系统n坦克火控系统n导弹弹上控制系统n工业控制系统n核反应堆控制系统第一章第一章 计算机软件技术基础计算机软件技术基础什么是软件n软件软件（Software）是一系列按照特定顺是一系列按照特定顺序组织的计算机的数据和指令的集合。序组织的计算机的数据和指令的集合。n软件并不只是包括可以在计算机上运行软件并不只是包括可以在计算机上运行的程序，与这些电脑程序相关的文档，的程序，与这些电脑程序相关的文档，一般也被认为是软件的一部分。简单的一般也被认为是软件的一部分。简单的说软件就是程序加文档的集合体。说软件就是程序加文档的集合体。第一章第一章 计算机软件技术基础计算机软件技术基础什么是软件n软件软件（Software）是程序、数据及相关是程序、数据及相关文档的集合文档的集合 程序程序：指示计算机完成指定任务的命令序列 数据数据：程序操作的对象，也是操作的结果 文档文档：软件开发、维护与使用的相关图文材料,是对程序与数据的描述。第一章第一章 计算机软件技术基础计算机软件技术基础软件和硬件的关系n硬件是基础硬件是基础n软件是灵魂软件是灵魂第一章第一章 计算机软件技术基础计算机软件技术基础软件的分类第一章第一章 计算机软件技术基础计算机软件技术基础操作系统数据库技术开发工具计算机软件系统软件中间件用户软件办公软件专业软件娱乐软件的分类n中间件 在操作系统、网络和数据库之上，应用软件的在操作系统、网络和数据库之上，应用软件的下层，总的作用是为处于自己上层的应用软件下层，总的作用是为处于自己上层的应用软件提供运行与开发的环境，帮助用户灵活、高效提供运行与开发的环境，帮助用户灵活、高效地开发和集成复杂的应用软件。地开发和集成复杂的应用软件。nIDC表述：中间件是一种独立的系统软件或服表述：中间件是一种独立的系统软件或服务程序，分布式应用软件借助这种软件在不同务程序，分布式应用软件借助这种软件在不同的技术之间共享资源，中间件位于客户机服务的技术之间共享资源，中间件位于客户机服务器的操作系统之上，管理计算资源和网络通信器的操作系统之上，管理计算资源和网络通信。软件学科n软件理论软件理论 算法理论算法理论 数据理论数据理论 n软件系统软件系统 操作系统操作系统 数据库数据库 开发工具（编译原理）开发工具（编译原理）n软件开发软件开发 软件工程软件工程软件n软件是程序+说明信息 （从内容上说）n软件是具有使用性能的程序 （从性能上说）n软件是商品 （从本质上说）。与其他商品比较，研制开发是主要的生产方式。（软件工程）n软件只有过时而无“损耗”的商品。注重软件的柔性或有机性。第一章第一章 计算机软件技术基础计算机软件技术基础软件开发项目结构组成项 目 总 监质 量 控 制 经 理航 空 公 司 专 家系 统 总 工 程 师项 目 总 体 组机 务 业 务 专 家系 统 工 程 专 家系 统 需 求 组数 据 库 分 析 人 员软 件 分 析 人 员程 序 员文 档 管 理 人 员系 统 开 发 组测 试 经 理测 试 人 员用 户 业 务 代 表培 训 经 理培 训 人 员测 试 培 训 组项 目 实 施 规 划第一章第一章 计算机软件技术基础计算机软件技术基础软件开发文档l 系统建设可行性研究报告l 系统现状调研报告l 项目开发计划l 系统及软件需求说明书；l 数据要求说明书l 概要设计说明书l 详细设计说明书l 数据库设计说明书l 用户操作手册l 测试计划；l 测试分析报告；l 模块开发卷宗；l 开发进度月报l 项目开发总结报告软件开发和程序设计(编程)n软件开发软件开发: 根据用户要求建造出软件系统或者根据用户要求建造出软件系统或者系统中软件部分的一个产品开发的过程。软件系统中软件部分的一个产品开发的过程。软件开发是一项包括需求获取、开发规划、需求分开发是一项包括需求获取、开发规划、需求分析和设计、编程实现、软件测试、版本控制的析和设计、编程实现、软件测试、版本控制的系统工程。系统工程。n程序设计程序设计，是指编写和维护源代码的过程。是，是指编写和维护源代码的过程。是软件开发过程的一小部分，有时也用来指狭义软件开发过程的一小部分，有时也用来指狭义的软件开发。的软件开发。n软件一般是通过某种或数种程序设计语言、在软件一般是通过某种或数种程序设计语言、在特定的计算机平台上实现的。通常采用软件开特定的计算机平台上实现的。通常采用软件开发工具进行开发发工具进行开发。合格软件开发人员的素养n团队精神和协作能力团队精神和协作能力n文档习惯文档习惯n规范化，标准化的代码编写习惯规范化，标准化的代码编写习惯 n需求理解能力需求理解能力 n复用性，模块化思维能力复用性，模块化思维能力n测试习惯测试习惯 n学习和总结的能力学习和总结的能力 软件设计的一些问题n这么多的程序设计语言，我究竟该选哪这么多的程序设计语言，我究竟该选哪一种？一种？n是不是懂得的计算机语言越多，就表示是不是懂得的计算机语言越多，就表示计算机水平越高？计算机水平越高？n怎样才能学好软件设计？怎样才能学好软件设计？开发语言的选择C 语言编写的语言编写的 Hello, World 程序程序void main() printf(“Hello, world !n”);Pascal 语言编写的语言编写的 Hello, World 程序程序Program main;begin Writeln(Hello, world!);end第一章第一章 计算机软件技术基础计算机软件技术基础根据具体的应用选择程序设计语言，没有必要反根据具体的应用选择程序设计语言，没有必要反复争论哪种语言好（如复争论哪种语言好（如 VC+ 与与 Delphi 之争之争,注意注意开发工具和语言本身的区别）开发工具和语言本身的区别）（1）通讯软件（实时系统、嵌入式系统）：汇编、C、Java （2）数据库管理软件：Delphi、VB（3）计算机游戏：VC+（网络游戏）、Java（手机游戏）（4）Web 设计：ASP、JSP、PHP + MySQL、Python （5）特定平台：.NET C#（6）科学仿真：Matlab（7）数值计算：Fortran（8）特征领域：人工智能（Lisp）第一章第一章 计算机软件技术基础计算机软件技术基础熟悉基本的程序设计原理和相关知识（如数据结熟悉基本的程序设计原理和相关知识（如数据结构），精通最常用构），精通最常用 1 2 门语言（如门语言（如C+，Java等）等）程序设计语言是相通的，程序设计语言是相通的，高手使用任何语言都高手使用任何语言都能够设计出高质量的程序。关键不在于语言本能够设计出高质量的程序。关键不在于语言本身，而在于程序设计理念与方法，以及大量的身，而在于程序设计理念与方法，以及大量的项目经验。项目经验。是否要掌握多种语言怎样提高软件设计水平第一章第一章 计算机软件技术基础计算机软件技术基础n熟悉应用开发平台上的常用工具。熟悉应用开发平台上的常用工具。n至少掌握一种程序设计语言。请注意，程序语言只是至少掌握一种程序设计语言。请注意，程序语言只是表达工具，重要的是学会分析问题和解决问题的方法表达工具，重要的是学会分析问题和解决问题的方法，不要以为学会，不要以为学会C+就会用就会用oo范型编制范型编制oo软件了。软件了。n注重分析：从某种意义上来讲，软件开发其实就是用注重分析：从某种意义上来讲，软件开发其实就是用程序语言来描述解决问题的方法和步骤。所以分析用程序语言来描述解决问题的方法和步骤。所以分析用户的需求得到需要解决的问题，分析问题得到解决的户的需求得到需要解决的问题，分析问题得到解决的方法步骤。分析是软件开发中最基本的一环。方法步骤。分析是软件开发中最基本的一环。n写文档，软件开发其实是一个问题驱动的基于文档的写文档，软件开发其实是一个问题驱动的基于文档的开发过程。应把写文档看作是应用开发的主要工作，开发过程。应把写文档看作是应用开发的主要工作，这是最容易被忽视的工作也是现代软件工程最为强调这是最容易被忽视的工作也是现代软件工程最为强调的一点。的一点。怎样提高软件设计水平第一章第一章 计算机软件技术基础计算机软件技术基础n从来没有那个高手是培训成功的。成为软件开发高从来没有那个高手是培训成功的。成为软件开发高手的路只有一条：自学！软件开发中需要大量的编手的路只有一条：自学！软件开发中需要大量的编程实践和独立思考，只有在此过程中，你才能够逐程实践和独立思考，只有在此过程中，你才能够逐步成长起来。学院里面能够培养出软件开发经理更步成长起来。学院里面能够培养出软件开发经理更是十足的谎言，软件项目经理更强调从实际中学习是十足的谎言，软件项目经理更强调从实际中学习软件。软件。第一章第一章 计算机软件技术基础计算机软件技术基础 2012-8 编程语言排名TOP20第一章第一章 计算机软件技术基础计算机软件技术基础Long term trendsGNU/LinuxWindows 能干而 Linux 干不了的事情，那就是不需要干的事情。nGNU是“GNUs Not Unix”的递归缩写 自由自在 永远免费 资源众多 没有病毒UNIXnUNIX元年 1970n两个人 Ken Thompson Dennis Ritchie nUNIX is basically a simple operating system, but you have to be a genius to understand the simplicity.- Dennis Ritchie n两大阵营 AT&T的UNIX UC Berkeley的BSD对抗霸权的GUNn“革奴计划”的精神领袖Richard Stallman GNU 工程 开始於一九八四年，旨在发展一个类似 Unix ，且为自由软件的完整操作系统： GNU 系统。n两种思潮 “大教堂”：集权、封闭、受控、保密 “集市”：分权、公开、精细的同僚复审nOpen source 距开源越近就越繁荣。任何将Unix专有化的企图，只能陷入停滞和衰败。nGNU General Public License (GPL)n到了1990年，GNU计划已经开发出的软件包括了一个功能强大的文字编辑器Emacs、C语言编译器GCC以及大部分UNIX系统的程序库和工具。n唯一依然没有完成的重要组件，就是操作系统的内核网络时代的英雄Linuxn比尔盖茨的头号对手Linus Torvaldsn1990年，芬兰赫尔辛基大学的一名学生Linus Torvalds发布了与UNIX兼容的Linux内核n“hello,this is linus torvalds and i pronounce linux as Linux”Top 5 Distributions5432全人类的Linux：UBUNTUnMark Shuttleworth 1969年，生于南非小镇。大学毕业后创办了以及信息安全公司，1999年以5.75亿美元的价格卖出。在30岁时成为南非最年轻有为的本土富翁。 2002年他自费3百万英镑乘坐俄罗斯联盟号飞船，在国际空间站中度过了8天的时光。当时他不知道他是否能回到遥远而又真实的地球。所以他决定如果能顺利回到地球，一定为人类做一件有意义的事。 结束太空之行之后，Mark Shuttleworth创立了Ubuntu社区。nUbuntu发行版光盘，免费索取发展简介1.4.10 . Warty Warthhog. (长疣的疣猪) 2004-10 2.5.04 . Hoary Hedgehog. (灰白的刺猬) 2005-043.5.10 Breezy Badger. (愉快的獾) 2005-104.6.06 Dapper Drake. (LTS)(漂亮的鸭子)2006-65.6.10 Edgy Eft. (躁动的蜥蜴)2006-106.7.04 Feisty Fawn. (活泼的小花鹿) 2007-47.7.10 . Gutsy Gibbon.(勇敢的长臂猿) 2007-108.8.04 . Hardy Heron. (LTS)(强壮的苍鹭) 2008-49.8.10. Intrepid Ibex (无畏的山羊) 2008-1010.9.04. Jaunty Jackalope (活潑的兔子 )2009-411.9.10. Karmic Koala (命運的考拉 )2009-1012.10.04 Lucid Lynx (LTS)(清醒的猞猁 )2010-4第一章第一章 计算机软件技术基础计算机软件技术基础1算法算法所谓算法是指解题方案的准确而完整的描述。所谓算法是指解题方案的准确而完整的描述。2算法的基本特征算法的基本特征（1）可行性）可行性 （2）确定性）确定性 （3）有穷性）有穷性 （4）拥有足够的情报）拥有足够的情报 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础3算法的基本要素算法的基本要素一个算法通常由两种基本要素组成：一是对数据一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是算法的控制结构。对象的运算和操作，二是算法的控制结构。（1）算法中对数据的运算和操作）算法中对数据的运算和操作基本的运算和操作有以下四类：基本的运算和操作有以下四类：算术运算：主要包括加、减、乘、除等运算。算术运算：主要包括加、减、乘、除等运算。逻辑运算：主要包括逻辑运算：主要包括“与与”、“或或”、“非非”等运算。等运算。关系运算：主要包括关系运算：主要包括“大于大于”、“小于小于”、“等于等于”、“不等于不等于”等运算：等运算：数据传输：主要包括赋值、输入、输出等操作。数据传输：主要包括赋值、输入、输出等操作。1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础（2）算法的控制结构）算法的控制结构 算法的控制结构给出了算法的基本框架，它不仅算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、算法的工具通常有传统流程图、N-S结构化流程结构化流程图、算法描述语言等。一个算法一般都可以用图、算法描述语言等。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。顺序、选择、循环三种基本控制结构组合而成。1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础4算法设计基本方法算法设计基本方法（1 1）列举法）列举法根据提出的问题，列举所有可能的情况，并用问题中给定根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。的条件检验哪些是需要的，哪些是不需要的。（2 2）归纳法）归纳法通过列举少量的特殊情况，经过分析，最后找出一般的关通过列举少量的特殊情况，经过分析，最后找出一般的关系。系。（3 3）递推）递推所谓递推，是指从已知的初始条件出发，逐次推出所要求所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。已经给定，或是通过对问题的分析与化简而确定。（4 4）递归）递归（5 5）减半递推技术）减半递推技术 1.3 1.3 算法及算法分析算法及算法分析 一、算法一、算法 第一章第一章 计算机软件技术基础计算机软件技术基础q对算法的分析主要是对算法的时间复杂度和空对算法的分析主要是对算法的时间复杂度和空间复杂度的分析。间复杂度的分析。q1时间复杂度时间复杂度一个算法的时间复杂度是该算法的时间耗费，一个算法的时间复杂度是该算法的时间耗费，即算法执行过程中所需要的基本运算次数。即算法执行过程中所需要的基本运算次数。一个算法所耗费的时间一个算法所耗费的时间=算法中每条语句的执行算法中每条语句的执行时间之和。每条语句的执行时间时间之和。每条语句的执行时间=语句的执行次语句的执行次数数语句执行一次所需时间。语句执行一次所需时间。q2空间复杂度空间复杂度一个算法的空间复杂度为该算法在执行过程中一个算法的空间复杂度为该算法在执行过程中所需要的存储空间。所需要的存储空间。算法的时间复杂度和空间复杂度合称为算法的算法的时间复杂度和空间复杂度合称为算法的复杂度。复杂度。 1.3 1.3 算法及算法分析算法及算法分析 二、算法分析二、算法分析 第一章第一章 计算机软件技术基础计算机软件技术基础1线性表的逻辑定义线性表的逻辑定义线性表（线性表（Linear List）是由）是由n（n0）个数据元素（结点）个数据元素（结点）a1，a2，an组成的有限序列。组成的有限序列。 数据元素的个数数据元素的个数n定义为表的长度（定义为表的长度（n=0时称为空表）。时称为空表）。 将非空的线性表（将非空的线性表（n0）记作：（）记作：（a1，a2，an） 数据元素数据元素ai（1 i n）只是个抽象符号，其具体含义在）只是个抽象符号，其具体含义在不同情况下可以不同。不同情况下可以不同。 如学生成绩表中，每个学生及其成绩是一个数据元素，如学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩等数据项组成。其中数据元素由学号、姓名、各科成绩等数据项组成。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础2线性表的逻辑结构特征线性表的逻辑结构特征对于非空的线性表对于非空的线性表: 有且仅有一个开始结点有且仅有一个开始结点a1，没有直接前趋，有，没有直接前趋，有且仅有一个直接后继且仅有一个直接后继a2； 有且仅有一个终结结点有且仅有一个终结结点an，没有直接后继，有，没有直接后继，有且仅有一个直接前趋且仅有一个直接前趋an-1； 其余的内部结点其余的内部结点ai（2in1）都有且仅有一）都有且仅有一个直接前趋个直接前趋ai-1和一个直接后继和一个直接后继ai1。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础 3线性表的顺序存储结构线性表的顺序存储结构 有顺序存储和链式存储两种有顺序存储和链式存储两种 顺序存储方法即把线性表的结点按逻辑次序依顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。次存放在一组地址连续的存储单元里的方法。用顺序存储方法存储的线性表简称为顺序表。用顺序存储方法存储的线性表简称为顺序表。 在顺序表中，每个结点在顺序表中，每个结点ai的存储地址是该结点的存储地址是该结点在表中的位置在表中的位置i的线性函数。只要知道基地址和的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一每个结点的大小，就可在相同时间内求出任一结点的存储地址。结点的存储地址。 1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础4常见的线性表的基本运算常见的线性表的基本运算（1）InitList(L)：构造一个空的线性表：构造一个空的线性表L，即表的，即表的初始化。初始化。（2）ListLength(L)：求线性表：求线性表L中的结点个数，中的结点个数，即求表长。即求表长。（3）GetNode(L,i) ：取线性表：取线性表L中的第中的第i个结点，个结点，这里要求这里要求1 i ListLength(L)。（4）LocateNode(L,x)：在：在L中查找值为中查找值为x 的结点，的结点，并返回该结点在并返回该结点在L中的位置。若中的位置。若L中有多个结点中有多个结点的值和的值和x 相同，则返回首次找到的结点位置；若相同，则返回首次找到的结点位置；若L中没有结点的值为中没有结点的值为x，则返回一个特殊值表示，则返回一个特殊值表示查找失败。查找失败。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础（5）InsertList(L,x,i)：在线性表：在线性表L的第的第i个位置上个位置上插入一个值为插入一个值为x 的新结点，使得原编号为的新结点，使得原编号为i，i1，n的结点变为编号为的结点变为编号为i1，i2，n1的结点。这里的结点。这里1 i n1，而，而n是原表是原表L的长的长度。插入后，表度。插入后，表L的长度加的长度加1。（6）DeleteList(L,i)：删除线性表：删除线性表L的第的第i个结点，个结点，使得原编号为使得原编号为i1，i2，n的结点变成编的结点变成编号为号为i，i1，n1的结点。这里的结点。这里1 i n，而而n是原表是原表L的长度。删除后表的长度。删除后表L的长度减的长度减1。1.4 1.4 线性表、栈和队列线性表、栈和队列 一、线性表一、线性表第一章第一章 计算机软件技术基础计算机软件技术基础 1栈的定义栈的定义 栈（栈（Stack）是限制仅在表的一端进行插入和）是限制仅在表的一端进行插入和删除运算的线性表。栈的示意图如图删除运算的线性表。栈的示意图如图1-4所示：所示：（1）通常称插入、删除的这一端为栈顶，另一端）通常称插入、删除的这一端为栈顶，另一端称为栈底。称为栈底。（2）当表中没有元素时称为空栈。）当表中没有元素时称为空栈。（3）栈为后进先出（）栈为后进先出（Last In First Out）的线性表，）的线性表，简称为简称为LIFO表。表。 栈的修改是按后进先出的原则进行。栈的修改是按后进先出的原则进行。 1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈第一章第一章 计算机软件技术基础计算机软件技术基础2栈的基本运算栈的基本运算（1）InitStack(S)：构造一个空栈：构造一个空栈S。（2）StackEmpty(S)：判栈空。若：判栈空。若S为空栈，则返回为空栈，则返回TRUE，否则返回否则返回FALSE。（3）StackFull(S)：判栈满。若：判栈满。若S为满栈，则返回为满栈，则返回TRUE，否则返回否则返回FALSE。注意：该运算只适用于栈的顺序存储。注意：该运算只适用于栈的顺序存储结构。结构。（4）Push(S,x)：进栈。若栈：进栈。若栈S不满，则将元素不满，则将元素x插入插入S的栈的栈顶。顶。（5）Pop(S)：退栈。若栈：退栈。若栈S非空，则将非空，则将S的栈顶元素删去，的栈顶元素删去，并返回该元素。并返回该元素。（6）StackTop(S)：取栈顶元素。若栈：取栈顶元素。若栈S非空，则返回栈顶非空，则返回栈顶元素，但不改变栈的状态。元素，但不改变栈的状态。1.4 1.4 线性表、栈和队列线性表、栈和队列 二、栈二、栈第一章第一章 计算机软件技术基础计算机软件技术基础1定义定义只允许在一端进行插入，而在另一端进行删只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。除的运算受限的线性表。（1）允许删除的一端称为队头（）允许删除的一端称为队头（Front）。）。（2）允许插入的一端称为队尾（）允许插入的一端称为队尾（Rear）。）。（3）当队列中没有元素时称为空队列。）当队列中没有元素时称为空队列。（4）队列亦称作先进先出（）队列亦称作先进先出（First In First Out）的线性表，简称为的线性表，简称为FIFO表。表。队列的修改是依先进先出的原则进行的。队列的修改是依先进先出的原则进行的。 1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列第一章第一章 计算机软件技术基础计算机软件技术基础2队列的基本逻辑运算队列的基本逻辑运算（1）InitQueue(Q)：置空队。构造一个空队列：置空队。构造一个空队列Q。（2）QueueEmpty(Q)：判队空。若队列：判队空。若队列Q为空，则返回为空，则返回真值，否则返回假值。真值，否则返回假值。（3）QueueFull(Q)：判队满。若队列：判队满。若队列Q为满，则返回真值，为满，则返回真值，否则返回假值。否则返回假值。注意：注意：此操作只适用于队列的顺序存储结构。此操作只适用于队列的顺序存储结构。（4）EnQueue(Q,x)：若队列：若队列Q非满，则将元素非满，则将元素x插入插入Q的的队尾。此操作简称入队。队尾。此操作简称入队。（5）DeQueue(Q)：若队列：若队列Q非空，则删去非空，则删去Q的队头元素，的队头元素，并返回该元素。此操作简称出队。并返回该元素。此操作简称出队。（6）QueueFront(Q)：若队列：若队列Q非空，则返回队头元素，非空，则返回队头元素，但不改变队列但不改变队列Q的状态。的状态。 1.4 1.4 线性表、栈和队列线性表、栈和队列 三、队列三、队列第一章第一章 计算机软件技术基础计算机软件技术基础以链接方式存储的线性表简称为链表。以链接方式存储的线性表简称为链表。1链表的具体存储表示为：链表的具体存储表示为： 用一组任意的存储单元来存放线性表的结点用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不（这组存储单元既可以是连续的，也可以是不连续的）。连续的）。 链表中结点的逻辑次序和物理次序不一定相链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针或链结点的地址（或位置）信息（称为指针或链)。1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念第一章第一章 计算机软件技术基础计算机软件技术基础2链表的结点结构链表的结点结构1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念datanext data域域存放结点值的数据域。存放结点值的数据域。next域域存放结点的直接后继的地址的指针域。存放结点的直接后继的地址的指针域。其中：其中： 链表通过每个结点的链域将线性表的链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的。个结点按其逻辑顺序链接在一起的。 每个结点只有一个链域的链表称为单链表。每个结点只有一个链域的链表称为单链表。每个结点有两个链域的链表，既指出该数据元每个结点有两个链域的链表，既指出该数据元素的后继素的后继,指出前驱，则这种链表称为双链表。指出前驱，则这种链表称为双链表。第一章第一章 计算机软件技术基础计算机软件技术基础 在单链表中增加一个表头结点，指针域指向线在单链表中增加一个表头结点，指针域指向线形表的第一个元素的结点，令最后一个结点的形表的第一个元素的结点，令最后一个结点的指针域指向表头结点，即构成了循环链表，指针域指向表头结点，即构成了循环链表，在在循环链表中，所有结点的指针构成了一个环状循环链表中，所有结点的指针构成了一个环状链。链。 1.5 1.5 线性链表线性链表 一、线性链表的概念一、线性链表的概念a1aiai+1an第一章第一章 计算机软件技术基础计算机软件技术基础n线性链表的基本运算主要有以下几个：线性链表的基本运算主要有以下几个：（1）在线性链表中包含指定元素的结点之前插入）在线性链表中包含指定元素的结点之前插入一个新元素一个新元素（2）在线性链表中删除包含指定元素的结点）在线性链表中删除包含指定元素的结点（3）将两个线性链表按要求合并成一个线性链表）将两个线性链表按要求合并成一个线性链表（4）将一个线性链表按要求进行分解。）将一个线性链表按要求进行分解。（5）逆转线性链表）逆转线性链表（6）复制线性链表）复制线性链表（7）线性链表的排序）线性链表的排序（8）线性链表的查找）线性链表的查找1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础1.插入运算插入运算思想方法思想方法:插入运算是将值为插入运算是将值为x的新结点插入的新结点插入到表的第到表的第i个结点的位置上，即插入到个结点的位置上，即插入到ai与与ai1之间。之间。具体步骤：具体步骤： （1）找到）找到ai存储位置存储位置p；（2）生成一个数据域为）生成一个数据域为x的新结点的新结点ax；（3）令结点）令结点*p的指针域指向新结点；的指针域指向新结点；（4）新结点的指针域指向结点）新结点的指针域指向结点ai1。1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础2.删除运算删除运算思想方法思想方法:删除运算是将表的第删除运算是将表的第i个结点删去。个结点删去。具体步骤：具体步骤： （1）找到）找到ai-1的存储位置的存储位置p（因为在单链表中结点（因为在单链表中结点ai的存储地址是在其直接前趋结点的存储地址是在其直接前趋结点ai-1的指针域的指针域next中）；中）；（2）令）令pnext指向指向ai的直接后继结点（即把的直接后继结点（即把ai从链上摘下）；从链上摘下）；（3）释放结点）释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。1.5 1.5 线性链表线性链表 二、二、线性链表的基本运算线性链表的基本运算 第一章第一章 计算机软件技术基础计算机软件技术基础n树形结构是一类重要的非线性结构。树形结构树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。是结点之间有分支，并具有层次关系的结构。 如家谱、行政组织机构都可用树形象地表示。如家谱、行政组织机构都可用树形象地表示。 1.6 1.6 树树 一、什么是树一、什么是树 经济管理学经济管理学院院经济信息系经济信息系计划统计系计划统计系外贸系外贸系信息处理信息处理教研室教研室经济数学经济数学教研室教研室计划学计划学教研室教研室统计学统计学教研室教研室外语外语教研室教研室国际贸易国际贸易教研室教研室第一章第一章 计算机软件技术基础计算机软件技术基础2树结构的基本术语树结构的基本术语在树结构中，每一个结点只有一个前件，称为在树结构中，每一个结点只有一个前件，称为父结点。父结点。没有前件的结点只有一个，称为树的根结点。没有前件的结点只有一个，称为树的根结点。每一个结点可以有多个后件，都称为该结点的每一个结点可以有多个后件，都称为该结点的子结点。子结点。没有后件的结点称为叶子结点。没有后件的结点称为叶子结点。一个结点所拥有的后件个数称为该结点的度。一个结点所拥有的后件个数称为该结点的度。一棵树的度是指该树中结点的最大度数。一棵树的度是指该树中结点的最大度数。1.6 1.6 树树 一、什么是树一、什么是树 第一章第一章 计算机软件技术基础计算机软件技术基础结点的层数结点的层数(Level)：从根起算，根的层数为：从根起算，根的层数为1，其余结点的层数等于其双亲结点的层数加其余结点的层数等于其双亲结点的层数加1。树中结点的最大层数称为树的高度树中结点的最大层数称为树的高度(Height)或深或深度度(Depth)。ACBHDFIJGE1.6 1.6 树树 一、什么是树一、什么是树 图中，树的根结点图中，树的根结点A度为度为2，结点结点B的度为的度为3，结点，结点I的度为的度为0，树的度为，树的度为3，结点，结点A在第一在第一层，结点层，结点B，C在第二层，结在第二层，结点点D,E,F,G,H在第三层在第三层,结点结点I,J在第四层。在第四层。第一章第一章 计算机软件技术基础计算机软件技术基础n森林森林(Forest)是是m(m0)棵互不相交的树的棵互不相交的树的集合。集合。n树和森林的概念相近。删去一棵树的根，树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。作树根，森林就变为一棵树。1.6 1.6 树树 一、什么是树一、什么是树 第一章第一章 计算机软件技术基础计算机软件技术基础1.二叉树的特点二叉树的特点（1）非空二叉树只有一个根结点。）非空二叉树只有一个根结点。（2）每一个结点最多有两棵子树，称为该结点的）每一个结点最多有两棵子树，称为该结点的左子树和右子树。左子树和右子树。如算术运算式如算术运算式3 * 5 6 / 2 8就可用二叉树表就可用二叉树表示。示。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 +*83562/第一章第一章 计算机软件技术基础计算机软件技术基础2.二叉树具有以下重要性质：二叉树具有以下重要性质：性质性质1 二叉树第二叉树第i层上的结点数目最多为层上的结点数目最多为2i1(i1)。性质性质2 深度为深度为k的二叉树至多有的二叉树至多有2k1个结点个结点(k1)。性质性质3 在任意一棵二叉树中，若终端结点的个数在任意一棵二叉树中，若终端结点的个数为为n0，度为，度为2的结点数为的结点数为n2，则，则no=n21。性质性质4 具有具有n个结点的完全二叉树的深度为：个结点的完全二叉树的深度为： （或（或 ）。）。1lgn1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 1lgn1lgn) 1lg(n第一章第一章 计算机软件技术基础计算机软件技术基础3.满二叉树和完全二叉树是二叉树满二叉树和完全二叉树是二叉树（1）满二叉树）满二叉树(FullBinaryTree) 一棵深度为一棵深度为k且有且有2k1个结点的二叉树称为满二个结点的二叉树称为满二叉树。叉树。满二叉树的特点：满二叉树的特点： 每一层上的结点数都达到最大值。即对给定的每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。高度，它是具有最多结点数的二叉树。 满二叉树中不存在度数为满二叉树中不存在度数为1的结点，每个分支结的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下点均有两棵高度相同的子树，且树叶都在最下一层上。一层上。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础（2）完全二叉树）完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度数可若一棵二叉树至多只有最下面的两层上结点的度数可以小于以小于2，并且最下一层上的结点都集中在该层最左边，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。的若干位置上，则此二叉树称为完全二叉树。完全二叉树的特点：完全二叉树的特点： 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 在满二叉树的最下一层，从最右边开始连续删去若干结在满二叉树的最下一层，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。点后得到的二叉树仍然是一棵完全二叉树。 在完全二叉树中，若某个结点没有左孩子，则它一定没在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。有右孩子，即该结点必是叶结点。1.6 1.6 树树 二、二、二叉树的基本性质二叉树的基本性质 第一章第一章 计算机软件技术基础计算机软件技术基础n链接的方法是它最自然的存储表示方法。链接的方法是它最自然的存储表示方法。n每个结点有一个数据域，两个指针域。数据域每个结点有一个数据域，两个指针域。数据域存储数据元素的值，两个指针分别指向该数据存储数据元素的值，两个指针分别指向该数据元素的左子女和右子女。当某个子女不存在时，元素的左子女和右子女。当某个子女不存在时，相应的指针为空指针。结点形式如下：相应的指针为空指针。结点形式如下：1.6 1.6 树树 三、三、二叉树的存储结构二叉树的存储结构 llinkinforlink一棵二叉树的所有这样形式的结点，再加上一个一棵二叉树的所有这样形式的结点，再加上一个指向根的指针，就构成此二叉树的存储表示。这指向根的指针，就构成此二叉树的存储表示。这种存储表示法称为种存储表示法称为llink-rlink表示法或称为二叉链表示法或称为二叉链表。表。第一章第一章 计算机软件技术基础计算机软件技术基础n遍历一棵二叉树实际上是对二叉树的结点进遍历一棵二叉树实际上是对二叉树的结点进行一次扫描，是将二叉树的结点放入一个线性行一次扫描，是将二叉树的结点放入一个线性序列的过程，或者说把二叉树进行线性化。遍序列的过程，或者说把二叉树进行线性化。遍历运算是二叉树的一种最基本的运算。历运算是二叉树的一种最基本的运算。遍历二叉树有三种主要的方法：前序法、中遍历二叉树有三种主要的方法：前序法、中序法和后序法。序法和后序法。 前序法，其操作如下：前序法，其操作如下：访问根；访问根；按前序遍历左子树；按前序遍历左子树；按前序遍历右子树。按前序遍历右子树。1.6 1.6 树树 四、四、二叉树的运算二叉树的运算第一章第一章 计算机软件技术基础计算机软件技术基础 中序法，其操作如下：中序法，其操作如下：按中序遍历左子树；按中序遍历左子树；访问根；访问根；按中序遍历右子树。按中序遍历右子树。 后序法，其操作如下：后序法，其操作如下：按后序遍历左子树；按后序遍历左子树；按后序遍历右子树；按后序遍历右子树；访问根。访问根。1.6 1.6 树树 四、四、二叉树的运算二叉树的运算第一章第一章 计算机软件技术基础计算机软件技术基础+*83562/1.6 1.6 树树 四、四、二叉树的运算二叉树的运算对于图中的二叉树，它的对于图中的二叉树，它的三种方法遍历结果是：三种方法遍历结果是：前序序列：前序序列： * 3 5 6 2 8中序序列：中序序列： 3 * 5 6 2 8后序序列：后序序列： 3 5 * 6 2 8 第一章第一章 计算机软件技术基础计算机软件技术基础n顺序查找又称顺序搜索。顺序查找一般是指在线性表中顺序查找又称顺序搜索。顺序查找一般是指在线性表中查找指定的元素，其基本方法如下：查找指定的元素，其基本方法如下：n从线性表的第一个元素开始，依次将线性表中的元素与从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功被查元素进行比较，若相等则表示找到（即查找成功)；若线性表中所有的元素都与被查元素进行了比较但都不若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素相等，则表示线性表中没有要找的元素(即查找失败即查找失败)。n在下列两种情况下也只能采用顺序查找：在下列两种情况下也只能采用顺序查找：(1)如果线性表为无序表如果线性表为无序表(即表中元素的排列是无序的即表中元素的排列是无序的)，则，则不管是顺序存储结构还是链式存储结构，都只能用顺序不管是顺序存储结构还是链式存储结构，都只能用顺序查找。查找。(2)即使是有序线性表，如果采用链式存储结构，也只能用即使是有序线性表，如果采用链式存储结构，也只能用顺序查找。顺序查找。1.7 1.7 查找技术查找技术 一、顺序查找一、顺序查找第一章第一章 计算机软件技术基础计算机软件技术基础1.7 1.7 查找技术查找技术 二、二分法查找二、二分法查找n二分法查找只适用于顺序存储的有序表。二分法查找只适用于顺序存储的有序表。 设有序线性表的长度为设有序线性表的长度为n，被查元素为，被查元素为x，则对二，则对二分查找的方法如下：分查找的方法如下：将将x与线性表的中间项进行比较：与线性表的中间项进行比较：若中间项的值等于若中间项的值等于x，则说明查到，查找结束；，则说明查到，查找结束；若若x小于中间项的值，则在线性表的前半部分小于中间项的值，则在线性表的前半部分(即中间项以前的部分即中间项以前的部分)以相同的方法进行查找；以相同的方法进行查找；若若x大于中间项的值，则在线性表的后半部分大于中间项的值，则在线性表的后半部分(即中间项以后的部分即中间项以后的部分)以相同的方法进行查找。以相同的方法进行查找。第一章第一章 计算机软件技术基础计算机软件技术基础n所谓排序是指将一个无序序列整理成按值递减（或递增）所谓排序是指将一个无序序列整理成按值递减（或递增）顺序排列的有序序列。顺序排列的有序序列。 n1冒泡排序冒泡排序冒泡排序法的基本过程是：首先，从表头开始往后扫描冒泡排序法的基本过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序：显然，在扫描过程它们互换，称之为消去了一个逆序：显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是最大元素应线性表中的最大者换到了表的最后，这也是最大元素应有的位置。有的位置。依次剩下的线性表元素重复上述过程，直到线性表中依次剩下的线性表元素重复上述过程，直到线性表中每一个元素都找到它应有的位置，此时的线性表变为有每一个元素都找到它应有的位置，此时的线性表变为有序。序。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础2快速排序快速排序n快速排序法也是一种互换类的排序方法，但由于它比冒快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。泡排序法的速度快，因此称之为快速排序法。n快速排序法的基本思想如下：快速排序法的基本思想如下：从线性表中选取一个元素，设为从线性表中选取一个元素，设为T，将线性表后面小，将线性表后面小于于T的元素移到前面，而前面大于的元素移到前面，而前面大于T的元素移到后面。的元素移到后面。结果就将线性表分成了两部分结果就将线性表分成了两部分(称为两个子表称为两个子表)，T插入插入到其分界线的位置处，这个过程称为线性表的分割。通到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以过对线性表的一次分割，就以T为分界线，将线性表分为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于，而后面子表中的所有元素均不小于T。如果对分割后的各子表再按上述原则进行分割，并且，如果对分割后的各子表再按上述原则进行分割，并且，这种分割过程可以一直做下去，直到所有子表为空为止，这种分割过程可以一直做下去，直到所有子表为空为止，则此时的线性表就变成了有序表。则此时的线性表就变成了有序表。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础3.简单插入排序简单插入排序n所谓插入排序，是指将无序序列中的各元素依所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。次插入到已经有序的线性表中。n我们从线性表的第我们从线性表的第2个元素开始直到最后一个元个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有素，逐次将其中的每一个元素插入到前面的有序子表中。在简单插入排序法中，每一次比较序子表中。在简单插入排序法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的后最多移掉一个逆序，因此，这种排序方法的效率与冒泡法相同。在最坏情况下，排序需要效率与冒泡法相同。在最坏情况下，排序需要经过经过n（n1）/2次的比较。次的比较。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础4希尔排序希尔排序n希尔排序属于插入类排序，但它对简单插入排希尔排序属于插入类排序，但它对简单插入排序做了较大的改进。序做了较大的改进。n希尔排序的基本思想如下：希尔排序的基本思想如下：将整个无序序列分割成若干小的子序列分别将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法是将相隔某进行插入排序。子序列的分割方法是将相隔某个增量个增量h的元素构成一个子序列。在排序过程中，的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当逐次减小这个增量，最后当h减到减到1时，进行一时，进行一次插入排序，排序就完成。增量序列一般取次插入排序，排序就完成。增量序列一般取ht=n/2K(K=1,2,log2n)，其中，其中n为待排序序列为待排序序列的长度。的长度。1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础5简单选择排序简单选择排序n选择排序方法中最简单的一种就是直接选择排选择排序方法中最简单的一种就是直接选择排序算法。序算法。n其操作过程是：首先，从表头开始往后扫描线其操作过程是：首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的性表，在扫描过程中逐次比较相邻两个元素的大小。先选出最小的元素并将其与第一个元素大小。先选出最小的元素并将其与第一个元素交换。然后在剩下的交换。然后在剩下的n1个元素中再选出最小个元素中再选出最小的元素与第二个元素交换的元素与第二个元素交换最后在剩下的两最后在剩下的两个元素中。选出一个小的元素与第个元素中。选出一个小的元素与第n1个元素个元素交换。交换。 1.7 1.7 查找技术查找技术 三、排序技术三、排序技术第一章第一章 计算机软件技术基础计算机软件技术基础6堆排序堆排序n堆排序属于选择类的排序方法。堆排序属于选择类的排序方法。n根据堆的定义，可以得到堆排序的方法如下：根据堆的定义，可以得到堆排序的方法如下：（1）首