公共基础知识讲课教案

本文格式为Word版，下载可任意编辑——公共基础知识讲课教案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、线性布局、agt;得志的条件

agt;第一个结点无前驱，结果一个结点无后继

bgt;除agt;外的每一个结点有且仅有一个前驱和一个后继.

bgt;对一个线性布局操作后，如故是一个线性布局

cgt;优点、查找对比便当，通过计算地址可以直接找到它

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

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

dgt;缺点、插入和删除结点时要移动大量的元素，要知道最优和最坏的处境

egt;一般采用依次存储布局，规律上相邻的结点在存储布局中也是相邻的。

两个特例栈

队列

栈、只有一个出入口

特点、先进后出。

对栈操作的过程

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

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

特点、先进先出

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

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

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

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

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

数据域指针域

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

缺点、查找务必从第一个结点开头。

6、非线性布局、agt;分类

树

图

bgt;树与二叉树

树、agt;根结点、无前驱的结点

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

cgt;除agt;和bgt;之外的每个结点有且仅有一个前驱结点和若干个后继结点

dgt;结点的度、结点对应后继结点的个数

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

fgt;树的深度、树的层次数。

ggt;树是无序的

二叉树

agt;二叉树是有序树，它区分左右子树

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

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

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

满二叉树

完全二叉树

这两个不是完全二叉树

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

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

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

egt;二叉树的存储布局、采用链式存储布局

fgt;二叉树的遍历按先左后右的次序

先序遍历

中序遍历

后序遍历三、查找技术、

依次查找、从第一个结点开头逐个查找的过程。

最坏的处境下对比n次。

适合

无序的线性表

线性链表

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

在最坏的处境下要举行long2n次对比。

四、排序技术

交换类排序冒泡排序

快速排序

选择类排序简朴选择排序

堆排序

插入类排序简朴插入排序

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

空间繁杂度繁杂性

平均处境最坏处境最好处境

直接插入排序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)较繁杂其次章

程序设计根基一、程序设计体验的阶段布局化程序设计

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

agt;符号名的命名最好达成'见名知意'

bgt;添加必要的解释，解释不是可有可无的。

cgt;程序要写成锯齿状，视角效果

dgt;限制使用goto语句

egt;采用三种根本的操纵布局

fgt;每个操纵布局或每个模块只有一个出口和一个入口.三、布局化程序设计的原那么、自顶向下、逐步求精、模块化、限制使用goto语句

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

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

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

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

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

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

类的特点

继承性

封装性

多态性

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

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

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

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

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

3、软件的特点

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

2gt;没有明显的制作过程,其本金主要表达在软件的开发和研制上,可举行大量的复制。

3gt;软件的开发、运行对计算机系统具有凭借性。

。

4gt;开发和维护本金高。

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

4、软件的分类

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

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

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

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

解释程序

编译程序

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

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

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

软件需求的增长得不到得志；

软件开发本金和进度无法操纵；

软件质量难以保证；

软件不成维护或维护程度分外低；

软件的本金不断提高；

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

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

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

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

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

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

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

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

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

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

D(Do):软件开发。产生得志规格说明的软件。

C(Check):软件确认。确认软件能够得志客户提出的要求。

A(Action).软件演讲。为得志客户的变更要求，软件务必在使用的过程中演讲。

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

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

定义问题

软件定义期

可行性研究

需求分析

概要设计

细致设计

软件开发期

实现

测试

运行维护期

使用和维护

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

抽象、是事物最根本的特性和行为，疏忽非本质细节，采用分层次抽象，自顶向下，逐层细化的手段操纵软件开发过程的繁杂性。

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

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

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

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

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

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

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

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

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