数据结构 绪论

数据结构 绪论

越行勤 628 2021-01-30

开启一个新的篇章

作为一个将来成为社畜的我，不掌握数据结构，操作系统，计算机组成原理，以及计算机网络。那么我以后日子一定很惨，所以加油把。

数据结构绪论

1.1 基本概念

image-20210129230209996

数据，数据元素，数据项，

  • 数据就是信息的载体，是描述客观事物属性的数，字符以及能够输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
  • 数据元素，是数据的基本单位，通常作为一个整体进行考虑和处理。
  • 一个数据元素可以由若干个数据项组成，数据项是构成数据元素中不可分割的最小单位

将这些单位具体化，要根据实际的业务需求来确定什么是数据元素，什么是数据项

比如下面，qq信息

qq数据

结构，数据结构，数据对象

  • 结构，各个元素之间的关系，就好似与，咱汉字的左右结构，上下结构等。
  • 数据结构，相互之间存在一种或者多种特定关系的数据元素的集合
  • 数据对象，具有相同性质的数据元素的集合，是数据的一个子集。

比如正在排队买吃的的顾客，

1号<——2号<——3号<——4号<——5号<——6号<——7号

那么对于这一个数据元素，1号在2号的前面，2号又在3号的前面，这就是一种结构。

那么由这一种关系所组成的集合就叫数据结构

那假如还有一堆顾客在排队打疫苗，

打疫苗的队伍 a号<——b号<——c号<——d号<——e号<——f号

但是这两队有一样的性质，都是队伍，所组成的集合就是数据对象。

1.2三要素的基本概念

image-20210129230059472

逻辑结构

逻辑结构：是指元素之间的逻辑关系，它与数据的存储无关，是独立于计算机的。

我们将会学习到如下的逻辑结构：

  • 集合：这个概念和高数的概念差不多，就是各个元素所凑到一起，不强调逻辑结构。
  • 线性结构： 各个元素是一一对应的关系。除了第一个元素，所有元素都有前驱；除了最后一个元素，其他元素都有后驱。
  • 树形结构，数据元素之间是一对多的关系。前面的思维导图就是一种属性结构
  • 网状结构，好比与人们的人际关系。

存储结构

存储结构：计算机用于存储数据的结构。

数据的存储结构主要分为，顺序存储，链式存储，索引存储，散列存储。

  • 顺序存储：逻辑上相邻的元素存储在物理位置上也相邻，元素之间的存储关系由数据单元的邻接关系来体现。

    image-20210129233451521
    这当然要求给数据，分配连续的存储空间。

  • 链式存储，逻辑上相邻，但是物理位置上可以不相邻，借助于指针来表示元素之间的逻辑关系。

    image-20210129234025558

  • 索引存储，在存储信息的同时，还专门给数据建立附加的索引表。索引表中的每一项被称为索引项，索引项的一般表示方式是关键字+地址。

    image-20210129234409352

  • 散列存储，又叫哈希存储，更具元素的关键子直接计算出该元素的存储地址。

后面三种存储结构可以统称为非顺序存储。

补充

  1. 顺序存储，在物理空间上是必须连续的。如果采用非顺序存储，那么在物理空间上可以是离散的。

  2. 数据的存储结构会影响存储空间的分配方便程度

    分配方便程度，就好比顺序存储，有数据想要插队，那么后面的数据也要跟着变，太麻烦了。但是非顺序存储就不会这样了。

  3. 数据的存储结构会影响对数据的运算速度。

数据运算

数据运算：施加在数据上的运算，包括运算的定义和实现。运算的定义是针对逻辑结构，指出运算的功能；运算的实现是正对存储结构的，指出运算的具体操作步骤。

对于线性存储，运算的定义无非就是入栈和出栈，但是线性存储不一定是由顺序结构来实现的，链表和顺序结构的实现方法是不一样的。

1.3数据类型和抽象数据类型

数据类型

数据类型是 一个值的集合和定义在集合上的一组操作的总称。

  1. 原子类型：无法在分割的数据类型，如 bool 和int
  2. 结构类型：可以被分成原子类型或者是其他结构类型的数据类型。如结构体

为啥说，一个值的集合和一组操作呢？

如bool类型，值的范围就是 false，true,操作呢？或与非等

抽象数据类型

抽象数据类型 abstract Data Type ,ADT，是抽象数据组织及与之相关的操作

1.4 探讨数据结构的方法

以后在学习数据结构的时候，就会讨论如下内容。

  1. 定义逻辑结构
  2. 定义数据运算
  3. 定义存储方式

算法绪论

2.1 什么是算法

程序= 数据结构 + 算法。

  • 数据结构解决的是，如何把现实世界的问题信息化，存储到计算机当中，同时还要解决如何结构现实的实际问题。
  • 算法就是解决 如何处理这些信息，已解决现实的实际问题。

如果对于排队的问题，数据结构解决存储到计算机。那么算法就是如何解决军人优先，残疾人优先的问题。

2.2算法的特性

  • 有穷性：有限步骤后结束
  • 确定性：不存在二义性，对于相同的输入，那么只能得出相同的输入
  • 可行性：受限于计算机的计算能力
  • 输入：能被计算机处理的各种类型数据，算法可以没有输入。
  • 输出：一个或多个输出结果，但是算法不能没有输出。

一个优秀的算法的特性

  1. 正确性，能够正确的解决问题

  2. 可读性，算法应该具有良好的可读性，帮助人们理解。

    算法可以用代码表示，也可用伪代码表示，甚至也可以被文字语言描述，最重要的时能够没有歧义的描述出解决问题的步骤。

  3. 健壮性，比如输入了非法数据，算法能够做出合适的处理，而不是直接挂掉。

  4. 高效率，执行效率快，时间复杂度低

  5. 低存储量，占少量内存，空间复杂度低

2.3 效率的度量：时间复杂度

如何评判算法的时间开销呢？

如果单独从时间考虑话，是不准确的，ardrunio单片机和超级计算机太湖之光，运行同一个算法，时间上可不一样。

还有其他因素，编程语言有关，问题规模有关，还和编译后的机器代码指令集有关等等。

去评判一个算法的时间开销，应该先排除与算法无关的外界因素，抓本质的问题。

时间复杂度：事先估计的算法的时间开销与问题规模n存在函数关系。

这一句话实在抽象的不要不要的，我们还是举一个列子吧。

这个问题就是 爱你n次的 问题，对于的算法就是 loveYou函数，那么n就是问题的规模。

#include <stdio.h>
#include <windows.h>
void loveYou(int n)
{//n为问题的规模
    int i = 1;//爱你的程度
    while (i <= n)
    {
        i++;//爱你程度加1
        printf("i love you %d\n", i);
    }
    printf("i love you more than %d\n", n);
}
int main()
{
    loveYou(3000);
    system("pause");
    return 0;
}

我们观察一下，loveYou()函数代码的执行次数（语句频次），

  1. int i = 1 一次
  2. i<=n 执行 n+1次
  3. i++;printf("i love you %d\n", i);执行n次
  4. printf("i love you more than %d\n", n);执行1次

倘若每一次代码的执行花费时间一致都为1ms，那么花费的时间应该是 总花费时间=3000*2+3001+1+1=3000*3+3

如果写成表达式就为，T(n)=3n+3

我们这个式子就是 时间开销与问题规模n存在函数关系

但是这样去判断一个算法的时间复杂度实在过于累赘。

面对千行代码的算法，我们要一行一行数码？我们可以简化时间复杂度的表达式。

image-20210130171645514

对于上面的式子，当n很大的时候，我们完全可以，抓大头， T1=3n,T2=n^2......，也就是考虑阶数高的部分。

不说人话，大O表示法，就是下面的数学表达式，

image-20210130172241133

我们这里只谈到了加法。

image-20210130172526948

我们还需要掌握如上的问题，可以总结成如下的人话：

  • 乘法规则：多项相乘，都保留
  • 加法规则：只保留最高阶且系数变为1
  • 时间复杂度：常<对<幂<指<阶

补充：

  • 顺序执行的代码只会影响常数项，可以忽略
  • 只需要挑循环中的一个基本操作分析它的执行次数n的关系即可(其余语句只会影响前面的系数)
  • 如果是多层循环嵌套，只需关注最深层循环了几次
练习一下

image-20210130173653550

平均时间复杂度 ，最好时间复杂度，最坏时间复杂度
  • 最好时间复杂度：考虑输入情况最好的情况下。
  • 最坏时间复杂度：考虑输入最坏的情况下。
  • 平均时间复杂度：考虑每一次输入情况概率都一样的情况下。

image-20210130174117246

注意： 算法的性能问题只有在问题规模足够大才能暴露出来

2.4 效率的度量 ：空间复杂度

程序的内存空间：程序代码+数据定义。

程序代码：与问题规模无关。

image-20210130180236288

算法原地工作，算法所需要的内存空间为常量，就比如上面的程序就是算法原地工作，程序跑起来了之后，占用空间大小不变。

和时间复杂度一样，我们用S(n)表示,乘法规则，加法规则和前面的一样了。我们只需要抓住问题的本质: 存储空间大小和问题规模相关的变量.

在计算空间复杂度的时候，我们要区分开一个特别的程序 ： 递归程序。

数据结构