C++代码实现数据结构 |21xrx.com

C++代码实现数据结构

2023-07-01 16:04:46 深夜i -- --

C++ 代码数据结构实现

C++是一种很强大的编程语言，可以用来实现许多各种各样的数据结构。数据结构是计算机科学中一个非常重要的领域，它涉及到如何组织和管理数据以及对数据进行操作和处理。

C++实现数据结构的方法有很多种，比如使用数组、指针、链表、堆、栈、队列等等。其中，最常见的数据结构包括数组、链表、树和图。

数组是一种最基本的数据结构之一，其可以容易地存储一系列的数据。例如，下面是一个用数组实现的栈：


class Stack {
private:
  int top;
  int arr[SIZE];
public:
  Stack()
    top = -1;
  
  void push(int x) {
    if (top >= SIZE - 1)
      cout << "Stack Overflow" << endl;
      return;
    
    arr[++top] = x;
  }
  int pop() {
    if (top < 0)
      cout << "Stack Underflow" << endl;
      return 0;
    
    return arr[top--];
  }
  bool isEmpty() {
    return (top == -1);
  }
};

链表是另一种比较常见的数据结构，其可以动态地分配内存空间，而且插入和删除操作比数组更加高效。例如，下面是一个使用链表实现的栈：


class Node {
public:
  int data;
  Node* next;
};
class Stack {
private:
  Node* top;
public:
  Stack()
    top = nullptr;
  
  void push(int x) {
    Node* newNode = new Node();
    newNode->data = x;
    newNode->next = top;
    top = newNode;
  }
  int pop() {
    if (top == nullptr)
      cout << "Stack Underflow" << endl;
      return 0;
    
    int res = top->data;
    Node* temp = top;
    top = top->next;
    delete temp;
    return res;
  }
  bool isEmpty() {
    return (top == nullptr);
  }
};

树是一种层次结构的数据结构，其通常用于表示具有层次关系的数据。例如，下面是一个使用树实现的二叉搜索树：


class Node {
public:
  int key;
  Node* left;
  Node* right;
};
class BinarySearchTree {
private:
  Node* root;
  Node* insertRec(Node* root, int key) {
    if (root == nullptr) {
      Node* newNode = new Node();
      newNode->key = key;
      newNode->left = newNode->right = nullptr;
      return newNode;
    }
    if (key < root->key)
      root->left = insertRec(root->left, key);
    else if (key > root->key)
      root->right = insertRec(root->right, key);
    return root;
  }
public:
  BinarySearchTree()
    root = nullptr;
  
  void insert(int key) {
    root = insertRec(root, key);
  }
  bool search(int key) {
    Node* temp = root;
    while (temp != nullptr) {
      if (temp->key == key)
        return true;
      else if (temp->key > key)
        temp = temp->left;
      else
        temp = temp->right;
    }
    return false;
  }
};

图是一种非常复杂的数据结构，其可以用来表示任何一种复杂的关联关系。例如，下面是一个使用图实现的广度优先搜索算法：


class Graph {
private:
  int V;
  list<int>* adjList;
public:
  Graph(int V) {
    this->V = V;
    adjList = new list<int>[V];
  }
  void addEdge(int v, int w) {
    adjList[v].push_back(w);
  }
  void BFS(int start) {
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
      visited[i] = false;
    list<int> queue;
    visited[start] = true;
    queue.push_back(start);
    while (!queue.empty()) {
      start = queue.front();
      cout << start << " ";
      queue.pop_front();
      for (auto i = adjList[start].begin(); i != adjList[start].end(); ++i) {
        if (!visited[*i]) {
          visited[*i] = true;
          queue.push_back(*i);
        }
      }
    }
  }
};

在实现数据结构时，我们需要注意一些问题，比如数据结构的正确性、操作的效率、空间使用等等。同时，我们还需要不断地学习和掌握最新的编程技术和最优秀的实践。只有不断地努力和学习，才能够写出高效、健壮而且优雅的代码，实现更加出色的数据结构，从而更好地服务于我们的实际需求。

上一篇: idea打包java可执行jar包

下一篇: C语言和C++语言有哪些区别？

评论区

()

相似文章