概览

数据结构与算法 - 基础知识 - 图1

一、什么是数据结构？

基本概念

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、（存储）物理结构和数据的运算三个部分。常见的数据结构有：队列，树，堆，数组，栈，链表，图，散列表等。
屏幕快照 2020-05-04 上午11.29.09.png

1.1 数据

程序的操作对象,用于描述客观事物
特点： 
1.可以输入到计算机 
2.可以被计算机处理

1.2 数据对象

性质相同的数据元素的集合(类似于数组)

1.3 数据元素

组成数据的对象的基本单位

1.4 数据项

一个数据元素由若干数据项组成

1.5 结构

数据元素之间不是独立的,存在特定的关系.这些关系即是结构;

1.6 数据结构

指的数据对象中的数据元素之间的关系

1.7 实例

// 声明一个结构体类型
struct Teacher{     // 一种数据结构
    char *name;     // 数据项--名字
    char *title;    // 数据项--职称
    int  age;       // 数据项--年龄
};
struct Teacher t1;         // 数据元素;
struct Teacher tArray[10]; // 数据对象;
t1.age = 18;       // 数据项
t1.name = "CC";    // 数据项
t1.title = "讲师";  // 数据项

二、逻辑结构

2.1 集合结构

屏幕快照 2020-05-04 上午11.55.35.png

2.2 线性结构

屏幕快照 2020-05-04 上午11.56.15.png

2.3 树形结构

屏幕快照 2020-05-04 上午11.57.00.png

2.4 图形结构

屏幕快照 2020-05-04 上午11.57.32.png

三、存储结构

3.1 顺序存储结构

屏幕快照 2020-05-04 上午11.58.51.png

3.2 链式存储结构

屏幕快照 2020-05-04 上午11.59.38.png

四、常见的数据结构

数组(Array)

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。数组可以说是最基本的数据结构，在各种编程语言中都有对应。一个数组可以分解为多个数组元素，按照数据元素的类型，数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。数组还可以有一维、二维以及多维等表现形式。

栈( Stack)

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

队列(Queue)

队列和栈类似，也是一种特殊的线性表。和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素时，称为空队列。

链表( Linked List)

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。其中，指针域保存了数据结构中下一个元素存放的地址。链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

树( Tree)

树是典型的非线性结构，它是包括，2个结点的有穷集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。

图(Graph)

图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

堆(Heap)

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构

散列表(Hash)

散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

五、算法

5.1 算法的定义

  算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每个指令表示⼀个或多个操作. 每个人对问题的解决方案都是不一样的, 不同的算法可能用不同的时间、空间或效率来完成同样的任务, 一个算法的优劣可以用 空间复杂度 与 时间复杂度 来衡量。

5.2 数据结构和算法的关系

  两者基友联系又有区别。联系是程序=算法+数据结构。数据结构是算法实现的基础，算法总是要依赖某种数据结构来实现的。算法的操作对象是数据结构。区别是数据结构关注的是数据的逻辑结构、存储结构有一集基本操作，而算法更多的是关注如何在数据结构的基本上解决实际问题。算法是编程思想，数据结构则是这些思想的基础。<br />![123.png](https://cdn.nlark.com/yuque/0/2020/png/171814/1588580629421-0c5eb151-5e21-4193-927a-0edcb5e4dc5d.png#align=left&display=inline&height=435&margin=%5Bobject%20Object%5D&name=123.png&originHeight=771&originWidth=1066&size=277962&status=done&style=none&width=602)

5.3 算法的特性

有穷性：一个算法必须在执行有穷步之后结束，且每一步都必须在有穷时间内完成。如果有类似无限循环的语句，那么就不能称之为算法。
可行性：一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。每一步操作都是可以实现的才能称之为算法。
确定性：算法中每条指令、每条语句必须有确切的含义，相同的输入必须得出到相同的输出，不能产生二义性。
输入：一个算法必须有零个或多个输入。
输出：一个算法必须有一个或多个输出。

5.4 算法设计要求

在不考虑效率的情况下, 一个合格的算法必须满足下面的三个条件:

正确性

算法的正确性是评价一个算法优劣的最重要的标准。

可读性

可读性是指一个算法可供人们阅读的容易程度, 可读性高有助于人们理解算法; 晦涩难懂的算法往往很难调试和修改。

注意: 代码越少, 越牛逼!!! 这种想法是不可取的, 如今团队协作的今天, 不再是个人英雄主义的时代, 我觉得能让人更容易读懂才是关键。 ( 所以, 能加注释的顺手加上吧, 队友很难受的。)

健壮性

健壮性是值一个算法对不合理数据输入的反应能力和处理能力, 也成为 容错性。

时间效率和存储效率

这里就是下面要说到的 时间复杂度与空间复杂度 , 在保证上面的一切的同时, 还要尽可能的提升算法的执行效率和资源占用情况。

5.5 算法时间复杂度

5.5.1 定义

在进行算法分析时, 语句的总执行次数 T(n) 是关于问题规模 n 的函数, 进而分析T(n)随着n变化情况并确定T(n)的数量级, 算法的时间复杂度, 也就是算法的时间量度
T(n) = O(f(n))
他表示随着问题的规模 n 的增大, 算法执行时间的增长率和 f(n) 的增长率相同, 成为算法的渐进时间复杂度, 简称时间复杂度。(这种使用 O( ) 来体现算法时间复杂度的记法, 我们称之为大O表示法。)

5.5.2 大 O 表示法

 1. 用常数1取代运行时间中所有常数 3->1 O(1)
 2. 在修改运行次数函数中,只保留最高阶项 n^3+2n^2+5 -> O(n^3)
 3. 如果在最高阶存在且不等于1,则去除这个项目相乘的常数 2n^3 -> n^3

5.5.3 常见案例

常数阶 ```c / 1. 常数阶时间复杂度计算 O(1) / //1+1+1 = 3 O(1) void testSum1(int n){ int sum = 0; //执行1次 sum = (1+n)*n/2; //执行1次 printf(“testSum1:%d\n”,sum);//执行1次 }

//1+1+1+1+1+1+1 = 7 O(1) void testSum2(int n){ int sum = 0; //执行1次 sum = (1+n)n/2; //执行1次 sum = (1+n)n/2; //执行1次 sum = (1+n)n/2; //执行1次 sum = (1+n)n/2; //执行1次 sum = (1+n)*n/2; //执行1次 printf(“testSum2:%d\n”,sum);//执行1次

} //x=x+1; 执行1次 void add(int x){ x = x+1; }


- 线性阶
```objectivec
//x=x+1; 执行n次 O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}
//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

对数阶

/*2的x次方等于n x = log2n  ->O(logn)*/
void testA(int n){ // 8
  int count = 2;         //执行1次
  //n = 10
  while (count < n) {
      count = count * 2;
  }
}

平方阶 ```objectivec //x=x+1; 执行n*n次 ->O(n^2) void add3(int x,int n){ for (int i = 0; i< n; i++) {
```
  for (int j = 0; j < n ; j++) {
      x=x+1;
  }
```
} } //n+(n-1)+(n-2)+…+1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2) //sn = n(a1+an)/2 void testSum4(int n){ int sum = 0; for(int i = 0; i < n;i++)
```
  for (int j = i; j < n; j++) {
      sum += j;
  }
```
printf(“textSum4:%d”,sum);

}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2) void testSum5(int n){ int i,j,x=0,sum = 0; //执行1次 for (i = 1; i <= n; i++) { //执行n+1次 for (j = 1; j <= n; j++) { //执行n(n+1) x++; //执行nn次 sum = sum + x; //执行nn次 } } printf(“testSum5:%d\n”,sum); }


- 立方阶
```objectivec
void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

屏幕快照 2020-05-04 下午8.17.41.png

5.6 算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记做:S(n)=n(f(n)),
其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数

 程序空间计算因素:
 1. 寄存本身的指令
 2. 常数
 3. 变量
 4. 输入
 5. 对数据进行操作的辅助空间
 在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间.
 空间复杂度计算:
 问题: 数组逆序,将一维数组a中的n个数逆序存放在原数组中.

实例

int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    //算法实现(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)
    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]);
    }