数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。
算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。
一般有以下几种常用运算：
- 检索：检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
- 插入：往数据结构中增加新的节点。
- 删除：把指定的结点从数据结构中去掉。
- 更新：改变指定节点的一个或多个字段的值。
- 排序：把节点按某种指定的顺序重新排列。例如递增或递减。
递归算法：是一种直接或者间接地调用自身的算法。在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归过程一般通过函数或子过程来实现。
递归算法的实质：是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数(或过程)来表示问题的解。
递归算法解决问题的特点：
- 递归就是在过程或函数里调用自身。
- 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
- 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
- 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序。
下面来详细分析递归的工作原理。
先看看C语言中函数的执行方式，需要了解一些关于C程序在内存中的组织方式：
堆的增长方向为从低地址到高地址向上增长，而栈的增长方向刚好相反（实际情况与CPU的体系结构有关）。
当C程序中调用了一个函数时，栈中会分配一块空间来保存与这个调用相关的信息，每一个调用都被当作是活跃的。
栈上的那块存储空间称为活跃记录或者栈帧。
栈帧由5个区域组成：输入参数、返回值空间、计算表达式时用到的临时存储空间、函数调用时保存的状态信息以及输出参数，参见下图：
栈是用来存储函数调用信息的绝好方案，然而栈也有一些缺点：
栈维护了每个函数调用的信息直到函数返回后才释放，这需要占用相当大的空间，尤其是在程序中使用了许多的递归调用的情况下。
除此之外，因为有大量的信息需要保存和恢复，因此生成和销毁活跃记录需要消耗一定的时间。
我们需要考虑采用迭代的方案。幸运的是我们可以采用一种称为尾递归的特殊递归方式来避免前面提到的这些缺点。
例题1：计算n！计算n的阶乘，数学上的计算公式为：
n！=n×(n-1)×(n-2)……2×1
使用递归的方式，可以定义为：
以递归方式实现阶乘函数的实现：
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
int main(void)
{
int sumInt = fact(3);
printf("3的阶乘为：%d\n", sumInt);
system("PAUSE");//结束不退出
}
//递归求阶乘
int fact(int n) {
if (n < 0)
return 0;
else if (n == 0 || n == 1)
return 1;
else
return n * fact(n - 1);
}
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
void main(void)
{
printf("%d \n", fibonacci(10));
system("PAUSE");//结束不退出
}
//斐波那契数列，第一二项为1；后面的每一项为前两项之和
int fibonacci(int a){
if (a == 1 || a == 2)
{
return 1;
}
else{
return fibonacci(a - 1) fibonacci(a - 2);
}
}例题3：递归将整形数字转换为字符串
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
void main(void)
{
char str[100];
int i;
printf("enter a integer:\n");
scanf("%d", &i);
toString(i, str);
puts(str);
system("PAUSE");//结束不退出
}
//递归将整形数字转换为字符串
int toString(int i, char str[]){
int j = 0;
char c = i % 10 '0';
if (i /= 10)
{
j = toString(i, str) 1;
}
str[j] = c;
str[j 1] = '\0';
return j;
}例题4：汉诺塔
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
//递归汉诺塔
void hanoi(int i, char x, char y, char z){
if (i == 1){
printf("%c -> %c\n", x, z);
}
else{
hanoi(i - 1, x, z, y);
printf("%c -> %c\n", x, z);
hanoi(i - 1, y, x, z);
}
}
void main(void)
{
hanoi(10, 'A', 'B', 'C');
system("PAUSE");//结束不退出
}例题5：猴子吃桃
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
//猴子吃桃，每天吃一半再多吃一个，第十天想吃时候只剩一个
int chitao(int i){
if (i == 10){
return 1;
}
else{
return (chitao(i 1) 1) * 2;
}
}
void main(void)
{
printf("%d", chitao(5));
system("PAUSE");//结束不退出
}例题6：N皇后问题
#define _CRT_SECURE_NO_WARNINGS //避免scanf报错
#include <stdio.h>
/*======================N皇后问题========================*/
#define N 100
int q[N];//列坐标
//输出结果
void dispasolution(int n)
{
static int count = 0;
printf(" 第%d个解:", count);
for (int i = 1; i <= n; i )
{
printf("(%d,%d) ", i, q[i]);
}
printf("\n");
}
//判断位置(i,j)能否放皇后
int place(int i, int j)
{
//第一个皇后总是可以放
if (i == 1)
return 1;
//其他皇后不能同行，不能同列，不能同对角线
int k = 1;
//k~i-1是已经放置了皇后的行
while (k < i)
{
if ((q[k] == j) || (abs(q[k] - j) == abs(i - k)))
return 0;
k ;
}
return 1;
}
//放置皇后
void queen(int i, int n)
{
if (i > n)dispasolution(n);
else
{
for (int j = 1; j <= n; j )
{
if (place(i, j)==1)
{
q[i] = j;
queen(i 1, n);
}
}
}
}
int main()
{
queen(1, 4);
system("PAUSE");//结束不退出
}2、排序算法
冒泡排序：排序是程序设计中常做的操作，初学者往往只知道冒泡排序算法，其实还有很多效率更高的排序算法，比如希尔排序、快速排序、基数排序、归并排序等。
不同的排序算法，适用于不同的场景，本章最后从时间性能，算法稳定性等方面，分析各种排序算法。
排序算法，还分为内部排序算法和外部排序算法，之间的区别是，前者在内存中完成排序，而后者则需要借助外部存储器。
这里介绍的是内部排序算法。
起泡排序，别名“冒泡排序”，该算法的核心思想是将无序表中的所有记录，通过两两比较关键字，得出升序序列或者降序序列。
例如，对无序表{49，38，65，97，76，13，27，49}进行升序排序的具体实现过程如图 1 所示：
