第一章数据结构与算法

二级公共基础知识

算法的基本特征如下：

（1）可行性： 步骤可以执行，且执行结果达到预期的目的。
（2）确定性： 步骤明确，不准有多义性。
（3）有穷性： 在有限的时间里完成。
（4）拥有足够的情报： 算法在拥有足够的输入信息和初始化信息时，才是有效的；当提供的情报不足时，算法可能无效。

算法的复杂度：

算法的复杂度是用来衡量算法的优劣，它包括算法的 时间复杂度 和算法的 空间复杂度 。

时间复杂度： 指执行算法所需要的计算工作量（计算的次数），但是算法的时间复杂度不等于算法程序执行的计算工作量。

空间复杂度： 指执行这个算法所需要的内存空间。

顾名思义，数据结构是指互相有关联的数据元素的集合，它包含两个要素，即 “数据” 和 “结构” 。

数据： 需要处理的数据元素的集合，这些元素具有某个共同特征。

结构： 所谓结构，就是关系，集合中的各个数据元素之间存在着某种关系（联系）。

数据结构分为数据的逻辑结构和数据的存储结构。数据的逻辑结构指反映数据元素之间逻辑关系的数据结构。数据的存储结构又称为数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式。

”数据的逻辑结构的数学形式定义 ———— 数据结构“

是一个二元组：B = (D,R)

其中，B表示数据结构，D是数据元素的集合，R是D上关系的集合，它反映了D中个数据元素之间的前后件关系，前后件关系也可以用一个二元组来表示。

1.结构化程序的基本原则
1.自顶而下：由总到小，由全局到局部;
2.逐步求精：由复杂到逐步细化;
3.模块化：由总目标分成小目标、小模块;
4.限用 goto语句.

各种排序的消耗情况
例：(当然不仅仅这么多，在这就只举这几个例子)

面向对象
也有许多概念最好记住的，
比如四个特征：抽象性、封装性、继承性、多态性

取模运算%

// 异号取模：
if |x|>|y|
return x+y ;
else
x;

// 同号取模：
if |x|>|y|
return x-y;
else
x;

7.switch语句应该注意的事
default语句，不用注意位置，switch会先看case语句;
注意break的有无;
switch()的括号内，不能用浮点数、long型、字符串
可以是整数、字符、枚举

8.strlen()与sizeof()
strlen()里’\0’不占用字符长度的
sizeof()里’\0’是占用内存空间的

9.return应该注意的
1）允许多个return在一个函数里，但是一次只可以返回一个
2）void类型，不允许使用return和从此函数获得返回值
3）没有return语句的函数在执行到函数的最后一条语句后会自动返回调用处

10.二叉树的结点公式
叶子结点总是比度为2的结点多一个
公式：(数字表示度的值,n表示总结点数)
n0 = n2 + 1
n = n0 + n1 + n2

11.程序调试任务
诊断和改正程序中的错误

12.数据库
数据库在需求分析阶段建立数据字典

13.软件过程
软件过程不规范不属于软件危机表现

14.PAD图和DFD图
PAD图：问题分析图，软件详细设计表示工具
DFD图：数据流图，程序设计不会使用这个图

15.字符串
字符串要用“”双引号定义，并且字符型数组存放

16.c语言
c语言中只有字符串常量，而没有字符串变量

17.feof
feof是用输入流读取数据，若到文件末尾(文件结束符)，返回值为非0值，否则则为0.