C++数据结构算法篇Ⅰ

简介: C++数据结构算法篇Ⅰ

C++数据结构算法篇Ⅰ

📟作者主页:慢热的陕西人

🌴专栏链接:C++算法

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

主要内容讲解数据结构中的链表结构


Ⅰ. 链表

Ⅰ . Ⅰ 单链表

在C++中我们用list来代替动态的链表,但是new()申请动态内存是非常缓慢的。所以我们在竞赛中一般采用数组的方式模拟实现一种静态的链表;

首先我们需要涉及到四个变量:

//e[idx]  --- 用来存储第idx个节点的值
//ne[idx] --- 用来存储第idx个节点的next指针
//idx     --- 用来表示当前指向的是第idx个节点
//head    --- 用来指向第一个节点

所以如下我们实现一个例题:

代码:

#include<iostream>
using namespace std;
#define N 100010
int e[N];
int ne[N];
int x;
int idx;
int head;
char op;
int k;
void init()
{
    //我们规定最后一个空节点的地址为-1
    head = -1;
    idx = 0;
}
void add_to_head(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}
void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}
void remove(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    int m;
    cin >> m;
    init();
    while (m--)
    {
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}

Ⅰ. Ⅱ 双链表

双链表的实现方式类似,不过变量的参数有所变化

//l[idx]   ---表示的是第idx个节点的左节点的地址
//r[idx]   ---表示的是第idx个节点的有节点的地址
//e[idx]   ---存储的是第idx个节点的值
//head     ---存储的是头节点的地址
//tial     ---存储的是尾节点的地址

int idx, e[N], l[N], r[N];
int m, tail, head;
void init()
{
  //起始规定0为head,1为tail
  r[0] = 1, l[1] = 0;
  idx = 2;
  head = 0, tail = 1;
}
//在下标为k的右边插入x
void addr(int k, int x)
{
  e[idx] = x;
  r[idx] = r[k];
  l[idx] = k;
  r[k] = idx;
  l[r[k]] = idx;
  if (k == tail) tail = idx;
  idx++;
}
//在下标为k的左边插入x
void addl(int k, int x)
{
  addr(l[k], x);
  if (k == head) head = idx;
}
//删除第k个点
void remove(int k)
{
  r[l[k]] = r[k];
  l[r[k]] = l[k];
}
//最右侧插入一个数
void addt(int x)
{
  addr(tail, x);
}
//最左侧插入一个数
void addh(int x)
{
  addl(head, x);
}

到这本篇博客的内容就到此结束了。
如果觉得本篇博客内容对你有所帮助的话,可以点赞,收藏,顺便关注一下!
如果文章内容有错误,欢迎在评论区指正

相关文章
|
9天前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
|
20天前
|
存储 算法 关系型数据库
深入理解InnoDB索引数据结构和算法
1. **索引定义**:索引是提升查询速度的有序数据结构,帮助数据库系统快速找到数据。 2. **索引类型**:包括普通索引、唯一索引、主键索引、空间索引和全文索引,每种有特定应用场景。 3. **数据结构**:InnoDB使用B+树作为索引结构,确保所有节点按顺序排列,降低查询时的磁盘I/O。 4. **B+树特性**:所有数据都在叶子节点,非叶子节点仅存储索引,提供高效范围查询。 5. **索引优势**:通过减少查找数据所需的磁盘I/O次数,显著提高查询性能。 **总结:**InnoDB索引通过B+树结构,优化了数据访问,使得查询速度快,尤其适合大数据量的场景。
27 0
深入理解InnoDB索引数据结构和算法
|
12天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
16天前
|
算法
【算法与数据结构】二叉树(前中后)序遍历2
【算法与数据结构】二叉树(前中后)序遍历
|
23天前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法(二)
Java数据结构与算法-java数据结构与算法
66 1
|
9天前
|
算法 测试技术 C#
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
【广度优先搜索】【堆】【C++算法】407. 接雨水 II
|
9天前
|
算法 测试技术 Serverless
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
【二分查找】【C++算法】378. 有序矩阵中第 K 小的元素
|
9天前
|
算法 测试技术 C#
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
【字典树】【KMP】【C++算法】3045统计前后缀下标对 II
|
12天前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解(全源码优化)
【算法与数据结构】深入二叉树实现超详解(全源码优化)
|
12天前
|
存储 算法
【算法与数据结构】深入解析二叉树(二)之堆结构实现
【算法与数据结构】深入解析二叉树(二)之堆结构实现