数据结构 Base|云端浮梦

概念

数据逻辑结构
数据储结构
数据运算和其实现

数据结构两要素

数据元素的集合
关系的集合

数据结构三方面内容

数据逻辑结构
数据存储结构
数据的运算

数据的逻辑结构

数据的逻辑结构指数据元素之间的逻辑关系（从具体问题抽象出来的数学模型）

数据的四种基本结构

数据的存储结构

数据的存储结构是指数据的物理结构，是逻辑结构在计算机上的实现，既要存储元素本身，也要存储计算机元素之间的关系

顺序存储数据元素顺序存放，每个结点只有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大，但是插入、删除操作效率较差。
链式存储每个结点除了包含数据元素信息外还包含一组指针，指针反映数据元素间的逻辑关系。这种存储方式不要求存储空间连续，便于进行插入和删除操作，但是存储空间利用率较低。另外，由于逻辑上相邻的数据元素在存储空间上不一定相邻，所以不能对其进行随机存取。
索引存储除了数据元素存储在一地址连续的内存空间外，尚需建立一个索引表。索引表中的索引指示结点的存储位置，兼有动态和静态的特性。
哈希（散列）存储通过哈希函数解决冲突的方法，将关键字散列在连续的有限的地址空间内，并将哈希函数的值座位该数据元素的存储地址，其特点是存取速度快，只能按关键字随机存取，不能顺序窜出，也不能折半存取。

数据的存储结构-CSDN博客

数据的运算

数据的运算是施加在逻辑结构上的一组操作的总称。运算的定义直接依赖于逻辑结构，运算的实现必须依赖于存储结构，即在逻辑结构上定义运算，在存储结构上实现运算

基本运算包括

插入
修改
删除
查找
排序

算法

算法是对特定问题的描述，数据结构和算法密不可分，算法设计一定要基于确定的数据结构考虑算法的实现和效率

算法流程图的描述

使用visio画流程图最舒服

基本用法

N-S结构化流程图

参考【N-S图详解_ns图怎么画-CSDN博客】

N-S图，也被称为盒图或NS图（Nassi Shneiderman图）

算法的评价

算法的评价主要是研究比较各种算法时间的性能和优劣【高效性，低存储】

算法时间复杂度和空间复杂度

算法的时间与空间复杂度（一看就懂） - 知乎 (zhihu.com)

时间复杂度是指执行这个算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的内存空间。时间和空间（即寄存器）都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少。

数组

数组是一种线性的数据结构将相同数据结构的数据放在连续的内存中

// 初始化数组
int arr[10]; // 数据存储在栈
int *arr = new arr[10] /*[{val1,val2,...}] */;  // 数据存储在堆

因为数组的数据结构是线性连续的我们可以随机访问数据时间复杂度为

可以使用公式访问地址

内存地址首地址元素索引数据类型大小

在数组中插入元素

数组的元素是连续的中间没空需要将要插入元素位置的数后移在进行插入,如果是静态的数组插入需要将后面超过的数也删除

删除元素需要将相应位置的元素删除，将后面的元素补上

时间发杂度：

数组可以实现其他的数据结构进行模拟

链表

链表也是一种线性的数据结构每个元素都是一个节点的对象

单链表包含一个数据域和指针域,相比于数组使用更大的空间

通过指针域链接下一个链表实现链表的连续

单链表的内存地址不连续，所以不至此随机访问只能访问到下一个节点，所以访问的时间复杂度为O(n)

链表的尾节点为空在c++中为 { nullptr 、NULL}

构建链表

struct ListNode{
    int val; //数据
    ListNode * next; //指针
    struct ListNode(int x)val(x),next(nullptr){}  // 构造函数
};

初始化

ListNode *n1 = new ListNode(1);
ListNode *n2 = new ListNode(2);
ListNode *n3 = new ListNode(3);
ListNode *n4 = new ListNode(4);


n1.next = n2;
n2.next = n3;
n3.next = n4;

数组模拟链表

const int N = 1e5;
int h = -1,e[N],ne[N],idx = 0;

int add(int val){
    e[idx] = val;
    ne[idx] = h;
    h = idx ++;
}// 头插法

删除节点

找到要删除节点的前一个节点
存一下要删除节点的地址
将要删除节点前一个节点的指针指向言删除节点的后一个节点
释放存储节点的内存

void RemoveNode(ListNode N){
    auto p = head;
    while(p->next != N){
        p = p->next;
    }
    auto t = p -> next;
    p->next = t->next;
    delete t;
}

链表访问元素查找元素都是O（n）数组是O（1）

链表添加元素删除元素都是O（1）链表是O（1）

在C++中，`.`（点操作符）和`->`（箭头操作符）都用于访问类的成员，但它们的使用情境有所不同：

1. 使用`.`：
   - 当你有一个对象的实例时，你使用`.`来访问其成员。这适用于直接访问对象的成员变量和成员函数。
   ```cpp
   MyClass obj;
   obj.memberVariable = 10;
   obj.memberFunction();

使用->：
- 当你有一个指向对象的指针时，你使用->来访问对象的成员。这通常用于访问动态分配的对象或者对象在堆上的实例。
```
MyClass *ptr = new MyClass();
ptr->memberVariable = 20;
ptr->memberFunction();
```

在使用->时，编译器会自动将其解释为(*ptr).member的形式，因此ptr->member等价于(*ptr).member，这意味着首先解引用指针，然后访问对象的成员。




### 列表

动态的数组

继承数组的优点并且可以动态扩容

```cpp
#include <vector>

vector<int> n;

n.push ...

列表

vector实现

#include <iostream>

using namespace std;

class Vecotr
{
private:


    int *arr; // 列表元素
    int arrSize; // 列表长度
    int MaxLen  = 10; // 列表容量
    int extendRatio  = 2; // 每次扩容倍数
public:
    Vecotr(/* args */);
    ~Vecotr();
    int size();
    int CapaCity();
    int get(int index);
    int set(int index,int val);
    void extendRatio();
    void Vecotr::vpush(int val)
    {
        if(arrSize == MaxLen){
            extendCapaCity();
        }
        arr[arrSize] = val;
    }
    void Vecotr::extendCapaCity()
    {   
        MaxLen *= extendRatio;
        auto *temp = arr;
        arr = new int[MaxLen];
        for(int i = 0 ;i < size();i++){
            arr[i] = temp[i];
        }
        delete temp;
    }
};

Vecotr::Vecotr(/* args */)
{
    arr = new int[MaxLen];
}

Vecotr::~Vecotr()
{
    delete arr;
}

int Vecotr::size()
{
   return arrSize;
}

int Vecotr::CapaCity()
{
    return MaxLen;
    // return 0;
}

int Vecotr::get(int index)
{
    if(index<0||index>arrSize)return -1;
    return arr[index];
}

int Vecotr::set(int index, int val)
{
    if(index<0||index>arrSize)return -1;
    arr[index] = val;
    return 1;
}

栈stack

一种先入后出后入先出的数据结构 FILO/LIFO last in first out 的线性数据结构

c++ 带有的栈

#include <stack>
stack<int> st;   // c++ 自带的栈

int main(){
    
    st.push(1);
    st.push(2); // 入栈
    st.push(3);
    
    int top = st.top(); //取得栈顶元素
    st.pop();
    int size = st.size();
    
    
    return 0;
}

基于链表实现的栈

#include <iostream>

using namespace std;


struct ListNode{
    int val;
    ListNode * next;
    ListNode(int val):val(val){
        this->next = nullptr;
    }
};


class LinkNodeStack
{
private:
    ListNode *stackTop;
    int stackSize;
public:
    LinkNodeStack(/* args */);
    ~LinkNodeStack();
    int size();
    bool empty();
    int pop();
    int top();
    int push(int val);

    void freeMemoryLinkNodeStack(auto *To_delete);
};

LinkNodeStack::LinkNodeStack(/* args */)
{
    stackSize = 0;
    stackTop = nullptr;
}

LinkNodeStack::~LinkNodeStack()
{
    freeMemoryLinkNodeStack(stackTop);
}

int LinkNodeStack::size()
{
    return stackSize;
}

bool LinkNodeStack::empty()
{
    return stackSize == 0;
}

int LinkNodeStack::pop()
{
    if(empty())return -1;
    
    auto Tod = stackTop;

    stackTop = stackTop->next;
    delete Tod;
    stackSize --;   
    return top();
    
}

int LinkNodeStack::top()
{
    if(!empty())
        return stackTop->val;
    return -1;
}

int LinkNodeStack::push(int val)
{   
    ListNode *newListNode = new ListNode(val);

    stackSize++;
    newListNode -> next = stackTop;
    stackTop =  newListNode;

}

void LinkNodeStack::freeMemoryLinkNodeStack(auto *To_delete)
{
    while(!empty()){
        pop();
    }
}

int main(){

    

    return 0;
}

基于数组实现的栈

直接套用vector

#include <iostream>
#include <vector>

using namespace std;

class arrStack
{
private:
    int stackSize;
    vector<int> sta;
public:
    int pop();
    int top();
    int push(int val);
    bool empty();
    int size();

};




int main(){

}

int arrStack::pop()
{
    sta.pop_back();
    return sta.back();
}

int arrStack::top()
{
    if(!empty())
        return sta[0];
    else return -1;
}

int arrStack::push(int val)
{
    sta.push_back(val);
    return 0;
}

bool arrStack::empty()
{

    return size() == 0;
}

int arrStack::size()
{
    return sta.size();
}

其实没什么意义

算法直接

const int N = 1e5;
int arr[N];
int idx = -1;
void add(int x){
    idx ++;
    arr[idx] = x;
}
int top(){
   if(idx>=0)
    return arr[idx];
}
//size = idx + 1

队列

是一种类似于排队的先进先出，后进后出的数据结构

#include <queue>

queue<int> q;

q.fount();
q.push(val);
q.size();
q.empty();

#include <iostream>
using namespace std;

struct ListNode{

    int val;
    ListNode * next;

    ListNode(int val):val(val){
        next = nullptr;
    };
};

class Queue
{
private:

    ListNode *front,*rear;
    int quesize;    

    
public:
    Queue(/* args */);
    ~Queue();
    int size();
    bool empty();
    void push(int val);
    int pop();
    int peek();



};

Queue::Queue(/* args */)
{
    quesize = 0;
    front = nullptr;
    rear = nullptr;
}

Queue::~Queue()
{
    while(empty()){
        pop();
    }
}



int Queue::size()
{
    return quesize;
}

bool Queue::empty()
{
    return size() == 0;
}

void Queue::push(int val)
{
    ListNode *new_Push = new ListNode(val);

    if(empty()){
        front = rear = new_Push;
    }else{
            new_Push->next =  rear ->next;
            rear = new_Push;
    }
    quesize++;

}

int Queue::pop()
{
    
    quesize -- ;

    int c = peek();

    auto k = front;
    front = front->next;
    delete k;
    return c;
}

int Queue::peek()
{
    if(empty()) return -1;
    return front->val;
}

数组实现其实不用这么麻烦

#include <iostream>
using namespace std;


class arrqueue
{
private:
    int front;
    int quSize;
    int *arr;
    int CapaCity;
public:
    arrqueue(int CapaCity);
    ~arrqueue();
    int pop();
    int push(int val);
    int peek();
    int size();
    bool empty();
};

arrqueue::arrqueue(int CapaCity)
{
    quSize = 0;
    this->CapaCity =  CapaCity;
    arr = new int[CapaCity];
}

arrqueue::~arrqueue()
{
    delete[] arr;
}

int arrqueue::pop()
{
    int c = peek();

    front = (front+1)%CapaCity;
    quSize --;
    return c;
}

int arrqueue::push(int val)
{
    if(size() == CapaCity){
        cout <<" full "<<endl;
        
    }
    int rear = (front + rear)%CapaCity; // 循环数组最重要
    arr[rear] = val;
    quSize ++; 
}

int arrqueue::peek()
{
    if(empty()){
        return -1;
    }
    return arr[front]; /// 直接返回头
}

int arrqueue::size()
{
    return quSize;
}

bool arrqueue::empty()
{
    return size() == 0;
}

int main(){

    return 0;
}

双端队列

双端队列在头尾添加删除

#include <deque>

deque<int> dq;

dq.push_back(2);
dq.push_back(3);
dq.push_back(4);  // 尾端进
dq.push_front(6); //头进
dq.push_front(8); 

int font = dq.front();
int bk = dq.back();

构造双向队列

#include  <iostream>

using namespace std;



struct DoubleQueue{
    int val;
    DoubleQueue *left,*right;
    DoubleQueue(int cao):val(cao){
        left = right = nullptr;
    }
};

class dequeue
{
private:
    DoubleQueue *front ,*rear;
    int dequeueSize;
public:
    dequeue(/* args */):front(nullptr),rear(nullptr),dequeueSize(0){};
    int size();
    bool empty();
    void push(int val,bool st);
    void push_front(int val);
    void push_back(int val);
    int pop(bool st);
    int pop_front();
    int pop_back();
    int q_front();
    int q_back();

    ~dequeue();
};



dequeue::~dequeue()
{
    while(dequeueSize){
        pop_back();
    }
}

int dequeue::size()
{
    return dequeueSize;
}

bool dequeue::empty()
{

    return size() == 0;
}

void dequeue::push(int val, bool st)
{
    auto c = new DoubleQueue(val);
    dequeueSize ++;
    
    if(empty()){
        front = rear = c;
    }
    else if(st){
        front->left = c;
        c->right = front;
        front = c;
    }else{
        rear->right = c;
        c->left = rear;
        rear = c;
    }
}

void dequeue::push_front(int val)
{
    push(val,1);
}

void dequeue::push_back(int val)
{
    push(val,0);
}

int dequeue::pop(bool st)
{
    if(empty()){
        cout << " 2b 空了" << endl;
        return -1 ;
    }
    
    if(st){
        int ret = front->val;
        auto fNext = front->right;
        if(fNext!=nullptr){
            front->right = nullptr;
            fNext->left = nullptr;
        }

        delete front;

        front = fNext;

        return ret;
    }else{
        int ret = rear->val;

        auto rLeft = rear->left;

        if(rLeft!=nullptr){
            rLeft->right = nullptr;
            rear->left = nullptr;
        }

        delete rear;
        
        rear = rLeft;

        return ret;

    }
}

int dequeue::pop_front()
{
    return pop(1);
}

int dequeue::pop_back()
{
    return pop(0);
}

int dequeue::q_front()
{
    if(empty()){
        cout << " 2b 空了" << endl;
        return -1;
    }
    return front->val;
}

int dequeue::q_back()
{
    if(empty()){
        cout << " 2b 空了" << endl;
        return -1;
    }
    return rear->val;
}

也可以使用环形数组实现双向队列