【学习笔记】数据结构（一）

基本概念和术语

在这里插入图片描述

👉数据：所有能被输入到计算机中，且被计算机处理的符号的集合；

是计算机操作对象的总称；
是计算机处理信息的载体；
是信息的某一种特定的符号表示形式
包括数值型数据、非数值型数据

👉数据元素/元素/记录/结点/顶点：数据中的一个”个体“，数据结构的基本单位

数据元素的映象是二进制位(bit)的位串

👉数据项：数据结构的最小单位，数据元素是数据项的集合，不可分割的最小单位

例如：一本书的书目信息为一个数据元素，而书目信息中的每一项（如书名、作者名等）为一个数据项。

👉数据对象：是性质相同的数据元素的集合，是数据的一个子集

👉数据结构：带结构的数据元素的集合（结构：数据元素之间存在的一个约束关系）

例如：一维数组的次序关系：{<a_i a_i+1>|i = 1,2,3,4,5}

逻辑结构分类
- 线性结构
- 树形结构
- 图状结构
- 集合结构
形式定义 - 逻辑结构
- 数据结构是一个二元组 Data_Structures = (D , S) D是数据元素的有限集，S是D上关系的有限集
存储结构/物理结构：逻辑结构在存储器中的映象
- 关系的映象方法 - 有序对<x,y>的表示方法：
  - 顺序映象：以存储位置的相邻表示后继关系
    
    以数据元素在存储器之间一个固定的相对位置的关系来表示数据元素的关系
    
    y的存储位置和x的存储位置之间差一个常量C，C是一个隐含值，整个存储结构只含数据元素本身的信息
  - 链式映象：以附加信息（指针）表示后继关系
    
    x的存储映象是一个节点，这个节点包含了两部分信息，一部分是数据元素x的映象，另一部分是指向后继元素的指针
  - 索引存储结构：在存储结点信息的同时，还建立附加的索引表例如：通讯录
  - 散列存储结构：根据结点的关键字直接计算出该节点的存储地址

👉数据类型：在高级程序语言编写中，每个类型明显或隐含的规定了在程序执行期间，他的变量或表达式允许取值的范围以及允许进行的操作；是一个值的集合和定义在此集合上的一组操作的总称

👉抽象数据类型（ADT）：指一个数学模型以及定义在此数学模型上的一组操作

两个特征：
- 数据抽象 - 用ADT描述实体时，强调本质特征、所能完成实现的功能、外界使用的方法
- 数据封装 - 实体的外部特性和内部实现细节分离，并且对外部用户隐藏其内部实现细节
形式定义——抽象数据类型可用以下三元组表示

(D,S,P)

其中， D是数据对象，S是D上的关系集， P是对D的基本操作集。

定义格式

ADT 抽象数据类型名{
	数据对象：<数据对象的定义>
	数据关系：<数据关系的定义>
	基本操作：<基本操作的定义>
}ADT 抽象数据类型名

数据对象、数据关系的定义用伪代码描述

基本操作的定义格式：
	基本操作名(参数表)
	初始条件：<初始条件描述>
	操作结果: <操作结果描述>

在这里插入图片描述

👉算法：为了解决某类问题而规定的一个有限长的操作序列。算法是对问题求解的一种描述。

特性：
- 有穷性
  
  对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即算法中的每个步骤都能在有限
  
  （合理）时间内完成。
- 确定性
  
  每一条指令必须有确切的含义,读者理解时不会产生二义性。
  
  并且对同样的输入值，在任何条件下都能得到相同的结果
- 可行性
  
  算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
- 有输入 —— 有零个或多个的输入
- 有输出 —— 有一个或多个的输出
设计原则
- 正确性
  
  a. 程序不含语法错误；
  
  b. 程序对于几组输人数据能够得出满足规格说明要求的结果；
  
  c. 程序对于精心选择的典型、苛刻而带有刁难性的几组输人数据能够得出满足规格说明要求的结果；
  
  d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
  
  通常以第三层意义上的正确性作为衡量一个算法是否合格的标准
- 可读性
- 健壮性
  
  输入数据非法时，应返回一个表示错误或者错误性质的值，而不是中断程序执行
- 高效率和低存储量需求
  - 效率：算法执行时间
    - 效率衡量方法：
      - 事后统计法 - 缺点必须执行程序、其他因素掩盖算法本质
      - 事前分析估算法
        
        算法运行时间 = 一个简单操作所需的时间 x 简单操作次数
    - 和算法执行时间相关的因素：(后三条与计算机硬件、软件相关)
      - 算法选用的策略
      - 问题的规模
      - 编写程序的语言
      - 编译程序产生机器代码的质量
      - 计算机执行指令的速度
    - 算法执行的时间是问题规模的函数，称之为是一个特定算法的运行工作量
    - ⭐️时间复杂度:
      
      - 随着问题规模n的增长，算法执行时间的增长率和f(n)的增长率相同，可记作：
      
      T(n) = O(f(n)), 称T(n)为算法的（渐进）时间复杂度
      
      - 算法 = 控制结构 + 原操作（固有数据类型的操作）
      
      - 算法的执行时间 = ∑原操作(i)的执行次数 * 原操作(i)的执行时间
      
      原操作(i)的执行次数 - 指的是语句的频度
      
      算法的执行时间和原操作执行次数之和成正比
```
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>

void bubble_sort(int a[], int n) {
    //最好情况 - 只执行一次 - n-1
	//最坏情况 - (n-1)*n/2 - O(n^2)
	int i, j;
	bool change;
	int temp;
	for (i = n - 1, change = true; i > 0 && change; --i) {
		change = false;
		for (j = 0; j < i; ++j) {
			if (a[j] > a[j + 1]) {
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;

				change = true;
			}
		}
	}

}

int main() {
	int a[] = { 8,7,6,5,4,3,2,1 };
	int size = sizeof(a) / sizeof(a[0]);
	bubble_sort(a, size);
	for (int i = 0; i < size; i++)
	{
		printf("%d \n", a[i]);
	}
	return 0;
}
```
      O(1) < O(log₂n) < O(n) < O(n log₂n) < O(n²) < O(n³) < O(n^k) < O(2ⁿ)
  - 存储量：算法执行过程中所需的最大存储空间
    - ⭐️空间复杂度 ：
      
      随着问题规模n的增长，算法运行所需存储量的增长率和g(n)的增长率相同，可记作：
      
      S(n)= O(g(n))
      
      包含：输入数据所占空间、程序本身所占空间、辅助变量所占空间
      
      若输入数据所占空间只取决于问题本身和算法无关，只需分析辅助变量所占的额外空间