大学计算机基础第9章

大学计算机基础第9章知识点：数据结构的基本概念操作系统的分类以及主要功能软件与软件生存周期软件工程的框架及开发过程数据库系统组成和数据模型通过对本章的学习读者应掌握数据结构的特性，为应用中所涉及的数据选择适当的逻辑结构、存储结构，了解操作系统的基本原理，建立软件开发的基本思想，掌握关系数据库，在软件知识和技术方面打下基础。29.1数据结构概述9.1.1相关概念与术语

数据（Data）是信息的载体，它能够被计算机识别、存储和加工处理抽象数据类型（AbstructDataType，简称ADT）是指一个数学模型以及定义在该模型上的一组操作数据结构（DataStructure）是指互相之间存在着一种或多种关系的数据元素的集合。各元素之间的关系称为结构。3

四类基本的数据结构9.1数据结构概述（a）集合结构（b）线性结构（c）树型结构（d）图形结构图9-1四类基本结构的示意图49.1数据结构概述

数据结构的两个要素：

1.数据元素的集合

2.关系的集合。通常可以采用一个二元组来表示：

Data_Structure＝（D，R）其中，D是数据元素的有限集，R是D上关系的有限集。59.1.2线性表1．线性表的定义线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，通常记为：(a1，a2，…ai-1，ai，ai+1，…an)其中n为表长，n＝0时称为空表。62．线性表的顺序存储和基本操作线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。

图9-2线性表的顺序存储7

顺序表上基本操作有线性表初始化、求表长、取表元、按值查找、插入、删除。

1)插入2)删除

（a）删除前（b）删除后8大家有疑问的，可以询问和交流可以互相讨论下，但要小声点93.线性链表的存储与基本操作链表是通过一组任意的存储单元来存储线性表中的数据元素，由一个个结点构成。图9-5链式存储结构10（1）建立单链表图9-8在头部插入建立单链表11图9-9在尾部插入建立单链表12（2）插入：设p指向单链表中某结点，s指向待插入的值为x的新结点。

1）将*s插入到*p的后面2）将*s插入到*p的前面13（3）删除：设p指向单链表中某结点，删除*p。图9-12删除*p149.1.3栈

1．栈的定义栈是限制在表的一端进行插入和删除的线性表。又称为后进先出的线性表（LastInFirstOut），简称LIFO表。图9-13栈示意图159.2操作系统管理9.2.1操作系统的发展和分类发展阶段手工操作阶段早期批量处理阶段管理程序阶段多道程序设计和多道批处理阶段169.2操作系统管理

按照操作系统的使用环境和对作业处理方式可将操作系统的基本类型分为五种：

1．批处理操作系统（BatchProcessingSystem）

2．分时操作系统（Time-SharingSystem）

3．实时操作系统

4．网络操作系统

5．分布式操作系统179.2操作系统管理9.2.2操作系统的功能

按照资源管理和用户接口的观点，操作系统主要有以下功能：

1．处理机管理（1）进程控制：（2）进程同步：（3）进程通信（4）进程调度：189.2操作系统管理2．存储器管理（1）内存分配与回收（2）存储保护（3）地址映射（4）内存扩充

3．设备管理

4．文件管理

5．作业管理199.3软件工程方法

9.3.1软件工程概述

软件工程是一门指导计算机软件开发和维护的工程学科，应用计算机科学、数学及管理科学等原理，借鉴传统工程的原则、方法，创建软件以达到提高质量，降低成本的目的。1945年，第一台电子数字计算机诞生，自此软件开发方法从机器码编程到软件工程方法，经历了三个阶段：

1．程序设计时期（1946年到60年代中）

2．软件时期（60年代中到70年代中）

3．软件工程时期（70年代至今）209.3软件工程方法“软件危机”的产生由于软件的需求和规模不断的增大，以及软件本身的特点，在软件开发的过程中，用户对软件需求的描述不精确以及软件开发人员对用户需求的理解与用户本来的愿望有差异导致了软件危机的产生。主要表现在以下几个方面；

1.开发成本高

2.研制周期长

3.软件质量差

4.文档资料缺乏

5.维护困难

6.不能满足发展需要219.3软件工程方法9.3.2软件生命周期

1．软件定义阶段

2．软件开发阶段

3．软件维护阶段229.3软件工程方法

9.3.3软件工程框架软件开发过程目标需求分析：书写需求分析说明书总体设计设计过程活动详细设计

测试与维护239.3软件工程方法

图9-16需求分析任务与其实现步骤249.3软件工程方法

1.概述说明开发本软件的目的、意义和背景。2.需求说明（1）功能说明：逐项列出个中功能需求的序号、名称和简要说明。

（2）性能说明：说明处理速度，响应时间、精度等。

需求说明书的内容259.3软件工程方法3.数据描述（1）数据流图（2）数据字典（3）接口说明4.运行环境（1）设备：说明软件运行所需的硬件设备。（2）支持软件：说明软件运行所需的系统软件和软件工具。5.限制说明软件开发的成本、进度、设计和实现方面的限制。

269.3软件工程方法图9-17设计流程图279.3软件工程方法

289.3软件工程方法

纠错性维护适应性维护软件维护完善性维护预防性维护299.4数据库技术理论9.4.1数据管理技术的发展1．相关概念数据处理：对数据进行收集、存储、加工和传播的一系列活动的总和。数据管理：是指对数据进行分类、组织、编码、存储、检索和维护工作。2．数据管理的三个阶段

1)人工管理阶段

2)文件系统阶段

3)数据库系统阶段309.4数据库技术理论9.4.2数据模型

模型是对现实世界特征的模拟和抽象，它能比较真实地模拟现实世界，容易为人所理解，并且便于在计算机上实现。1.概念模型概念模型是按用户观点来对数据和信息建模，主要用于数据库设计。2.数据模型数据模型是计算机系统的核心和基础，是对现实世界数据特征的抽象。包括网状、层次和关系模型三种。319.4数据库技术理论

关系模型的数据结构常用术语：（1）关系（Relation）：一个关系对应通常所说的一张二维表;（2）元组（Tuple）：表中的一行即为一个元组;（3）属性（Attribute）：给每一个属性起一个名称即属性名。（4）域（Domain）：属性的取值范围，所以又称“值域”；（5）分量：元组中的一个属性值；32

（6）关系模式：对关系的描述，一般表示为：关系名（属性1，…，属性n）（7）关键字或码（Key）：表中用来唯一确定（标识）一个元组的某个属性或属性组合。（8）关系模型（Relationalmodel）：用二维表结构来表示实体及实体间联系的模型。339.4数据库技术理论349.5本章小结

本章对软件技术基础所涉及的四个方面：数据结构、操作系统、软件工程和数据库技术进行了简单阐述。在数据结构的概述中重点以线性表、栈这些常见而简单的结构类型为例讨论了其在计算机中的存储结构及基本操作。在操作系统管理一节中，介绍了操作系统的发展历史，特点及功能，从资源管理和用户角度探讨了操作系统的主要功能。在软件工程中根据其框架结构介绍了软件工程开发的一般过程。并简单介绍了数据库系统组成和数据模型的相关概念。359.6实践检验理论巩固（1）数据结构主要研究哪些内容？（2）什么是数据的逻辑结构和存储结构，主要可分为哪几种？（3）设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，具体写出这四辆车开出站的所有可能顺序。（4）二维数组A的元素是6个字符组成的串，行下标i的范围从0~8，列小标j的范围从1~10。从供选择的答案中选出应填入下列关于数组存储的叙述中括号内的正确答案。

①存放A至少需要（）个字节。

②