转载于崽🐏的小屋

数据结构绪论

数据结构研究

这门课我们学什么？

凭借一句话获得图灵奖的Pascal语言之父——Nicklaus Wirth,让他获得图灵奖的这句话就是他提出的著名公式：程序=数据结构+算法

这个公式对计算机科学的影响程度足以类似物理学中爱因斯坦的E=mc^2

​ ————这个公式展示了程序的本质

算法其实就是用于解决某一类问题的公式与思想。（给出问题的数学模型）而数据结构就是数据的组织、管理和存储格式，其使用目的是为了高效的访问和修改数据。至于程序就是计算机处理问题的一系列指令。

程序设计的实质是对确定的问题选择一种好的数据结构，并设计一种好的算法。

课程内容

07beaa43b8f244d9d621fc6b23f8dcabbc53abf0.png@942w_510h_progressive.webp

  • 数据结构是计算机软件相关专业的专业基础课

  • 在教学计划中的地位 ：承上启下、核心部分

    04ff17b0b5b8238300c047a4489b817d71ef5ff5.png@737w_425h_progressive.webp

  • 数据结构是介于数学、计算机硬件和计算机软件之间的一门核心课程

    e9b2e882a12d84272b0fc84d3a864deb3f70b02a.png@942w_476h_progressive.webp

  • 类似于武术中的基本功，练武不练功，到头一场空

  • 考研必考专业课4门专业课共150分【《数据结构与算法》占45分(更有很多学校只考数据结构与算法)】

  • 找工作面试，主要考核的内容

数据结构研究的内容

  1. 起初计算机被人们视作数值计算的工具

  2. 通常用计算精机解决一个问题的步骤：

  • 具体问题抽象成数学模型；
    分析问题；
    提取操作对象；
    找出操作对象之间的关系；
    用数学语言描述==>数据结构;【建立相应方程】<一般建立方程容易数据元素之间的关系简单但运算量大，人们就利用计算机来快速的完成复杂的计算>

  • 设计算法；

  • 编程调试运行

  1. 随着计算机应用领域的扩展，计算机被越来越多地用于非数值计算，比如信息的处理

    150a30eded7c3b7ccce278ba54cd1b00a731ce44.png@549w_162h_progressive.webp

    • 来了一位新同学把他的信息加入到系统中；有同学转学或出国了要把他的信息删除道；想查看某位同学的信息；修改某位同学改名字了在系统中也应相应的修改。
      • 操作对象每位学生的信息(姓名、学号、性别、籍贯、专业)
      • 操作算法：查询、插入、修改、删除等
      • 操作对象之间的关系线，性关系数据结构线性数据结构线性表

    b1c0c58eb4e4813aa6f478af15739635fa09b0b5.png@618w_303h_progressive.webp

    • 计算机之所以能和人对弈是因为已经将对弈的策略在计算机中存储好。由千对弈的过程是在一定规则下随机进行的，所以，为使计算机能灵活对弈，就必须把对弈过程中所有可能发生的清况及相应的对策都加以考虑

      • 操作对象：各种棋盘格局

      • 计算机的算法：根据当前的格局，从提供的派生格局中选择一种。也就是下一步棋，则构成一个新的棋盘格局。

      • 操作对象之间的关系：非线性关系(树）

        d670190794d2ddd77e56542acc8fe9a0dfc2b229.png@335w_393h_progressive.webp

        • 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件但每一个子目录只有一个父目录

          4b15a9405a76a4517676ca96c3ea82d8d1acacfe.png@414w_243h_progressive.webp

        • 最短路径问题。从城市A到城市B有多条线路，但每条线路的交通费不同，那么，如何选择一条线路，使得从城市A到城市B的交通费用最少呢？

综上所述：这些问题的共性是:都无法用数学的公式或方程来描述，是一些“非数值计算”的程序设计问题，描述非数值计算问题的数学模型不是数学方程，而是诸如表，树和图之类的具有逻辑关系的数据

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科

基本概念和术语

基本概念和术语

  1. 数据(Data)是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称（集合）。是信息的载体；是对客观事物的符号化表示；可以被计算机识别、存储和加工。数据不仅仅包含整型、实型等数值类型，还包含图形、图像、声音、视频及动画等非数值类型。
    对于整型、实型等数值类型,可以进行数值计算；
    对于字符数据类型，就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。

  2. 数据元素(DataElement)是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、记录、节点、顶点等。如前一节示例中的一名学生记录，树中棋盘的一个格局（状态），以及图中的一个顶点等。

  3. 数据项(Data Item)是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。【数据项是“数据的最小单位。但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。就像我们讨论一部电影时，是讨论这部电影角色这样的数据元素”，而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。】

    244f1b250abd4c6e16b1887abdbd72c618b748be.png@618w_161h_progressive.webp

  4. 数据对象(DataObject)是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0, ±1,±2,…}, 字母字符数据对象是集合C={‘A’,’B’, …‘Z’,’a’,’b’, …， ‘z’}, 学生基本信息表也可以是一个数据对象。由此可以看出，不论数据元素集合是无限集（如整数集），或是有限集（如字母字符集），还是由多个数据项组成的复合数据元素（如学生表）的集合，只要集合内元素的性质均相同，都可称之为一个数据对象。

数据结构

结构，简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。严格点说，结构是指各个组成部分相互搭配和排列的方式。在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。那数据结构是什么？

数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带”结构＂的数据元素的集合，“结构”就是指数据元素之间存在的关系。

逻辑结构和物理结构

  • 逻辑结构

    数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的逻辑结构有两个要素：一是数据元素；二是关系。

    20220816225347.png

    下面四种结构中所举的示例是以某班级学生作为数据对象(数据元素是学生的学籍档案记录),来分别考察数据元素之间的关系。

    1. 集合结构数据元素之间除了“属于同一集合”的关系外,别无其他关系。例如,确定一名学生是否为班级成员,只需将班级看做一个集合结构。
    2. 线性结构数据元素之间存在一对一的关系。例如,将学生信息数据按照其入学报到的时间先后顺序进行排列,将组成一个线性结构。
    3. 树结构数据元素之间存在一对多的关系。例如,在班级的管理体系中,班长管理多个组长,每位组长管理多名组员,从而构成树形结构。
    4. 图结构或网状结构数据元素之间存在多对多的关系。例如,多位同学之间的朋友关系,任何两位同学都可以是朋友,从而构成图状结构或网状结构。
    20220816232333.png

  • 物理结构/存储结构

    物理结构：数据的逻辑结构在计算机中(内存)的存储形式。分为顺序存储结构、链式存储结构、索引存储结构、散列存储结构。

    1. 顺序存储结构

      顺序存储结构是把数据元素存放在连续的存储单元里，数据元素之间的逻辑关系是通过数据元素的位置。(在前面的数据元素就存在前面；在后面的数据元素就存在后面)C语言用数组来实现顺序存储结构。

      8ecfe03cd03fe3d6393fbc2d69698de1eb1b7d8c.png@432w_341h_progressive.webp

      • 例：(bat,cat,eat_mat)

    2. 链式存储结构

      用一组任意的存储单元存储数据元素(可能连续也可能不连续)，数据元素之间的逻辑关系用指针来表示(用指针存放后继元素的存储地址)
      C语言中用指针来实现链式存储结构

      6dee658a2e28bc14521be051b3df209280c2fa84.png@504w_546h_progressive.webp

      • 存放(bat,cat,eat_mat)

      02473a001c8071d48aff77324bc9c48fe7e96847.png@942w_69h_progressive.webp

      现在如银行、医院等地方，设置了排队系统，也就是每个人去了，先领一个号，等着叫号，叫到时去办理业务或看病。在等待的时候，你爱在哪在哪，可以坐着、站着或者走动，甚至出去逛一圈，只要及时回来就行。你关注的是前一个号有没有被叫到，叫到了，下一个就轮到了。

    3. 索引存储结构

    在存储节点信息的同时，还建立附加索引
    索引表中的每一项称为一个索引项，
    索引项的一般形式是：(关键字，地址）
    关键字是能唯一标识一个结点的那些数据项。
    若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index)。若一组结点在索引表中只对应一个索引项，则该索引表称之为稀疏索引（Sparse Index)。

    1. 散列存储结构

      f6638e7342466dd488afbd377999cfe53256e747.png@662w_251h_progressive.webp

数据类型

说到数据类型其实我们并不陌生，在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式、C语言中函数的参数、返回值，明确说明它们所属的数据类型。

C语言中：提供int,char,float,double等基本数据类型；数组、结构、共用体、枚举等构造数据类型；还有指针、空（void)类型，用户也可用typedef自己定义数据类型。而另一些常用的数据结构，如栈、队列、树、图等，不能直接用数据类型来表示。
在C语言中，数据类型可以分为两类：

  • 原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等
  • 结构类型：由若干个类型组合而成，是可以再分解的。例如，整型姿型数据组成的数组。

当年那些设计计算机语言的人，为什么会考虑到数据类型呢？

比如，大家都需要住房子，也都希望房子越大越好。但显然，没有钱，考虑房子是没啥意义的。于是商品房就出现了各种各样的房型，有别墅的，有错层的，有单间的；有一百多平米的，也有几十平米的，甚至在北京还出现了胶囊公寓——只有两平米的房间……这样就满足了不同人的需要。

类型明显或隐含地规定了程序执行期间变量或表达式的取值范围、存储方式以及允许进行的运算。
例如，C语言中定义变量i为int类型，就表示是[min,max]范围的整数，[-32768～32767,16位计算机上]

在这个整数集上可以进行+、-、*、/、%的操作，而不能进行其他数据类型比如字符串的一些操作，而实型变量也有自己的取值范围和相应运算，比如取模运算是不能用于实型变量的。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

抽象数据类型的表示与实现

抽象

抽象是从众多的事物中抽取出共同的、本质性的特征，而舍弃其非本质的特征的过程。具体地说，抽象就是人们在实践的基础上，对于丰富的感性材料通过去粗取精、去伪存真、由此及彼、由表及里的加工制作，形成概念、判断、推理等思维形式，以反映事物的本质和规律的方法。————百度百科

babd601ec2744d60deec5fad2d8a5268952cec3b.png@446w_285h_progressive.webp

其实这个园就是抽象。我们看到了他的本质，而去掉了一些非本质的东西，比如大小颜色，线条的粗细，空心还是实心。
那什么是圆呢？
圆是到某个点距离相等的点的集合这个定点就是圆心，距离就是半径，我们就可以描述这个圆的一些相关信息了。

运算:构造圆、求面积、求周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>

typedef struct {
    double r;
    double x, y, p;
} Circle;

Circle cir(double R, double X, double Y) {
    Circle C;
    C.r = R;
    C.x = X;
    C.y = Y;
    C.p = 3.14;
    return C;
}

double area(Circle C) {
    double a = C. p
    *(C.r * C.r);
    return a;
}

double circumference(Circle C) {
    double c = 2 * C. p
    *C.r;
    return c;
}

int main() {
    Circle z1;
    double z2, z3;
    z1 = cir(1.0, 1.0, 1.0);
    z2 = area(z1);
    z3 = circumference(z1);
    printf("圆的半径R：%.1f\n坐标轴X：%.1f\tY：%.1f\n", z1.r, z1.x, z1.y);
    printf("圆的面积：%5.2f\n", z2);
    printf("圆的周长：%5.2f\n", z3);
    return 0;
}

抽象数据类型

抽象数据类型 (Abstract Data Type, ADT)一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括三部分：

  • 数据对象

  • 数据对象上关系的集合

  • 对数据对象的基本操作的集合

由用户定义，从问题抽象出数据模型（逻辑结构）
还包括定义在数据模型上的一组抽象运算（相关操作）
不考虑计算机内的具体存储结构与运算的具体实现算法

抽象数据类型的形式定义

抽象数据类型可用(D,S,P)三元组表示【离散数学上的概念】其中：
D是数据对象；
S是D上的关系集；数据对象之间的关系构成的集合，(数据对象与数据对象之间可能有多种关系构成了这个集合)
P是对D的基本操作集。

c6e2f048cc294616d415a815568468e7420192cd.png@942w_353h_progressive.webp

例：复数的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ADT Complex{
    D = {r1, r2 | r1, r2 都是实数}
    S = { <r1, r2> | r1是实部, r2是虚部 }
    Assign(&Z, v1, v2)
    操作结果:构造复数Z, 其实部和虚部, 分别被赋以参数v1, v2的值
    Destroy(&Z)
    操作结果:复数Z被销毁
    GetReal(Z, &realPart)
    初始条件:复数已存在
    操作结果:用realPart返回复数的Z的实部值
    GetImag(Z, &imagPart)
    初始条件:复数已存在
    操作结果:用lmagPart返回复数的Z的虚部值
}ADT Complex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>

typedef struct {
    float realpart;
    float imagpart;
} Complex;

Complex assign(float real, float imag) {
    Complex C;
    C.realpart = real;
    C.imagpart = imag;
    return C;
}

float getreal(Complex C) {
    return C.realpart;
}

float getimag(Complex C) {
    return C.imagpart;
}

Complex add(Complex C1, Complex C2) {    //加法
    Complex Sum;
    Sum.realpart = C1.realpart + C2.realpart;
    Sum.imagpart = C1.imagpart + C2.imagpart;
    return Sum;
}

Complex sub(Complex C1, Complex C2) {        //减法
    Complex Diff;
    Diff.realpart = C1.realpart - C2.realpart;
    Diff.imagpart = C1.imagpart - C2.imagpart;
    return Diff;
}

Complex mul(Complex C1, Complex C2) {        //乘法
    Complex Pro;
    Pro.realpart = (C1.realpart * C2.realpart) - (C1.imagpart * C2.imagpart);
    Pro.imagpart = (C1.realpart * C2.imagpart) + (C2.realpart * C1.imagpart);
    return Pro;
}

Complex divs(Complex C1, Complex C2) {    //除法分子
    Complex Quos;
    Quos.realpart = (C1.realpart * C2.realpart) - (C1.imagpart * C2.imagpart);
    Quos.imagpart = (C1.realpart * C2.imagpart) + (C2.realpart * C1.imagpart);
    return Quos;
}

Complex divx(Complex C1, Complex C2) {    //除法分母
    Complex Quox;
    Quox.realpart = C1.realpart * C2.realpart;
    Quox.imagpart = C1.imagpart * C2.imagpart;
    return Quox;
}

int main() {
    Complex c1, c2, c3, c4, c5, c6, c7;
    c1 = assign(5.0, 6.0);
    c2 = assign(7.0, 8.0);
    c3 = add(c1, c2);
    c4 = sub(c1, c2);
    c5 = mul(c1, c2);
    c6 = divs(c1, c2);
    c7 = divx(c1, c2);
    printf("C1:%.2f+%.2fi\n", c1.realpart, c1.imagpart);
    printf("C2:%.2f+%.2fi\n", c2.realpart, c2.imagpart);
    printf("C1 realpart:%.2f\timagpart:%.2fi\n", getreal(c1), getimag(c1));
    printf("C2 realpart:%.2f\timagpart:%.2fi\n", getreal(c2), getimag(c2));
    printf("C1与C2的和:%.2f+%.2fi\n", c3.realpart, c3.imagpart);
    printf("C1与C2的差:%.2f+%.2fi\n", c4.realpart, c4.imagpart);
    printf("C1与C2的差:%.2f+%.2fi\n", c4.realpart, c4.imagpart);
    printf("C1与C2的积:%.2f+%.2fi\n", c5.realpart, c5.imagpart);
    printf("C1与C2的商:%.2f+%.2fi/%.2f+%.2f\n", c6.realpart, c6.imagpart, c7.realpart, c7.imagpart);
    return 0;
}

ps：

参数表：赋值参数，只为操作提供输入值
比如求圆的面积的操作area(操作的名字)(r)(操作的参数)
对图形进行一个缩放n倍scale(G(被操作的图形),n)对图形进行缩放，它当然也会返回一个图形 G’=scale(G,n)返回值要赋值给G 写成scale（**&G,n）
引用参数以”&**”打头，除可提供输入值外，还将返回操作结果。
”初始条件”描述了操作执行之前数据结构和参数应满足的条件，若初始条件为空，则省略。”
操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。

7256665582309bfa41dfd590a09dbb788927ff38.png@855w_452h_progressive.webp

总结

09f340c493df66106d8ea922d30e8ba778fb98b5.png@717w_908h_progressive.webp

抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于具体实现，将数据和操作封装在一起，使得用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，从而实现了信息隐藏。在C++中，我们可以用类的声明表示抽象数据类型，用类的实现来实现抽象数据类型。因此，C++中实现的类相当于数据的存储结构及其在存储结构上实现的对数据的操作。