数据结构基础(一)

1、数据结构的基本概念

数据

1. 是能输入计算机且能被计算机处理的各种符号合集
2. 信息的载体
3. 是对客观事物符号化的表示
4. 能够被计算机识别、存储和加工

数据元素

是数据的==基本单位==，通常作为一个整体进行考虑和处理

数据项

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

数据项是数据元素不可分割的==最小单位==

数据对象

具有相同性质的==数据元素集合==，是数据的一个子集

总结

如果用一张表来描述数据：

数据就是这些学生构成的整体

数据元素就是每一个学生

数据项就是每一条信息，例如张倩倩的学号，性别

数据对象就好比每一个班级的人

而==数据结构==就是互相之间存在的一种或多种特定关系的数据元素集合，比如他们是同一个宿舍，那他们就构成了室友关系

2、数据结构的三要素

逻辑结构

从逻辑关系上描述数据，与数据的存储无关，它是从具体问题抽象出来的数学模型

==逻辑结构的种类：划分方法一==

• 线性结构：

  有且仅有一个开始和一个终端终点，并且所有结点最多只有一个直接前趋和一个后继

  例如：线性表、栈、队列、串

• 非线性结构

  一个结点可能有多个直接前趋和直接后继

  例如：树、图

==逻辑结构的种类：划分方法二==

• 集合：数据元素间除“同属于一个合集”外，无其他关系
• 线性结构：一个对一个线性关系，如线性表、栈、队列
• 树形结构：一对多个层次关系
• 图形结构：多个对多个任意关系

物理结构（存储结构）

数据元素及其关系在计算机中内存中的存储形式（又称映象）

物理结构（存储结构）的种类：

• 顺序存储
• 链式存储
• 索引存储
• 散列存储

数据的运算

数据上的某些操作。包括增删改查排序等

3、算法基本概念

什么是算法

程序 = 数据结构 + 算法

算法五个特征

有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。

确定型：算法中每条指令必须有确切的含义，对于相同的输入，只能得出相同的输出

可行性：一个算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现

输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合

输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量

==好的算法：==正确性、可读性、健壮性、高效率、低存储

4、时间复杂度

事前预估算法时间开销T(n)与问题规模n的关系

#include "stdio.h"

//算法1:逐步递增型爱你
void loveYou(int n){
   
   
    int i = 1;
    while (i<=n){
   
   
        i++;
        printf("I love You");
    }
    printf("end");
}


int main(){
   
   
    loveYou(3000);
}

语句频度：

int i = 1;
    while (i<=n){
   
   
        i++;
        printf("I love You");
    }
    printf("end");


第一句执行了1次

第二句执行了3001次，因为到达3000次的时候，while要再进行一次判断

第三句和第四句执行3000次

第六句执行了1次

则：T(3000) = 1 + 3001 + 2 * 3000 + 1

时间开销与问题规模n的关系：T(n) = 3n + 3

==问题：==是否可以忽略表达式某些部分？

• 其实是可以的，当n的规模足够大的时候，我们可以只考虑阶数高的部分

时间复杂度的使用规则

• 加法规则（多项相加，只保留最高阶的项，系数变成1）

  例子：T(n) = n^3^ + n^2^ + 999999

  ​ 改写成：T(n) = O(n^3^) + O(n^2^) + O(1)

• 乘法规则（多项想乘，都保留）

  例子： T(n) = n^2^ * log~2~n

  ​ 改写成：T(n) = O(n^2^ * log~2~n）

  ==问题：==O(n^3^) 和 O(n^2^ * log~2~n）哪个更大呢

==结论：==

1. 顺序执行的代码只会影响常数项，可以忽略

2. 只需要挑循环中的一个基本操作分析它执行次数与n的关系即可

3. 如果有多层嵌套循环，只需要关注最深层循环循环几次

   

5、空间复杂度

空间开销（内存开销）与问题规模n之间的关系

当执行程序的时候，代码会存入内存空间，程序代码在内存的大小固定，与问题规模无关

//算法1:逐步递增型爱你
void loveYou(int n){
   
   
    int i = 1;
    while (i<=n){
   
   
        i++;
        printf("I love You");
    }
    printf("end");
}

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为S(n)= 0(1)

==注意：==如果算法是常数阶，那称这个算法==原地工作==