C++版数据结构代码实现 |holyya.com

C++版数据结构代码实现

2023-07-03 12:45:15 深夜i -- --

C++ 数据结构代码实现

C++作为一种高级编程语言，可以用来实现许多不同类型的数据结构，如数组、链表、栈、队列、堆、树等等。在本文中，我们将简要介绍C++中一些常见的数据结构，并提供一些实现它们的示例代码。

### 数组

数组是一组连续的内存空间，可以保存相同类型的数据。C++中的数组可以使用以下语法声明和初始化：


int arr[5]; // 声明一个包含5个整数的数组
arr[0] = 1; // 初始化第一个元素
arr[1] = 2; // 初始化第二个元素
arr[2] = 3; // 初始化第三个元素
arr[3] = 4; // 初始化第四个元素
arr[4] = 5; // 初始化第五个元素

C++中的数组可以使用下标访问其元素。例如：


cout << arr[0]; // 输出数组的第一个元素

### 链表

链表是一种动态数据结构，它由节点组成，每个节点包含一个值和一个指向下一个节点的指针。链表可以使用以下代码实现：


struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};
class LinkedList {
public:
  LinkedList()
    head = NULL;
  
  ~LinkedList() {
    ListNode *cur = head;
    while (cur != NULL) {
      ListNode *temp = cur->next;
      delete cur;
      cur = temp;
    }
  }
  void addNode(int x) {
    ListNode *node = new ListNode(x);
    if (head == NULL)
      head = node;
     else {
      ListNode *cur = head;
      while (cur->next != NULL)
        cur = cur->next;
      
      cur->next = node;
    }
  }
private:
  ListNode *head;
};

在上面的代码中，我们定义了一个`ListNode`结构体来表示链表中的每个节点。我们还定义了一个`LinkedList`类，它包含一个头节点指针，并提供了`addNode`函数来添加新节点。注意，在销毁链表时，我们需要遍历整个链表并逐个删除每个节点以避免内存泄漏。

### 栈

栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表实现。以下是一个使用数组实现的栈的示例代码：


class Stack {
public:
  Stack()
    top = -1;
  
  ~Stack() {
    delete[] data;
  }
  void push(int x) {
    data[++top] = x;
  }
  void pop() {
    if (top >= 0) {
      top--;
    }
  }
  int peek() {
    if (top >= 0) {
      return data[top];
    }
    return -1;
  }
private:
  int data[100];
  int top;
};

在上面的代码中，我们定义了一个`Stack`类，并使用数组来保存栈中的元素。我们提供了`push`、`pop`和`peek`函数来添加、删除和查看栈顶元素。

### 队列

队列是一种先进先出（FIFO）的数据结构，也可以使用数组或链表实现。以下是一个使用链表实现的队列的示例代码：


class Queue {
public:
  Queue() {
    front = NULL;
    rear = NULL;
  }
  ~Queue() {
    while (front != NULL) {
      Node *temp = front;
      front = front->next;
      delete temp;
    }
  }
  void enqueue(int x) {
    Node *node = new Node(x);
    if (front == NULL) {
      front = node;
    } else {
      rear->next = node;
    }
    rear = node;
  }
  void dequeue() {
    if (front != NULL) {
      Node *temp = front;
      front = front->next;
      delete temp;
    }
  }
  int peek() {
    if (front != NULL) {
      return front->val;
    }
    return -1;
  }
private:
  struct Node {
    int val;
    Node *next;
    Node(int x) : val(x), next(NULL) {}
  };
  Node *front;
  Node *rear;
};

在上面的代码中，我们定义了一个`Queue`类，并使用链表来保存队列中的元素。我们提供了`enqueue`、`dequeue`和`peek`函数来添加、删除和查看队列的头部元素。注意，在销毁队列时，我们需要遍历整个链表并逐个删除每个节点以避免内存泄漏。

### 堆

堆是一种完全二叉树，可以用来实现优先队列。C++中的堆可以使用`priority_queue`类来实现，如下所示：


#include <queue>
using namespace std;
int main() {
  priority_queue<int> q;
  q.push(3);
  q.push(1);
  q.push(4);
  q.push(1);
  while (!q.empty()) {
    cout << q.top() << " ";
    q.pop();
  }
}

在上面的代码中，我们声明了一个`priority_queue`对象，它用来保存整数，并使用`push`添加四个元素。然后，我们使用`top`来查看堆顶元素，并使用`pop`来删除堆顶元素。

### 树

树是一种递归的数据结构，由一个根节点和若干子树组成。在C++中可以使用以下代码来实现树的结构：


struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Tree {
public:
  Tree() {
    root = NULL;
  }
  ~Tree() {
    destroy(root);
  }
  void insert(int x) {
    if (root == NULL) {
      root = new TreeNode(x);
    } else {
      TreeNode *cur = root;
      while (cur != NULL) {
        if (x < cur->val) {
          if (cur->left == NULL) {
            cur->left = new TreeNode(x);
            break;
          }
          cur = cur->left;
        } else {
          if (cur->right == NULL) {
            cur->right = new TreeNode(x);
            break;
          }
          cur = cur->right;
        }
      }
    }
  }
  bool search(int x) {
    TreeNode *cur = root;
    while (cur != NULL) {
      if (x == cur->val) {
        return true;
      } else if (x < cur->val) {
        cur = cur->left;
      } else {
        cur = cur->right;
      }
    }
    return false;
  }
private:
  TreeNode *root;
  void destroy(TreeNode *node) {
    if (node != NULL) {
      destroy(node->left);
      destroy(node->right);
      delete node;
    }
  }
};

在上面的代码中，我们定义了一个`TreeNode`结构体来表示树中的每个节点，以及一个`Tree`类，它包含一个指向根节点的指针，并提供了`insert`和`search`函数来插入和搜索树中的元素。注意，在销毁树时，我们使用递归函数来遍历整个树并逐个删除每个节点以避免内存泄漏。

### 总结

C++是一种非常强大的编程语言，可以用来实现许多不同类型的数据结构。我们在本文中简要介绍了C++中一些常见的数据结构，并提供了一些示例代码。希望这些示例代码能帮助您更好地理解和掌握C++中的数据结构实现。

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

下一篇: Node.js 实现表格的增删改查功能

评论区

()

相似文章