软件技术基础教学绪论.ppt

第一章软件技术基础 软件设计能力是大学生的一种基本能力科研需要 现有工具软件并不总能满足要求工作需要 现代工业离不开自动化设备 自动化设备离不开计算机的控制 计算机的灵魂是软件 对于一个非计算机专业的人来说 如何学 学什么 是学习计算机技术的重要问题 为什么学习这门课 如何学 学什么 如何学兴趣 实践学什么将本专业和计算机的应用联系起来 在学习中应该掌握尺度 并非每一门课都做到 完全透彻 但也不能什么都一知半解 要有一个 拳头 方向 必要的准备熟悉应用开发平台上的常用工具至少掌握一种程序设计语言注重分析 分析问题 解决问题 课程内容 算法数据结构查找与排序技术操作系统数据库技术计算机网络软件工程 课程特点重点分散难度集中广而不深杂而不乱学习方法重视基础原理理解思维方式实践 实践再实践善于自学 善于利用电子资源 软件改变了我们的生活 工作生活娱乐 第一章计算机软件技术基础 第一章计算机软件技术基础 软件无所不在 软件无所不在 第一章计算机软件技术基础 第一章计算机软件技术基础 软件无所不在 第一章计算机软件技术基础 软件无所不在 第一章计算机软件技术基础 软件无所不在 第一章计算机软件技术基础 软件无所不在 软件无处不在 电力调度系统火车调度系统民航调度系统天气预报系统地震预警系统核试验模拟系统 第一章计算机软件技术基础 看不见的软件 嵌入式软件 战斗机飞控系统坦克火控系统导弹弹上控制系统工业控制系统核反应堆控制系统 第一章计算机软件技术基础 什么是软件 软件 software 是一系列按照特定顺序组织的计算机的数据和指令的集合 软件并不只是包括可以在计算机上运行的程序 与这些电脑程序相关的文档 一般也被认为是软件的一部分 简单的说软件就是程序加文档的集合体 第一章计算机软件技术基础 什么是软件 软件 software 是程序 数据及相关文档的集合程序 指示计算机完成指定任务的命令序列数据 程序操作的对象 也是操作的结果文档 软件开发 维护与使用的相关图文材料 是对程序与数据的描述 第一章计算机软件技术基础 软件和硬件的关系 硬件是基础软件是灵魂 第一章计算机软件技术基础 软件的分类 第一章计算机软件技术基础 操作系统数据库技术开发工具 计算机软件 系统软件 中间件 用户软件 办公软件专业软件娱乐 软件的分类 中间件在操作系统 网络和数据库之上 应用软件的下层 总的作用是为处于自己上层的应用软件提供运行与开发的环境 帮助用户灵活 高效地开发和集成复杂的应用软件 idc表述 中间件是一种独立的系统软件或服务程序 分布式应用软件借助这种软件在不同的技术之间共享资源 中间件位于客户机服务器的操作系统之上 管理计算资源和网络通信 软件学科 软件理论算法理论数据理论软件系统操作系统数据库开发工具 编译原理 软件开发软件工程 软件 软件是程序 说明信息 从内容上说 软件是具有使用性能的程序 从性能上说 软件是商品 从本质上说 与其他商品比较 研制开发是主要的生产方式 软件工程 软件只有过时而无 损耗 的商品 注重软件的柔性或有机性 第一章计算机软件技术基础 软件开发项目结构组成 第一章计算机软件技术基础 软件开发文档 系统建设可行性研究报告系统现状调研报告项目开发计划系统及软件需求说明书 数据要求说明书概要设计说明书详细设计说明书 数据库设计说明书用户操作手册测试计划 测试分析报告 模块开发卷宗 开发进度月报项目开发总结报告 软件开发和程序设计 编程 软件开发 根据用户要求建造出软件系统或者系统中软件部分的一个产品开发的过程 软件开发是一项包括需求获取 开发规划 需求分析和设计 编程实现 软件测试 版本控制的系统工程 程序设计 是指编写和维护源代码的过程 是软件开发过程的一小部分 有时也用来指狭义的软件开发 软件一般是通过某种或数种程序设计语言 在特定的计算机平台上实现的 通常采用软件开发工具进行开发 合格软件开发人员的素养 团队精神和协作能力文档习惯规范化 标准化的代码编写习惯需求理解能力复用性 模块化思维能力测试习惯学习和总结的能力 软件设计的一些问题 这么多的程序设计语言 我究竟该选哪一种 是不是懂得的计算机语言越多 就表示计算机水平越高 怎样才能学好软件设计 开发语言的选择 c语言编写的hello world程序voidmain printf hello world n pascal语言编写的hello world程序programmain beginwriteln 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等 程序设计语言是相通的 高手使用任何语言都能够设计出高质量的程序 关键不在于语言本身 而在于程序设计理念与方法 以及大量的项目经验 是否要掌握多种语言 怎样提高软件设计水平 第一章计算机软件技术基础 熟悉应用开发平台上的常用工具 至少掌握一种程序设计语言 请注意 程序语言只是表达工具 重要的是学会分析问题和解决问题的方法 不要以为学会c 就会用oo范型编制oo软件了 注重分析 从某种意义上来讲 软件开发其实就是用程序语言来描述解决问题的方法和步骤 所以分析用户的需求得到需要解决的问题 分析问题得到解决的方法步骤 分析是软件开发中最基本的一环 写文档 软件开发其实是一个问题驱动的基于文档的开发过程 应把写文档看作是应用开发的主要工作 这是最容易被忽视的工作也是现代软件工程最为强调的一点 怎样提高软件设计水平 第一章计算机软件技术基础 从来没有那个高手是培训成功的 成为软件开发高手的路只有一条 自学 软件开发中需要大量的编程实践和独立思考 只有在此过程中 你才能够逐步成长起来 学院里面能够培养出软件开发经理更是十足的谎言 软件项目经理更强调从实际中学习软件 第一章计算机软件技术基础 2012 8编程语言排名top20 第一章计算机软件技术基础 longtermtrends gnu linux windows能干而linux干不了的事情 那就是不需要干的事情 gnu是 gnu snotunix 的递归缩写自由自在永远免费资源众多没有病毒 unix unix元年1970两个人kenthompsondennisritchieunixisbasicallyasimpleoperatingsystem butyouhavetobeageniustounderstandthesimplicity dennisritchie两大阵营at t的unixucberkeley的bsd 对抗霸权的gun 革奴计划 的精神领袖richardstallmangnu工程开始於一九八四年 旨在发展一个类似unix 且为自由软件的完整操作系统 gnu系统 两种思潮 大教堂 集权 封闭 受控 保密 集市 分权 公开 精细的同僚复审opensource距开源越近就越繁荣 任何将unix专有化的企图 只能陷入停滞和衰败 gnugeneralpubliclicense gpl 到了1990年 gnu计划已经开发出的软件包括了一个功能强大的文字编辑器emacs c语言编译器gcc以及大部分unix系统的程序库和工具 唯一依然没有完成的重要组件 就是操作系统的内核 网络时代的英雄linux 比尔盖茨的头号对手linustorvalds1990年 芬兰赫尔辛基大学的一名学生linustorvalds发布了与unix兼容的linux内核 hello thisislinustorvaldsandipronouncelinuxaslinux top5distributions 5 4 3 2 全人类的linux ubuntu markshuttleworth1969年 生于南非小镇 大学毕业后创办了以及信息安全公司 1999年以5 75亿美元的价格卖出 在30岁时成为南非最年轻有为的本土富翁 2002年他自费3百万英镑乘坐俄罗斯联盟号飞船 在国际空间站中度过了8天的时光 当时他不知道他是否能回到遥远而又真实的地球 所以他决定如果能顺利回到地球 一定为人类做一件有意义的事 结束太空之行之后 markshuttleworth创立了ubuntu社区 ubuntu发行版光盘 免费索取 发展简介 4 10 wartywarthhog 长疣的疣猪 2004 105 04 hoaryhedgehog 灰白的刺猬 2005 045 10 breezybadger 愉快的獾 2005 106 06 dapperdrake lts 漂亮的鸭子 2006 66 10 edgyeft 躁动的蜥蜴 2006 107 04 feistyfawn 活泼的小花鹿 2007 47 10 gutsygibbon 勇敢的长臂猿 2007 108 04 hardyheron lts 强壮的苍鹭 2008 48 10 intrepidibex 无畏的山羊 2008 109 04 jauntyjackalope 活潑的兔子 2009 49 10 karmickoala 命運的考拉 2009 1010 04lucidlynx lts 清醒的猞猁 2010 4 第一章计算机软件技术基础 1 算法所谓算法是指解题方案的准确而完整的描述 2 算法的基本特征 1 可行性 2 确定性 3 有穷性 4 拥有足够的情报 1 3算法及算法分析一 算法 第一章计算机软件技术基础 3 算法的基本要素一个算法通常由两种基本要素组成 一是对数据对象的运算和操作 二是算法的控制结构 1 算法中对数据的运算和操作基本的运算和操作有以下四类 算术运算 主要包括加 减 乘 除等运算 逻辑运算 主要包括 与 或 非 等运算 关系运算 主要包括 大于 小于 等于 不等于 等运算 数据传输 主要包括赋值 输入 输出等操作 1 3算法及算法分析一 算法 第一章计算机软件技术基础 2 算法的控制结构算法的控制结构给出了算法的基本框架 它不仅决定了算法中各操作的执行顺序 而且也直接反映了算法的设计是否符合结构化原则 描述算法的工具通常有传统流程图 n s结构化流程图 算法描述语言等 一个算法一般都可以用顺序 选择 循环三种基本控制结构组合而成 1 3算法及算法分析一 算法 第一章计算机软件技术基础 4 算法设计基本方法 1 列举法根据提出的问题 列举所有可能的情况 并用问题中给定的条件检验哪些是需要的 哪些是不需要的 2 归纳法通过列举少量的特殊情况 经过分析 最后找出一般的关系 3 递推所谓递推 是指从已知的初始条件出发 逐次推出所要求的各中间结果和最后结果 其中初始条件或是问题本身已经给定 或是通过对问题的分析与化简而确定 4 递归 5 减半递推技术 1 3算法及算法分析一 算法 第一章计算机软件技术基础 对算法的分析主要是对算法的时间复杂度和空间复杂度的分析 1 时间复杂度一个算法的时间复杂度是该算法的时间耗费 即算法执行过程中所需要的基本运算次数 一个算法所耗费的时间 算法中每条语句的执行时间之和 每条语句的执行时间 语句的执行次数 语句执行一次所需时间 2 空间复杂度一个算法的空间复杂度为该算法在执行过程中所需要的存储空间 算法的时间复杂度和空间复杂度合称为算法的复杂度 1 3算法及算法分析二 算法分析 第一章计算机软件技术基础 1 线性表的逻辑定义线性表 linearlist 是由n n 0 个数据元素 结点 a1 a2 an组成的有限序列 数据元素的个数n定义为表的长度 n 0时称为空表 将非空的线性表 n 0 记作 a1 a2 an 数据元素ai 1 i n 只是个抽象符号 其具体含义在不同情况下可以不同 如学生成绩表中 每个学生及其成绩是一个数据元素 其中数据元素由学号 姓名 各科成绩等数据项组成 1 4线性表 栈和队列一 线性表 第一章计算机软件技术基础 2 线性表的逻辑结构特征对于非空的线性表 有且仅有一个开始结点a1 没有直接前趋 有且仅有一个直接后继a2 有且仅有一个终结结点an 没有直接后继 有且仅有一个直接前趋an 1 其余的内部结点ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 1 4线性表 栈和队列一 线性表 第一章计算机软件技术基础 3 线性表的顺序存储结构有顺序存储和链式存储两种顺序存储方法即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法 用顺序存储方法存储的线性表简称为顺序表 在顺序表中 每个结点ai的存储地址是该结点在表中的位置i的线性函数 只要知道基地址和每个结点的大小 就可在相同时间内求出任一结点的存储地址 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线性表 栈和队列一 线性表 第一章计算机软件技术基础 5 insertlist l x i 在线性表l的第i个位置上插入一个值为x的新结点 使得原编号为i i 1 n的结点变为编号为i 1 i 2 n 1的结点 这里1 i n 1 而n是原表l的长度 插入后 表l的长度加1 6 deletelist l i 删除线性表l的第i个结点 使得原编号为i 1 i 2 n的结点变成编号为i i 1 n 1的结点 这里1 i n 而n是原表l的长度 删除后表l的长度减1 1 4线性表 栈和队列一 线性表 第一章计算机软件技术基础 1 栈的定义栈 stack 是限制仅在表的一端进行插入和删除运算的线性表 栈的示意图如图1 4所示 1 通常称插入 删除的这一端为栈顶 另一端称为栈底 2 当表中没有元素时称为空栈 3 栈为后进先出 lastinfirstout 的线性表 简称为lifo表 栈的修改是按后进先出的原则进行 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 定义只允许在一端进行插入 而在另一端进行删除的运算受限的线性表 1 允许删除的一端称为队头 front 2 允许插入的一端称为队尾 rear 3 当队列中没有元素时称为空队列 4 队列亦称作先进先出 firstinfirstout 的线性表 简称为fifo表 队列的修改是依先进先出的原则进行的 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 链表的具体存储表示为 用一组任意的存储单元来存放线性表的结点 这组存储单元既可以是连续的 也可以是不连续的 链表中结点的逻辑次序和物理次序不一定相同 为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还必须存储指示其后继结点的地址 或位置 信息 称为指针或链 1 5线性链表一 线性链表的概念 第一章计算机软件技术基础 2 链表的结点结构 1 5线性链表一 线性链表的概念 data域 存放结点值的数据域 next域 存放结点的直接后继的地址的指针域 其中 链表通过每个结点的链域将线性表的n个结点按其逻辑顺序链接在一起的 每个结点只有一个链域的链表称为单链表 每个结点有两个链域的链表 既指出该数据元素的后继 指出前驱 则这种链表称为双链表 第一章计算机软件技术基础 在单链表中增加一个表头结点 指针域指向线形表的第一个元素的结点 令最后一个结点的指针域指向表头结点 即构成了循环链表 在循环链表中 所有结点的指针构成了一个环状链 1 5线性链表一 线性链表的概念 第一章计算机软件技术基础 线性链表的基本运算主要有以下几个 1 在线性链表中包含指定元素的结点之前插入一个新元素 2 在线性链表中删除包含指定元素的结点 3 将两个线性链表按要求合并成一个线性链表 4 将一个线性链表按要求进行分解 5 逆转线性链表 6 复制线性链表 7 线性链表的排序 8 线性链表的查找 1 5线性链表二 线性链表的基本运算 第一章计算机软件技术基础 1 插入运算思想方法 插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai与ai 1之间 具体步骤 1 找到ai存储位置p 2 生成一个数据域为x的新结点ax 3 令结点 p的指针域指向新结点 4 新结点的指针域指向结点ai 1 1 5线性链表二 线性链表的基本运算 第一章计算机软件技术基础 2 删除运算思想方法 删除运算是将表的第i个结点删去 具体步骤 1 找到ai 1的存储位置p 因为在单链表中结点ai的存储地址是在其直接前趋结点ai 1的指针域next中 2 令p next指向ai的直接后继结点 即把ai从链上摘下 3 释放结点ai的空间 将其归还给 存储池 1 5线性链表二 线性链表的基本运算 第一章计算机软件技术基础 树形结构是一类重要的非线性结构 树形结构是结点之间有分支 并具有层次关系的结构 如家谱 行政组织机构都可用树形象地表示 1 6树一 什么是树 第一章计算机软件技术基础 2 树结构的基本术语在树结构中 每一个结点只有一个前件 称为父结点 没有前件的结点只有一个 称为树的根结点 每一个结点可以有多个后件 都称为该结点的子结点 没有后件的结点称为叶子结点 一个结点所拥有的后件个数称为该结点的度 一棵树的度是指该树中结点的最大度数 1 6树一 什么是树 第一章计算机软件技术基础 结点的层数 level 从根起算 根的层数为1 其余结点的层数等于其双亲结点的层数加1 树中结点的最大层数称为树的高度 height 或深度 depth 1 6树一 什么是树 图中 树的根结点a度为2 结点b的度为3 结点i的度为0 树的度为3 结点a在第一层 结点b c在第二层 结点d e f g h在第三层 结点i j在第四层 第一章计算机软件技术基础 森林 forest 是m m 0 棵互不相交的树的集合 树和森林的概念相近 删去一棵树的根 就得到一个森林 反之 加上一个结点作树根 森林就变为一棵树 1 6树一 什么是树 第一章计算机软件技术基础 1 二叉树的特点 1 非空二叉树只有一个根结点 2 每一个结点最多有两棵子树 称为该结点的左子树和右子树 如算术运算式3 5 6 2 8就可用二叉树表示 1 6树二 二叉树的基本性质 第一章计算机软件技术基础 2 二叉树具有以下重要性质 性质1二叉树第i层上的结点数目最多为2i 1 i 1 性质2深度为k的二叉树至多有2k 1个结点 k 1 性质3在任意一棵二叉树中 若终端结点的个数为n0 度为2的结点数为n2 则no n2 1 性质4具有n个结点的完全二叉树的深度为 或 1 6树二 二叉树的基本性质 第一章计算机软件技术基础 3 满二叉树和完全二叉树是二叉树 1 满二叉树 fullbinarytree 一棵深度为k且有2k 1个结点的二叉树称为满二叉树 满二叉树的特点 每一层上的结点数都达到最大值 即对给定的高度 它是具有最多结点数的二叉树 满二叉树中不存在度数为1的结点 每个分支结点均有两棵高度相同的子树 且树叶都在最下一层上 1 6树二 二叉树的基本性质 第一章计算机软件技术基础 2 完全二叉树 completebinarytree 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2 并且最下一层上的结点都集中在该层最左边的若干位置上 则此二叉树称为完全二叉树 完全二叉树的特点 满二叉树是完全二叉树 完全二叉树不一定是满二叉树 在满二叉树的最下一层 从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树 在完全二叉树中 若某个结点没有左孩子 则它一定没有右孩子 即该结点必是叶结点 1 6树二 二叉树的基本性质 第一章计算机软件技术基础 链接的方法是它最自然的存储表示方法 每个结点有一个数据域 两个指针域 数据域存储数据元素的值 两个指针分别指向该数据元素的左子女和右子女 当某个子女不存在时 相应的指针为空指针 结点形式如下 1 6树三 二叉树的存储结构 一棵二叉树的所有这样形式的结点 再加上一个指向根的指针 就构成此二叉树的存储表示 这种存储表示法称为llink rlink表示法或称为二叉链表 第一章计算机软件技术基础 遍历一棵二叉树实际上是对二叉树的结点进行一次扫描 是将二叉树的结点放入一个线性序列的过程 或者说把二叉树进行线性化 遍历运算是二叉树的一种最基本的运算 遍历二叉树有三种主要的方法 前序法 中序法和后序法 前序法 其操作如下 访问根 按前序遍历左子树 按前序遍历右子树 1 6树四 二叉树的运算 第一章计算机软件技术基础 中序法 其操作如下 按中序遍历左子树 访问根 按中序遍历右子树 后序法 其操作如下 按后序遍历左子树 按后序遍历右子树 访问根 1 6树四 二叉树的运算 第一章计算机软件技术基础 1 6树四 二叉树的运算 对于图中的二叉树 它的三种方法遍历结果是 前序序列 35 628中序序列 3 5 6 2 8后序序列 35 62 8 第一章计算机软件技术基础 顺序查找又称顺序搜索 顺序查找一般是指在线性表中查找指定的元素 其基本方法如下 从线性表的第一个元素开始 依次将线性表中的元素与被查元素进行比较 若相等则表示找到 即查找成功 若线性表中所有的元素都与被查元素进行了比较但都不相等 则表示线性表中没有要找的元素 即查找失败 在下列两种情况下也只能采用顺序查找 1 如果线性表为无序表 即表中元素的排列是无序的 则不管是顺序存储结构还是链式存储结构 都只能用顺序查找 2 即使是有序线性表 如果采用链式存储结构 也只能用顺序查找 1 7查找技术一 顺序查找 第一章计算机软件技术基础 1 7查找技术二 二分法查找 二分法查找只适用于顺序存储的有序表 设有序线性表的长度为n 被查元素为x 则对二分查找的方法如下 将x与线性表的中间项进行比较 若中间项的值等于x 则说明查到 查找结束 若x小于中间项的值 则在线性表的前半部分 即中间项以前的部分 以相同的方法进行查找 若x大于中间项的值 则在线性表的后半部分 即中间项以后的部分 以相同的方法进行查找 第一章计算机软件技术基础 所谓排序是指将一个无序序列整理成按值递减 或递增 顺序排列的有序序列 1 冒泡排序冒泡排序法的基本过程是 首先 从表头开始往后扫描线性表 在扫描过程中逐次比较相邻两个元素的大小 若相邻两个元素中 前面的元素大于后面的元素 则将它们互换 称之为消去了一个逆序 显然 在扫描过程中 不断地将两相邻元素中的大者往后移动 最后就将线性表中的最大者换到了表的最后 这也是最大元素应有的位置 依次剩下的线性表元素重复上述过程 直到线性表中每一个元素都找到它应有的位置 此时的线性表变为有序 1 7查找技术三 排序技术 第一章计算机软件技术基础 2 快速排序快速排序法也是一种互换类的排序方法 但由于它比冒泡排序法的速度快 因此称之为快速排序法 快速排序法的基本思想如下 从线性表中选取一个元素 设为t 将线性表后面小于t的元素移到前面 而前面大于t的元素移到后面 结果就将线性表分成了两部分 称为两个子表 t插入到其分界线的位置处 这个过程称为线性表的分割 通过对线性表的一次分割 就以t为分界线 将线性表分成了前后两个子表 且前面子表中的所有元素均不大于t 而后面子表中的所有元素均不小于t 如果对分割后的各子表再按上述原则进行分割 并且 这种分割过程可以一直做下去 直到所有子表为空为止 则此时的线性表就变成了有序表 1 7查找技术三 排序技术 第一章计算机软件技术基础 3 简单插入排序所谓插入排序 是指将无序序列中的各元素依次插入到已经有序的线性表中 我们从线性表的第2个元素开始直到最后一个元素 逐次将其中的每一个元素插入到前面的有序子表中 在简单插入排序法中 每一次比较后最多移掉一个逆序 因此 这种排序方法的效率与冒泡法相同 在最坏情况下 排序需要经过n n 1 2次的比较 1 7查找技术三 排序技术 第一章计算机软件技术基础 4 希尔排序希尔排序属于插入类排序 但它对简单插入排序做了较大的改进 希尔排序的基本思想如下 将整个无序序列分割成若干小的子序列分别进行插入排序 子序列的分割方法是将相隔某个增量h的元素构成一个子序列 在排序过程中 逐次减小这个增量 最后当h减到1时 进行一次插入排序 排序就完成 增量序列一般取ht n 2k k 1 2 log2n 其中n为待排序序列的长度 1 7查找技术三 排序技术 第一章计算机软件技术基础 5 简单选择排序选择排序方法中最简单的一种就是直接选择排序算法 其操作过程是 首先 从表头开始往后扫描线性表 在扫描过程中逐次比较相邻两个元素的大小 先选出最小的元素并将其与第一个元素交换 然后在剩下的n 1个元素中再选出最小的元素与第二个元素交换 最后在剩下的两个元素中 选出一个小的元素与第n 1个元素交换 1 7查找技术三 排序技术 第一章计算机软件技术基础 6 堆排序堆排序属于选择类的排序方法 根据堆的定义 可以得到堆排序的方法如下 1 首先将一个无序序列建成堆 2 然后将堆顶元素与堆中最后一个元素交换 不考虑已经换到最后的那个元素 只考虑前n 1个元素构成的子序列 显然 该子序列已不是堆 但左 右子树仍为堆 可以将该子序列调整为堆 反复做第 2 步 直到剩下的子序列为空为止 1 7查找技术三 排序技术 第一章计算机软件技术基础 1 结构化程序设计的原则 1 自顶向下 程序设计时 应先考虑总体 后考虑细节 先考虑全局目标 后考虑局部目标 不要一开始就过多追求众多的细节 先从最上层总目标开始设计 逐步使问题具体化 2 逐步求精 对复杂问题 应设计一些子目标作过渡 逐步细化 3 模块化 一个复杂问题 肯定是由若干稍简单的问题构成 模块化是把程序要解决的总目标分解为分目标 再进一步分解为具体的小目标 把每个小目标称为一个模块 4 限制使用goto语句 限制使用goto语句后 程序易理解 易排错 易维护 程序容易进行正确性证明 1 8程序设计文法一 结构化程序设计 第一章计算机