C++ 数据结构_业界新闻

发布时间:2024-07-19 21:48

阅读量:2

C++ 数据结构

引言

数据结构是计算机科学中的一个核心概念，它涉及到如何在计算机中组织和存储数据，以便高效地进行数据访问和修改。C++作为一种高效的编程语言，提供了丰富的内置数据类型和库，支持各种复杂的数据结构实现。本文将探讨C++中常用的数据结构，包括数组、链表、栈、队列、树和图等，并分析它们的特点、应用场景以及如何在C++中实现这些数据结构。

数组

数组是C++中最基本的数据结构，它允许存储相同类型的数据元素集合。数组的特点是元素在内存中连续存储，可以通过索引快速访问。然而，数组的长度在定义时固定，不易动态扩展。

数组的声明和初始化

int arr[10]; // 声明一个包含10个整数的数组 int arr[5] = {1, 2, 3, 4, 5}; // 声明并初始化数组

数组的访问和修改

int firstElement = arr[0]; // 访问第一个元素 arr[2] = 10; // 修改第三个元素

链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。链表的特点是元素不连续存储，通过指针连接，便于插入和删除操作。

单链表的实现

struct Node {     int data;     Node* next; };  class LinkedList { public:     LinkedList() : head(nullptr) {}     void insert(int value);     void deleteValue(int value);     void display(); private:     Node* head; };

链表的插入和删除操作

void LinkedList::insert(int value) {     Node* newNode = new Node{value, nullptr};     if (head == nullptr) {         head = newNode;     } else {         Node* current = head;         while (current->next != nullptr) {             current = current->next;         }         current->next = newNode;     } }  void LinkedList::deleteValue(int value) {     if (head == nullptr) return;      if (head->data == value) {         Node* temp = head;         head = head->next;         delete temp;         return;     }      Node* current = head;     while (current->next != nullptr && current->next->data != value) {         current = current->next;     }      if (current->next != nullptr) {         Node* temp = current->next;         current->next = current->next->next;         delete temp;     } }

栈和队列

栈和队列是两种特殊的线性数据结构，它们对元素的插入和删除操作有特定的限制。

栈

栈是一种后进先出（LIFO）的数据结构。在C++中，可以使用标准模板库（STL）中的stack容器来实现栈。

#include <stack>  std::stack<int> s; s.push(1); // 入栈 s.pop(); // 出栈 int top = s.top(); // 获取栈顶元素

队列

队列是一种先进先出（FIFO）的数据结构。在C++中，可以使用STL中的queue容器来实现队列。

#include <queue>  std::queue<int> q; q.push(1); // 入队 q.pop(); // 出队 int front = q.front(); // 获取队首元素

树和图

树和图是两种非线性数据结构，用于表示元素之间的复杂关系。

树

树是一种层次化的数据结构，由节点组成，每个节点有零个或多个子节点。常见的树结构包括二叉树、二叉搜索树（BST）、平衡树（如AVL树）等。

struct TreeNode {     int value;     TreeNode* left;     TreeNode* right; };

图

图是由节点（或顶点）和边组成的数据结构，用于表示对象之间的多对多关系。图的表示方法有邻接矩阵和邻接表等。

#include <vector>  class Graph { public:     Graph(int vertices) : adjacencyList(vertices) {}     void addEdge(int src, int dest);     void display(); private:     std::vector<std::vector<int>> adjacencyList; };