您的位置:

数据结构: C++实现常用算法及数据结构

一、数组与链表

1、数组是一组连续的内存空间,可以进行随机访问,其增删操作较为低效。链表是由一系列结点组成,每个结点包含数据和指向下一个结点的指针,其插入删除操作较为高效,但是访问元素时需要遍历整个链表,时间复杂度为O(n)。

2、示例代码:

//定义一个数组
int arr[5] = {1,2,3,4,5};

//定义一个链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

//创建链表
ListNode* head = new ListNode(1);
ListNode* node1 = new ListNode(2);
ListNode* node2 = new ListNode(3);
ListNode* node3 = new ListNode(4);
ListNode* node4 = new ListNode(5);
head->next = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;

二、栈和队列

1、栈是一种后进先出的数据结构,其存储方式可以使用数组或链表实现。可以使用栈来实现一些逆序输出的问题,如字符串逆置、括号匹配等。队列是一种先进先出的数据结构,其存储方式同样可以使用数组或链表实现。队列可以用来解决广度优先遍历的问题。

2、示例代码:

//定义一个栈
stack stk;
stk.push(1);
stk.push(2);
stk.push(3);
int x = stk.top(); //获取栈顶元素
stk.pop(); //弹出栈顶元素

//定义一个队列
queue
    q;
q.push(1);
q.push(2);
q.push(3);
int x = q.front(); //获取队首元素
q.pop(); //弹出队首元素

   
  

三、哈希表

哈希表是一种根据键(key)直接访问内存地址的数据结构,其查找、插入、删除操作的平均时间复杂度为O(1)。哈希函数是实现哈希表的关键,决定了如何将键转化为内存地址。哈希函数需要满足以下两个条件:(1)散列均匀;(2)尽量避免哈希冲突。常用的哈希函数包括取模法、乘法哈希等。

2、示例代码:

//定义一个哈希表
unordered_map mp;
mp["apple"] = 10;
mp["orange"] = 3;

//查找元素
if (mp.find("apple") != mp.end()) {
    int x = mp["apple"];
}

//遍历哈希表
for (auto& it : mp) {
    cout << it.first << ":" << it.second << endl;
}

  

四、堆

堆是一种动态的数据结构,它分为最大堆和最小堆。其中最大堆要求父结点的值大于或等于子结点的值,最小堆要求父结点的值小于或等于子结点的值。堆可以用于解决一些查找最大/小值的问题,如Top K 问题、求中位数等。

2、示例代码:

//定义一个最小堆
priority_queue, greater
   > pq;
pq.push(3);
pq.push(1);
pq.push(4);
int x = pq.top(); //获取堆顶元素
pq.pop(); //弹出堆顶元素

   
  

五、图

图由结点和边组成,其中结点可以包含任意信息,边可以包含权值等信息。图的遍历方式有深度优先遍历和广度优先遍历。深度优先遍历可以使用递归或栈来实现,广度优先遍历可以使用队列来实现。图的常见算法包括最短路径算法、最小生成树算法、网络流算法等。

2、示例代码:

//定义一个图(使用邻接表表示)
vector
   > graph(n);
graph[0].push_back(1);
graph[0].push_back(2);
graph[1].push_back(3);
graph[2].push_back(3);

//DFS遍历
vector
     visited(n); //标记是否访问过
void DFS(int node) {
    visited[node] = true;
    //访问当前结点
    for (int i = 0; i < graph[node].size(); i++) {
        int next_node = graph[node][i];
        if (!visited[next_node]) {
            DFS(next_node);
        }
    }
}

//BFS遍历
queue
      q;
vector
       visited(n); //标记是否访问过
void BFS(int start) {
    q.push(start);
    visited[start] = true;
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        //访问当前结点
        for (int i = 0; i < graph[node].size(); i++) {
            int next_node = graph[node][i];
            if (!visited[next_node]) {
                q.push(next_node);
                visited[next_node] = true;
            }
        }
    }
}

      
     
    
   
  
Java数据结构学习笔记

2023-05-11
数据结构: C++实现常用算法及数据结构

2023-05-13
C++实现数据结构和算法

2023-05-13
数据结构版c语言视频教程30课时,c++数据结构视频

2022-11-27
c语言算法和数据结构关系,数据结构与算法C语言

2022-11-30
java数据结构,Java数据结构与算法

2022-12-02
C++ 数据结构实现

一、数据结构概述 数据结构是计算机科学的基本概念之一,是指数据的组织、管理和存储方式。在计算机科学中,数据结构是一种特殊的格式,用于组织和存储数据。数据结构可分为线性结构、树结构、图结构等不同类型。在

2023-12-08
用C++实现高效数据结构和算法

2023-05-13
java数据结构,java数据结构和c语言数据结构区别

2023-01-10
C++程序设计:实现高效算法及数据结构

2023-05-13
golang数据结构库,golang数据结构与算法

2022-11-27
c语言数据结构与算法,c语言数据结构与算法第44讲

2022-11-24
C++函数库:快速实现常见数据结构和算法

一、背景介绍 在 C++ 的程序开发中,常常需要实现各种常见的数据结构和算法。然而,这些常见的数据结构和算法实现起来并不是很简单,会消耗程序员大量的时间和精力。为应对这一挑战,现在有许多 C++ 函数

2023-12-08
c语言基础数据结构,数据结构C语言

2022-12-01
C++数据结构库

2023-05-13
数据结构java,数据结构java语言描述

2022-12-01
使用C++实现高效数据结构和算法

2023-05-13
C++模板类:实现通用数据结构和算法

一、模板类的概念 模板是C++中的一种特殊的数据类型,可以将类型作为参数进行操作。模板类是使用模板创建的,提供了一种通用的数据结构和算法的实现方式。模板类的定义一般包括模板参数列表、类的定义和成员函数

2023-12-08
先学c语言数据结构,数据结构的c语言基础

2022-11-29
了解C++的数据结构和算法实现

2023-05-13