《算法精解:C语言描述》note-1 数据结构和算法简介

---

《算法精解:C语言描述》这本书在讲解数据结构和算法的概念同时，使用C代码而不是伪代码来实现具体的细节，很适合刚学完C语言的人来读：既可以熟练各种用法，也能了解数据结构和算法的底层实现。

---

1 预备知识

1.1 数据结构和算法简介

数据结构简介

数据结构是组织数据的方式。
常用的数据结构有：链表、栈、队列、集合、哈希表、树、堆、优先级队列、图。
数据结构和它自身的基本操作一起，构成抽象数据类型。

数据结构的作用

1. 使算法更加高效；
2. 为解决问题提供抽象概念；
3. 接口固定，可重用；

算法简介

算法是定义良好的用来解决问题的步骤。
使用算法的好处：效率、抽象、重用性。

很多算法解决问题的思路是相同的。
算法设计的常见方法：

1. 随机法
   依据是随机数的统计特性，如快速排序算法。
2. 分治法
   分解问题，然后求解，最后合并结果。如归并排序算法。
3. 动态规划
   分解问题然后合并结果，子问题互相之间可能有关联。
4. 贪心法
   不从整体上长远考虑，而是找当下的最优解。如霍夫曼编码。
5. 近似法
   不计算最优解，仅计算出足够好的解。常用于计算成本高的问题，如推销员最短路线问题。

软件工程思想

对数据结构和算法的理解在开发软件时非常重要。
开发软件时还有其他的良好准则：

1. 模块化。隐藏和封装内部实现，仅公开使用时必要的信息。
2. 可读性。合理使用注释、标识符等。
3. 简洁性。大量研究后证明正确的算法，其形态都是最简洁的。
4. 一致性。建立并遵守编码约定。

---

1.2 指针操作

C语言的指针是构建数据结构和操作内存的高效工具。

指针基础

指针是一类变量，它不存储数据本身，而是存储数据在内存中的地址。

在编码错误时，指针有可能指向无效地址，称为悬空指针。

存储空间分配

变量在声明时，C编译器会根据变量类型预留足够的空间。

C语言声明变量时，编译器会根据变量类型预留足够的内存空间。在进入和离开一个函数或模块时可以自动分配和释放存储空间的变量称为自动变量。

使用malloc或realloc可以在运行时动态地分配存储空间。
动态分配存储空间时，可以得到一个指向一个堆存储空间的指针。该空间会一直存在，除非手动释放。
内存泄漏是指动态分配了内存空间，却从未释放它。

数据集合与指针的算数运算

C语言的数据集合包括结构和数组。结构是各种类型的有序的元素组成，数组由有序的同类元素组成。
结构不允许包含自身实例，但可以包含自身实例的指针。
数组的标识符实际上就是指向数组第一个元素的指针。数组下标表达式a[i]就等价于*(a+i)。

做为函数参数的指针

按引用传递函数参数时，如果函数改变这个参数，这个改变在函数退出后仍然存在。
而按值传递参数，对参数的改变在函数退出后就不复存在。

指针支持把参数按引用传递给函数。

泛型指针与类型转换

C语言指针的类型不能转换，但是泛型指针可以转换为任意类型的指针。

// 声明泛型指针
void* ptr;

编译器不会对泛型指针做类型检查，因此可以随意转换类型。
泛型指针必须转换为具体类型后才能访问数据。

// malloc返回泛型指针，因此需要强制转换
int* intArray = (int*)malloc(sizeof(int) * 10);

函数指针

函数指针是指向可执行代码段的信息块的指针。
函数指针可以把函数当做普通数据来存储和管理。它可以用来把函数封装到数据结构中，实现间接绑定、回调等机制和类似面向对象的多态行为，提高代码的模块化。

// 声明一个函数指针，接收两个int参数，指向返回int
int (*funcptr)(int, int);// 声明函数
int add(int a, int b) { return a + b; }// 函数地址赋给函数指针
funcptr = add;  // 或 funcptr = &add;// 通过函数指针调用函数，两种方式都可以
int result1 = funcptr(2, 8);
int result2 = (*funcptr)(4, 6);

---

1.3 递归

基本递归

递归是指函数调用自身。
程序运行时，栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用大量空间。多重递归时，大量的信息需要保存和恢复，生成和销毁也会耗费时间。此时应该采用迭代的方案来优化。

尾递归

当递归调用是整个函数体中最后执行的语句，且它的返回值不属于表达式的一部分时，就是尾递归。
尾递归的特点是在回归过程中不需要做别的操作了。因此编译器检测到一个函数调用是尾递归时，就覆盖当前的栈帧而不是创建一个新的，因为递归调用返回时这个栈帧已经没什么事情需要做了。这样可以节省很大空间。

---

1.4 算法分析

分析最坏情况

最佳情况下算法的性能没什么意义。
平均情况下的性能不容易评估。
最坏情况下的性能可以表示算法的上限。

O表示法

O表示法是最常用的表示算法性能的标记法。
它表示一个算法的增长规律，即当输入数据量变得无穷大时算法的性能趋近一个什么样的值。

O表示法类似一个关于数据量n的函数。它一般会忽略常数项和常数因子，并且只考虑高阶项的因子。如O(5)简化为O(1)，O(5n)简化为O(n)，O(n + n^2)简化为O(n^2)。

计算的复杂度

算法的复杂度与它处理数据需要的资源的增长速率相关。
算法的复杂度可以使用O表示法来计算。

常见的复杂度：

复杂度	例子
O(1)	从数据集中取第一个元素
O(lg n)	把数据集分为两半，分开的每一半再分两半，一直进行直到不可再分
O(n)	遍历一个数据集
O(nlgn)	把数据集分为两半，分开的每一半再分两半，一直进行直到不可再分。在此过程中遍历每一半数据
O(n^2)	遍历一个数据集中的每个元素，遍历每个元素时都遍历另一个数量级相同的数据集
O(2^n)	为一个数据集生成可能的所有子集
O(n!)	为一个数据集生成可能的所有排列组合

---