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模型的基本概念

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

又能相互区别的事物；

②属性：现实世界中事物均有一些特性，这些特性可以用属性来表示；

③码：唯一标识实体的属性集称为码；

④域：属性的取值范围称为该属性的域；

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

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

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

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

属性：二维表中垂直方向的列称为属性，每一列有一个属性名；

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

关系模型采用二维表来表示，二维表一般满足下面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）

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

选择：对一个关系的操作（找出相同的行）

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

除和投影：

除：是从两个表里找出相同的列，

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

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

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

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

笛卡尔积

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

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

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

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

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

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

以此类推

数据库设计与原理

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

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

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