第3章计算机系统的软件.ppt

本章的重点和学习要求：计算机软件概念，分类(熟悉)编程语言的定义(理解)数据结构，分类(熟悉)编译原理的过程(掌握)操作系统的分类，功能(掌握)软件工程的生命周期和模型(熟悉)，算法和数据结构，3.2，软件工程，3.7，数据库系统，3.4，教学目的本讲座主要介绍计算机软件的基本概念。它对教学的重点和难点有一个全面的了解。软件定义了软件分类计算机系统的组成。3.1计算机软件概述。教学介绍。在第二章中，我们学习了计算机的内部组成。那么是谁控制硬件让它为我们服务呢？程序作为商品，以有形媒体作为交易载体，称为软件。也就是说，软件是指为计算机的操作、维护、管理和应用而编译的所有程序及其文档的总和。软件的特点：软件是一个功能和性能相对完整的程序，系统软件是一个具有操作性能的软件设备，信息商品软件是一种过时的商品，没有“磨损”。3.1.1什么是软件P106，上一页，返回，下一页，系统软件：软件制造商为释放硬件潜力而配备的、使用方便的软件。操作系统、语言编译/解释系统、网络软件、数据库管理软件、各种服务程序、接口工具箱以及其他支持计算机正常运行和“通用”的软件。应用软件：指解决某一应用领域问题的软件。会计软件、通讯软件、科技计算软件、计算机辅助设计/计算机辅助制造软件等。3.1.2软件P107的分类，上一页，返回，下一页，三类软件之间的关系，上一页，返回，下一页，常用软件，操作系统，群件系统，办公软件，系统工具软件，管理计算机系统软硬件数据，合理组织计算机工作流程，并为用户使用计算机提供良好的工作环境。如窗口等。一种日常办公软件，如办公、编程语言一般是以集成环境的形式出现的。例如：VisualStutio。可以帮助操作系统更有效地完成系统的管理和维护。例如，反病毒软件、程序开发工具、互联网工具软件、多媒体处理、数据库等都是信息管理的中心，如基于电子邮件的应用系统软件Access和SQLServer，它拓宽了电子邮件的内涵，保留了许多通信和协作功能。如Notes、ExchangeServer和GroupWise，在中央处理器级别提供多媒体指令，以实现对多媒体的直接支持。基于网络环境和互联网环境的应用软件，如网络服务器、文件传输协议、上一页、返回、下一页、3.1.4计算机系统组成P108-109、上一页、返回、下一页、计算机系统架构、上一页、返回、下一页、软件概念；软件分类；计算机系统的组成；本讲座主要介绍算法和数据结构的基本概念，以及几种常用数据结构的教学重点和难点。1.算法的基本概念2。线性表3。堆栈4。队列5。树，3.2算法和数据结构。教学介绍。电脑里有很多数据需要我们去处理。那么计算机是如何处理这些数据的呢？3.2.1为什么要学习算法和数据结构，上一页，返回，下一页，问题描述建立数学模型算法设计算法正确性证明算法分析算法程序实现，2。计算机求解过程，前一页，返回，下一页，算法数据结构=程序的研究主要包括两个方面：第一，如何设计算法，常用的算法设计方法包括分治递归法，贪心法，回溯法，动态规划法，分支定界法等。第二是如何分析给定算法的效率和性能。数据结构分为逻辑和逻辑学习算法和数据结构的含义，前一页，返回，下一页，算法算法的概念算法原意是指计算机科学中的计算步骤或规则，算法是指通过计算机算法解决问题的方法特征有限的确定性有效性有0个或多个输入项和至少一个输出项。3.2.2算法基础P113，上一页，返回，下一页，算法描述自然语言描述流程图描述伪代码描述算法结构序列结构选择(分支)结构循环结构，3.2.2算法基础(序列)，上一页，返回，下一页，算法设计方法递归技术分而治之方法贪婪算法回溯方法动态编程方法算法分析时间复杂度是指算法在计算机上运行所需的时间和空间复杂度。3.2.2算法基础(序列)、上一页、返回、下一页、示例：图书列表P122、上一页、返回、下一页、数据定义：所有可以输入计算机并由计算机处理以描述客观事物的符号都称为数据。在计算机中，数据的定义是广泛的。数字、字符、图形和声音都是由计算机处理的对象。它们统称为数据分类数字数据：应用于科学计算的程序有相对简单的组织，如变量、数组、简单表等。我关心的是计算速度和准确性。非数字数据：应用于商业或管理项目，它们的组织更加复杂。他们关心的是组织数据的规则，以便数据占用更少的空间，被快速访问，并有利于维护(添加、删除和修改)。3.2.3数据结构基础P121。数据结构是一门研究非数字程序设计中计算机操作对象及其关系和操作的学科。上一页，返回，下一页，数据类型：数据域。常见的数据类型包括字符类型、整数类型、逻辑类型、数组、集合、记录等。数据项：数据的最小单位。日期元素：数据项的集合(或记录)。数据对象：它是具有相同特征的数据元素的集合。例如整数数据对象的集合。数据结构：数据元素之间的关系。数据结构：它是具有结构的数据元素的集合。数据结构是数据的组织形式，反映数据之间的关系，但不涉及数据的具体内容。基本概念P122，上一页，返回，下一页，数据项，数据元素，数据，示例：图书书目表，数据的逻辑结构：指数据元素之间的逻辑关系，与计算机中数据的存储方式无关。线性结构。数据之间有顺序关系。除了第一个元素和最后一个元素，所有其他节点只有一个前置节点和一个后续节点(一对一关系)。包括数组、链表、堆栈、队列等。树形结构。数据之间有顺序关系。除了一个根节点，所有其他节点都有一个唯一的前体节点，并且可以有多个后续节点(一对多关系)。网状结构。每个节点可以有多个前体和多个后继节点(多对多关系)，3.2.3数据结构(顺序)，上一页，返回，下一页，数据存储结构：指数据到计算机内存的逻辑结构的映像。顺序存储结构在物理上相邻的存储单元中存储逻辑上相邻的数据元素。它主要存储线性结构的数据。节点之间的关系由物理邻接关系决定，节点中只存在信息域，因此存储密度高，空间利用率高。数据结构中第I个节点的存储地址可以通过以下公式获得：Li=l0 (I-1) k插入和删除操作将导致相应节点的大量移动。链式存储结构打破了计算机存储单元的连续性，可以在物理上不相邻的存储单元中存储两个逻辑上相邻的数据元素。除了数据，节点还具有表示链接信息的指针字段，因此比顺序存储结构占用更多的存储空间。逻辑上，相邻节点不一定物理上相邻，可以灵活方便地用于线性表、树、图等各种逻辑结构的存储、插入、删除等，无需移动大量节点，只需修改节点的指针值。3.2.3数据结构(序列)、前一页、返回、下一页、顺序存储结构、前一页、返回、下一页、链存储结构、前一页、返回、下一页和线性列表被定义为有限序列(a1，a2，人工智能，n个数据元素。元素ai可以是数字、符号或更复杂的信息。具有相同属性的线性表中的元素必须属于同一类数据对象。除了a1元素，每个元素只有一个直接的先行词。除了一个元素，每个元素只有一个直接的后继元素。每个元素的下标表示该元素在线性表格中的位置。行表P123，上一页，返回，下一页，数组。它是由n个相同类型的数据元素组成的序列，连续存储在计算机的内存中，数组中的每个元素占用相同的存储空间。数组的描述通常包括以下5个属性数组名。声明内存中数组第一个元素的起始地址。尺寸。每个元素中包含的数据项的数量，如一维数组、二维数组等。数组下标。数组中元素的存储位置。数组元素的数量。数组上下下标之间的差1。数组类型。声明此数组的类型，该类型决定数组元素在内存中占用的空间量。线性表(序列)，上一页，返回，下一页，链表：它是一个0或多个元素的序列，称为节点，每个节点包含一个或多个链接，称为指向链表中其他元素的指针，此外还存储数据。2。线性表(序列)、上一页、返回、下一页、堆栈结构定义：只能在末尾插入和删除的线性表。允许插入和删除的一端是变化端，称为顶部，另一端是固定端，称为底部。特点：这是一个后进先出线性表，即根据后进先出原则进行堆栈操作。堆栈存储结构：顺序存储：链式存储占用连续的存储空间：也称为链式堆栈，它是一个操作有限的链表，即链表中的插入和删除操作只能在链表的开头执行。堆栈的基本操作：放入堆栈(在堆栈顶部插入元素)，放出堆栈(删除堆栈顶部的元素)，从堆栈中取出堆栈顶部的元素，将S设置为空堆栈，以确定S是否为空堆栈。线性表(序列)，上一页，返回，下一页，a1，a2，an-1，an，堆栈进入和堆栈退出的动画演示、上一页、返回、下一页、堆栈链的顺序存储结构堆栈的存储结构、上一页、返回、下一页、队列定义：只允许一端插入而另一端删除的线性表称为队列。允许插入的末端称为队列末端(后端)，允许删除的末端称为队列头队列特征：先进先出。队列的存储结构：序列结构，链式结构队列的基本操作：进入队列(在队列末尾插入元素)；队列外(删除队列Q的队列头元素)；取出队列Q的队长元素；将队列Q设置为空队列；2.线性表(序列)、上一页、返回、下一页、顺序存储结构：队列中的所有元素都存储在一维数组中，数组的下端是队列的头部，下标的上端是队列的尾部。这种队列被视为顺序队列。如果一维数组中的所有位置都用元素填充，则称为队列满，即尾部指针指向一维数组的末尾，头部指针指向一维数组的开头，称为队列满。链存储结构：它被称为链队列，可以使用单个链表作为队列的链存储结构。队列的存储结构，上一页，返回，下一页，a1，a2，一个，一个，一个，一个，动画演示的队列进入和队列退出，上一页，返回，下一页，一个图形G=是一个数据结构，它由两部分组成：一个有限集合v，其元素称为顶点；另一个有限集合e，其元素由顶点对组成，叫做边。如果每对顶点之间没有顺序，即顶点对(u，v)和顶点对(v，u)是相同的，我们说图g是无向图，如图(a)所示。否则，它被称为有向，边的方向是从顶点U到顶点V，如图(b)所示。图，上一页，返回，下一页，图(序列)，上一页，返回，下一页，邻接矩阵。n个顶点的邻接矩阵是一个nn阶的布尔矩阵，用来表示图中节点之间的邻接关系。邻桌。它是一组链表，其中每个顶点由一个相邻的链表表示。链表包含与顶点相邻的所有顶点的加权图(即与顶点的边相连的所有顶点):图的每条边对应一个数值，通常是距离、运费、时间等。在实际应用中。这些值称为边缘权重或成本。相邻矩阵。当存在从节点1到节点j的边时，矩阵元素aij的值是该边的权重；当这样的边不存在时，它由一个特殊的符号来表示。邻桌。邻接表中的节点不仅包含相邻节点的名称，还包含相应边的权重。树、上一页、返回、下一页、树和林：没有循环连接的图称为树，如图A所示。虽然有些图不是树，但有些图的每个子图(连接的分支)都是树，称为林，如图B所示。树有两个属性：边数=顶点数减1。树的任意两个顶点之间只有一条路径。树示例图b森林示例4。树(顺序)，上一页，返回，下一页，根树：选择树的一个顶点并将其用作树的根。在根树的描述中，根通常被放置在顶部(树的第0层)，与根相邻的顶点被放置在根的下面(第1层)，然后顶点远离根的两侧(第2层)，以此类推。内部节点和叶节点：除根节点外，后续节点称为内部节点；没有后继的节点称为叶节点(或叶)父节点和子节点；一个节点的上层节点称为它的父节点；较低的节点称为子节点，树的深度是从根节点开始的树的级别。树的高度：是从根到叶节点的最长路径的长度。有序树，上一页，返回，下一页，5。有序树，上一页，返回，下一页，有序树：它是一个根树，树中每个顶点的所有子节点都是有序的。二叉树：在二叉树中，有序树中所有顶点的子树数不超过两个，每个子树要么是父树的左子树，要么是父树的右子树。通过对顺序存储的线性表和链接存储的优缺点的分析，可以发现选项c中顺序存储的线性表对于添加和删除操作是不正确的。但是，如果这个主题只是让我们选择了错误的语句，那么它一定是选项c。在下面的线性表的描述中，错误是()。a)线性表按顺序存储，必须占用一个连续存储单元b)线性表存储在链接中，而不是一个连续存储单元c)线性表按顺序存储，以便于插入和删除操作d)线性表存储在链接中，以便于插入和删除操作。结论：答案应该是c)，上一页，返回，下一页，上一页，返回，下一页，例2:查找下列图形的相邻矩阵，教学总结，数据结构的基本概念线性表堆栈队列树，操作，P1957，9，在上一页，计算机可以直接识别和执行高效的指令。很难记住二进制代码。手工编写机器语言很繁琐，容易出错的计算机有不同的机器语言，因此它们的通用性很差。第四代面向过程的语言。如SQL、PB、Delphi。面向对象的编程语言和网络语言，如VB、VB、C、HTML和Java。各种软件开发工具，如CASE，不能由计算机硬件直接识别和执行。它们必须由汇编程序的系统软件“组装”，然后才能由硬件执行。汇编语言指令与机器语言指令一一对应。具有不同低级语言的计算机具有不同的汇编语言。记忆指令助记符比记忆指令二