引言
计算机解决具体问题的步骤如下：
- 从具体问题中抽象出一个适当的数学模型
- 设计一个求解该数学模型的算法
- 用某种计算机语言编写实现该算法的程序，调试和运行程序直到问题得到解决。
注：
- 原始数据：实际问题中的数据
- 逻辑结构：原始数据之间按照逻辑关系组织起来，人为因素大
- 存储结构：原始数据实实在在在计算机中是如何存储的
此处可以以一个人处理有经验事情拿来类比，首先再次处理已经处理过的事情我们会先思考上回我们是这么做的（模型），这回我该怎么做（算法），付诸实践（编写程序直到解决）；原始数据可以理解为该问题本身如：我要去办一个XXX证书，我需要XXX做；逻辑结构就是我的这些申请材料应该给XXX，存储结构就是我的这些申请材料实际给了XXX（理想与现实的差别）
基本概念和术语
数据、数据元素和数据项
- 数据：所有被计算机存储、处理的对象
- 数据元素：数据的基本单位，数据元素通常简称为元素
- 数据项：数据元素的组成部分，是不可分割的最小标识单位；在数据库中又称为字段或域
下面以二维表为例，具体解释：
- 一行即是一个数据元素；即827这一行数据代表一个数据元素
- 一行中的每一列都是一个数据元素；即单827一个单元格代表一个数据项
- 整张表代表数据；
数据的逻辑结构
- 数据的逻辑结构是指数据之间的逻辑关系（数据元素之间的关联方式或“邻接方式”）
- 四类基本结构如下图所示：
- 集合：组织形式松散，两个结点之间没有邻接关系
- 线性结构：结点按逻辑关系依次排列形成“链”，结点之间一个一个依次邻接
- 树形结构：分支、层次
- 图：任何两个结点都可以邻接，最复杂
数据的存储结构（物理结构）
- 数据的存储结构定义：数据的逻辑结构在计算机中的实现
- 存储结构包括：
- 存储数据元素（存）
- 数据元素之间的关联方式（怎么存）
- 存储方式举例：
- 顺序存储方式：所有结点存储在一个连续的存储区里，利用结点在存储器的相对位置来表达数据元素之间的逻辑关系
- 链式存储方式：除数据元素外还有一个指针，每个指针指向下一个与本结点有逻辑关系的结点
注： 顺序和链式最常用，除了上述两种，还有索引存储方式和散列存储方式
- 存储结构的描述
- 机器级：讨论存储结构在计算机存储器里的表现形式，直接以内存地址来描述存储结构
- 语言级：用程序设计中的类型说明，变量说明等手段来描述存储结构；如数组、结构体和指针等
运算
注：基本运算包括：建立、查找、读取、插入和删除等
算法及描述
C语言基本语法：
- 函数描述形式
函数类型 函数名（函数参数表）
//算法说明
{
语句序列
}
- 输入、输出语句
//输入
scanf(格式串,变量1,...,变量n);
//输出
printf(格式串,变量1,...,变量n);
- 赋值语句
变量名=表达式
- 选择语句
//if
if(表达式) 语句;
//if ...else...
if(表达式) 语句;
else 语句;
//switch
switch
{
case 条件1：语句序列;break;
......
default: 语句序列;
}
- 循环语句
//for
for(赋初值表达式序列;条件;修改表达式序列)语句;
//while
while(条件) 语句;
//do...while
do
{
语句;
}while(条件);
- 结束语句
//函数结束
return 表达式;
//case结束
break;
//异常结束语句
exit(异常代码);
- 出错语句
error("错误描述")
- 注释
单行注释：//注释内容
多行注释：/* 注释内容 */
算法分析
评价算法好坏的因素：
- 正确性：能正确实现预定的功能，满足具体问题的需要
- 易读性：易于阅读、理解和交流，便于调试、修改和扩充
- 健壮性：即使输入非法数据，算法也能适当的做出反应或处理，不会产生预料不到的结果
- 时空性：该算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法所需要的存储量
时间复杂度
- 时间复杂度常见阶数：常数阶O（1）——与输入规模无关；对数阶O（log n）、线性阶O（n）、多项式阶O（n）、指数阶O（C）;其中C为大于1的正整数
- 具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的
- 最坏时间复杂度：对于相同输入数据量的不同输入数据，算法时间用量的最大值
- 平均时间复杂度：对所有相同输入数据量的各种不同输入数据，算法时间用量的平均值
- 时间复杂度的计算看下图（由C知道支持）：
空间复杂度
- 空间复杂度：由程序代码所占用的空间、输入数据所占用的空间、辅助变量所占用的空间组成，一般只需分析辅助变量占用的空间即可
- 算法f1、f2均是实现逆置的算法
- 算法f1仅需2个辅助变量i，temp；与问题规模无关，空间复杂度为O（1）
- 算法f2所需辅助变量为1个i和n为100的数组，与问题规模相关），空间复杂度为O（n）
牛刀小试
- 在一般情况下，一个算法的时间复杂度是______的函数
- 下列算法的时间复杂度T（n）=______
for(i=1;j<=n;i++)
{
k++;
for(j=1;j<=n;j++)
m+=k;
}
- 与数据元素本身的形式、内容、相对位置、个数无关的是数据的_____