公共基础知识讲课教案

　P11 第一章 数据结构与算法 一、算法 1、 算法的概念、解决实际问题时准确而完整的描述，也可以理解为一系列解决问题的指令的集合。

　2、 算法的四个特点

　可行性、执行后能够得到满意的结果。说明这个算法是可行的,

　 确定性、每一步都必须有明确的定义,不允许有模能两可的解释和多义性

　 有穷性、在有限的时间内完成,即算法执行有限的步骤后终止

　 拥有足够的情报、充分调查,获得足够的(信息)情报 3、 算法的两种基本要素

　数据对象的运算和操作

　 算法的控制结构 4、 算法的设计方法

　列举法、来解决“是否存在”或“有多少种可能”

　归纳法、通过特殊情况一般性的结论来

　递推法、从已知的初始条件中间结果或最后结果

　递归法、对问题层层分解,当解决了那些最简单的问题后,再沿层层分解的逆序过程,导出最后的结果来

　减半递推技术、对问题分而治之

　回溯法、即“试探”的方法。即找出一个解决问题的线索,然后沿着这个线索试探，若试探成功,就得到了问题的解,若试探失败，就逐步回退，回到正确的位置再向下试探 5、 算法的复杂度

　时间复杂度:算法所需要的计算工作量

　空间复杂度、执行算法所需要的内存空间

　 衡量一个算法的技术指标就是时间复杂度和空间复杂度。一个好的算法就是要求时间复杂度和空间复杂度越小越好。

　二、数据结构 1、概念:指相互有关联的数据元素的集合。逻辑结构

　 存储结构

　 运算的集合 2、逻辑结构:它反映数据元素之间的逻辑结构，它用前后件的关系来表示，根据前后件关系的复杂程度分

　线性结构

　如、B=(a,b,c,d)

　 D={a,b,c,d},R={{a,b},{b,c},{c,d}}

　 非线性结构

　如、

　 具体用 B=(D,R)来表示 3、存储结构、逻辑结构在计算机存储空间的映射。

　顺序存储

　 链式存储

　 索引存储

　 散列存储 4、线性结构、a>满足的条件

　a>第一个结点无前驱，最后一个结点无后继

　b>除 a>外的每一个结点有且仅有一个前驱和一个后继.

　b>对一个线性结构操作后，仍旧是一个线性结构

　c>优点、查找比较方便，通过计算地址可以直接找到它

　 Address(a(i)=address(a1)+(i-1)*k

　k:每个元素所占存储单元的字节数

　d>缺点、插入和删除结点时要移动大量的元素，要知道最优和最坏的情况

　e>一般采用顺序存储结构，逻辑上相邻的结点在存储结构中也是相邻的。

　 两个特例 栈

　队列

　 栈、 只有一个出入口

　特点、先进后出。

　对栈操作的过程

　入栈(push)、出栈(pop)和读栈顶元素

　 队列、一个出口，一个入口

　特点、先进先出

　 循环队列对满与对空的条件 对满、s=1,且 front=real

　对空、s=0,且 front=real=m

　m:队列的大小 5、线性链表、链表结点的组成

　数据域、存放当前结点的数据信息

　指针域、存放下一个结点的地址

　数据域 指针域

　优点、插入和删除结点时不需要移动元素

　缺点、查找必须从第一个结点开始。

　6、 非线性结构、 a>分类

　树

　图

　b>树与二叉树

　 树、a>根结点、无前驱的结点

　 b>叶子结点、无后继的结点，也就是度为零的结点。

　 c>除 a>和 b>之外的每个结点有且仅有一个前驱结点和若干个后继结点

　 d>结点的度、结点对应后继结点的个数

　 e>树的度、在一个树中，度最大的结点的度就是树的度。

　f>树的深度、树的层次数。

　 g>树是无序的

　二叉树

　 a>二叉树是有序树，它区分左右子树

　是两个完全不同的二叉树。

　b>二叉树的度为 2 c>二叉树的性质 性质 1、在二叉树的第 k 层上，最多有 2^(k-1)个结点(k>=1) 性质 2、深度为 m 的二叉树最多有 2^m-1 个结点。

　性质 3、在任意一棵二叉树中，度为零的结点数总是被度为 2 的结点数多一个. 性质 4、具有 n 个结点的二叉树，其深度至少为㏒[2n]+1 d>满二叉树与完全二叉树

　 满二叉树

　完全二叉树

　 这两个不是完全二叉树

　 满二叉树、除最末一层的结点外，其余各层都是满的。

　完全二叉树、罪最末两层外其他各层都是满的，最末两层要做到“先左后右”。

　所以满二叉树一定是一个完全二叉树，而完全二叉树并不一定是一个满二叉树.

　e>二叉树的存储结构、采用链式存储结构

　f>二叉树的遍历 按先左后右的次序

　 先序遍历

　中序遍历

　后序遍历 三、查找技术、

　 顺序查找、从第一个结点开始逐个查找的过程。

　 最坏的情况下比较 n 次。

　 适合

　无序的线性表

　线性链表

　二分法查找、适合有序的线性表

　在最坏的情况下要进行 long 2n 次比较。

　四、排序技术

　交换类排序 冒泡排序

　 快速排序

　选择类排序 简单选择排序

　 堆排序

　插入类排序 简单插入排序

　 希尔排序 排序方法 时 间 复 杂度

　 空间复杂度 复杂性

　平均情况 最坏情况 最好情况

　 直接插入排序 O(n2) O(n2) O(n) O(1) 简单 冒泡排序 O(n2) O(n2) O(n) O(1) 简单 希尔排序 O(nlong2n) O(nlong2n)

　O(1) 较复杂 快速排序 O(nlong2n) O(n2) O(nlong2n) O(nlong2n) 较复杂 直接选择排序 O(n2) O(n2) O(n2) O(1) 简单 堆排序 O(nlong2n) O(nlong2n) O(nlong2n) O(1) 较复杂 第二章

　 程序设计基础 一、程序设计经历的阶段 结构化程序设计

　面向对象的程序设计 二、良好的编程风格要注意

　 a>符号名的命名最好达到”见名知意”

　 b>添加必要的注释，注释不是可有可无的。

　 c>程序要写成锯齿状，视角效果

　 d>限制使用 goto 语句

　 e>采用三种基本的控制结构

　 f>每个控制结构或每个模块只有一个出口和一个入口. 三、结构化程序设计的原则、自顶向下、逐步求精、模块化、限制使用 goto 语句

　自顶向下：即先考虑总体,后考虑细节；先考虑全局目标,后考虑局部目标。即按功能划分为若干个基本模块,这些模块形成一个树状结构。

　逐步求精：对复杂问题，应设计一些子目标做过度，逐步细化。

　模块化：模块化是把程序要解决的总目标分解为分目标，再进一步分解为具体的小目标，把每个小目标称为一个模块

　四、面向对象的程序设计、 1、面向对象的本质：就是 主张从客观世界固有的事物出发来构造系统,强调最终建立的系统能够映射问题域。

　2、面向对象的基本概念 对象、客观存在，相互区别的事物。它是类的一个实例。它也由类产生而来.

　 类、具有共同属性、共同方法的对象的集合，它描述了属于该对象类型的所有对象的性质，而一个对象则是其对应类的一个实例。即 类是关于对象性质的描述。也像对象一样，包括一组数据性质和在数据上的一组合法操作。

　类的特点

　继承性

　封装性

　多态性

　继承、使用已有的类定义作为基础建立新类的定义技术。

　多态性、指对象根据所接受的信息而做出的动作，同样的信息被不同的对象接收时有不同行为的现象。

　消息、 实现对象之间的通讯，它统一了数据流和控制流。

　面向对象程序设计的优点、与人类习惯的思维方法一致、稳定性好、可重用性好、易于开发大型软件产品、可维护性好. 第三章

　 软件工程基础 一、软件的相关概念、 1、软件、指与计算机系统操作有关的计算机程序、规程、规则、以及可能有的文件、文档和数据. 2、软件的组成 程序、数据和文档。

　3、软件的特点

　1> 软件是逻辑产品, 而不是物理实体, 它具有无形性, 也不在磨损和消耗问题。

　 2> 没有 明显的制作过程, 其成本主要体现在软件的开发和研制上, 可进行大量的复制。

　 3> 软件的开发、运行对计算机系统具有依赖性。

　。

　 4>开发和维护成本高。

　 5>软件开发涉及诸多社会因素。

　4、软件的分类

　应用软件 系统软件 支撑软件

　应用软件、为解决特定领域的应用而开发的软件.如人力资源管理系统;财务管理系统等。

　系统软件、计算机管理自身资源,提高计算机使用效率并为计算机用户提供各种服务的软件。

　如操作系统 os、语言处理程序 汇编程序、DBMS 等等。

　 解释程序

　 编译程序

　 支撑软件、是介于两者之间，协助用户开发软件的工具性软件。

　5、软件的作用、 它是用户与硬件之间的接口,是计算机系统的指挥者,是计算机系统结构设计的重要依据。

　二、软件危机与软件工程 1、软件危机、泛指在计算机软件的开发和维护过程中所遇到的一系列严重问题，具体的说，在软件开发和维护过程中，软件危机主要表现在：

　软件需求的增长得不到满足；

　 软件开发成本和进度无法控制；

　 软件质量难以保证；

　 软件不可维护或维护程度非常低；

　 软件的成本不断提高；

　 软件开发生产率的提高赶不上硬件发展和应用需求的增长。

　总之，可以将软件危机归结为成本、质量和生产率等问题 2、软件工程、指采用工程的概念、原理、技术和方法指导软件的开发与维护，软件工程学的主要研究对象包括软件开发

　与维护的技术、方法、工具和管理等方面。

　软件工程学包含两方面的内容 1> 软件开发技术、主要有软件开发方法学、软件工具、软件工程环境 2> 软件工程管理、主要有软件管理、软件工程经济学。

　3>软件工程包括 3 个要素：方法、工具和过程。

　方法、是完成软件工程项目的技术手段。

　工具、支持软件的开发、管理、文档生成。

　过程、支持软件开发的各个环节的控制、管理。

　3、软件工程过程包含 4 种基本活动

　 P(Plan)软件规格说明。规定软件的功能及其运行时的限制。

　 D(Do):软件开发。产生满足规格说明的软件。

　  C(Check):软件确认。确认软件能够满足客户提出的要求。

　 A(Action).软件演讲。为满足客户的变更要求，软件必须在使用的过程中演讲。

　三、软件的生命周期、软件产品从提出、实现、使用维护到停止使用退役的过程。

　1、软件生命周期分为 3 个(定义、开发、运行维护)时期共 8 个阶段

　定义问题

　 软件定义期

　可行性研究

　需求分析

　 概要设计

　 详细设计

　软件开发期

　 实现

　 测试

　运行维护期

　 使用和维护

　退役 2、软件工程的原则、包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性。

　抽象、是事物最基本的特性和行为，忽略非本质细节，采用分层次抽象，自顶向下，逐层细化的办法控制软件开发过程的复杂性。

　信息隐蔽、采用封装技术，将程序模块的实现细节隐藏起来，使模块接口尽量简单。

　模块化、模块是程序中相对独立的成分，一个独立的编程单位，应有良好的接口定义，模块的大小要适中，模块过大会使模块内部的复杂性增加，不利于模块的理解和修改，也不利于模块的调试和重用，模块太小会导致整个系统表示过于复杂，不利于控制系统的复杂性。

　局部化、保证模块间具有松散的耦合关系，模块内部有较强的内聚性。

　确定性、软件开发过程中所有概念的表达应是确定、无歧义且规范的。

　一致性、程序内外部接口应保持一致，系统规格说明与系统行为应保持一致。

　完备性、软件系统不丢失任何重要成分，完全实现系统所需的功能。

　可验证性、应遵循容易检查、测评、评审的原则，以确保系统的正确性。

　四：软件开发工具与软件开发环境 1、软件开发工具：包括 需求分析工具、设计工具、编码工具、排错工具、测试工具等。

　2、软件开发环境：指支持软件产品开发的软件系统，它由 软件工具集和环境集成机制构成。

　五：结构化分析方法:

　结构化方法的核心和基础是结构化程序设计理论 1、需求分析 的任务是发现需求、求精、建模和定义需求的过程。

　1>需求分析阶段的工作

　需求分析阶段的工作可概括为 4 4 个方面：

　①需求获取； ②需求分析； ③编写需求规格说明书； ④需求审评。

　 所以 需求分析阶段产生的成果是需求规则说明书。

　2、需求分析方法

　(1)结构化分析方法

　 结构化分析方法主要包括 面向数据流的结构化分析方法、面向数据结构的 n Jackson 方法和面向数据结构的结构化数据...