数据结构笔记

基于王道数据结构的笔记

数据结构是什么？

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据元素是数据的基本单位，数据元素由多个数据项组成，数据项是数据不可分割的最小单位。

数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。

数据结构三要素

逻辑结构：数据元素之间的关系。常见的逻辑结构有集合、线性结构、树形结构和图形结构。
存储结构：数据元素在计算机中的存储方式。常见的存储结构有顺序存储结构和链式存储结构。
运算：对数据元素的操作。常见的运算有插入、删除、查找、排序等。

逻辑结构:

集合：（并查集）是数学中的概念
线性结构：线性的数据结构（第二、三章）例：排行榜
树形结构：（第四章）例：思维导图、文件夹（文件系统）
网状结构（图结构）：（第五章）例：道路信息，朋友圈

数据计算（运算）

针对某种逻辑结构，结合实际需求，定义基本运算。
逻辑架构-线性结构的运算： 1.查找第i个数据元素 2.在第i个位置插入数据元素 3.删除数据元素

存储结构（物理结构）

数据的存储结构：顺序存储、链式存储、索引存储、散列存储

如何用计算机表示数据元素的逻辑关系？
数据元素的三要素

数据类型、抽象数据类型

数据类型：数据类型是一个值的集合和定义在此集合上的一组操作的总称。
原子类型:不可再分的数据类型。
结构类型：可以在分解成若干成分（分量）的数据类型。
抽象数据类型：由用户定义，用以表示应用问题的数据模型，仅取决于逻辑特性，与计算机内部如何实现无关，即独立于实现。

算法

程序 = 数据结构 + 算法

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

算法的特性：

有穷性、确定性、可行性、输入、输出

有穷性：算法必须在执行有限个步骤之后终止。
确定性：算法的每一个步骤都必须是确定的。
可行性：算法的每一步都必须是可行的。
输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。
输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是没有意义的。

※与函数类似

“好”算法的特质

1.正确性：算法应满足具体问题的需求。
2.可读性：算法应易于理解，便于调试、修改和扩充。
3.健壮性：当输入非法数据时，算法能适当地做出反应或进行处理，而不会产生不正确的结果。
4.高效性：执行时间短，存储空间省。
5.低存储量：存储空间省。

算法时间开销度量

事后统计法、事前分析估算法

事后统计法：运行程序，统计时间开销。
事前分析估算法：根据统计规律，对算法时间开销做出估算。✅

算法时间复杂度

算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，其时间量度记作T(n) = O(f(n))，称作算法的渐近时间复杂度，简称时间复杂度。

✅最坏情况时间复杂度：最坏情况下，执行算法的全部过程所需要的时间。
✅平均时间复杂度：所有可能输入实例在等概率前提下，算出平均时间复杂度。
❌最好情况时间复杂度：最好情况下，执行算法的全部过程所需要的时间。

加法原则：T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max(f(n), g(n)))
乘法原则：T(n) = T1(n) * T2(n) = O(f(n)) * O(g(n)) = O(f(n) * g(n))

大小比较：O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
口诀：常对幂指阶
通过数学方式比较算法复杂度
趋近于0则分子时间复杂度速度增大快无穷小比阶

线性表(Linear List)

数据结构三要素

线性表是具有相同数据类型的n个数据元素的有限序列。n为表长，当n=0时，线性表是一个空表。
每个数据元素占用空间一样大，相邻的两个数据元素逻辑上彼此紧邻。
第一个数据元素没有前驱，称为首元素；最后一个数据元素没有后继，称为尾元素。
除第一个和最后一个之外，其他数据元素都有唯一的前驱和后继。

线性表是具有相同数据类型的n个数据元素的有限序列。其中，n表示表长度，当n=0时，该表称为空表。
若用L命名线性表，则其一般表示为：
L = (a1,a2,…,an)
L表示线性表的名字，ai是线性表中第i个元素，n为线性表的表长（即元素个数）。ai-1和ai为相邻两个数据元素。a1表示第一个元素表头元素，an表示最后一个元素表尾元素。

线性表的位序

线性表中每个元素都有一个序号，称为位序。位序是从1开始。
首元素a1的位序为1，尾元素an的位序为n。

线性表中第一个元素a1的位序是1，最后一个元素an的位序是n，当位序i>2时，ai-1和ai为相邻的数据元素，ai-1称为ai的直接前驱，ai称为ai-1的直接后继。

线性表的特点：

线性表中元素的数据类型可以是简单的数据结构，也可以是由多个数据元素构成(如学生表)。
线性表在内存中占用一片连续的存储单元，首元素的位置称为起始位置，末元素所占的存储单元的位置称为终端位置，除第一个和最后一个数据元素之外，其他数据元素有唯一的前驱和后继。
线性表有两种实现方式，一种是顺序存储，一种为链式存储，在下章详细介绍。线性表为动态结构。

线性表的基本操作

线性表的顺序存储结构下，数据元素个数会受到限制，称为静态存储方式，使用比较容易实现，但使用起来不够灵活。
顺序存储是指用一段连续的存储空间，来实现顺序存储。
线性表的基本操作：
InitList(&L) //初始化操作，构造一个空的线性表L，分配内存空间
DestroyList(&L) //销毁操作，销毁线性表L，释放内存空间
ListInsert(&L, i, e) //插入元素，在第i个位置插入元素e
ListDelete(&L, i, &e) //删除元素，删除第i个元素，并用e返回其值
LocateElem(&L, e) //按值查找，返回元素e的位置，
ListLength(&L) //求表长，返回线性表L的数据元素个数
GetElem(&L, i, &e) //查找第i个元素，并用e返回其值
ListEmpty(&L) //判断是否为空表，若为空返回True，反之返回False

封装

为什么要对数据结构进行封装：
1.团队合作编程，你定义的数据结构要让别人能够很方便的使用（封装）-方便团队编程。
2.将常用的操作/运算封装成函数，避免重复工作，降低出错概率。-方便自己
3.简化程序接口，方便调试，方便扩展功能。-方便他人。
4.实现信息隐藏，保证安全性，实现可移植性。-方便未来使用

顺序表

线性表的一种，数据元素排列在一块地址连续的内存空间。继承了线性表的特性

顺序表的实现方式

顺序表的两种实现方式：
1.静态分配：在编译时确定线性表的最大长度，分配固定大小的存储空间。
2.动态分配：在程序执行时，根据实际需求确定空间大小。

顺序存储，即使用顺序表（顺序存储结构）来实现线性表。使用一个一维数组来存储表中的元素值，定义如下：

typedef struct {
    ElemType elem[MAXSIZE];
    int length;
}Sqlist;

ElemType定义数据元素的类型，SqList定义线性表。
ElemType的定义可以是基础数据类型、结构体、枚举等类型。  
SqList是包含数据元素类型和线性表长度的复合类型。  
SqList是一个由SqList构成的结构体。SqList为指向结构体的指针类型，即SqList *Sqlist。
SqList在内存中的位置是确定的，因此每个数据元素之间的相对位置也是确定的，但具体位置不确定（动态的）。因此，线性表在顺序存储结构时，可以实现随机存取。

线性表是一种逻辑结构，顺序存储结构是它的物理结构，实现逻辑结构时，需用物理结构提供存储功能。
线性表实现为链表时，链表是一种逻辑结构，它的实现方式是物理结构。实现逻辑结构时，需用物理结构提供存储功能。
线性表的长度可以随时增加或减少，即具有动态性，与数组不同，数组一旦声明，长度不变。
线性表的最大长度固定时，即具有静态性。
线性表可以是静态顺序表，也可以是动态顺序表，但线性表是一种逻辑结构，其存储结构可以是线性表可以是顺序表，也可以是链表。
线性表、顺序表、顺序存储结构三者没有关系。

顺序表在内存中占用连续的存储空间，因此可以实现随机存取。

静态分配

代码示例

#define MAXSIZE 100 // 顺序表最大的存储长度
typedef int ElemType;// ElemType为int类型
typedef struct
{
  ElemType data[MAXSIZE];// 定义数组长度为100，即最大长度
  int length;
}SqList;

静态分配的特点：静态分配的顺序表是静态的，在编译时确定顺序表的最大长度，一旦确定，不能改变，静态分配的顺序表长度是固定的。
优点：实现起来比较简单，无需考虑空间不够时，调整存储区的空间大小。
缺点：顺序表长度不能变化，造成空间浪费或不够用，不利于实现随机存取，浪费空间，因此使用较少。

记得初始化，否则可能会生成随机数据（内存中的数据遗留 —— 脏数据）

动态分配

#define MAXSIZE 100
typedef struct
{
  ElemType *data;//用指针来存放数组首地址
  int length;// 定义当前长度
}SqList;

定义两个函数，分别为CreateList()：动态分配顺序表空间并初始化，返回数据表。
InsertList()：实现插入操作。

顺序表的基本操作

插入操作**

用存储位置相邻来体现数据元素之间的逻辑关系。

1.在元素i前插入元素e。
2.元素插入到表尾，不需要移动元素，O(1)；插入到表中其它位置，要移动元素，时间复杂度为O(n)。
3.在位置i插入一个元素，表中n个元素依次后移，因此插入操作平均要移动[n/2]个元素，O(n)；最坏的情况需要移动n个元素，时间复杂度为O(n)；若在表末尾插入元素，时间复杂度为O(n)；若在表头插入元素，需要移动n-1个元素，时间复杂度为O(n)。
4.插入操作平均移动近一半的元素，因此时间复杂度为O(n)，最坏情况为O(n)。
5.最坏的情况：表空间已满，没有插入元素空间。

ListInsert（&L，i，e);插入操作，在表L的第i个位置插入指定元素e。

使用静态分配的方式实现的顺序表，表空时length为0，表满时length为100，无法判断是否满了，使用malloc()方法实现动态分配顺序表，将长度改为n。