操作系统> ※<操作系统 操作系统 操作系统是加在裸机上的第一层软件。它是系统应用程序和用户程序与硬件之间的 接口，而且是整个计算机系统的核心，起着控制和管理的中心作用。 根据操作系统提供的服务方式，操作系统可分为批处理系统、分时系统、实时系统 、单用户交互系统、网络操作系统及分布式操作系统。 通常，操作系统可被划分为处理机管理、存储器管理、设备管理、文件管理及作业 管理五大部分。 处理机管理也称为进程管理。进程管理中重要的问题是处理好进程的同步与互斥， 同步是并发进程因相互合作而产生的一种制约关系，互斥是并发进程因共享资源而 产生的一种制约关系。 内存管理的基本目的是提高内存利用率以及方便用户使用，它涉及四个基本问题： 内存分配、地址映射、内存保护和内存扩充。内存管理有各种方法，有分区管理、 分页管理、分段管理和段页式管理等。虚拟存储器是广泛采用的内存扩充技术。 设备管理是操作系统的主要资源管理功能之一，由I/O系统实施，它涉及主机之外 的所有外设的管理。设备管理的基本目标是：向用户提供方便的设备使用接口以及 充分发挥设备的利用率。 文件管理及作业管理与使用的系统有直接的关系，在这里不做过多的解释。
××O O O ××O ×O … O ××O O ×O ×× O O O ×× O O ×× O O O ×× O O O ×× O O O
××× ×× O ×O … O O O O
因此，若将从对奕开始到结束的过程 中所有可能出现的格局都画在一张图上， 则可得到一棵倒长的“树”。“树根”是 对奕开始之前的棋盘格局，而所有的“叶 子”就是可能出现的结局，对奕的过程就 是从树根沿树叉到某个叶子的过程。“树 树 ”可以是某些非数值计算问题的数学模型 ，它也是一种数据结构。
实际问题中对象之间的关系
例3：交通图的最短路径问题 关系：图型 特征：多个直接前趋， 多个直接后继
7 4 5 A1 2 A3 6 A2 1 8 A5 A4 9 A6
实际问题中对象之间的关系
例4田径赛的时间安排问题 （无向图的着色问题） ：
设有六个比赛项目，规定每个选手至多可参加三个项目， 有五人报名参加比赛（如下表所示）设计比赛日程表，使 得在尽可能短的时间内完成比赛。
四、课程的主要内容
1. 数据结构部分 （1）数据结构的概念、数据的逻辑结构和数据的物理结构 （2）一般线性表及特殊线性表（栈、队列、串、数组） （3）树形结构及应用 （4）图形结构及应用 （5）查找 （6）排序
2. 操作系统部分 （1）操作系统的基本概念、特征和功能 （2）操作系统的发展、基本操作系统的类型 （3）处理机管理中进程与线程、进程的状态与转 换、进程的控制/调度/死锁 （5）存储管理的分区、分页、分段、段页式及虚 拟存储管理 （6）设备管理、设备管理程序、虚拟设备--假脱机 系统 （7）文件结构及存取方式、文件目录、文件的共 享与安全性 （8）作业管理与用户界面
八、重点内容的概述
数据结构> ※<数据结构 数据结构 数据结构是描述数据元素及元素间的相互关系。数据结构的概念一般包括三个方 面内容：数据之间的逻辑关系、数据在计算机中的存储方式以及在这些数据上定 义的运算的集合。 数据的逻辑结构直接称作数据结构，它抽象地反映数据元素间的逻辑关系。数据 的逻辑结构有三种基本数据结构：线性表、树和图。这三种基本数据结构又分为 线性结构（线性表）和非线性结构（树和图）。 数据的存储结构(亦称为物理结构)是数据的逻辑结构在计算机存储设备中的映象。 最常用的二种方式是：顺序存储结构和链接存储结构。大多数据结构的存储表示 都采用其中的一种方式，或两种方式的结合。 线性表是最简单的，也是最基本的一种数据结构。栈和队列是两种操作受限的线 性表。串也是一种特殊的线性表。 树形结构是一种重要的非线性结构。二叉树是另一种树形结构，二叉树有三种遍 历方法，称为先序遍历、中序遍历和后序遍历。二叉树的应用十分广泛，可以用 于判定和对策，其中哈夫曼树是一类带权路径长度最短的树。 图是较线性表和树更为复杂的数据结构，同一个图可以有多种多样的遍历顺序。 通常采用的遍历顺序有两种，深度优先搜索和广度优先搜索。它们对有向图和无 向图都适用。图的一个重要应用就是求网络的最小生成树。 查找就是在数据结构中找出满足某种条件的数据元素。查找的方法有线性查找和 二叉排序树查找等。 排序又称分类，是数据结构中另一种十分重要的运算。其功能就是将一个数据元 素的无序序列，按其关键字的大小重新排列，最后变成一个有序序列。
姓 丁 马 张 李 王
名 一 二 三 四 五
项目 1 跳高 标 枪 标 抢 铅 球 跳 远
项目 2 跳 远 铅 球 100 米 200 米 200 米
项目 3 100 米 200 米 跳 高
----田径赛的时间安排问题解法 ----田径赛的时间安排问题解法
（1）设用如下六个不同的代号代表不同的项目： 跳高 跳远 标枪 铅球 100米 200米 A B C D E F （2）用顶点代表比赛项目 不能同时进行比赛的项目之间连上一条边。 （3）某选手比赛的项目必定有边相连（不能同时 比赛）。 （4）对图上的每个顶点染一种颜色，并且要求有 线相连的两个顶点不能具有相同颜色，而总的颜色 种类应尽可能地少。同色可以同时比赛。
在建筑设计时计算梁结构的应力要求解线性方程组 预报人口增长情况时要求解微分方程等。
非数值计算问题： 但是随着计算机应用领域的不断扩大，计算机更 多地应用于处理非数值计算问题，这类问题涉及到数据 元素间复杂的相互关系，一般无法用数学方程来描述。
现实中对象之间的关系
线性关系：如列车中各车箱之间的关系、排队买车 票人之间的关系、一叠盘子中各盘子之间的关系等。 层次关系：如学校的组织结构、人的辈分关系等。 网状关系：如城市铁路交通网、电话网、计算机网 络等。
二、课程的基本要求与特点
1. 了解计算机软件的基本概念，软件的分类和功能； 2．系统地学习和掌握数据结构中三种基本类型（线性 表、树和图）的逻辑结构、物理结构及其运算，以及 常用的排序和查找方法； 3．了解操作系统的基本分类，掌握操作系统的主要功 能。 4．学习和掌握数据库的基本概念，掌握关系数据库的 设计方法及ACCESS、SQL SERVER等常见的数据库管理 系统。 5．了解软件工程的概念，了解结构化系统分析与设计 方法。 6．了解网络的基本概念，掌握网络的协议与标准、结 构与通信、安全性等内容。
软件技术基础
杨舰 微固学院 Email:yangjian@ Tel:83207790
写在前面的话
本课程学习的是什么？
学习在思考问题时， 不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考 学习在解决问题时， 不仅考虑人的处理方式，也要考虑计算机的处理方式
我是你亲密的朋友，你要理解和尊重我， 也要能被我理解。 对你而言，是一场有趣的思维体操； 对我而言，是一座顺畅沟通的桥梁
姓名 丁一 马二 张三 李四 王五
项目1 A C C D B
项目2 B D E F F
项目3 E
F A
只需 安排四 个单位 时间进 行比赛
比赛时 间 比赛项目
A F D
B E C
1 2 3 4
A，C B，D E F
在此例题中，可以用图中一个顶点表示一条通路，而通路之 间互相矛盾的关系以两个顶点之间的连线表示。设置交通灯 的问题等价为对图的顶点的染色问题，要求对图上的每个顶 点染一种颜色，并且要求有线相连的两个顶点不能具有相同 颜色，而总的颜色种类应尽可能地少。通常，这类交通、道 路、教学计划编排问题的数学模型是一种称谓“图”的数据 结构。 应用例子：旅游线路、工程工期。 综上几个例子可见，描述这类非数值问题的数学模型不再是 数学方程，而是诸如表、树和图之类的数据结构。因此简单 说来，数据结构是一门研究非数值计算的程序设计问题中计 数据结构是一门研究非数值计算的程序设计问题中计 算机的操作对象以及它们之间的关系和操作等等的学科。 算机的操作对象以及它们之间的关系和操作等等的学科。
C语 数据结 … 言 构 95 90 99 86 78 ： … … … … … ：
线性的数据理的数学模型中，计 算机处理的对象之间通常存在着的是一种 最简单的线性关系，这类数学模型可称谓
实际问题中对象之间的关系
例2：“井字棋”的人机对弈 关系：树型 特征：一个直接前趋， 多个直接后继
六、考核方式
1． 考核方法：采用试卷考试，闭卷方式 2． 出题方式：从A、B两份试卷中抽取 3． 考试用时： 120分钟 4． 成绩评定： 平时成绩(含中期测试、 考勤、作业等) 占20% 、 实验占10%、期 末考试占70%
七、使用教材和参考书
1.使用教材： 黄迪名主编，软件技术基础 ，高等教育出版社 2.参考书： 冯萍主编，计算机软件技术及应用基础，清华大 学出版社 谭浩强编著， C程序设计，清华大学出版社
三、本课程与其它课程的联系
本课程的先修课程为：计算机应用基础、C语 言程序设计。 数据结构中存储结构和基本运算的实现需要程 序设计的知识和程序编制的能力，在教材中的实例 都是用C语言进行编写的，因此，掌握C语言的基 础知识是学习本课程的前提；操作系统是管理计算 机系统资源的一种系统软件，是对裸机（不配有任 何的计算机软件）的首次扩充，因此只有了解计算 机的原理和基本结构，才能在此基础上进一步地学 习操作系统。
实际问题中对象之间的关系—— 实际问题中对象之间的关系—— 学生成绩表 学生成绩管理
关系：线性 特征：一个直接前趋， 一个直接后继
学号 姓名 大学英 语 90 80 95 70 82 ： A07005 黄勇 82 76 78 A07001 王萍 A07002 马玲 A07003 张兰 A07004 李建 A07005 黄勇 : A07001 王萍 90 85 95 A07002 马玲 80 85 90 A07003 张兰 95 91 99 A07004 李建 70 84 86 ： 85 85 91 84 76 ：
数据结构