数据结构

第一章：语言基本知识

1.C语言中的 `malloc` 函数使用 `m`

malloc ：C语言标准库函数，全称 memory allocation，可向操作系统的堆内存区申请一块指定字节数的连续内存.

使用前需引入标准库函数<stdlib.h>，使用后用 free 手动释放内存，避免内存泄漏；
返回值类型：无类型指针 void* ，可以转换为任意类型的指针，但通常需要强制类型转换；
内存分配成功：返回分配内存的起始地址；
内存分配失败：返回空指针 NULL ，可能由内存不足等原因导致。

int *big_ptr = (int *)malloc(sizeof(int)*100000000000);

若系统没有这么大的连续空间，就会分配失败，返回空指针 NULL 。

释放堆内存，并置空防止野指针

free(ptr);
ptr = NULL;

2.C++中的 `new` 关键字使用

new ：C++中的关键字，不是函数，无需引入任何头文件便可使用。

向操作系统的堆区申请指定类型的内存，并返回该块内存的地址；
支持初始化和数组分配，是c++动态管理内存的核心；
分配内存失败抛出 bad_alloc 异常，程序崩溃，C++11可选失败时返回 nullptr ;
使用完成需手动释放，使用关键字 delete 。

对比C语言的 malloc

malloc 只分配内存，不初始化，内存里放的是随机垃圾值，返回无类型指针 void* ；
new 既分配内存，又可以自动初始化，返回对应类型的指针，不需要后续强制转换类型。

1.为单个对象分配内存：类型* 指针 = new 类型(初始化值)；

无初始值：基本类型是随机值，类对象调用默认构造函数；
有初始值：内存被初始化为指定值。

//基本类型int
//1.不初始化，为内存中的随机垃圾值，*p1 = 56378678
int *p1 = new int;

//2.显示初始化为指定值，*p2 = 99
int *p2 = new int(99);

//string对象
//3.不初始化，调用string类的默认构造函数(初始化为空字符串)
string *p3 = new string;

//4.初始化为指定内容
string *p4 = new string("Hello");

2.分配数组：类型* 指针 = new 类型[数组长度](初始化值)；

!!!释放内存时使用 delete[]
() 是c++11后开始支持，所有元素初始化为0/空

//1.使用()将数组元素全部初始化为\0
char *p1 = new char[5]();

//2.不初始化，元素为随机值
int * p2 = new int[10];

3.C++中动态数组 `vector`

vector 是 c++标准库STL中提供的动态数组容器，占用的是连续的堆内存，使用前需包含头文件****，有以下特点：

动态扩容：无需提前指定大小，可根据需要自动增长、收缩；
扩容原理：申请一块更大的堆内存，将原数据拷贝过去，再释放旧内存；
自动内存管理：底层自动申请、释放堆内存，无需手动 new/delete ；
自带丰富的增删改查、排序算法，需包含头文件。

定义与初始化

#include <vector>
#include <iostream>

// 定义指定类型、指定大小容器,若不指定大小则为空容器
// 容器默认初始化：int类型初始化为0，string类型初始化为""
std::vector<int> vec1(5);

// 指定大小+初始值
// 创建长度为5，初始值全为10的容器
std::vector<int> vec2(5,10); 

// 使用普通数组拷贝初始化
int arr[] = {1,2,3};
std::vector<int> vec3(arr,arr+3);

// 用列表初始化，C++11之后支持
std::vector<int> vec4 = {1,2,3,4};

// 用一个容器拷贝初始化
std::vector<int> vec5(vec1);

STL标准方式遍历容器：可理解为智能指针，指向容器中的元素，支持移动、取值等操作。

std::vector<int> vec = {1,2,5,9};
// 使用迭代器方法遍历vector
for(std::vector<int>::iterator it = vec.begin();it!=vec.end();it++){
    // 解引用迭代器对象it
    std::cout<<*it<<std::endl;
}

增删改查

// vector容器的增删改查
std::vector<int> vec = {0,1,2,3};

// 尾部插入元素4
vec.push_back(4);
// 指定位置插入
vec.insert(vec.begin()+1,100);

// 删除尾部元素
vec.pop_back();
// 指定位置删除，删除索引为2的元素
vec.erase(vec.begin()+2);
// 清空所有元素
vec.clear();

// 获取元素值的两种方式,第一种方式不做越界检查，第二种越界则抛出异常
int a0 = vec[0];
int a1 = vec.at(1);

第一个元素：vec.front();
最后一个元素：vec.back();
获取元素个数：vec.size();
获取容量，能存储的元素个数：vec.capacity();
判断是否为空，返回布尔值：vec.empty();

动态数组代码实现：包括元素数量记录、扩容、增删改查等操作。

class List{
    private:
        int *arr; //存储列表元素
        // c++ 11开始支持直接类内初始化
        int listCapacity = 10;  //数组容量
        int listSize=0; //记录当前数组数量
        int extendRatio = 2; //扩容倍数默认为2

    public:
        // 构造函数：分配内存空间
        List(){arr = new int[listCapacity];}
        // 析构函数
        ~List(){delete[] arr;}
        // 获取列表容量
        int getCapacity(){return listCapacity;}
        // 获取列表当前元素数量
        int getSize(){return listSize;}

        // 访问索引为index的元素
        int getElement(int index){
            // 注意index = getSize()也是不合法的情况
            if(index<0||index >= getSize())
                throw std::out_of_range("索引越界");
            return arr[index];
        }

        // 更新索引为index的元素
        void change(int index,int num){
            if(index<0||index >= getSize())
                throw std::out_of_range("索引越界");
            arr[index] = num;
        }

        // 在尾部添加元素，注意检查是否超过容量capacity
        void add_in_end(int num){
            if(getSize() == getCapacity())
                extendCapacity();
            arr[getSize()] = num;
            listSize ++; 
        }

        // 在中间索引index处插入元素num
        void insert(int index,int num){
            if(index<0||index >= getSize())
                throw std::out_of_range("索引越界");
            if(getSize()==getCapacity())
                extendCapacity();
            for(int i = getSize()-1;i>index;i--)
                arr[i] = arr[i-1];
            arr[index] = num;
            listSize ++;
        }

        // 删除元素并返回该元素
        int remove(int index){
            if(index<0||index>=getSize())
                throw std::out_of_range("索引越界");
            int num = arr[index];
            for(int i = index;i<getSize()-1;i++)
                arr[i] = arr[i+1];
            listSize --;
            return num;
        }

        // 扩容函数,默认倍数为2
        void extendCapacity(){
            // 新建数组长度为原来的extendRatio倍
            // 若直接给arr申请更大的内存会覆盖掉原来的地址，导致原数据丢失
            // 指针tmp可解决该问题
            int newCapacity = extendRatio*listCapacity;
            int *tmp = arr;
            arr = new int[newCapacity];
            for(int i=0;i<getSize();i++){
                arr[i] = tmp[i];
            }
            // 释放内存
            delete[] tmp;
            tmp = nullptr;
            listCapacity = newCapacity;
        }
};

第二章：数组与链表

1.链表的创建与初始化

链表为线性结构的一种，每个节点包括自身数据和指向下一个节点的指针

C++实现链表的创建与初始化

//节点结构体
typedef struct ListNode{
int val;
listNode* next;
ListNode(int a):val(a),next(nullptr){}
}ListNode;

//初始化节点
ListNode* n0 = new ListNode(0);
ListNode* n1 = new ListNode(1);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(3);
ListNode* n4 = new ListNode(4);
//串联节点
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
//实现的链表为0->1->2->3->4

由于C语言中不可在结构中创建函数，因此单独写一个用于节点初始化的函数

ListNode* newListNode(int x){
    //声明并分配堆内存
    ListNode* node;
    node = (ListNode*)malloc(sizeof(Listnode));
    //初始化
    node->val = x;
    node->next = nullptr;
    return node;
}

通常将头节点作为链表的代称，上述列表可称为 链表n0 。

2.链表的插入与删除

插入节点仅需改变指针即可，注意顺序，避免链表断裂

//在节点n0之后插入节点p
void insert (ListNode *n0,ListNode* p){
   ListNode *n1 = n0->next;
   p->next = n1;
   n0->next = p;
}

其中n1为临时指针变量，即使顺序错了也不会导致指针断裂，容错更高。

删除节点：链表由n0->p->n1变为n0->n1

// 删除n0之后的首个节点
void delete_node(ListNode *n0){
   if(n0->next == nullptr){
       return;
   }
   ListNode *p = n0->next;
   ListNode *n1 = p->next;
   n0->next = n1;
   delete p;
}

上述删除节点代码中p(必须)和n1的作用

p：保存要删除的节点地址，后续才能通过 delete 释放内存，同时避免先执行 n0->next = n1 导致要删除的节点被覆盖。
n1：避免先执行 delete p 导致的野指针问题。

3.链表的访问与查找

已知索引时，数组访问任意元素的时间复杂度为O(1)，而链表访问索引为i的元素时，需要循环i-1次，时间复杂度为O(n)。

//访问链表中索引为index的元素
// 访问索引为index的元素，传入头节点head
ListNode* visit(ListNode *head,int index){
   for(int i=0;i<index;i++){
       if (head == nullptr){
           //链表长度小于要访问的索引的情况
           return nullptr;
       }
       head = head->next;
   }
   return head;
}

查找链表中值为 index 的节点
找到返回其索引，找不到返回-1

int find(ListNode *head,int target){
    int index=0;
    while(head != nullptr){
        if(head->val == target){
            return index;
        }
        head = head->next;
        index ++;
    }
    return -1;
}

4.链表VS数组效率对比

数组
占用连续内存空间，长度较为固定；单个元素占用内存空间较小，但可能会浪费；方便访问元素，添加删除元素麻烦。
链表
占用分散的内存空间，长度灵活可变；单个元素占用空间比数组大（要存放下一个元素的指针）；方便插入、删除元素，访问元素时间复杂度较高。

5.常见的三种链表

单向链表：尾节点指向空。
环状链表：将单链表的尾节点指向头节点，摇身一变双链表。此时每个节点都可看作是头节点。
双向链表：每个节点有 自己的数据 、 指向前驱节点的指针 和 指向后继节点的指针 ，可双向循环遍历，占用的内存空间也更大。

6.链表常见使用场景

单链表通常用于栈与队列、图、哈希表等数据结构。

栈：插入和删除操作都在链表的一端进行，类似一个容器，后进先出；
队列：插入和删除在链表的两端进行，可类比排队，先进先出；
哈希表：解决哈希冲突时会使用链表，所有冲突的元素都放到一个链表中；
图：表示多对多的关系，分为有向图和无向图，常用邻接表表示图，其中图的每一个顶点都与一个链表相关联，链表中的每个元素都代表与该顶点相连。

双向链表用于需要快速查找前一个和后一个元素的场景。

高级数据结构：红黑树、B树
浏览器历史：
LRU算法：

环形链表用于需要周期性操作的场景。

时间片轮转调度算法：
数据缓冲区：