文档库

最新最全的文档下载
当前位置:文档库 > C语言学习资料

C语言学习资料

算法一般具有4个基本特征:可行性、确定性、有穷性、拥有足够的情报。

算法的基本结构是:顺序结构、选择结构、循环结构。

算法的复杂度分为时间复杂度和空间复杂度。

时间复杂度,执行算法所需要的计算工作量(次数)。

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

数据的逻辑结构:是指反映数据元素之间逻辑关系,而与它们在计算机中的存储位置无关

数据的存储结构(物理结构):数据的逻辑结构在计算机存储空间中的存放形式,数据元素在计算机存储空间的位置关系可能与逻辑关系不同。

数据结构:线性结构(线性表、栈、队列、链表)和非线性结构(树)。

线性表:1 有且只有一个根结点,它无前件。

2 有且只有一个终端结点,它无后件。

3 其他结点,只一个前件,一个后件。

线性表的顺序存储结构特点:

1线性表中所有元素所占的存储空间是连续的;

2线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

栈:(一种特殊的线性表)只允许在一端插入,删除,改写数据。

原则为先进后出。

进栈出栈顺序。

例:进栈顺序:ABCD123

出栈顺序:321DCBA

队列:允许在一端进行插入,而另一端进行删除的线性表。

允许插入一端,尾指针。允许删除的一端,头指针。

原则为先进先出。

循环队列中元素的个数是由队头指针和队尾指针共同决定。循环队列的头指针为front,尾指针为rear,容量为maxSize,则循环队列中元素的个数是【(rear-front+maxSize) mod maxSize】。

一个容量为15的循环队列中,若头指针front=6,尾指针rear=9,则该循环队列中共有多少个元素?(3个) 若头<尾,元素个数=尾-头;若头>尾,元素个数=15+(尾-头)

线性链表:一个存储结点分为两部分。一部分用来存储数据元素的值(数据域),另一部分用来下一个数据元素的存储地址(指针域)。

线性链表是线性表的链式存储结构。用链表表示线性表的优点是便于插入和删除操作。

线性链表的存储空间不一定连续,且个元素的存储顺序是任意的

树(非线性结构)

特征:每一个结点只有一个前件,该前件称为父结点。无前件的结点,根结点。一个结点所拥有的后件个数称为该结点的度。树的最大层次称为树的深度。没有后件的结点称为叶子结点。

二叉树:

特点:1 非空的二叉树只有一个根结点。

2 每一个结点最多有两棵子树,分别左子树,右子树。

性质:1 在二叉树第K层上,最多有2k-1个结点。

2 深度为m的二叉树最多有2m-1个结点。

3 在任意一棵二叉树中,叶子结点总是比度为2的结点多一个。

4 具有n个结点的二叉树,其深度至少为(log2n)+1

满二叉树与完全二叉树

满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的k层上有2k-1个结点,且深度为

m的满二叉树有2m-1个结点。

完全二叉树是指这样的二叉树:除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。

5具有n个结点的完全二叉树,其深度为(log2n)+1

6 设完全二叉树有n个结点,进行编号,取其中一个结点为k,

(1)若k=1,说明该结点为根结点,若k> 1,则该结点的父结点编号为INT(k/2)。

(2)若2k<=n,则编号为k的结点的左子结点编号为2k。

(3)若2k+1<=n,则编号为k的结点的右子结点编号为2k+1。

二叉树的遍历:

前序遍历:根→前序遍历左子树→前序遍历右子树

中序遍历:中序遍历左子树→根→中序遍历右子树

后序遍历:后序遍历左子树→后序遍历右子树→根

最坏情况下,顺序查找需要比较n次,二分查找有序线性表需要比较log2n次。

最坏情况下,冒泡排序,插入排序,简单排序需要比较n(n-1)/2次。

最坏情况下,希尔排序法,最坏情况需要O(n1.5 ) 次。

最坏情况下,堆排序法,O(nlog2n)次。

相比以上几种(除希尔排序法外),堆排序法的时间复杂度最小。

程序设计基础:

结构化程序设计的原则:1.自顶向下 2.逐步求精 3.模块化 4.限制使用goto语句

结构化程序设计主要强调程序的易读性

良好的程序设计风格是程序应简单、清晰、可读性好

对象的基本特点:1.标识的惟一性 2.分类性 3.多态性 4.封装性 5.模块独立性好

类是具有共同属性,共同方法的对象的集合。

消息是实例之间传递的信息,它请求对象执行某一处理或回答某一要求的信息,它统一数据流和控制流。一个消息由三部分组成:接收消息的对象的名称、消息标识符(消息名)和零个或多个参数。

继承分为单继承与多重继承。单继承是指,一个类只允许有一个父类,即类等级为树形结构。多重继承是指,一个类允许有多个父类。

多态性是对象根据所接受的消息而做出动作,同样的消息被不同的对象接受时可导致完全不同的行动。在面向对象方法中,信息隐蔽是通过对象的封装性来实现的

软件工程基础

软件工程包括3个要素,即方法,工具和过程。

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

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

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

软件生命周期分为软件定义,软件开发及软件运行维护三个阶段。

软件定义期:包括问题定义、可行性研究和需求分析3个阶段;

软件开发期:包括概要设计、详细设计、实现和测试4个阶段;

运行维护期:即运行维护阶段。

软件生命周期的主要活动阶段:可行性分析、需求分析、软件设计、软件实现、软件测试、运行和维护。常见的需求分析方法(1)结构化分析方法---主要包括面向数据流的结构化分析方法SA;

面向数据结构的Jackson方法JSD;

面向数据结构的结构化数据系统开发方法DSSD。

(2)面向对象的分析方法OOA

结构化分析方法工具---(1)数据流图DFD,记住DFD图的几个符号:

(2)数据字典DD

(3)判定树

(4)判定表

程序结构图(SC),N-S图,问题分析图(PAD)

程序流程图(PFD)的几个符号:

从技术观点上看,软件设计包括软件结构设计、数据设计、接口设计、过程设计。

从工程管理角度来看,软件设计分两步完成:概要设计和详细设计。

软件工程的原则:抽象,信息隐蔽,模块化,局部化,确定性,一致性,完备性和可验证性。

软件需求规格说明书的作用:

1.便于用户,开发人员进行理解和交流。

2.反映出用户问题的结构,可以作为软件开发工作的基础和依据。

3.作为确认测试和验收的依据。

内聚性是模块内部的联系,耦合性模块之间的相互联系的紧密程度。

一个优秀的软件设计,应尽量做到高内聚低耦合。

典型的数据流类型有两种:变换型和事务型。

软件测试的目的:为了发现错误而执行程序的过程。

软件测试方法:白盒测试和黑盒测试。

白盒测试法也称为结构测试或逻辑驱动测试。白盒测试是在程序内部进行,主要用于完成软件内部操作的验证。

黑盒测试法也称功能测试或数据驱动测试。黑盒测试完全不考虑程序内部的逻辑结构和内部特性,只依据程序的需求和功能规格说明,检查程序的功能是否符合它的功能说明。

软件测试过程分4个步骤,即单元测试、集成测试、验收测试和系统测试。

程序的调试:其任务是诊断和改正程序中的错误。调试主要在开发阶段进行。

程序调试的基本步骤:

1.错误定位。从错误的外部表现形式入手,研究有关部分的程序,确定程序中出错位置,找出错误的

内在原因;

2.修改设计和代码,以排除错误;

3.进行回归测试,防止引进新的错误。

程序的调试主要方法有:强行排错法、回溯法和原因排除法3种。

数据库设计基础

数据库:是数据的集合,具有统一的结构开式并存放于统一的在统一的介质内

数据库管理系统是数据库的机构,它是一种系统软件,负责数据库中的数据组织、数据操作、数据维护、控制及保护和数据服务等。

DBS包括DB和DBMS。完整讲,数据库系统DBS由数据库DB、数据库管理系统DBMS、数据库管理员DBA、硬件平台和软件平台组成。

数据库系统减少了数据冗余;数据库管理系统是数据库系统的核心。

数据库管理系统提供相应的数据语言:数据定义语言、数据操纵语言、数据控制语言。

数据管理技术的发展经历了 3个阶段:人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是数据库系统

数据库系统的3 级模式:①概念模式,也称逻辑模式②外模式,外模式也称子模式③内模式,内模式又称物理模式

内模式处于最底层,它反映了数据在计算机物理结构中的实际存储形式,概念模式处于中间层,它反映了设计者的数据全局逻辑要求,而外模式处于最外层,它反映了用户对数据的要求。

数据模型从抽象层次上描述了数据库系统的静态特征、动态行为和约束条件,因此数据模型通常由数据结构、数据操作及数据约束三部分组成。

数据模型:层次,网状,关系

E-R模型的基本概念

C语言学习资料

①实体:现实世界中的事物可以抽象成为实体,实体是概念世界中的基本单位,它们是客观存在的且

又能相互区别的事物;

②属性:现实世界中事物均有一些特性,这些特性可以用属性来表示;

③码:唯一标识实体的属性集称为码;

④域:属性的取值范围称为该属性的域;

⑤联系:在现实世界中事物间的关联称为联系。

两个实体集间的联系实际上是实体集间的函数关系,这种函数关系可以有下面几种:

一对一的关系、一对多或多对一关系、多对多关系。

关系模型采用二维表来表示,表中的每一行,元组

属性:二维表中垂直方向的列称为属性,每一列有一个属性名;

域:属性的取值范围,也就是不同元组对同一属性的取值所限定的范围。

关系模型采用二维表来表示,二维表一般满足下面7个性质:

①二维表中元组个数是有限的_元组个数有限性;

②二维表中元组均不相同_元组的唯一性;

③二维表中元组的次序可以任意交换_元组的次序无关性;

④二维表中元组的分量是不可分割的基本数据项_元组分量的原子性;

⑤二维表中属性名各不相同_属性名唯一性;

⑥二维表中属性与次序无关,可任意交换_属性的次序无关性;

⑦二维表属性的分量具有与该属性相同的值域_分量值域的统一性。

关系模型有插入,删除,修改和查询四种操作。

关系代数

◆在交、差、投影中,不改变关系表中的属性个数但是能减少元组个数的是【交】运算。

关系运算的规则(下面介绍的7种运算,考试的时候一般会考察一种,都要背)

(1)并运算R∪S:并运算是两个表行上的合并,重复的行只出现一次。

(2)交运算R∩S:交运算是选出两个表中的公共行。

(3)差运算R-S:差运算是从表R中,删除R与S中都出现过的行。

(4)选择运算:选出二维表【部分的行】称为选择运算。

(5)投影运算:选出二维表【部分的列】称为投影运算。

(6)连接运算:根据两个表的共同属性的值,将它们连接起来,无需去除共同属性。如果去掉了重复属性,就称为自然连接。

(7)笛卡尔乘积:将关系R中的每一行依次与关系S中的每一行进行排列组合。

注意:除了选择运算和投影运算操作的是单个表之外,其余的元算都需要两个表(两个关系)。其中,并运算、交运算和差运算要求两个关系R与S要具有相同个数的属性

设有

则R和S能进行交集(RnS)、并集(RuS)、差操作(R-S)

C语言学习资料

C语言学习资料

如果R和S的元不同的话,则R和S只能进行笛卡尔集(RXS)和自然连接

选择:对一个关系的操作(找出相同的行)

是从一个表中找出满足条件的一个表,所以给的是两个表,一个表加一个结果表。

C语言学习资料

除和投影:

C语言学习资料

除:是从两个表里找出相同的列,

所以给的是三个表,二个表加一个结果表

投影:是从一个表中找出满足条件的列,所以给的是两个表,一个表加一个结果表。

C语言学习资料

自然连接:自然连接是将相同列值相等的进行连接

C语言学习资料

乘是不管是否相等,全部连接

C语言学习资料

笛卡尔积

C语言学习资料

是R图的第一行加上S图的第一行

是R图的第一行加上S图的第二行

是R图的第一行加上S图的第三行

是R图的第二行加上S图的第一行

是R图的第二行加上S图的第二行

是R图的第二行加上S图的第三行

以此类推

数据库设计与原理

数据库设计中有两种方法,面向数据的方法和面向过程的方法:

面向数据的方法是以信息需求为主,兼顾处理需求;面向过程的方法是以处理需求为主,兼顾信息需求。由于数据在系统中稳定性高,数据已成为系统的核心,因此面向数据的设计方法已成为主流。

数据库设计目前一般采用生命周期法,即将整个数据库应用系统的开发分解成目标独立的若干阶段。它们是:需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段和进一步修改阶段。在数据库设计中采用前4个阶段。