2022年《计算机软件技术基础教案》

1、Teaching Plan For “Basis of Software of Computer”By Zhonghua LiangDepartment of Communication Engineering, School of Information Engineering, Changan University, Xian, 710064, Peoples Republic of China Date of Creation: September 19, 2010 Teaching Program 一本课程的性质和任务（教学大纲）本课程是通信工程专业的一门重要基础课程。其任务为 通过对

2、软件工程、数据结构、操作系统和数据库等方面的基本 概念及基本技术的学习和掌握，使学生对计算机软件有比较深 入、系统的了解，为将来能够熟练地编写比较复杂的应用程序 打下坚实的基础。二本课程的基本要求1对能力培养的要求1). 软件开发方法和技术 ：要求学生学习和掌握软件的基本概 念，软件的研制过程、软件工程概述、软件设计方法、程序结 构、算法描述工具，如流程图和算法语言。2). 数据结构 ：要求学生学习和掌握数据结构的基本概念与原 理、线性表、顺序存储结构和链式存储结构、算法实现、数 组、栈、队列、树等。3). 操作系统 ：要求学生学习和掌握操作系统的基本概念与原 理、操作系统提供的接口、进程与进

3、程管理、多道程序技术、同步与互斥、内存管理、设备管理、文件系统的原理、文件的 使用。4). 数据库技术 ：要求学生学习和掌握数据库的基本概念与原 理、数据模型、关系数据库。5). 网络及数据安全技术 ：要求学生学习和掌握网络及数据安 全技术的基本概念与原理。2重点和难点1). 本课程的重点 ：第二章 数据结构。2). 本课程的难点 ：(a) 线性链表； (b) 树、图的遍历；(c) 查 找、索引和排序技术运算及其应用。3先修课程： 计算机基础； C 语言。三课程内容1理论知识： （22 学时）1). 计算机软件概述 ：计算机软件的基本概念、程序设计技 术、数据结构的基本概念及术语、算法描述及算

4、法分析初步。2). 线性表：线性表的逻辑结构、线性表的顺序存储结构、线 性表的链式存储结构、表的基本运算在特定存储结构中的实现及应用。3). 栈和队列 ：栈的定义、表示和实现、栈的应用、队列的定 义、表示和实现、队列的应用。4). 树：树的定义和基本操作、二叉树定义和表示、遍历二叉 树和线索二叉树、树和森林、哈夫曼树及其应用。5). 串和图 ：串及图的定义、表示和操作、存储结构图的遍 历。6). 查找和排序 ：查找和排序及其运算的基本知识和算法。7). 操作系统 ：学习和掌握操作系统的基本概念与原理、操作 系统提供的接口、进程与进程管理、多道程序技术、同步与互斥、内存管理、设备管理、文件系统的

5、原理、文件的使用。8). 数据库 ：学习和掌握数据库的基本概念与原理、数据模 型、关系数据库、SQL 语言。9). 计算机网络 ：学习和掌握计算机网络体系结构、网络互联 与互联网、网络安全及防火墙技术、计算机病毒及防治。10). 软件工程 ：学习和掌握软件开发与技术，要求学生学习和 掌握软件的基本概念，软件的研制过程、软件工程概述、软件 设计方法、程序结构、算法描述工具，如流程图和算法语言。2课外作业：加深对课内所学的理论知识的理解，锻炼分析 问题和解决问题的能力。3上机实验：围绕本课程学习的重点和难点，实践理论知 识，上机完成题目（8 学时）。4考核方式：考核成绩主要根据：学生平时听课、完成

6、作业 情况 20% ；上机实验、完成实验报告 20% ；期末考试成绩60% 来综合评定。四课程教材及主要参考书1课程教材：1. 计算机软件技术基础第三版，沈被娜等编著，清华大 学出版社。2教学参考书：1. 计算机软件技术基础，庞丽萍编，华南理工大学出版社。2.Operating Systems-Design and Implementation，Second Edition, Andrew S, Tanenbaum, Albert S. Woodhull, 清 华 大 学 出 版 社 和PRENTICE HALL. 3.Software Engineering-A Practitioners

7、Approach， Fourth Edition, Roger, S. Pressman, 机械工业出版社和 McGraw-Hill. 4. Data Structure Algorithms, and Applications in C+ ， First Edition, Sartaj Sahni, 机械工业出版社和McGraw-Hill. 第 1 章 算法1算法的基本概念1). 算法的基本特征 ：(1). 能行性 (effectiveness) a). 算法中的每一个步骤必须能够实现，例如在算法执行中，分母不能为零，实数范围内不能求一个负数的平方根等等；b). 算法执行的结果要能够达到预期

8、目的，例如需要考虑计算精度的影响。(2). 确定性 (definiteness) 算法中的每一个步骤都必须是有明确定义的，不允许有模棱两 可的解释或多义性。(3). 有穷性 (finitenes s) 算法必须能在有限的时间内昨晚，计算法必须能在执行有限个 步骤后终止。例如无穷级数的计算只能是根据精读要求取有限 项的有穷计算；如果一个算法需要执行千万年，则失去了实用 价值。(3). 拥有足够的情报（sufficient information）通常算法中的各种运算总是要施加到各个运算的对象上，而这 些对象又可能具有某种初始状态，这是算法执行的起点或依 据。因此，一个算法执行的结果总是与输入的初

9、始数据有关，不同 的输入将会有不同的结果输出。当输入不够或输入错误 时，算法本身也就无法执行或导致执行有错。一般来说，当算 法拥有足够的情报时，此算法才是有效的，而当情报不够时，算法并不有效。综上所述 ：所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的 次数下终止。2). 算法的基本要素 ：(1). 对数据对象的运算和操作：a). 算术运算，加、减、乘、除等运算；b). 逻辑运算，“ 与” 、“ 或” 、“ 非” 等运算；c). 关系运算，“ 大于” 、“ 小于” 、“ 等于” 、“ 不等于”等运算；d). 数据传输，主要包括赋值、输入、输出等操

10、作；注意 ：计算机程序仅作为算法的一种描述；但通常不直接用 计算机程序来描述算法，而是用别的描述工具（如流程图、专 门的算法描述语言，甚至自然语言）来描述算法。(2). 算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之 间执行顺序有关。算法中各操作之间的执行顺序称为算法的控 制结构。一个算法一般可以用顺序、选择、循环 3 种基本的 控制结构组合而成。2算法设计基本方法 1). 列举法：举例白鸡问题，画出搜索空间的立体示意图。2). 归纳法：基本思想和本质（抽象）。3). 递推法：本质（归纳法）。4). 递归法：基本思想（逐层分解）；基础（归纳）。5). 减半递推法 ：又称

11、为分治法。“ 减半” 是将问题的规模减 半；“ 递推” 是指重复“ 减半” 。举例：矩阵相乘；二分法求 实根。6). 回溯法：基本思想（“ 试” ），处理复杂数据结构方面有广泛应用。举例：求解皇后问题，用方格图 讲解。3算法的复杂度分析 1). 算法的时间复杂度 ：所谓算法的时间复杂度，是指执行算 法所需要的计算工作量。可用算法在执行过程中所需基本运算 的执行次数来度量算法的工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数（see page 10 ）。在同一问题规模下，如果算法执行所需的基本运算次数取决于 某一特定输入时，可以用以下两种方法来分析

12、算法的工作量：(a) 平均性态（ average behaviour）分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量（定义，see page 10 ）。(b) 最坏情况复杂性（worst-case complexity）分析是指在规模为 n 时，算法所执行的基本运算的最大次数（上界），更具使用价值（定义，see page 10 ）。两者的分析比较举例（例1.5, see pages 10-11）。注意 ：本小节最后一段的论述（提及算法的工作量与输入无 关时的情况）。2). 算法的空间复杂度 ：一般是指执行这个算法所需要的内存 空间。一个算法所占用的存储空间包括算法程序所占

13、的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的 额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如在链式结构中，除了要存储数据本身外，还需要存储连接信息）。4习题讲解及作业布置：举例讲解： 1.1、 1.3 。第一次上机实验：1.2 、1.4、1.5 三题中任选 2 题（三题难度系数分别为 1.0, 1.0, 1.2 ）。第 2 章数据结构及其运算1数据结构的基本概念数据结构作为计算机的一门学科，主要研究以下三个方面的问 题：(a). 数据集合中各数据元素之间所固有的逻辑关系，即数据 的逻辑结构；(b). 在对数据进行处理时，各数据

14、元素在计算机中的存储关 系，即数据的存储结构；(c). 对各种数据结构进行的运算。讨论以上各问题的主要目的是为了提高数据处理的效率。所谓 提高数据处理的效率，主要包括两个方面：一是提高数据处理 的速度；二是尽量节省数据处理过程中所占用的计算机存储空 间。1). 两个实例 ：(a). 无序表和有序表的查找效率对比；(b). 学生情况登记表。1). 数据结构的定义 ：相互有关联的数据元素的集合。(a). 数据元素的含义；(b). 前后件关系。(1). 数据的逻辑结构：反映数据元素之间逻辑关系的数据结构。两个要素：一是数据元素的集合 D ；二是 D 上的关系R 。一个数据结构可以表示为 B=(D,R

15、) 。举例（see page 18）更正：page 18 中最后一行和 Ai。page 19 中第一行： D i 应改为(2). 数据的存储结构（物理结构）：数据的逻辑结构在计算机 存储空间中的存放形式。常用的存储结构：顺序；链接；索引。3).数据结构的图形表示：直观(1). 需要理解的概念名词：根节点；终端结点；内部节点；(2). 数据结构的基本运算：插入和删除；其它运算还有：查找 分类合并分解复制和修改等。(3). 数据结构中根据各数据元素之间前后件关系的复杂度，一 般将数据结构分为：线性结构和非线性结构。一般来说，如果一个非空的数据结构满足两个条件：(a)有且只有一个根节点；(b)每个节

16、点最多有一个前件，也最多只有一个后件。则称该数据结构为线性结构，又称线性表。此外：在插入或删除任何一个节点后还应该满足上述条件。2线性表及其顺序存储结构 1). 线性表及其运算 ：(1). 什么是线性表 (a). 需要理解的概念名词：记录；文件。(b). 非空线性表的结构特征（(2). 线性表的顺序存储结构see page 22 ）。(a). 基本特点：（ see page 22 ）。(b). 初始化线性表的顺序存储空间（delete 语句成对使用的习惯：申请空间see page 23 ）， new 和-释放空间。(c). 线性表的主要运算：（see page 23 ）(3). 线性表在顺序存

17、储下的插入运算：例 2.7 (a). 插入前后两线性表中的元素关系（(b). 平均移动元素数量的计算：see page 24 ）(0+1+ +n)/(n+1)=(n+1)(0+n)/2/(n+1)=n/2 (c). 由于 C+ 中数组下标从 要减去 1。0 开始，涉及到数组下标的变量均(4). 线性表在顺序存储下的删除运算(a). 删除前后两线性表中的元素关系（(b). 平均移动元素数量的计算：see page 26 ）(0+1+ +n-1)/n=(n)(0+n-1)/2/n=(n-1)/2 更正： page 26 中最后一行应改为：素，即无此元素。(5). 顺序表类 认为删除第 (n+1)

18、个元将顺序表的数据和基本操作（包括初始化、输出、插入和删 除）封装成类。更正： page 30 中第二段应该为：用2).栈及其应用 ： 如果顺序表非空，则调(1). 什么是栈（ stack ）：一种特殊的线性表，其插入和删除都 只在线性表的一端进行，即一端封闭，另一端开口。概念名词：栈顶（top ）；栈底（ bottom ）；入栈（ push ）；退栈（ pop ）(2). 栈的顺序存储及其运算：see 34 注意：程序中数组下标减一的操作。(3). 顺序栈类 (4). 表达式的计算 (4). 递归的实现 3).队列及其应用 ：(1). 什么是队列（queue ）：一种特殊的线性表，允许在一端

19、进行插入，而在另一端进行删除。FIFO or LILO 概念名词：排头指针（front ）；队尾指针（rear ）；入队运算；退队运算(2). 循环队列及其运算：see 43 (3). 循环队列类 (4). 队列的应用： a. 分配工作； b. IO 缓冲区； c. 加油模拟 3线性链表及其运算 1). 线性链表的基本概念 ：(1). 线性表的顺序存储结构的缺点：a. 插入或删除线性表中元素过程中需要移动大量数据元素；b. 存储空间不便于扩充；c. 不便于对存储空间的动态分配。(2). 链式存储方式中的存储结点构成：a.数据域； b.指针域(3). 线性链表：线性表的链式存储结构。(4). 基

20、本概念： a.Head 指针； b.NULL 或 0；c.线性单链表； d.线性双向链表；e. 左指针（ Llink ）； f.右指针（ Rlink ）(3). 线性链表类 (4). 链栈及其基本操作：a.初始化； b.入栈； c.退栈； d.读栈顶元素。(5). 链队及其基本操作：a.初始化； b.入队； c.退队。2). 线性链表的基本运算 ：(1). 插入：在指定元素的结点之前插入一个新元素。(2). 删除：删除包含制定元素的结点。(3). 合并：将两个线性链表按要求合并为一个线性链表。(4). 分解：将一个线性链表按要求进行分解。(5). 逆转； (6). 复制； (7). 排序； (

21、8). 查找。3). 循环链表：为了克服对空表与非空表运算的不统一问题。(1). 增加一个表头结点：其数据域为任意或根据需要来设置，指针域指向线性表的第一个元素的结点。(2). 最后一个结点的指针域不是空（NULL ），而是指向表头结点。即在循环链表中，所有结点的指针域构成了一个环状 链。3). 多项式的表示与运算 ：略4数组 二维数组：矩阵在程序设计语言中的表示； 程序设计语言中的数组在计算机中是顺序存储的。当矩阵中 的绝大部分元素为零时，采用一般的两维数组存储方式会浪费 大量的存储空间，同时也做了大量不必要的运算。1). 数组的顺序存储结构 ：(1). 二维数组以行为主的顺序存储：逐行、从

22、左至右的顺序。ADR(a ij)=ADR(a 11)+(i-1)n+j-1L, where 1i m, 1j n BASIC、C中的多维数组采用以行为主的顺序存储。(2). 二维数组以列为主的顺序存储：逐列、从上至下的顺序。ADR(a ij)=ADR(a 11)+(j-1)m+i-1L, where 1i m, 1j nFORTORAN 中的多维数组采用以列为主的顺序存储。2).规则矩阵的压缩(1). 下三角阵（ lower triangular matrix）；(2). 对称阵（ symmetrical matrix）；(3). 三对角阵（ tridiagonal matrix）；3).一般

23、稀疏矩阵（sparse matrix ）的表示(1). 三列二维数组：a. 矩 阵 的 大 小 总 行 数 （ number （number of columns）；b.非零元素的位置（行号和列号）；c. 非零元素的值；d.POS 和 NUM ；of rows ） 和 总 列 数e.操作：生成；输出；转置；相加；相乘。(2). 线性链表：(3). 十字链表： （自学，不考）5树与二叉树 1). 树的基本概念 ：一种简单的非线性结构。(1). 基本概念： a. 父结点； b. 子结点； c. 根； d. 度； e. 树的 度； f. 叶子结点2). 二叉树及其基本性质：一种实用的非线性结构（bi

24、nary tree ）(1). 特点： a. 非空二叉树只有一个根结点；两颗子树（称为左子树和右子树）；(2). 基本性质： 1，2，3， 4，5，6 b. 每个结点最多有(3). 遍历： a. 前序遍历； b. 中序遍历； c. 后序遍历；6图（自学，不考）7习题讲解及作业布置：举例讲解： 2.10。第一次作业： 2.5 、2.6、2.8 第二次实验：2.9 、 2.13 中选 1 题； 2.10 、 2.11 、2.12 、2.14 中选 1 题（各题难度系数均为 1.0）。第二次作业：2.15 、 2.16 、 2.17 中选 1 题； 2.20 、2.21 、2.22 第 3 章 1基本的查找技术查找与排序技术 基本概念：所谓查找是指在一个给定的数据结构中查找某个 指定的元素。通常根据不同的数据结构，采用不同的查找方 法。1). 顺序查找 ：顺序搜索。从线性表的第一个元素开始，依次 比较，结果为找到或失败。平均搜索比较次数为 n/2 。以下两种情况下必须使