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

TeachingPlanFor“BasisofSoftwareofComputer”ByZhonghuaLiangDepartmentofCommunicationEngineering,SchoolofInformationEngineering,Chang’anUniversity,Xi’an,710064,People’sRepublicofChinaDateofCreation:September19,2010TeachingProgram（教学大纲）一．本课程的性质和任务本课程是通信工程专业的一门重要基础课程。其任务为通过对软件工程、数据结构、操作系统和数据库等方面的基本概念及基本技术的学习和掌握，使学生对计算机软件有比较深入、系统的了解，为将来能够熟练地编写比较复杂的应用程序打下坚实的基础。二．本课程的基本要求1．对能力培养的要求1).软件开发方法和技术：要求学生学习和掌握软件的基本概念，软件的研制过程、软件工程概述、软件设计方法、程序结构、算法描述工具，如流程图和算法语言。2).数据结构：要求学生学习和掌握数据结构的基本概念与原理、线性表、顺序存储结构和链式存储结构、算法实现、数组、栈、队列、树等。3).操作系统：要求学生学习和掌握操作系统的基本概念与原理、操作系统提供的接口、进程与进程管理、多道程序技术、同步与互斥、内存管理、设备管理、文件系统的原理、文件的使用。4).数据库技术：要求学生学习和掌握数据库的基本概念与原理、数据模型、关系数据库。5).网络及数据安全技术：要求学生学习和掌握网络及数据安全技术的基本概念与原理。2．重点和难点1).本课程的重点：第二章数据结构。2).本课程的难点：(a)线性链表；(b)树、图的遍历；(c)查找、索引和排序技术运算及其应用。3．先修课程：计算机基础；C语言。三．课程内容1．理论知识：（22学时）1).计算机软件概述：计算机软件的基本概念、程序设计技术、数据结构的基本概念及术语、算法描述及算法分析初步。2).线性表：线性表的逻辑结构、线性表的顺序存储结构、线性表的链式存储结构、表的基本运算在特定存储结构中的实现及应用。3).栈和队列：栈的定义、表示和实现、栈的应用、队列的定义、表示和实现、队列的应用。4).树：树的定义和基本操作、二叉树定义和表示、遍历二叉树和线索二叉树、树和森林、哈夫曼树及其应用。5).串和图：串及图的定义、表示和操作、存储结构图的遍历。6).查找和排序：查找和排序及其运算的基本知识和算法。7).操作系统：学习和掌握操作系统的基本概念与原理、操作系统提供的接口、进程与进程管理、多道程序技术、同步与互斥、内存管理、设备管理、文件系统的原理、文件的使用。8).数据库：学习和掌握数据库的基本概念与原理、数据模型、关系数据库、SQL语言。9).计算机网络：学习和掌握计算机网络体系结构、网络互联与互联网、网络安全及防火墙技术、计算机病毒及防治。10).软件工程：学习和掌握软件开发与技术，要求学生学习和掌握软件的基本概念，软件的研制过程、软件工程概述、软件设计方法、程序结构、算法描述工具，如流程图和算法语言。2．课外作业：加深对课内所学的理论知识的理解，锻炼分析问题和解决问题的能力。3．上机实验：围绕本课程学习的重点和难点，实践理论知识，上机完成题目（8学时）。4．考核方式：考核成绩主要根据：学生平时听课、完成作业情况20%；上机实验、完成实验报告20%；期末考试成绩60%来综合评定。四．课程教材及主要参考书1．课程教材：[1].《计算机软件技术基础》第三版，沈被娜等编著，清华大学出版社。2．教学参考书：[1].《计算机软件技术基础》，庞丽萍编，华南理工大学出版社。[2].《OperatingSystems-DesignandImplementation》，SecondEdition,AndrewS,Tanenbaum,AlbertS.Woodhull,清华大学出版社和PRENTICEHALL.[3].《SoftwareEngineering-APractitioner’sApproach》，FourthEdition,Roger,S.Pressman,机械工业出版社和McGraw-Hill.[4].《DataStructureAlgorithms,andApplicationsinC++》，FirstEdition,SartajSahni,机械工业出版社和McGraw-Hill.第1章算法1．算法的基本概念1).算法的基本特征：(1).能行性(effectiveness)a).算法中的每一个步骤必须能够实现，例如在算法执行中，分母不能为零，实数范围内不能求一个负数的平方根等等；b).算法执行的结果要能够达到预期目的，例如需要考虑计算精度的影响。(2).确定性(definiteness)算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义性。(3).有穷性(finiteness)算法必须能在有限的时间内昨晚，计算法必须能在执行有限个步骤后终止。例如无穷级数的计算只能是根据精读要求取有限项的有穷计算；如果一个算法需要执行千万年，则失去了实用价值。(3).拥有足够的情报（sufficientinformation）通常算法中的各种运算总是要施加到各个运算的对象上，而这些对象又可能具有某种初始状态，这是算法执行的起点或依据。因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。当输入不够或输入错误时，算法本身也就无法执行或导致执行有错。一般来说，当算法拥有足够的情报时，此算法才是有效的，而当情报不够时，算法并不有效。综上所述：所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。2).算法的基本要素：(1).对数据对象的运算和操作：a).算术运算，加、减、乘、除等运算；b).逻辑运算，“与”、“或”、“非”等运算；c).关系运算，“大于”、“小于”、“等于”、“不等于”等运算；d).数据传输，主要包括赋值、输入、输出等操作；注意：计算机程序仅作为算法的一种描述；但通常不直接用计算机程序来描述算法，而是用别的描述工具（如流程图、专门的算法描述语言，甚至自然语言）来描述算法。(2).算法的控制结构：一个算法的功能不仅取决于所选用的操作，而且还与各操作之间执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。一个算法一般可以用顺序、选择、循环3种基本的控制结构组合而成。2．算法设计基本方法1).列举法：举例白鸡问题，画出搜索空间的立体示意图。2).归纳法：基本思想和本质（抽象）。3).递推法：本质（归纳法）。4).递归法：基本思想（逐层分解）；基础（归纳）。5).减半递推法：又称为分治法。“减半”是将问题的规模减半；“递推”是指重复“减半”。举例：矩阵相乘；二分法求实根。6).回溯法：基本思想（“试”），处理复杂数据结构方面有广泛应用。举例：求解皇后问题，用方格图讲解。3．算法的复杂度分析1).算法的时间复杂度：所谓算法的时间复杂度，是指执行算法所需要的计算工作量。可用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数（seepage10）。在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量：(a)平均性态（averagebehaviour）分析是指用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量（定义，seepage10）。(b)最坏情况复杂性（worst-casecomplexity）分析是指在规模为n时，算法所执行的基本运算的最大次数（上界），更具使用价值（定义，seepage10）。两者的分析比较举例（例1.5,seepages10-11）。注意：本小节最后一段的论述（提及算法的工作量与输入无关时的情况）。2).算法的空间复杂度：一般是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间，输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单元以及某种数据结构所需要的附加存储空间（例如在链式结构中，除了要存储数据本身外，还需要存储连接信息）。4．习题讲解及作业布置：举例讲解：1.1、1.3。第一次上机实验：1.2、1.4、1.5三题中任选2题（三题难度系数分别为1.0,1.0,1.2）。第2章数据结构及其运算1．数据结构的基本概念数据结构作为计算机的一门学科，主要研究以下三个方面的问题：(a).数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；(b).在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；(c).对各种数据结构进行的运算。讨论以上各问题的主要目的是为了提高数据处理的效率。所谓提高数据处理的效率，主要包括两个方面：一是提高数据处理的速度；二是尽量节省数据处理过程中所占用的计算机存储空间。1).两个实例：(a).无序表和有序表的查找效率对比；(b).学生情况登记表。1).数据结构的定义：相互有关联的数据元素的集合。(a).数据元素的含义；(b).前后件关系。(1).数据的逻辑结构：反映数据元素之间逻辑关系的数据结构。两个要素：一是数据元素的集合D；二是D上的关系R。一个数据结构可以表示为B=(D,R)。举例（seepage18）更正：page18中最后一行和page19中第一行：Di应改为Ai。(2).数据的存储结构（物理结构）：数据的逻辑结构在计算机存储空间中的存放形式。常用的存储结构：顺序；链接；索引。3).数据结构的图形表示：直观(1).需要理解的概念名词：根节点；终端结点；内部节点；(2).数据结构的基本运算：插入和删除；其它运算还有：查找分类合并分解复制和修改等。(3).数据结构中根据各数据元素之间前后件关系的复杂度，一般将数据结构分为：线性结构和非线性结构。一般来说，如果一个非空的数据结构满足两个条件：(a)有且只有一个根节点；(b)每个节点最多有一个前件，也最多只有一个后件。则称该数据结构为线性结构，又称线性表。此外：在插入或删除任何一个节点后还应该满足上述条件。2．线性表及其顺序存储结构1).线性表及其运算：(1).什么是线性表(a).需要理解的概念名词：记录；文件。(b).非空线性表的结构特征（seepage22）。(2).线性表的顺序存储结构(a).基本特点：（seepage22）。(b).初始化线性表的顺序存储空间（seepage23），new和delete语句成对使用的习惯：申请空间-释放空间。(c).线性表的主要运算：（seepage23）(3).线性表在顺序存储下的插入运算：例2.7(a).插入前后两线性表中的元素关系（seepage24）(b).平均移动元素数量的计算：(0+1+…+n)/(n+1)=(n+1)(0+n)/2/(n+1)=n/2(c).由于C++中数组下标从0开始，涉及到数组下标的变量均要减去1。(4).线性表在顺序存储下的删除运算(a).删除前后两线性表中的元素关系（seepage26）(b).平均移动元素数量的计算：(0+1+…+n-1)/n=(n)(0+n-1)/2/n=(n-1)/2更正：page26中最后一行应改为：…认为删除第(n+1)个元素，即无此元素。(5).顺序表类将顺序表的数据和基本操作（包括初始化、输出、插入和删除）封装成类。更正：page30中第二段应该为：…如果顺序表非空，则调用…2).栈及其应用：(1).什么是栈（stack）：一种特殊的线性表，其插入和删除都只在线性表的一端进行，即一端封闭，另一端开口。概念名词：栈顶（top）；栈底（bottom）；入栈（push）；退栈（pop）(2).栈的顺序存储及其运算：seepage33-34注意：程序中数组下标减一的操作。(3).顺序栈类(4).表达式的计算