数据结构笔记

文章目录

数据结构笔记

绪论：数据结构的基本概念

数据：信息的载体，能输入到计算机中并被计算机程序识别和处理的符号的集合。

数据元素：数据的基本单位。

数据项：构成数据元素的不可分割的最小单位。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

数据对象：具有相同性质的数据元素的集合。是数据的一个子集。

数据结构的三要素：逻辑结构、物理结构（存储结构）、数据的运算

1. 逻辑结构–数据元素之间的逻辑关系

数据的逻辑结构分为：集合、线性结构、树形结构、图状结构（网状结构）

集合：各个元素同属一个集合。

线性结构：数据元素之间是一对一的关系。除了第一个元素，所有元素都有唯一前驱；除了最后一个元素，所有元素都有唯一后继。

树形结构：数据元素之间是一对多的关系。

图结构：数据元素之间是多对多的关系。

2. 物理结构（存储结构）–用计算机表示数据元素的逻辑关系

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

顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中。

链式存储：逻辑上相邻的元素在物理位置上可以不相邻。

索引存储：建立附加索引表，索引表中的每项称为索引项。一般形式是（关键字，地址）。

散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。

后三个也称为非顺序存储。

顺序存储：各个数据元素在物理上必须是连续的。

非顺序存储：各个数据元素在物理上可以是离散的。

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

数据类型：原子类型（其值不可再分解）、结构类型（其值可以再分解）、抽象数据类型（ADT）（定义数据的逻辑结构、定义运算。与具体的实现无关）

绪论：算法和算法评价

程序 = 数据结构 + 算法

算法必须具备的特性：有穷性、确定性（相同的输入只能得出相同的输出）、可行性、输入、输出

好算法的特质：正确性、可读性、健壮性、高效率与低存储需求

算法的时间复杂度

算法的运行时间受机器性能、编程语言等的影响

算法时间复杂度：事前预估算法时间开销**T(n)**与问题规模n的关系

最好时间复杂度、最坏时间复杂度、平均时间复杂度

算法的空间复杂度

算法空间复杂度：事前预估算法辅助空间开销**S(n)**与问题规模n的关系

程序代码、数据装入内存

算法原地工作：O(1) – 算法所需的辅助空间为常量

递归程序要看调用的深度与问题规模n的关系

复杂度计算

加法规则：多项相加，只保留最高阶的项，且系数变为1

乘法规则：多项相乘，都保留

O(1) < O(log₂n)<O(n)<O(nlog2n)<O(n²) <O(n³) <O(2ⁿ) < O(n!) <O(nⁿ)

斐波那契数列：

非递归：时间复杂度O(n)

class Solution {
public:
    int fib(int n) {
        long long int a = 0;
        long long int b = 1; 
        long long int c;
        while(n--)
        {
            c = (a + b)%1000000007;
            a = b;
            b = c;
        }
        return a;
        
    }
};

递归：时间复杂度O(2ⁿ)

class Solution {
public:
    int fib(int n) {
        if (n==0) return 0;
        else if (n==1) return 1;
        else return fib(n-1)+fib(n-2); 
    }
};

线性表

线性表是具有相同数据类型的n个数据元素的有限序列，n为表长。若用L命名线性表，则其一般表示为：

L = (a₁,a₂,…,a_i,a_i+1,…,a_n)

a_i是线性表中第i个元素线性表中的位序。位序从1开始。

基本操作：初始化、销毁、插入、删除、按值查找、按位查找、求表长、输出操作、判空操作

什么时候需要传入参数的引用“&” ：对参数的修改结果需要“带回来”

顺序表

顺序表的定义

顺序表：用顺序存储的方式实现线性表顺序存储。

malloc:

malloc函数申请一整片连续的存储空间，返回一个指针，需要强制转型为你定义的数据元素类型指针

例： L.data = (ElemType*) malloc (sizeof(ElemType) * InitSize);

顺序表存满时，可再用malloc动态拓展顺序表的最大容量，将数据元素复制到新的存储区域，并用free函数释放原区域

顺序表的特点：随机访问；存储密度高；拓展容量不方便；插入、删除操作不方便，需要移动大量元素

顺序表的插入

判断i的范围是否有效，将第i个元素及之后的元素后移，在位置i处放入元素e，线性表长度加1

最好时间复杂度O(1)；最坏时间复杂度O(n)；平均时间复杂度O(n)

顺序表的删除

判断i的范围是否有效，将被删除的元素赋值给e，将第i个位置后的元素前移，线性表长度减1

最好时间复杂度O(1)；最坏时间复杂度O(n)；平均时间复杂度O(n)

顺序表的查找

按位查找：获取表L中第i个位置的元素的值

静态分配（数组）：返回下标为i-1的元素

动态分配（指针）：和访问普通数组的方法一样，return L.data[i-1]

按值查找：在表L中查找具有给定关键字值的元素

如果数组下标为i的元素值等于e，则返回其位序i+1；退出循环则说明查找失败

注意：结构体的比较不能直接用“==”，需要依次对比各个分量来判断两个结构体是否相等

最好时间复杂度O(1)；最坏时间复杂度O(n)；平均时间复杂度O(n)

线性表的链式表示

单链表

单链表：用链式存储实现了线性结构，各个结点间的先后关系用一个指针表示

优点：可随机存取，存储密度高

缺点：要求大片连续空间，改变容量不方便

结点包含：数据域、指针域

LinkList : 强调是链表

ListNode : 强调是结点

单链表的插入

按位序插入：在第i个位置插入元素e（带头节点）

指定节点的后插结点：时间复杂度为O(1)

指定节点的前插结点：传入头指针，找到前驱结点，时间复杂度为O(n)；或者先将新结点放在指定结点后面，再交换两个结点的值

单链表的删除

按位序删除：在第i个位置删除元素e（带头节点），需要新建临时结点temp存储需要删除的结点

最好时间复杂度O(1)；最坏时间复杂度O(n)；平均时间复杂度O(n)

单链表的查找

按位查找：获取表L中第i个位置的元素的值

按值查找：在表L中查找具有给定关键字值的元素

求单链表长度

平均时间复杂度都是O(n)

单链表的建立

尾插法、头插法（可以用于链表的逆置）

时间复杂度是O(n)

双链表

DLinklist: 强调是双链表

DNode: 强调是双链表结点

双链表的初始化

data（数据域）、prior（前驱指针）、next（后驱指针）

双链表的插入

bool InsertNextDNode( DNode* p, DNode* s)
{
	s->next = p->next;
	p->next->prior = s;//前提是p->next不为NULL
	s->prior = p;
	p->next = s;
}

按位序插入、前插操作都可以转换为后插操作

双链表的删除

p->next = q->next;
q->next->prior = p;
delete(q);

双链表的遍历

while (p!=NULL)
{
    p = p->next;
}

while (p!=NULL)
{
    p = p->prior;
}

双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)

循环链表

循环单链表

空的循环单链表的头结点的next指向自己

循环单链表从一个结点出发可以找到其他任何一个结点；从尾结点找到头结点的时间复杂度是O(1)，从头结点找到尾结点的时间复杂度是O(n)

循环双链表

空的循环双链表的头结点的next和prior都指向自己

循环双链表表头结点的prior指向表尾结点，表尾结点的next指向头结点

循环双链表的删除

p->next = q->next;
q->next->prior = p;
delete(q);

静态链表

静态链表：分配一整片连续的内存空间，各个节点集中安置。用数组的方式实现的链表。

每个元素包含：数据元素、下一个结点的数组下标（游标）

游标为-1表示已经到达表尾

查找：从头结点出发挨个往后遍历节点，时间复杂度为O(n)

插入位序为i的结点：找到一个空的结点，存入数据元素；从头结点出发找到位序为i-1的结点；修改新结点的next；修改i-1号结点的next

如何判断结点是否为空：为空的结点原本存的都是脏数据，可以在初始化时让next为某个特殊值，如-2

优点：增、删操作不需要大量移动元素

缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变

顺序表和链表的比较

逻辑结构：都属于线性表，都是线性结构

存储结构：顺序表为顺序存储，支持随机存取、存储密度高；链表为链式存储，离散的小空间分配方便、改变容量方便

基本操作：

顺序表需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。链表只需分配一个头结点（或只声明一个头指针），之后方便拓展。静态分配：静态数组，系统自动回收空间。动态分配：动态数组（malloc），需要手动free。

顺序表插入/删除元素要将后续元素都后移/前移，时间复杂度为O(n)，时间开销主要来自移动元素。链表插入/删除元素只需修改指针即可，时间复杂度为O(n)，时间开销主要来自查找目标元素。

顺序表按位查找时间复杂度为O(1)，按值查找时间复杂度为O(n)。若表内元素有序，可在O(log₂n)时间内找到。链表按位查找时间复杂度为O(n)，按值查找时间复杂度为O(n)。

开放式问题：实现线性表时，用顺序表好还是链表好？

顺序表和链表的逻辑结构都是线性结构，都属于线性表。但是二者的存储结构不同，顺序表采用顺序存储（特点，带来的优点缺点）；链表采用链式存储（特点、导致的优缺点）。由于采用不同的存储方式实现，因此基本操作的实现效率也不同。当初始化时，…当插入一个数据元素时…当查找一个数据元素时…

数据结构笔记