一、線性數據結構
線性數據結構是指數據元素之間存在一對一的相鄰關係的數據結構。常見的線性數據結構包括數組、鏈表和棧。
1. 數組
template <class T>
class Array {
public:
explicit Array(int size): size_(size) {
data_ = new T[size];
}
~Array() {
delete [] data_;
}
T& operator[](int idx) {
if (idx >= size_) {
throw std::out_of_range("Out of range");
}
return data_[idx];
}
int size() const {
return size_;
}
private:
T* data_;
int size_;
};數組是一組具有相同數據類型的數據元素按照一定的順序排列而成，並使用一個名字命名。數組有一個重要的特點就是隨機訪問，而且訪問速度非常快。
2. 鏈表
template<class T>
struct Node {
T val;
Node<T>* next;
Node(T val):val(val), next(nullptr) {
// Constructor
}
};
template<class T>
class LinkedList {
public:
LinkedList(): head(nullptr) {
}
~LinkedList() {
while (head) {
Node<T>* next = head->next;
delete head;
head = next;
}
}
void insert(T val) {
Node<T>* node = new Node<T>(val);
if (!head) {
head = node;
return;
}
Node<T>* tmp = head;
while (tmp->next) {
tmp = tmp->next;
}
tmp->next = node;
}
bool deleteNode(T val) {
if (!head) {
return false;
}
if (head->val == val) {
Node<T>* tmp = head->next;
delete head;
head = tmp;
return true;
}
Node<T>* cur = head;
while (cur->next) {
if (cur->next->val == val) {
Node<T>* tmp = cur->next->next;
delete cur->next;
cur->next = tmp;
return true;
}
cur = cur->next;
}
return false;
}
void print() {
Node<T>* cur = head;
while (cur) {
std::cout << cur->val << " ";
cur = cur->next;
}
}
private:
Node<T>* head;
};鏈表是由多個節點組成，每個節點包含了一個元素和一個指向下一個節點的指針。鏈表的優點在於可以任意增加或刪除節點，但缺點在於不能像數組那樣快速的隨機訪問。
3. 棧
template<class T>
class Stack {
public:
Stack() {
}
~Stack() {
while (!data.empty()) {
data.pop();
}
}
bool empty() const {
return data.empty();
}
T top() const {
return data.top();
}
void push(T value) {
data.push(value);
}
void pop() {
data.pop();
}
private:
std::stack<T> data;
};棧是一種後進先出的數據結構，由於後加入的元素最先被訪問到，所以只允許在末尾進行插入和刪除操作。
二、非線性數據結構
非線性數據結構是指元素之間存在一對多、多對一或多對多的關係，常見的非線性數據結構包括二叉樹、堆和圖。
1. 二叉樹
template<class T>
struct TreeNode {
T val;
TreeNode<T>* left;
TreeNode<T>* right;
TreeNode(T val): val(val), left(nullptr), right(nullptr) {
}
};
template<class T>
class BinaryTree {
public:
BinaryTree(): root(nullptr) {
}
void insert(T val) {
insert(root, val);
}
bool find(T val) {
return find(root, val);
}
void preOrder() {
preOrder(root);
}
void inOrder() {
inOrder(root);
}
void postOrder() {
postOrder(root);
}
private:
void insert(TreeNode<T>*& node, T val) {
if (!node) {
node = new TreeNode<T>(val);
return;
}
if (val < node->val) {
insert(node->left, val);
} else if (val > node->val) {
insert(node->right, val);
}
}
bool find(TreeNode<T>* node, T val) {
if (!node) {
return false;
}
if (node->val == val) {
return true;
}
if (val < node->val) {
return find(node->left, val);
} else {
return find(node->right, val);
}
}
void preOrder(TreeNode<T>* node) {
if (!node) {
return;
}
std::cout << node->val << " ";
preOrder(node->left);
preOrder(node->right);
}
void inOrder(TreeNode<T>* node) {
if (!node) {
return;
}
inOrder(node->left);
std::cout << node->val << " ";
inOrder(node->right);
}
void postOrder(TreeNode<T>* node) {
if (!node) {
return;
}
postOrder(node->left);
postOrder(node->right);
std::cout << node->val << " ";
}
private:
TreeNode<T>* root;
};二叉樹是一種每個節點最多有兩個子節點的樹結構，其中一個節點是其左子節點，另一個是其右子節點。二叉樹的遍歷方法包括前序遍歷(pre-order)、中序遍歷(in-order)和後序遍歷(post-order)。
2. 堆
template <class T>
class Heap {
public:
explicit Heap(int capacity) : capacity_(capacity), size_(0) {
data_ = new T[capacity_];
}
~Heap() {
delete [] data_;
}
void insert(T element) {
if (size_ == capacity_) {
throw std::out_of_range("Full heap");
}
int i = size_;
while (i > 0) {
int parent = (i - 1) / 2;
if (data_[parent] <= element) {
break;
}
data_[i] = data_[parent];
i = parent;
}
data_[i] = element;
size_++;
}
T min() const {
if (size_ == 0) {
throw std::out_of_range("Heap is empty");
}
return data_[0];
}
void deleteMin() {
if (size_ == 0) {
throw std::out_of_range("Heap is empty");
}
size_--;
T last = data_[size_];
int i = 0;
int child = 1;
while (child <= size_) {
if (child < size_ && data_[child] > data_[child + 1]) {
child++;
}
if (last <= data_[child]) {
break;
}
data_[i] = data_[child];
i = child;
child = 2 * i + 1;
}
data_[i] = last;
}
private:
T* data_;
int capacity_;
int size_;
};堆是一個具有特殊性質的完全二叉樹，堆的根節點的元素是所有元素中最小的或最大的。
3. 圖
template<class T>
class Graph {
public:
void addVertex(T val) {
if (adjList_.find(val) == adjList_.end()) {
adjList_[val] = std::vector<T>();
}
}
void addEdge(T from, T to) {
if (adjList_.find(from) == adjList_.end() || adjList_.find(to) == adjList_.end()) {
return;
}
adjList_[from].push_back(to);
}
void bfs(T startVertex) const {
std::unordered_set<T> visited;
std::queue<T> q;
visited.insert(startVertex);
q.push(startVertex);
while (!q.empty()) {
T vertex = q.front();
std::cout << vertex << " ";
q.pop();
for (const auto& neighbor : adjList_.at(vertex)) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
q.push(neighbor);
}
}
}
}
void dfs(T startVertex) const {
std::unordered_set<T> visited;
dfs(startVertex, visited);
}
private:
std::unordered_map<T, std::vector<T>> adjList_;
void dfs(T vertex, std::unordered_set<T>& visited) const {
visited.insert(vertex);
std::cout << vertex << " ";
for (const auto& neighbor : adjList_.at(vertex)) {
if (visited.find(neighbor) == visited.end()) {
dfs(neighbor, visited);
}
}
}
};圖是由多個頂點（vertex）和邊（edge）連接起來而成的，邊代表兩個頂點之間的關係。圖有兩種可能性：有向圖（directed graph）和無向圖（undirected graph），其中有向圖的邊是有順序的。
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hk/n/233967.html
微信掃一掃 
支付寶掃一掃 