引用文章

在此基础上增加自己的学习过程: 《王道》数据结构笔记整理2022

1.2数据结构三要素——逻辑结构和物理结构与数据运算之间的关系
1.3抽象数据结构: 抽象数据

第一章：绪论

1.0 数据结构在学什么

计算机组成原理、操作系统、数据结构和计算机网络之间的关系

• 如何使用程序代码把现实世界的问题信息化
• 如何使用计算机高效地处理这些信息从而创造价值

信息化的世界：数据结构是对数据的处理，对现实世界的数字化，生成数字文件再由操作系统完成对这些文件的管理。计算机组成原理，又是完成这一切的硬件基础。

1.1 数据结构的基本概念

• 数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被程序识别和处理的符号的集合。数据是计算机程序加工的原料（计算机处理的函数的入口，传递的参数）
• 数据元素：

1. 数据元素是数据的基本单位，通常作为一个整体（描述现实世界的一个真实存在的个体）进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。例如，学生记录（一个个体）就是一个数据元素，它由学号、姓名、性别等数据项组成。
2. 若一个数据项由多个更细分的属性组成，则称为组合项

• 结构：各个元素之间的关系
• 数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合
• 数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集

数据结构与数据对象之间的关系：

同样的数据元素，可以根据不同的逻辑组成不同的数据结构

不同的数据元素，可以根据一样的逻辑组成相同的数据结构

1.2 数据结构的三要素

1. 数据的逻辑结构
   逻辑结构是指数据元素之间的逻辑关系，即从逻辑关系上描述数据。

• 集合结构
  各个数据元素同属一个集合，别无其它关系
• 线性结构
  数据元素之间是一对一关系，前驱后继（首尾除外）
• 图形结构
  数据元素之间是一对多的关系
• 树形结构
  数据元素之间是多对多的关系

2. 数据的物理结构（存储结构）
   通过计算机表示数据元素的逻辑关系，存储结构是指数据结构在计算机中的表示（又称映像），也称物理结构。

存储结构：

• 顺序存储：把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
• 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
• 索引存储：在存储元素信息的同时，还建立附加的索引表，索引表中的每项称为索引项，索引项的一般形式是**（关键字，地址）**
• 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

ps:

若采用顺序存储，则各个数据元素在物理上必须是连续的，若采用非顺序存储，则各个数据元素在物理上可以是离散的。

数据的存储结构会影响存储空间分配的方便程度，和对数据运算的速度。

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

4. 三要素之间的关系

1.2数据结构三要素——逻辑结构和物理结构与数据运算之间的关系

1.确定一种存储结构，就意味者在计算机中表示出数据的逻辑结构（计算机中数据结构的映射）。2.存储结构不同（例如下边的例子，顺序跟链表存储的运算方式的实现不同，但是运算方式的定义是相同的），也会导致运算的具体实现不同。
3.确定了存储结构，才能实现数据结构。

逻辑结构：

• 运算会和逻辑结构有关，和物理结构无关。

物理结构：

• 这四种结构各有优缺点：顺序虽然可以实现直接存取，但是对于空间的利用不充分；链式虽然很好利用了空间，但是得到元素只能顺序存取，这样很不方便，并且还要有额外的空间给指针；索引虽然是结合了上面两种的优缺点，但额外的索引表增加了内存损耗；散列结构不可避免会有冲突的危险。

数据运算：

• 运算包括定义和实现。运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。
• 如果逻辑结构是线性的（A-B-C），物理结构是链式的（addr0[A]->addr2[B]->addr1[C]），运算的定义是找到B的前一个元素。B的前一个元素是A，但是如果实现起来，必须先找到addr0，再找addr2，确认了addr2中是B，就得到了A这个结果。但是如果这里的物理结构是顺序的，直接可以从addr0得到（B的前一个地址是addr0）。很明显两种不同的链式结构，同一种运算实现的方法是不同的。

5. 数据类型、抽象数据类型

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

• 原子类型：其值不可再分的数据类型。如bool 和int 类型。
• 结构类型：其值可以再分解为若干成分（分量）的数据类型（struct)

抽象数据类型（Abstract Data Type,ADT）：抽象数据组织及与之相关的操作。
ADT用数学化的语言定义数据的逻辑结构、定义运算。与具体的实现无关

抽象数据结构: 抽象数据

5.探讨数据结构的方式：

1.3 算法的基本概念

程序=数据结构（原料）+算法（方法步骤）

• 算法（algorithm)：是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。

• 算法的特性：（必要性而不是算法的定义，即不满足则不是算法，满足不一定是算法）
  1.有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
  2.确定性：算法中每条指令必须有确定的含义，对于相同的输入只能得到相同的输出。
  3.可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4.输入：一个算法有零个或多个输入（可以没有输入），这些输入取自于某个特定的对象的集合。
  5.输出：一个算法有一个多个输出（不能没有输出），这些输出是与输入有着某种特定关系的量。

• 好的算法达到的目标：
  1.正确性：算法应能够正确的求接问题。
  2.可读性：算法应具有良好的可读性，以帮助人们理解。
  3.健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名奇妙地输出结果。
  4.效率与低存储量需求：效率是指算法执行的时间（时间复杂度），存储量需求是指算法执行过程中所需要的最大存储空间（空间复杂度），这两者都与问题的规模有关。

1.4 算法的时间复杂度

1.4.1 渐近时间复杂度

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作T（n)=O(n)，它表示随问题规模n的增大而增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

大O表示“同阶”，同等数量级。即：当 n->∞时，二者之比为常数

1.4.2 常对幂指阶

表示图

1.4.3 时间复杂度的计算

• 顺序执行的代码只会影响常数项，可以忽略
• 挑选循环中的一个基本操作分析执行次数与n的关系即可
• 对于多层嵌套循环，只需要关注最深层的循环（嵌套最深的，即将每个循环执行次数相乘）

1.4.4 最好与最坏时间复杂度

1.5 算法的空间复杂度

1.5.1 空间复杂度

• 无论问题规模怎么变换，算法与运行所需的内存空间都是固定的常量，则空间复杂度为S(n) = O(1)
• 在计算空间复杂度时，只需关注存储空间大小与问题规模相关的变量

1.5.2 函数递归调用（未总结）

参考链接: 函数调用栈

1.5.3 存储地址

1.5.3.1 内存高低地址与高低位

参考: 内存高地址与低地址、变量的高位和低位

大端法就是，数据的前部（对于int型就是数据的高位）存在低地址

1.5.3.2 用户程序虚拟地址空间分布

Eg：分析代码中的常量、 变量所属的段

本地编译结果

结果分析：

• i1是已经初始化的全局变量，故i存于数据段，且类型为int，四字节三十二位。
• i2是未初始化的全局变量，未设置初始值故为0（BSS段全部置零），类型为int，且由于BSS段在数据段上方，故i2（407A20）地址大于i1（403010）。
• i3是已经初始化的静态全局变量，所以i3存于数据段，类型为int，并且因为在i1之后声明，所以i3（403014）的地址高于i1（403010）的地址四个字节。
• i4是在fun（）里定义的局部变量，所以至于该函数的栈，且栈段位于最上方，所以i4的地址大于之前定义的i1 i2 i3。
• i5同i4是位于fun（）里定义的局部变量，所以i5同样位于栈段，由于栈段是向下延申的，所以i5（62FDDC）的地址小于i4（62FE00）的地址。
• i6是在fun（）里声明的静态局部变量，所以位于数据段，又因为是在i3之后声明在数据段里的所以i6（403018）地址比i3（403014）高四个字节。
• Str1是在fun（）里声明的局部指针变量char*，所以str1变量本身存放在栈段，但是变量中指向的字符串常量”ABCDE”地址，因此%P的形式打印出来的是str1（40400）所存储字符串的地址，所以打印出来的是一个位于数据段地址。又因为在i6（403018）之后声明，所以地址高于i6。
• Str2是在fun（）里声明的局部变量，所以位于栈段，且因为栈段向下延申，所以str2（62FDD0）的地址小于i5（62FDDC）的地址。
• Pi是在fun（）里声明的局部指针变量，并且为它分配了空间，指针本身位于栈段，但是它不同于str1，str1所指向的是位于数据段里的字符串”ABCDE”的地址。它指向malloc动态申请的地址空间，申请的空间位于堆段，所以%P打印出来的是位于堆段的地址，所以地址位于BSS段与栈段之间。