一、数据结构概述
数据结构是计算机科学的基本概念之一,是指数据的组织、管理和存储方式。在计算机科学中,数据结构是一种特殊的格式,用于组织和存储数据。数据结构可分为线性结构、树结构、图结构等不同类型。在 C++ 语言中,可以通过类和模板来实现各种不同类型的数据结构。
二、链表实现
链表是一种常见的数据结构,可以在任意节点处插入或删除数据,而无需移动其他数据。在 C++ 中,可以使用类实现链表。下面是一个简单的链表实现,包括节点和链表类:
// 链表节点类 class ListNode { public: int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; // 链表类 class LinkedList { public: ListNode *head; LinkedList() { head = NULL; } // 在头部插入一个节点 void insert(int x) { ListNode *node = new ListNode(x); node->next = head; head = node; } // 删除第一个节点 void remove() { if (head == NULL) return; ListNode *node = head; head = head->next; delete node; } // 打印链表 void print() { ListNode *node = head; while (node != NULL) { cout << node->val << " -> "; node = node->next; } cout << "NULL" << endl; } };
使用该链表类可以很方便地进行链表操作:
LinkedList list; list.insert(1); // 插入 1 list.insert(2); // 插入 2 list.insert(3); // 插入 3 list.print(); // 输出 3 -> 2 -> 1 -> NULL list.remove(); // 删除 3 list.print(); // 输出 2 -> 1 -> NULL
三、栈实现
栈是一种后进先出(LIFO)的数据结构,可以在栈顶插入和删除数据,非栈顶数据不能访问。在 C++ 中,可以使用类和模板实现栈。下面是一个简单的栈实现:
templateclass Stack { private: vector data; public: // 入栈 void push(T x) { data.push_back(x); } // 取栈顶元素 T top() { if (data.empty()) return -1; // 栈为空 return data.back(); } // 出栈 void pop() { if (data.empty()) return; // 栈为空 data.pop_back(); } // 判断栈是否为空 bool empty() { return data.empty(); } // 返回栈中元素个数 int size() { return data.size(); } };
使用该栈类可以很方便地进行栈操作:
Stack<int> s; s.push(1); // 入栈 1 s.push(2); // 入栈 2 s.push(3); // 入栈 3 cout << s.top() << endl; // 输出 3 s.pop(); // 出栈 3 cout << s.top() << endl; // 输出 2 cout << s.size() << endl; // 输出 2 cout << s.empty() << endl; // 输出 0
四、队列实现
队列是一种先进先出(FIFO)的数据结构,可以在队尾插入和队头删除数据。在 C++ 中,可以使用类和模板实现队列。下面是一个简单的队列实现:
templateclass Queue { private: vector data; public: // 入队 void push(T x) { data.push_back(x); } // 取队头元素 T front() { if (data.empty()) return -1; // 队列为空 return data.front(); } // 出队 void pop() { if (data.empty()) return; // 队列为空 data.erase(data.begin()); } // 判断队列是否为空 bool empty() { return data.empty(); } // 返回队列中元素个数 int size() { return data.size(); } };
使用该队列类可以很方便地进行队列操作:
Queue<int> q; q.push(1); // 入队 1 q.push(2); // 入队 2 q.push(3); // 入队 3 cout << q.front() << endl; // 输出 1 q.pop(); // 出队 1 cout << q.front() << endl; // 输出 2 cout << q.size() << endl; // 输出 2 cout << q.empty() << endl; // 输出 0
五、堆实现
堆是一种特殊的树型数据结构,满足堆属性(heap property):对于每个节点 X,其父节点的键值小于或等于 X 的键值,子节点的键值大于或等于 X 的键值。在 C++ 中,可以使用类和模板实现堆。下面是一个简单的最小堆实现:
templateclass MinHeap { private: vector data; public: // 向堆中插入一个元素 void push(T x) { data.push_back(x); int cur = data.size() - 1; int parent = (cur - 1) / 2; while (cur > 0 && data[parent] > data[cur]) { swap(data[cur], data[parent]); cur = parent; parent = (cur - 1) / 2; } } // 取堆顶元素 T top() { if (data.empty()) return -1; // 堆为空 return data[0]; } // 删除堆顶元素 void pop() { if (data.empty()) return; // 堆为空 swap(data[0], data.back()); data.pop_back(); int cur = 0; int left_child = cur * 2 + 1; while (left_child < data.size()) { int right_child = (cur + 1) * 2; int min_child = left_child; if (right_child < data.size() && data[right_child] < data[left_child]) { min_child = right_child; } if (data[cur] <= data[min_child]) break; swap(data[cur], data[min_child]); cur = min_child; left_child = cur * 2 + 1; } } // 判断堆是否为空 bool empty() { return data.empty(); } // 返回堆中元素个数 int size() { return data.size(); } };
使用该堆类可以很方便地进行堆操作:
MinHeap<int> h; h.push(3); // 插入元素 3 h.push(1); // 插入元素 1 h.push(2); // 插入元素 2 cout << h.top() << endl; // 输出 1 h.pop(); // 删除堆顶元素 cout << h.top() << endl; // 输出 2 cout << h.size() << endl; // 输出 2 cout << h.empty() << endl; // 输出 0
六、总结
C++ 可以通过类和模板来实现各种不同类型的数据结构,例如链表、栈、队列和堆。这些数据结构在算法和数据处理中都有广泛应用。