《《软件专业综合》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《软件专业综合》PPT课件.ppt（86页珍藏版）》请在三一办公上搜索。
1、数据结构,数据结构：是指数据元素之间的相互联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。数据的逻辑结构：数据元素之间的逻辑关系。线性结构：有唯一的开始结点及终端结点，其余结点有且仅有一个前驱和后继。非线性结构：分为树型结构及图型结构。树型结构中，每个结点仅有一个前驱但可以有多个后继，只有一个开始结点但可以有多个终端结点。图型结构中，每个结点的前驱和后继的个数都可以是任意的，可能没有开始结点和终端结点,也可能有多个开始结点、多个终端结点。,数据结构,存储结构：数据元素及其关系在计算机存储器中的存储方式,也称为数据的物理结构。顺序结构链接结构索引结构散列结构评价算法的两个标准：时间复
2、杂度、空间复杂度。,数据结构,线性表是数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n0。当n=0时,表示线性表是一个空表。线性表的存储：顺序表、链表。线性表的主要操作：插入、删除。重点掌握单链表的操作。,数据结构,链表：链式存储结构不需要一片连续存储单元,其元素可以分散存放，每个元素中不仅包含本身的信息,而且包含后继元素的地址信息。一般，每个元素分为两部分：数据部分：存放元素的值，称为数据域。指针部分：存放后继元素的存储地址，称为指针域。,数据结构,单向链表：链表元素中只有一个指针域，指向它的后继元素。头指针：指向链表第一个元素的指针。空指针用nil或表示。单向链
3、表结点类型：假定单链表中每个结点数据域用data表示,指针域用next表示。用data(a)和next(a)表示地址为a的结点的数据域和指针域的内容。,数据结构,栈是一种只能在一端进行插入或删除操作的线性表。允许进行插入、删除操作的一端称为栈顶。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈。,数据结构,队列简称队,它是一种不同于栈的特殊线性表,它仅允许在表的一端进行插入,而在表的另一端进行删除。我们把进行插入的一端称做队尾(rear),进行删除的一端称做队首(front)。向队列中插入新元素称为进队或入队,新元素进队后就成为
4、新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。,数据结构,数组是n(n1)个相同类型数据元素a1,a2,an构成的有限序列,且该有限序列存储在一块地址连续的内存单元中。二维数组的存放方式：按行优先存储方式按列优先存储方式,数据结构,特殊矩阵：指非零元素或零元素的分布有一定规律的矩阵。一个阶数较大的矩阵中，非零元素个数s相对于矩阵元素的总个数t十分小时,即st时,称该矩阵为稀疏矩阵。稀疏矩阵的压缩存储方法：三元组（行标，列标，值）十字链表,三元组表示法例,设有一个67阶稀疏矩阵A,则对应的三元组线性表为：(1,3,1),(2,2,2),(3,1,3),(4,
5、4,5),(5,5,6),(6,6,7),(6,7,4),数据结构,树的存储可采用链式存储结构，按树的度设计结点的孩子结点指针域个数。n个结点的k叉树，有n*k个指针，有用指针域n-1个。,数据结构,二叉树是n(n0)个结点的有限集合，它或为空树，或为由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。,几种特殊二叉树,满二叉树：二叉树每一层上的结点数都达到最大值。完全二叉树：除最底层外，其余各层结点数都达到最大值，且最底层的结点都集中在该层最左边的若干连续位置上。平衡二叉树：它或者为空树，或者左右子树都为平衡二叉树，且左子树与右子树深度之差的绝对值不超过1。,满二叉树,二叉树每一层上
6、的结点数都达到最大值。,完全二叉树,除最底层外，其余各层结点数都达到最大值，且最底层的结点都集中在该层最左边的若干连续位置上。,平衡二叉树,它或者为空树，或者左右子树都为平衡二叉树，且左子树与右子树深度之差的绝对值不超过1。,二叉树的遍历,遍历是指按照一定次序访问某数据结构中的所有结点，并且每个结点仅被访问一次。二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次。,二叉树的遍历形式,先序遍历：访问根结点；先序遍历左子树；先序遍历右子树。中序遍历：中序遍历左子树；访问根结点；中序遍历右子树。后序遍历：后序遍历左子树；后序遍历右子树；访问根结点。,哈夫曼树,哈夫曼树又称最优树，
7、是一类带权路径最短的树。树的带权路径长度(WPL)：从根结点到某结点的路径长度与该结点上权的乘积。哈夫曼树：WPL为最小的二叉树。,哈夫曼树的构造,（1）根据给定的n个权值w1,w2,.,wn构成n棵二叉树的集合F=T1,T2,.,Tn,其中每棵二叉树只有一个带权为wi的根结点。（2）在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。（3）将新的二叉树加入F中，去除原来两棵根结点权值最小的树。（4）重复（2）和（3），直到F中只含有一棵数为止。这棵树就是哈夫曼树。,哈夫曼编码,编码：将要传送的文字转换成二进制位0，1
8、组成的字符串。让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长度便可减少。,哈夫曼编码,假定电文中共使用了n种字符，每种字符在电文中出现的次数为 wi。以wi作为哈夫曼树叶子结点的权值构造出哈夫曼树，然后将每个结点的左分支标上“0”，右分支标上“1”，则从根结点到代表该字符的叶结点之间，沿途路径上的分支号组成的代码串就是该字符的编码。,图,图G由两个集合V和E组成,记为G=(V,E),其中V是图中顶点的有限集合，V=v1,v2,vn，E是连接V中两个顶点的边的有限集合,边是顶点的有序对或无序对，记作或（vi,vj）。图的常用存储结构有：邻接矩阵邻接表,邻接矩阵例,邻接表例,查找,
9、常用的查找方法：顺序查找二分查找分块查找哈希查找,排序,常用的排序方法：冒泡排序法选择排序法快速排序法堆排序法归并排序法,操作系统,操作系统是一组控制和管理计算机硬件和软件资源，合理地组织计算机工作流程，以及方便用户的程序的集合。操作系统的基本类型：多道批处理系统分时系统实时系统,操作系统,操作系统的功能：处理机管理：负责处理及资源的管理，包括进程控制、进程同步、进程通信及调度。内存管理：负责内存资源管理，包括内存分配及回收、信息保护、地址映射及内存扩充。设备管理：负责设备资源的管理，包括设备分配回收、缓冲管理、设备处理、设备独立性。文件管理：负责信息资源管理，包括文件存储空间管理、目录管理、
10、文件操作、文件共享保护。用户接口：命令接口及程序接口,操作系统,操作系统的特性：并发性：是指两个或多个事件在同一时间间隔内发生。共享性：是指系统中的资源可供多个并发执行的进程共同使用。不确定性：多个作业的执行顺序和每个作业的执行时间是不确定的。,操作系统,存储管理功能：内存分配 地址变换 存储保护 内存扩充 重定位：将作业的逻辑地址转换为物理地址的过程。,操作系统,存储管理方法：分区存储管理固定分区可变分区分页存储管理分段存储管理,固定分区,固定分区存储管理方法将内存空间划分为若干固定大小的分区，每个分区中可以装入一道程序。为了便于管理，系统需建立一张分区说明表。,固定分区的分配及回收,分区分
11、配：当有用户程序要装入时，检索分区说明表，从中找出一个能满足要求的空闲分区，然后修改分区说明表中相应表项的状态；若找不到满足要求的分区则拒绝分配。分区回收：当程序执行完毕时，释放程序占用的分区，将对应分区的状态置为未分配。特点：最早的多道程序存储管理方式，优点是分区的分配及回收简单，缺点是不能充分利用内存，存在内存碎片。,可变分区,可变分区存储管理根据作业大小建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。可变分区中常用的数据结构有：空闲分区表。用一个空闲分区表来登记系统中的空闲分区。空闲分区链。将内存中的空闲分区以链表方式链接起来，构成空闲分区
12、链。,分区表及分区链示意图,空闲分区表 空闲分区链,分区号 大小 起始地址 1 8KB 24KB 2 12KB 128KB 3 8KB 248KB 4 5,空闲分区分配算法,首次适应算法：空闲分区按地址递增次序排列。分配时从空闲分区链首开始查找，找到第一个能满足其大小要求的空闲分区，再按作业大小划出一块分配给请求者。最佳适应算法：空闲分区按容量递增的次序排列。分配时，从空闲分区链首开始查找，找到第一个能满足其大小要求的空闲分区，再按作业大小划出一块分配给请求者。最差适应算法：空闲分区按容量递减的次序排列。分配时检查第一个空闲分区，若第一个空闲分区小于作业要求的大小，则分配失败。,碎片及拼接,碎
13、片也可称为零头，是指内存中无法被利用的存储空间。拼接：是解决碎片问题的办法之一，即通过移动把多个分散的小分区拼接成一个大分区，也可称为紧缩或紧凑。,虚拟存储器,常规存储器管理要求作业运行前全部装入内存，作业装入内存后一直驻留内存直至运行结束。虚拟存储器：程序运行之前只装入部分程序就启动执行，当程序执行过程中所访问信息不在内存时，由操作系统将其调入；另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。从效果上看，这样的计算机系统好像为用户提供了一个存储容量比实际内存大得多的存储器，将这个存储器称为虚拟存储器。,分页存储管理,分页思想：将进程的逻辑地址空间划
14、分成若干大小相等的页，相应地将主存空间也划分成与页大小相等的块。系统以块为单位分配内存。请求分页思想：作业运行之前只装入部分页面便启动运行，在作业运行过程中，若发现所要访问的页面不在内存，便由硬件产生缺页中断，请求OS将缺页调入内存。若内存无空闲存储空间，则根据某种置换算法淘汰已在内存的某个页面，以腾出内存空间装入缺页。,页面置换算法,先进先出（FIFO）页面置换算法:选择调入主存时间最长的页面予以淘汰。最近最久未使用（LRU）页面置换算法:选择最近一段时间内最长时间没有被访问过的页面予以淘汰。,处理器管理,进程是一个具有一定功能的程序关于某个数据集合的一次运行活动。处理器执行状态：核心态：又
15、称管态、系统态，是操作系统管理程序执行时机器所处的状态。用户态：又称目态，是用户程序执行时机器所处的状态。,进程的状态,一个进程至少应有以下三种基本状态：就绪状态：进程已获得除处理机以外的所有资源，一旦分配了处理机就可以立即执行，此时进程所处的状态为就绪状态。执行状态：又称运行状态。当一个进程获得必要的资源并正在处理机上执行，此时进程所处的状态为运行状态。阻塞状态：又称等待状态、睡眠状态。正在执行的进程，由于发生某事件而暂时无法执行下去（如等待输入/输出完成），此时进程所处的状态为的等待状态。这时即使把处理机分配给该进程，它也无法运行。,进程状态转换图,进程控制块,PCB是描述和管理进程的数据
16、结构。它是进程实体的一部分，操作系统通过PCB感知进程的存在，PCB是进程存在的唯一标志。进程控制块一般包含：进程名、优先级、进程状态cpu现场信息、程序及数据地址通信信息、资源清单、家族关系,进程控制,原语是由若干条机器指令构成的，用以完成特定功 能的一段程序，这段程序在执行期间不可分割。进程控制的原语有：创建原语挂起原语（阻塞原语）激活原语（唤醒原语）撤消原语,常见进程调度算法,优先级调度：将处理机分给就绪队列中优先级最高的进程。时间片轮转：将处理机时间分成很短的时间片，将时间片轮流分给就绪队列中的进程使用。多级队列调度：将就绪队列分为多个，每个队列采用不同调度算法。例如：终端型作业为前台
17、作业，批处理作业为后台作业。前台采用时间片轮转算法，后台采用先来先服务，前台作业的优先级高。,同步与互斥,同步：多个进程在执行次序上的协调。互斥：进程对共享资源的排它性使用。,P、V操作,设S为一个信号量，P（S）执行时主要完成下述动作：SS1；if（S 0）设置进程状态为等待；将进程放入信号量等待队列；转调度程序；V(S)执行时主要完成下述动作：SS1；if（S0）将信号量等待队列中的第一个进程移出；设置其状态为就绪状态并插入就绪队列；然后再返回原进程继续执行；,用P、V实现进程互斥,临界资源：一段时间内仅允许一个进程使用的资源称为临界资源。如：打印机、共享变量。临界区：进程中访问临界资源的
18、那段代码称为临界区。设S为两个进程P1、P2实现互斥的信号量，S的初值应为1进程P1：进程P2：P(S);P(S);进程P1的临界区；进程P2的临界区；V(S)；V(S)；,进程通信,进程通信是指进程之间的信息交换。P、V操作也是进程通信，因传递的信息量少，称为低级进程通信方式。高级进程通信方式是指进程之间以较高的效率传送大量数据。直接通信（消息缓冲通信）间接通信（信箱通信）,死锁,死锁是指多个进程因竞争系统资源或相互通信而处于永久阻塞状态，若无外力作用，这些进程都将永远不能向前推进。死锁产生的原因：系统资源不足。进程推进顺序不当,死锁产生的必要条件,互斥条件：在一段时间内某资源仅为一个进程所
19、占有。不剥夺条件：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。请求和保持条件：又称部分分配条件。当进程因请求资源被阻塞时，已分配资源保持不放。循环等待条件：死锁发生时，存在一个进程资源的循环。,死锁的预防方法,死锁的预防：设置某些限制条件，通过破坏死锁产生的四个必要条件之一来预防死锁。互斥条件不能破坏。破坏请求和保持条件：要求进程一次申请它所需的全部资源，若有足够的资源则分配给进程，否则不分配资源，进程等待。这种方法称为静态资源分配法。破坏不剥夺条件：一个已获得某些资源的进程，若新的资源请求得不到满足，则它必须释放已获得的所有资源。破坏循环等待条件：将所有资源按类型排队，并赋予不
20、同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。这种方法称为有序资源分配法。,死锁的避免,死锁的避免：在资源的动态分配过程中，用某种方法来防止系统进入不安全状态（银行家算法）。,死锁的检测及解除,死锁检测：S为死锁状态的条件是当且仅当S状态的资源分配图是不可完全简化的。死锁解除资源剥夺法撤消进程法,设备管理功能,设备分配：根据用户的I/O请求，为之分配设备。包含控制器和通道。设备处理：负责启动设备及I/O操作完成时的中断处理。缓冲管理：为缓和CPU与I/O速度不匹配的矛盾常设置缓冲区。缓冲管理负责缓冲区的分配和释放及有关管理工作。设备独立性：又称设备无关性，是指用户编制程
21、序时所使用的设备与物理设备无关。设备独立性有两种类型：独立于同类设备的具体设备号独立于设备类型,设备分类,按设备使用性质可以分为：独占设备：在一段时间内只允许一个用户进程使用的设备。共享设备：在一段时间内允许多个进程使用的设备。虚拟设备：指通过虚拟技术将一台独占设备改造成若干台逻辑设备，供若干个用户进程同时使用。通常把这种经过虚拟技术处理后的设备称为虚拟设备。,Spooling技术,Spooling技术是将独占设备改造为共享设备的技术。Spooling系统由三部分组成：输入井和输出井输入缓冲区和输出缓冲区输入进程和输出进程,Spooling组成图,输入：在输入进程控制下，从输入设备将信息经由输
22、入缓冲区存入输入井，当进程需要数据是从输入井直接输入。输出：进程将结果直接存入输出井，然后在输出进程控制下，将信息经由输出缓冲区在输出设备当输出。,文件结构,文件的逻辑结构记录式文件流式文件文件的物理结构顺序结构链接结构索引结构,文件目录,目录是管理文件的数据结构。每个文件在目录中都有一个表项，存放该文件的属性信息。每个目录项通常包含：文件名、文件类型、文件结构、文件的外存地址、存取控制信息、管理信息,目录结构,常用的文件目录结构有：一级目录结构二级目录结构多级目录 结构,文件存储空间的管理,常用的空闲存储空间管理方法有：空闲文件目录空闲块链位示图,文件共享,文件共享是指不同用户可以使用同一文
23、件。文件共享的方式：通过文件路径通过文件链接：如不同目录项指向同一文件,数据管理的三个阶段,人工管理：20世纪50年代以前，当时没有操作系统，没有专门软件管理数据。程序员设计数据的逻辑和物理结构，数据和程序互相依赖。文件系统：50年代末代60年代中，由操作系统的文件管理模块管理数据，数据可以长期保存，因逻辑结构与存储结构分开，使程序和数据间具有一定独立性。但数据冗余大，数据间的联系弱。数据库系统：20世纪60年代后，它将所有使用的数据汇集起来，在数据库管理系统的管理下使用。数据独立性较高，不仅描述数据本身，还描述数据间的联系。,数据模型,数据模型：表示实体及实体之间联系的模型。模式：是对模型的
24、描述，是用数据描述语言来定义数据模型。数据模型分类概念模型（语义模型），如E-R模型。结构数据模型（简称数据模型），有层次模型、网状模型、关系模型。,DB、DBS与DBMS,数据库(DB)：按一定结构组织存储的、集成的、可共享的数据的集合。数据库管理系统(DBMS)：管理和维护数据库的系统软件。数据库系统(DBS)：具有管理数据库功能的计算机系统。,DBMS的功能,数据定义功能DBMS提供了数据定义语言（DDLData Definition Language）供用户对数据库中的数据对象进行定义。数据操纵功能DBMS提供了数据操纵语言（DMLData Manipulation Language）
25、实现对数据库的查询、插入、删除和修改等操作。数据库的运行管理DBMS提供了数据的安全性、完整性、并发控制机制及发生故障后数据库系统恢复的方法。数据库的建立与维护 提供了初始数据输入、数据库重组织和性能监视、分析功能等。,数据库的结构,一般将数据库的结构分为三级：用户级：又称外模式、子模式，是从各用户角度看到和使用的的数据库，是局部数据逻辑结构和特征的描述。概念级：又称概念模式、模式，是数据库管理员看到的数据库，是全局数据逻辑结构和特征的描述。物理级：又称内模式、存储模式、物理模式，是系统管理员对数据进行的物理组织，是数据物理结构和存储方式的描述。,数据库的二级映象功能,数据独立性：数据结构的修
26、改不引起应用程序修改的特性。数据逻辑独立性数据物理独立性三级模式间存在两级映象：外模式/模式映象：将用户数据进行综合抽象为一个统一数据视图，实现数据逻辑独立性。模式/内模式映象：将全局视图的数据按物理组织的最优形式存放，实现数据物理独立性。,数据库设计,数据库设计是指对于一个给定的应用环境，构造（设计）最优的数据模型，然后据此建立数据库及其应用系统，使之能够有效地存储数据，满足各种用户的应用需求。DB设计的内容：结构设计：数据模型与数据库结构的设计行为设计：应用程序设计,数据库设计步骤,需求分析：了解用户需求概念设计：对用户需求进行综合抽象，形成独立于具体DBMS的概念模型。逻辑设计：将概念结
27、构转换为所用DBMS支持的数据模型并进行优化。物理设计：选择合适的物理数据库结构（包括物理结构和存取方法）数据库实施：用DBMS提供的数据语言描述逻辑设计及物理设计，编制及调试应用程序，组织数据入库。数据库运行和维护：收集和记录系统实际运行数据，评价数据库系统的性能，修正系统。,关系数据库的设计问题,关系模式设计不合理带来的问题：数据冗余插入操作异常删除操作异常对存在问题的关系模式如何处理？关系模式的规范化（1NF、2NF、3NF）,关系数据语言,关系数据语言：在关系数据库中提供给用户对数据进行操纵的语言。简称数据语言。数据语言的功能：数据定义：定义数据模式、数据类型以建立数据模型。数据操纵：
28、对数据进行查询、插入、删除、修改等操作。数据控制：对数据的使用权限、完整性、一致性等进行控制，以共享数据并保护数据安全。,关系数据语言的特点,一体化：用一种语言实现数据定义、操纵及控制功能。非过程化：只需向系统提出做什么，而不需指出怎么做。集合式操作：操作对象及结果均为关系。灵活的使用方式：自含式：可以交互式或编程方式使用，但不能与其他语言混合使用。嵌入式：嵌入到高级语言中使用。,SQL,SQL（Structured Query Language）是通用的、功能极强的关系DB语言。SQL的特点：一体化非过程化两种使用方式：自含式、嵌入式完善的故障恢复功能灵活分散的授权方式,SQL 数据查询语句
29、,语句格式:SELECT DISTINCT|ALL FROM WHERE GROUP BY HAVING ORDER BY ASC|DESC说明：SELECT：指出要查询输出的属性名或值表达式。ALL:表示保留满足条件的所有元组（缺省）DISTINCT:表示去掉重复元组 属性名表：可以使用通配符“*”，表示所有的属性列,SQL 数据查询语句,FROM：查询所涉及的表名或视图名 WHERE：查询满足的条件 GROUP BY：按指定的属性进行分组，在指定的属性上值相同的分为一组。HAVING：对一个组的限定条件(与GROUP BY一起使用)ORDER BY:按指定的属性进行排序输出 ASC 升序（
30、确省）DESC 降序 目标列中可使用SQL提供的集函数 COUNT、SUM、AVG、MAX、MIN,SQL 数据查询语句,常用的查询条件查询条件谓词比较=、=、确定范围NOT BETWEEN AND 确定集合 NOT IN 字符匹配NOT LIKE 空值检测IS NOT NULL 多重条件AND、OR、NOT,插入操作,插入单个元组。格式：INSERT INTO（，)VALUES(,);插入子查询结果。格式：INSERT INTO(,)子查询；,修改及删除操作,修改数据。格式：UPDATE SET=,=WHERE;删除数据。格式：DELETE FROM WHERE;,定义视图,一般格式：CREATE VIEW(,)AS 其中：子查询不允许含有ORDER BY子句和DISTINCT短语。,数据控制,数据控制功能包括授权数据完整性及一致性：定义完整性约束条件的功能：定义码、定义取值惟一的列、不允许空值的列、其他一些约束条件。如NOT NULL、UNIQUE,授权,GRANT语句向用户授予操作权限。一般格式为：GRANT，ON TO，.语义为将对指定操作对象的指定操作权限授予指定的用户。,撤消授权,REVOKE语句收回授予用户的操作权限。一般格式为：REVOKE，ON FROM，.语义为将从对指定用户处收回指定操作对象的指定操作权限。,
