一、基本概念和术语

1.1 数据、数据元素、数据项和数据对象

数据：是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。

1.2 数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

1.2.1 逻辑结构

数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看做是从具体问题抽象出来的数学模型。

数据的逻辑结构有两个要素，一是数据元素；二是关系。关系是指数据元素间的逻辑关系，根据数据元素之间关系的不同特性，通常有四类基本结构。

1. 集合结构
   数据元素之间除了“属于同一集合”的关系外，别无其他关系。
   

2. 线性结构
   数据元素之间存在一对一的关系。
   

3. 树结构
   数据元素之间存在一对多的关系。
   

4. 图结构或网状结构
   数据元素之间存在多对多的关系。
   
   其中集合结构、树结构和图结构都属于非线性结构。
   线性结构包括线性表、栈和队列、字符串、数组、广义表。
   非线性结构包括树和二叉树、有向图和无向图。
   

1.2.2 存储结构

数据对象在计算机中的存储表示称为数据的存储结构，也成为物理结构。

把数据对象存储到计算机时，通常要求既要存储个数据元素的数据，又要存储数据元素之间的逻辑关系，数据元素在计算机内用一个结点来表示。数据元素在计算机中有两种基本的存储结构，分别是顺序存储结构和链式存储结构。

1. 顺序存储结构
   顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。
2. 链式存储结构
   链式存储结构无需占用一整块的存储空间，但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址，所以链式存储结构通常借助于程序设计语言的指针类型来描述。

1.3 数据类型和抽象数据类型

1.3.1 数据类型

数据类型是高级程序设计语言中的一个基本概念，数据类型和数据结构的概念密切相关。

一方面，在程序设计语言中，每一个数据都属于某种数据类型。类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算，数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

1.3.2 抽象数据类型

抽象数据类型一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

抽象数据类型的定义格式如下：

ADT 抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名
1
2
3
4
5

其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式为：

基本操作名（参数表）
	初始条件：<初始条件描述>
	操作结构：<操作结果描述>
1
2
3

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以“&”打头，除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若初始条件为空，则省略。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

二、抽象数据类型的表示与实现

（1）预定义常量及类型

//函数结果状态代码
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status是函数返回值类型，其值是函数结果状态代码
typedef int Status;
1
2
3
4
5
6

（2）数据结构的表示（存储结构）用类型定义（typedef）描述；数据元素类型约定为ElemType，由用户在使用该数据类型时自行定义。

（3）基本操作的算法都用如下格式的函数来描述：

函数类型 函数名（函数参数表）
{
	//算法说明
	语句序列
}//函数名
1
2
3
4
5

当函数返回值为函数结果状态代码时，函数定义为Status类型。为了便于描述算法，除了值调用方式外，增加了C++语言引用调用的参数传递方式。在形参表中，以“&”打头的参数即为引用参数。传递引用给函数与传递指针的效果是一样的，形参裱花实参也发生变化，但引用使用起来比指针更加方便、高效。

（4）内存的动态分配与释放
使用new和delete动态分配和释放内存空间；

• 分配空间：指针变量=new数据类型；
• 释放空间：delete指针变量；

（5）赋值语句：

• 简单赋值：变量名=表达式;
• 串联赋值：变量名1=变量名2=…=变量名n=表达式；
• 成组赋值：（变量名1，…，变量名n）=（表达式1，…，表达式n）；
• 结构赋值：结构名1=结构名2
  结构名2=（值1，值2，…值n）；
• 条件赋值：变量名=条件表达式？表达式T：表达式F；
• 交换赋值：变量名1<–>变量名2；

（6）选择语句：
条件语句1 if (表达式)语句;
条件语句2 if (表达式)语句; else 语句;
开关语句

switch (表达式){
	case 值1; 语句序列1; break;
	case 值2; 语句序列2; break;
	...
	case 值n; 语句序列n; break;
	default; 语句序列n+1;
}
1
2
3
4
5
6
7

（7）循环语句：

• for语句 for（表达式1；条件；表达式2）语句；
• while语句 while（条件）语句；
• do-while语句 do{语句序列}while（条件）；

（8）结束语句：
函数结束语句

return 表达式；
return；
case或循环结束语句break；
异常结束语句exit（异常代码）；
1
2
3
4

（9）输入输出语句使用C++流式输入输出的形式：
输入语句 cin>>变量1>>…>>变量n；
输出语句 cout<<表达式1<<...<<表达式n；

（10）基本函数：
求最大值 Max（表达式1，...，表达式n）
求最小值 Min（表达式1，...，表达式n）

三、算法和算法分析

3.1 算法的定义及特性

算法是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性：

1. 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
2. 确定性。对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，使算法的执行者或阅读者都能明确其含义及如何执行。
3. 可行性。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
4. 输入。一个算法有零个或多个输入。
5. 输出。一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。

3.2 评价算法优劣的基本标准

1. 正确性
2. 可读性
3. 健壮性
4. 高效性

3.3 算法的时间复杂度

时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

//常量阶O（1）
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

//线性阶O(n)
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

//对数阶O(logN)
int i = 1;
while(i<n)
{
    i = i * 2;
}

//线性对数阶O(nlogN)
for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

//平方阶O(n²)
for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

// O（m*n）
for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

3.4 算法的空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

//空间复杂度O（1）
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

//空间复杂度O（n）
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14