计算机软件技术基础(第3版).

1计算机软件技术基础第1章信息与信息时代第7章管理信息系统第2章常用数据结构及其运算第3章操作系统第8章信息与计算机系统的安全保护第4章数据库系统第5章计算机网络与信息高速公路第6章软件工程技术基础1第1章信息与信息时代1.1信息与信息时代1.2计算机发展简史1.3计算机与计算机系统1.4计算机软件技术发展过程1数据与信息的关系信息的三种不同层次示意图1.1信息与信息时代1.1.1什么是信息11.1.2信息化是社会经济发展的必然结果1.背景–认识基础–技术基础–经济基础–社会基础2.特点–市场环境变化–机遇挑战并存–风险效益并存–多媒体、互联网、信息高速公路1计算机的逻辑判断1.1.3信息与计算机应用1.信息技术2.计算机的特点–高速自动的操作–记忆–逻辑判断–精确高速的计算11.2计算机发展简史1.2.1计算机发展的几个重要阶段1.2.2计算机应用的领域1.2.3计算机在现代人类活动中的地位和作用1.2.4计算机的现在与未来11.2.1计算机发展的几个重要阶段1.几个阶段（时间）–第一代、第二代、第三代、第四代2.应用–大型机、小型机、个人机、全球网络3.数字化信息的特点–容易交换、大容量（高速）传输、稳定性高11.2.2计算机应用的领域–科学研究和科学计算–事务处理–计算机辅助–生产过程控制–人工智能–网络通信–计算机教育–多媒体1讨论环节1.2.3计算机在现代人类活动中的地位和作用1.2.4计算机的现在与未来1计算机硬件系统1.3计算机与计算机系统1.3.1计算机系统的组成–硬件系统说1计算机系统示意图计算机广义系统–硬件与软件结合说–广义系统说1.3.1计算机系统的组成11.3.2计算机的硬件与软件1.硬件系统–主机：中央处理器（CPU）﹑内存储器–外存储器：磁盘﹑光盘等–输入设备：键盘﹑鼠标﹑扫描仪等–输出设备：显示器﹑打印机等–系统总线：数据﹑地址﹑控制总线2.软件系统–系统软件：操作系统、编译程序、诊断程序、系统服务程序等–应用软件：特定应用程序、软件工具等3.硬件与软件的关系–互相依存、无严格界面、相互促进11.3.3多媒体计算机1.定义：–媒体、多媒体计算机2.基本要素：–文本、图形、图像、动画、音频、视频3.基本配置：–硬件配置、软件配置1程序的三种基本结构具有GOTO语句的程序1.4计算机软件技术发展过程1.4.1高级语言阶段1.4.2结构程序设计阶段–程序的正确性1程序的三种基本结构具有GOTO语句的程序1.4.2结构程序设计阶段–程序设计方法论–软件生产管理1第四代语言和其他软件技术的关系第四代语言工作示意图1.4.3自动程序设计阶段1第2章常用数据结构及其运算2.1概述2.2线性表2.3栈与队2.4数组2.5树与二叉树2.6图2.7查找2.8排序12.1概述1.什么是数据结构2.基本概念和术语–数据–数据元素–数据对象–数据结构–逻辑结构与物理结构–数据类型–数据结构与算法1【举例】对一个n×n的矩阵A自乘后送入矩阵B，算法步骤为：该算法中，语句3重复n2，语句5重复n3。设语句3执行时间t1,语句5执行时间t2,忽略其他语句执行时间，则算法近似耗时：2.1概述3.算法–算法语言、算法描述语言4.算法分析–时间复杂度、空间复杂度1))(()(nFOnT)(nT)(nF各种时间复杂度的增长率2.1概述其中，为时间复杂度为频度常见的时间复杂度有：–常量型、多项式型、对数型、指数型1}2,,|,{},...,,{1121niDaaaaRaaaDiiiin),(RDL),,,(21naaaL2.2线性表2.2.1线性表的定义和运算–一般形式：–定义：–其中–基本运算：插入、删除、查找、排序1顺序存储线性表的存储形式2.2.2顺序存储线性表1.顺序存储结构–向量式存储结构、随机存储结构–存储地址–存储形式1顺序存储线性表的插入过程xii素个元素间插入一个新元与第在第12.2.2顺序存储线性表2.插入运算1顺序存储线性表的删除过程个元素的线性表中删除第在长度为in2.2.2顺序存储线性表3.删除运算12.2.2顺序存储线性表4.运算的时间分析1线性表的链式结构2.2.3线性链表1.链式存储结构–数据域–指针域：头指针、空指针–指针类型结构12.2.3线性链表2.基本运算12.2.3线性链表–（1）结点的生成及回收–从空白链表中获取一个结点，由指针P指向–回收一个由P指针指向的结点，放回空白链表1线性链表的插入过程2.2.3线性链表–（2）插入运算1%75129页面走向总数缺页中断率FfLRU页面替换过程FIFO页面淘汰过程2.2.3线性链表3.线性链表的其他形式1循环链表双向链表2.2.3线性链表3.线性链表的其他形式1一元多项式的链式结构用链式结构进行多项式求和”为相加后的“和多项式)(7683)(133-5)(8542xCxxxxxBxxxA2.2.3线性链表4.应用实例——一元多项式相加12.2.3线性链表4.应用实例——一元多项式相加12.2.4向量和链表的比较1.线性表的长度是否固定2.线性表的主要操作是什么3.采用的算法语言1栈的插入与删除栈结构2.3栈与队2.3.1栈的结构和运算1.栈的定义2.顺序栈1链栈表达式求值过程2.3.1栈的结构和运算3.链栈表达式A/B**C+D4.栈的应用（1）表达式求值–运算符优先级–操作数（NS）、运算符（OS）两个栈1表达式求值的算法2.3.1栈的结构和运算1过程嵌套调用示意图过程递归调用示意图2.3.1栈的结构和运算（2）过程嵌套和递归调用1求解背包问题时栈的变化状况2.3.1栈的结构和运算（3）回溯求解算法1队的假溢出现象循环队列队结构循环队列的插入和删除算法2.3.2队的结构和运算1.队的定义2.顺序队1队的假溢出现象循环队列队结构循环队列的插入和删除算法2.3.2队的结构和运算3.链队1%75129页面走向总数缺页中断率FfLRU页面替换过程FIFO页面淘汰过程2.3.2队的结构和运算4.队的应用–多道程序中的CPU管理–缓冲区的设计1用线性表定义其中2.4数组2.4.1数组的定义1二维数组按行优先顺序存放三维数组按行优先顺序存放的存储地址元素ija的存储地址元素ijka2.4.2数组的顺序存储结构1.按行优先顺序存放1二维数组按列优先顺序存放三维数组按列优先顺序存放的地址元素ija的地址元素ijka2.4.2数组的顺序存储结构2.按列优先顺序存放1的地址非零元素ija2.4.2数组的顺序存储结构3.特殊矩阵的存放方式–（1）下三角阵的存储方式–下三角阵–非零元素按行优先顺序存放–非零元素个数1地址非零元素ija非零元素优先顺序存放三对角阵2.4.2数组的顺序存储结构（2）三对角阵的存储方式1稀疏矩阵三元组表示实现矩阵转置2.4.3稀疏矩阵1.三元组表示1访问x行y列元素行辅助向量构造POS与NUM向量2.4.3稀疏矩阵2.带辅助向量的三元组表示1列辅助向量稀疏矩阵的转置算法2.4.3稀疏矩阵2.带辅助向量的三元组表示12.十字链表结构十字链表中元素结点组成十字链表2.4.4数组的链式存储结构1.带行指针向量的单链表11.树的定义和术语}{,},,,{),(T21HRΦRΦTxxxTRTreen否则则二元组术语：结点、结点的度、叶子、孩子、双亲、兄弟、结点的层次、深度、森林、有序树2.树的存储结构异构型、同构型2.5树与二叉树2.5.1树的定义及其存储结构1}{,},,,{),(_21HRΦRΦDxxxDRDTBn否则则若二叉树。的结点，则必有：个度为个叶子结点，有）在任意二叉树中，若（个结点。的二叉树中至多有）深度为（个结点。层上至多有）二叉树的第（123122)1(2120201nnnnhiihi2.5.2二叉树及其性质1.二叉树定义及其存储结构2.二叉树的基本性质1（1）满二叉树（2）完全二叉树（3）平衡二叉树2.5.2二叉树及其性质3.几种特殊的二叉树12.5.2二叉树及其性质4.一般树转换为二叉树1DLR:先序遍历ABCDEFGLDR:中序遍历CBDAEGFLDR:后序遍历CDBGFEA遍历二叉树2.5.2二叉树及其性质4.一般树转换为二叉树1-求二叉树中的叶子节点数（如下）-求结点的双亲-求结点的孩子-判断结点所在的层次-计算二叉树的深度2.5.3二叉树的遍历遍历方法是二叉树操作的基础：1（1）定义（2）生成二叉排序树插入过程2.5.4二叉树的应用1.二叉排序树12.5.4二叉树的应用（3）删除二叉排序树上的结点-P是叶子结点-P只有左（右）子树-P的左右子树均非空-P是根结点1树的路径长度（1）树的路径长度（2）树的带权路径长度树的带权路径长度2.5.4二叉树的应用2.哈夫曼树1算法2.5.4二叉树的应用（3）哈夫曼树的构造1–哈夫曼编码哈夫曼编码对应A,C,N,H,I的哈夫曼树2.5.4二叉树的应用（4）哈夫曼树的应用-最佳判定算法11.定义图无向图有向图图网2.6图2.6.1图的定义及基本术语1（2）度、入度和出度（3）路径和回路（4）连通图和连通分量（1）子图2.6.1图的定义及基本术语2.有关图的基本术语1无向图无向网2.6.2图的存储结构1.邻接矩阵12.6.2图的存储结构2.邻接表1深度优先遍历2.6.3图的遍历1.深度优先搜索12.6.3图的遍历2.广度优先搜索1算法思想计算过程及结果2.6.4图的应用1.单源最短路径12.6.4图的应用算法描述1AOV网拓扑排序过程拓扑排序的邻接表和链栈2.6.4图的应用2.拓扑排序12.6.4图的应用2.拓扑排序算法1关键路径AOE网关键活动2.6.4图的应用3.关键路径12.7查找2.7.1查找的基本概念数据元素（记录）–数据项–主关键字、次关键字查找的定义–K值–过程1流程图1流程图2平均查找长度2.7.2线性查找顺序查找1判定树2.7.3对分查找算法思想1nbASLASLASL索引表与块的平均长度和对分查找顺序查找2.7.4分块查找索引顺序查找–算法思想–两次查找1不同插入次序的二叉排序树2.7.5二叉排序树查找动态查找查找长度1(key),,keyHH2.7.6哈希表技术及其查找１.哈希表－关键字、哈希函数、哈希地址－哈希函数构造、冲突问题－[举例]学生姓名{Wang,Li,Zhao,Shen,Gao,Fung,Bai,Chang,Ren,Ma}1422，836，281，396，515，853，135对最后取（2）平方取中法对（0100,1100,1200,1160,2060,2061,2163,2261,2262）取(010,210,440,345,243,247,678,112,116)（4）折叠法-移位折叠-边界折叠对123203241112202.7.6哈希表技术及其查找2.构造哈希函数（1）数字分析法（3）除留余数法1（2）平方探测再散列（3）随机探测再散列)1,,,2,1(,mod)(1ssjmRddjj2.7.6哈希表技术及其查找3.解决冲突的方法（1）线性探测再散列12.7.6哈希表技术及其查找几种探测方法比较（13,29,01,23,44,55,20,84,27,68,11,10,79,14）12.7.6哈希表技术及其查找（4）链地址法12.7.6哈希表技术及其查找4.哈希表的查找性能分析对于n=14的线性表线性探测线性查找平方探测对分查找随机探测若哈希表是均匀的链地址法12.8排序2.8.1排序的基本概念–定义–稳定、不稳定–内部、外部–选择、插入、交换排序–关键字的比较、记录的移动1分析算法）（13n比较次数记录移动次数2.8.2选择排序1.简单选择排序–过程1（1）堆的构造2.8.2选择排序2.堆排序1（1）堆的构造-将完全二叉树构成堆1（2）堆排序–两个步骤111MC与移动次数堆栈过程中的比较次数22MC与移动次数数堆栈排序过程中比较次充分大时近似n（3）算法分析12.对半插入排序2.8.3插入排序1.线性插入排序1最小最大2.8.4