数据结构C语言基本概念

算法：一组完成特定任务的有穷指令序列
输入、输出、确定性、有限性、有效性。

递归：函数调用其自身，或者函数调用其他函数，而这个函数又调用了主调函数（间接递归）。
1）构造递归调用终止的边界条件
2）实现递归调用，使得每次递归调用都能够向最终解逼近。
例：二分查找递归

int binsearch(int list[],int searchnum,int left,int right)
{
    int middle;
    if(lest<=right)
    {
        middle=(left+right)/2;
        switch(COMPARE(list[middle]),searchnum){
        case -1:return binsearch(list,searchnum,middle+1,right);
        case 0:return middle;
        case 1:return binsearch(list,searchnum,left,middle+1);}
    }
    return -1;
}

典型递归：阶乘，二项式系数，霍纳规则，斐波那契数列，Aekerman函数，Hanoi塔等。

数据类型：是一个对象集合和一组在这些对象上的操作的总和。
抽象数据类型：是一个数据类型，其数据对象和对象上的操作的规格说明独立于对象的存储表示和对象上操作的实现。

算法的性能分析：
性能分析：时间、空间
空间复杂性：程序从开始执行到完成所需的存储空间的数量。
S（P）=c+Sp(I)
c:固定空间需求，不依赖于程序输入、输出数量和大小的空间需求。
Sp(I):程序P在实例I上所需的可变存储空间。
时间复杂性：程序从开始执行到完成所需的计算时间。
由为程序所编写的函数所需的执行步数确定。分三种请况：最好情况下的程序步数，最坏情况下的程序步数和平均情况下的程序步数。
采用大O记号：
O(1)：常数阶
O(n)：线性阶
O(logn)：对数阶
O(n2)：平方阶
O(n3)：立方阶
O(2n)：指数阶
O(1)