首页 > 其他分享 >数据结构

数据结构

时间：2024-05-08 13:35:03浏览次数：14  
标签：结点 idx int tt 二叉树 数据结构 节点

数据结构

链表

  • struct结构体构造链表
//定义ListNode结构、三种构造函数
struct ListNode {
     int val;
     ListNode *next;
     ListNode() : val(0), next(nullptr) {}
     ListNode(int x) : val(x), next(nullptr) {}
     ListNode(int x, ListNode *next) : val(x), next(next) {}
 };

单链表

// head存储链表头， e[]存储节点的值, ne[]存储节点的next指针, idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数字a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++;
}

// 将头结点删除, 需保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

// e[]表示节点的值，l[]表示节点的左指针, r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
 	l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

二叉树

  • 二叉链表

二叉树每个结点最多有两个孩子，所以它有一个数据域和两个指针域。
我们称这样的链表叫做二叉链表。
如图：

lchild data rchil
  • 二叉树的二叉链表结构定义
/*定义二叉树的结构*/
typedef struct Node
{
    char data;                    /*数据域*/
    struct Node *lchild, *rchild; /*左子树和右子树*/
} * BiTree, BiNode;
/*整棵树和结点名称*/
  • 二叉树的遍历
前序遍历：中 左 右
中序遍历：左 中 右
后序遍历：左 右 中
// 注意观察规律，就会很好记忆

// 遍历的示例代码
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*定义二叉树的结构*/
typedef struct Node
{
    char data;                    /*数据域*/
    struct Node *lchild, *rchild; /*左子树和右子树*/
} * BiTree, BiNode;
/*整棵树和结点名称*/

/*先需创建二叉树*/
void CreateBiTree(BiTree &T)
{
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiNode; /*创建一个新节点*/
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    /*递归创建*/
}
void InOrderTraverse(BiTree T)
{
    /*中序遍历*/
    if (T)
    {
        InOrderTraverse(T->lchild);
        cout << T->data;
        InOrderTraverse(T->rchild);
    }
}
void PreOrderTraverse(BiTree T)
{
    /*先序遍历*/
    if (T)
    {
        cout << T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}
void PostOrderTraverse(BiTree T)
{
    /*后序遍历*/
    if (T)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        cout << T->data;
    }
}
/*统计二叉树中结点的个数*/
int NodeCount(BiTree T)
{
    if (T == NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
/*求树的深度*/
int Depth(BiTree T)
{
    if (T == NULL)
        return 0;
    else
    {
        int i = Depth(T->lchild);
        int j = Depth(T->rchild);
        return i > j ? i + 1 : j + 1;
    }
}
/*复制二叉树*/
void Copy(BiTree T, BiTree &NewT)
{
    if (T = NULL)
    {
        NewT = NULL;
        return;
    }
    else
    {
        NewT = new BiNode;
        NewT->data = T->data;
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}
/*统计二叉树中叶子结点的个数*/
int LeafCount(BiTree T)
{
    if (!T)
        return 0;
    if (!T->lchild && !T->rchild)
        return 1;
    /*如果二叉树左子树和右子树皆为空，说明该二叉树根节点为叶子结点，结果为1*/
    else
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}
/*二叉树中从每个叶子结点到跟结点的路径*/
void PrintAllPath(BiTree T, char path[], int pathlen)
{
    int i;
    if (T != NULL)
    {
        path[pathlen] = T->data; /*将当前结点放入路径中*/
        if (T->lchild == NULL && T->rchild == NULL)
        {
            /*若这个节点是叶子结点*/
            for (i = pathlen; i >= 0; i--)
                cout << path[i] << "　";
            cout << "\n";
        }
        else
        {
            PrintAllPath(T->lchild, path, pathlen + 1);
            PrintAllPath(T->rchild, path, pathlen + 1);
        }
    }
}
/*判断二叉树是否为空*/
int BiTree_empty(BiTree T)
{
    if (T)
        return 1;
    else
        return 0;
}
int main()
{
    BiTree T;
    //测试数据AB#CD##E##F#GH###
    cout << "先序遍历输入(以#结束)：";
    CreateBiTree(T);
    cout << "中序遍历输出：";
    InOrderTraverse(T);
    cout << endl
         << "先序遍历输出:";
    PreOrderTraverse(T);
    cout << "\n"
         << "后序遍历输出:";
    PostOrderTraverse(T);
    cout << endl
         << "树的深度:" << Depth(T);
    cout << endl
         << "结点的个数:" << NodeCount(T);
    cout << endl
         << "二叉树中从每个叶子结点到根结点的所有路径：" << endl;
    char path[256];
    int pathlen = 0;
    PrintAllPath(T, path, pathlen);
    return 0;
}
  • 特殊二叉树
  1. 满二叉树
    一颗二叉树中，如果所有分支结点都存在左子树和右子树且左右子树都在同一层上，这样的二叉树成为满二叉树
    如图：

请添加图片描述

  1. 斜树

所有的结点都只有左子树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。二者统称斜树。（这玩意竖着看其实就是线性表）

  1. 完全二叉树

若一棵有n个结点的二叉树（按照层序规律编号），其中编号为i（1<=i<=n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置相同，则这棵树是完全二叉树，如图：

请添加图片描述

完全二叉树的性质：
1）叶节点只可能在最下两层
2）最下层的叶子一定集中在左部连续位置
3）结点度为 1，则该结点只有左孩子。
4）倒数第二层，如果有叶节点，则一定位于右部连续位置。
5）相同结点的二叉树，完全二叉树的深度最小

栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[++ tt] = x;

// 从栈顶弹出一个数
tt --;

// 栈顶的值
stk[tt];

// 判断栈是否为空， 如果tt > 0, 则表示不为空
if(tt > 0)
{
    
}

队列

  • 普通队列
// hh 表示队头， tt表示队尾
 int q[N], hh = 0; tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}
  • 循环队列
// hh 表示队头, tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if(tt == N) tt = 0;

// 从队头弹出一个数
hh ++;
if(hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{

}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数
int stk[N], tt = 0;  // stk 单调栈 tt 当前所指的位置
for(int i = 1; i <= n; i ++ )
{
    while(tt && check(stk[tt], i)) tt --;
    stk[ ++ tt] = i;
}

单调队列

常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1; // hh队头  tt队尾
for(int i = 0; i < n; i ++ )
{
	while(hh <= tt && check_out(q[hh])) hh ++;  // 判断队头是否滑出窗口
    while(hh <= tt && check(q[tt], i)) tt --;
    q[ ++ tt] = i;
}

KMP

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组
for(int i = 2, j = 0; i <= m; i ++ )
{
    while(j && p[i] != p[j + 1]) j = ne[j];
    if(p[i] == p[j + 1]) j ++;
    ne[i] = j;
}

// 匹配
for(int i = 1, j = 0; i <= n; i ++ )
{
    while(j && s[i] != p[j + 1]) j = ne[j];
    if(s[i] == p[j + 1]) j ++ ;
    if(j == m)
    {
		j = ne[j];
        // 匹配成功后的逻辑
    }
}

Trie树

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

并查集

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

堆

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

一般哈希

(1) 拉链法
    int h[N], e[N], ne[N], idx;

    // 向哈希表中插入一个数
    void insert(int x)
    {
        int k = (x % N + N) % N;
        e[idx] = x;
        ne[idx] = h[k];
        h[k] = idx ++ ;
    }

    // 在哈希表中查询某个数是否存在
    bool find(int x)
    {
        int k = (x % N + N) % N;
        for (int i = h[k]; i != -1; i = ne[i])
            if (e[i] == x)
                return true;

        return false;
    }

(2) 开放寻址法
    int h[N];

    // 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
    int find(int x)
    {
        int t = (x % N + N) % N;
        while (h[t] != null && h[t] != x)
        {
            t ++ ;
            if (t == N) t = 0;
        }
        return t;
    }

字符串哈希

核心思想：将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果

typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64

// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
    h[i] = h[i - 1] * P + str[i];
    p[i] = p[i - 1] * P;
}

// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

STL简介

vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反

标签：结点,idx,int,tt,二叉树,数据结构,节点
From： https://www.cnblogs.com/hnu-hua/p/18179469

相关文章

  • MySQL索引数据结构
    什么是索引索引在项目中还是比较常见的，它是帮助MySOL高效获取数据的数据结构，主要是用来提高数据检索的效率，降低数据库的IO成本，同时通过索引列对数据进行排序，降低数据排序的成本，也能降低了CPU的消耗。索引的底层数据结构MySQL的默认的存储引擎InnoDB采用的B+树的数据结构来存储......
  • 常用的数据结构
    日常开发中，可能会用到的数据结构类型数组一组相同类型的元素的集合，可以通过下标进行访问和操作。在C#中，有Array、ArrayList、List时间复杂度：查找是O(N)。插入和删除是O(N)。数组通过下标直接访问元素，时间复杂度是O(1)。数据的每次新增或者删除，数据需要重新排列顺序，时间复杂......
  • 数据结构
    前缀和结构特征：连续子数组的元素和技巧：len（前缀和）=len(list)+1前缀和可以作为list的v，也可做为list的index！----哈希表(问的是xxx的数目)presum=[0]+list(accumulate(nums))---得到前缀和数组accumulate函数可以累加nums的值哈希表使用......
  • 王道数据结构个人向笔记-第二章（线性表）
    目录2.1线性表的定义和基本操作2.2顺序表2.2.1顺序表的定义2.2.2顺序表的插入、删除（实现是基于静态分配）2.2.3顺序表的查找2.3链表2.3.1单链表的定义2.3.2单链表的插入删除2.3.3单链表的查找2.3.4单链表的建立2.3.4双链表2.3.5循环链表2.3.6静态链表2.3.7顺序表和链......
  • Redis核心数据结构与高性能原理
    参考-图灵课堂-https://vip.tulingxueyuan.cnhttps://www.runoob.com/redis/redis-tutorial.html 常见得数据类型：Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sortedset：有序集合)。stringstring是redis最基本的类型，你可以理解成与Memcached一......
  • 数据结构--线段树合并
    线段树合并前置知识权值线段树，动态开点线段树简单说明一下，权值线段树就是以值域开的一棵线段树，而动态开点就是因为值域过大导致线段树开不下，于是开一棵残疾的线段树。线段树合并模板例：给定两个数列\(a,b\)，求\(\suma_i+b_i\)当然我只是为了引出模板。代码(\(x\)表......
  • 好题——数学与数据结构
    前言本文章将会持续更新，主要是一些个人觉得比较妙的题，主观性比较强（给自己记录用的），有讲错请补充。带！号的题是基础例题，带*号的是推荐首先完成的题（有一定启发性的）。组合数P6620[省选联考2020A卷]组合数问题运用斯特林数好的例题，普通幂转下降幂。用到第二类斯特林数。\[......
  • 数据结构-二叉树的初始化
    数据结构-二叉树的相关初始化/*************************************************/***@filename: DcirLLinkInsert*@brief对双向循环链表插入的功能实现*@[email protected]*@date2024/04/29*@version1.0：在下坂本，有何贵干*@property：none......
  • python3的数据结构
    一.列表(列表可以修改,字符串和元组不能)list.append(x)-把一个元素添加到列表的结尾-相当于a[len(a):]=[x]list.extend(L)-通过添加指定列表的所有元素来扩充列表-相当于a[len(a):]=Llist.insert(i,x)-在指定位置插入一个元素-a.insert(0,x)会插入到整个列表之前-a.i......
  • .h5ad数据结构解释（anndata 数据格式）
    官方网站：https://anndata.readthedocs.io/en/latest/下面的内容官网都有概述h5ad文件提供了一种可扩展的方式来记录数据及其注释(annotation)，主要包含X,obs,var,uns等多个部分，分别存储不同的信息。结构如下图所示X是表达量矩阵，用来联系obs和var。具体来说X是一个稀疏......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99