1.数据结构的基本概念(抓大放小)

1)基本概念

数据、数据元素(如一个账号)、数据项(密码、昵称)、数据结构(具有关系的一组数据元素集合,联想汉字的结构其实就是具有布局关系的符号组合)、数据对象(具有相同性质的数据元素的集合、一家海底捞的排队信息可以看作数据结构、全国所有门店排队信息看做同一个数据对象,它们虽无直接关系,但是具有同样的联系)

2)数据结构的三要素

逻辑结构、物理结构、数据运算

逻辑结构:集合、线性、树、图

物理结构:顺序存储、链式存储、索引存储(在存储数据的同时建立一张索引表,索引表中一般存放唯关键字+地址,比如海底捞中每个人取一个号)、散列存储(由关键字计算出其存储位置)。顺序存储数据是连续的,非顺序存储数据是离散的。数据存储的物理结构影响:增删与查找的便利度

数据运算的定义由逻辑结构定义,由物理结构实现。

3)数据类型、抽象数据类型

数据类型:一组同类型数据+操作,比如int类型数据,可以+-*/,比如boolean类型,可以与或非操作。

数据类型分类:原子类型、结构类型(结构体)

抽象数据类型:抽象数据组织及其操作,即定义一个理论的数据类型,讨论其元素的逻辑关系,不讨论其实际物理结构。

2.算法的基本概念

1)什么是算法

程序=数据结构+算法,数据结构把现实生活中的信息存储到了计算机中,算法提供了解决实际问题的方法。比如海底捞的顾客排队信息用数据结构存储到了计算机中,那怎么实现vip插队就由算法来实现。

2)算法的五大特性

有穷性(程序可以无穷,比如海底捞排队系统只要不关机就一直运行)、确定性(无二义)、可行性(可由基本运算执行有限次实现)、0个或多个输入、1个或多个输出

3)“好算法”的特点

正确性(能够正确解决问题)、可读性、健壮性(非法输入可处理)、高效率低存储

3.算法的时间复杂度

算法的时间复杂度:预估运行时间与问题规模的关系T(n)。大O法表示,本质是:时间与问题规模的函数,不考虑低阶,不考虑系数,只考虑其数量级。

T(n)=O(f(n))

运算:加法规则、乘法规则(见课本)。

结论:

1.顺序执行的代码只影响常数项、忽略。

2.只需挑循环中的一个基本语句来判断其执行次数、分析时间复杂度即可。

3.多层嵌套只需关注最深层。

void loveYou(int flag[],int n)
{
    int i;
    for(i=0;flag[i]<n;i++)
    {
        if(flag[i]==n)printf("I love U");
        break;
    }
}

最好的情况:flag[0]等于n,最优时间复杂度O(1);

最坏的情况:要查找至最后一个数,最坏时间复杂度O(n);

平均情况:(1+2+...+n)/n=n*(n+1)/2,平均时间复杂度O(n)。

4.算法的空间复杂度

算法原地工作:算法的空间复杂度是常量。

void loveYou(int n;)
{
     int flag[n];   
    int i;
}

数据所占内存:4+4n+4 B;空间复杂度:S(n)=O(n);

递归调用:

void loveYou(int n)
{
    if(n>1) loveYou(n-1);
    printf("I love U %d\n");
}

int main(void){
    loveYou(5);
    return 0;
}

每次执行loveYou需要使用k(常数)个存储空间存储数据,调用5次就会使用5k个存储空间,空间复杂度S(n)=O(n);

void loveYou(int n)
{
    int flag[n];
    if(n>1) loveYou(n-1);
    printf("I love U %d\n");
}

int main(void){
    loveYou(5);
    return 0;
}

每一次执行loveYou占用4*(n+(n-1)+...1)+个空间存储数据[数组],S(n)=O(n^2);