数据结构与算法

数据结构与算法--一(概念偏)

2020-04-01  本文已影响0人  只写Bug程序猿

1.0 数据结构的基础概念

1.0.1 为什么要学习数据结构

在计算机界流行着一句经典名言"数据结构+算法=程序设计",就是由瑞士Niklaus Wirth 这个家伙说的
软件设计时要考虑的首要问题就是数据的展示,组织和处理方法,这直接关系到软件的运行效率
计算机技术发展迅速,处理的数据量越来越大,结构也越来越复杂,从简单的数值结构到现在的各种多媒体数据,因此如何组织数据,建立合适的数据结构时非常非常重要的

1.1什么是数据结构

数据机构最基本的五个概念: 数据,数据元素,数据项,数据对象,数据结构

1.1.1 数据

数据:是描述客观事物的数字,字符以及所能输入到计算机中,并能被机器识别的各种符号的统称,除了数值外还有字符串等非数值数据,以及图形图像音视频等

1.1.2 数据元素

数据元素时数据的基本单位,表示一个事物的一组数据
例如: 一个人,一辆车,一只动物

1.1.3 数据项

数据项是数据元素中有独立含义的,不可分割的最小表示单位.
例如: 一个整数,一个字符都是原子项,一个学生数据元素由学号,姓名,班级,性别等等多个数据项组成

1.1.4 数据对象

是性质相同的数据元素的集合,是数据的子集.
比如 数据元素具有相同的数量和类型的数据项,类似数组中的元素保持性质一直

1.1.5 数据结构

指数据元素之间的关系,一个数据结构是由n个数据元素组成的有限集合,数据元素之间具有某种特定关系
话不多说上代码

#include <stdio.h>

//声明一个结构体类型
struct Teacher{     //一种数据结构
    char *name;     //数据项--名字
    char *title;    //数据项--职称
    int  age;       //数据项--年龄
    
};


int main(int argc, const char * argv[]) {
   
    struct Teacher t1;     //数据元素;
    struct Teacher tArray; //数据对象;
    
    t1.age = 18;       //数据项
    t1.name = "CC";    //数据项
    t1.title = "讲师";  //数据项
    
    printf("老师姓名:%s\n",t1.name);
    printf("老师年龄:%d\n",t1.age);
    printf("老师职称:%s\n",t1.title);
    
   
    return 0;
}

1.2数据的逻辑结构和物理结构

1.2.1 逻辑结构

指数据对象中的数据元素之间的相互关系,逻辑结构分为:集合结构 ,线性结构,图形结构,树形结构

树形结构,重要的非线性数据结构,是一对多的关系,常见的有:二叉树,B树,哈夫慢树,红黑树等

多对多的关系,常见有:邻近矩阵,邻接表

1.2.2 物理结构

指数据的逻辑结构在内存中的物理存储方式
数据的存储结构有2种:顺序存储和链式存储;

跟顺序存储不一样的是,存储单元可以是连续的也可以是不连续的,存储关系不能反映逻辑关系,所以链式结构中一般一个节点会有数据域和一个指针域,通过指针来表述数据的关系

二.算法

算法:是解决问题步骤的描述,是一个有穷规则的集合,器规定确定一个解决某以特定问题的操作序列

2.1 两种算法比较

计算1+2+3+4+......+100的结果

 int sum ,n;
    n = 100;
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += I;
    }
    printf("%d",sum);

这简单啊,咔咔咔一顿操作猛如虎,打印结果.那么在看下边使用等差数列这种方式

int sum = 0,n = 100;
sum = (1+n)*n/2
printf("%d",sum);

据说德国的高斯小学时就用这种方式解决了,小学我还学1+1呢,这个逼就会等差数列了


就是这个货
2.2 算法特性

算法特性

  1. 有穷性
    指的是算法在执行有限的步骤之后,自动结束而不会出现无限循环,且每一个步骤在可接受的时间内完成
  2. 确定性
    算法的每一个步骤都具有确定的含义,不能出现二义性; 算法在一定条件下,只有一条执行路径,相同的输入只能有唯一的输出结果.
  3. 可行性
    算法的每一步都必须是可行的,换句话说,每一步都能通过执行有限次数完成.
  4. 有输入
  5. 有输出
2.3 算法设计要求
  1. 正确性
  2. 健壮性
  3. 高时间高空间效率
  4. 可读性
2.4 时间复杂度

时间复杂度我们用大O法来表示
规则

  1. 用常数1取代运行时间中所有加法常数
  2. 在修改后的运行次数函数中,只保留最高阶项
  3. 如果在最高阶项存在切不是1,则去除与这个项相乘的常数
2.4.1 常数阶
//1+1+1 = 3 O(1)  根据第一条用1取代3
void testSum1(int n){
    int sum = 0;                //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum1:%d\n",sum);//执行1次
}
2.4.2 线性阶
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

循环n次,也就是执行了n次,时间复杂度为O(n)

2.4.3 对数阶
int count = 1;
while(count < n){
    count = count * 2;
}

count = count * 2 ; 每次执行这句代码,就会距离n更近一步; 也就是说, 有多少个2相乘后大于n,则会退出循环.



所以这个时间复杂度为:O(logn)

2.4.4 平方阶
/x=x+1; 执行n*n次
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

时间复杂度为O(n ^2)

void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++) //执行n次
        for (int j = i; j < n; j++) { //执行n-i次
            sum += j;
        }
    printf("textSum4:%d",sum);
}
i = 0，循环执行次数是 n 次。
i = 1，循环执行次数是 n-1 次。
i = 2，循环执行次数是 n-2 次。
...
i = n-1，循环执行的次数是 1 次。

换算成: 

result = n + (n - 1) + (n - 2) … + 1

被加数递减，抽象为一个等差数列求n项和的问题，公差为1，带入公式，Sn = n(a1 + an ) ÷2

result = (n(n+1))/2 =  (n^2+n)/2 = (n^2)/2 + n/2

根据第一条没有加法常数不考虑,第二条只保留高阶项(n^2)/2, 第三条去除相乘的常数也就是1/2,所以最终时间复杂度为O(n^2)


2.5 空间复杂度

程序空间计算因素:

  1. 寄存本身的指令
  2. 常数
  3. 变量
  4. 输入
  5. 对数据进行操作的辅助空间
    通常情况下我们主要考虑算法执行时所需要的辅助空间.
    比如
int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    //算法实现(1)
    /*
    算法(1),仅仅通过借助一个临时变量temp,与问题规模n大小无关,所以其空间复杂度为O(1);
    */
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);

    }
    
    
    //算法实现(2)
    /*
     算法(2),借助一个大小为n的辅助数组b,所以其空间复杂度为O(n).
    */
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }
    for(int i = 0;i < 10;i++)
    {
        printf("%d\n",a[i]);
    }
上一篇下一篇

猜你喜欢

热点阅读