每种数据结构的实现通常可以通过多种语言来完成,以下是一些常用数据结构的基本实现示例,使用C++和Python分别演示:
1. 数组(Array)
C++ 实现
#include <iostream>
using namespace std;int main() {int arr[5] = {1, 2, 3, 4, 5};for(int i = 0; i < 5; i++) {cout << arr[i] << " ";}return 0;
}
Python 实现
arr = [1, 2, 3, 4, 5]
for elem in arr:print(elem, end=' ')
2. 链表(Linked List)
C++ 单链表实现
#include <iostream>
using namespace std;struct Node {int data;Node* next;
};void insert(Node** head, int data) {Node* newNode = new Node();newNode->data = data;newNode->next = *head;*head = newNode;
}void printList(Node* node) {while (node != nullptr) {cout << node->data << " ";node = node->next;}
}int main() {Node* head = nullptr;insert(&head, 1);insert(&head, 2);insert(&head, 3);printList(head);return 0;
}
Python 单链表实现
class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef insert(self, data):new_node = Node(data)new_node.next = self.headself.head = new_nodedef print_list(self):temp = self.headwhile temp:print(temp.data, end=' ')temp = temp.nextll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.print_list()
3. 栈(Stack)
C++ 实现
#include <iostream>
#include <stack>
using namespace std;int main() {stack<int> s;s.push(10);s.push(20);s.push(30);while (!s.empty()) {cout << s.top() << " ";s.pop();}return 0;
}
Python 实现
stack = []
stack.append(10)
stack.append(20)
stack.append(30)while stack:print(stack.pop(), end=' ')
4. 队列(Queue)
C++ 实现
#include <iostream>
#include <queue>
using namespace std;int main() {queue<int> q;q.push(10);q.push(20);q.push(30);while (!q.empty()) {cout << q.front() << " ";q.pop();}return 0;
}
Python 实现
from collections import dequequeue = deque([10, 20, 30])while queue:print(queue.popleft(), end=' ')
5. 哈希表(Hash Table)
C++ 实现
#include <iostream>
#include <unordered_map>
using namespace std;int main() {unordered_map<string, int> hashTable;hashTable["apple"] = 1;hashTable["banana"] = 2;for (auto& pair : hashTable) {cout << pair.first << ": " << pair.second << endl;}return 0;
}
Python 实现
hash_table = {"apple": 1, "banana": 2}
for key, value in hash_table.items():print(f"{key}: {value}")
6. 二叉树(Binary Tree)
C++ 实现
#include <iostream>
using namespace std;struct Node {int data;Node* left;Node* right;Node(int val) : data(val), left(nullptr), right(nullptr) {}
};void inOrder(Node* node) {if (node == nullptr) return;inOrder(node->left);cout << node->data << " ";inOrder(node->right);
}int main() {Node* root = new Node(1);root->left = new Node(2);root->right = new Node(3);root->left->left = new Node(4);root->left->right = new Node(5);inOrder(root);return 0;
}
Python 实现
class Node:def __init__(self, data):self.data = dataself.left = Noneself.right = Nonedef in_order(node):if not node:returnin_order(node.left)print(node.data, end=' ')in_order(node.right)root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
in_order(root)
7. 图(Graph)
C++ 邻接表实现
#include <iostream>
#include <vector>
using namespace std;class Graph {int V;vector<int>* adj;
public:Graph(int V);void addEdge(int v, int w);void printGraph();
};Graph::Graph(int V) {this->V = V;adj = new vector<int>[V];
}void Graph::addEdge(int v, int w) {adj[v].push_back(w);
}void Graph::printGraph() {for (int v = 0; v < V; ++v) {cout << v << ": ";for (int x : adj[v])cout << x << " ";cout << endl;}
}int main() {Graph g(4);g.addEdge(0, 1);g.addEdge(0, 2);g.addEdge(1, 2);g.addEdge(2, 0);g.addEdge(2, 3);g.printGraph();return 0;
}
Python 邻接表实现
class Graph:def __init__(self, vertices):self.V = verticesself.graph = [[] for _ in range(vertices)]def add_edge(self, v, w):self.graph[v].append(w)def print_graph(self):for i in range(self.V):print(f"{i}: {self.graph[i]}")g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.print_graph()
8. 堆(Heap)
C++ 实现(最大堆)
#include <iostream>
#include <queue>
using namespace std;int main() {priority_queue<int> maxHeap;maxHeap.push(10);maxHeap.push(5);maxHeap.push(20);while (!maxHeap.empty()) {cout << maxHeap.top() << " ";maxHeap.pop();}return 0;
}
Python 实现(最小堆)
import heapqmin_heap = []
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 20)while min_heap:print(heapq.heappop(min_heap), end=' ')
总结
这些是一些常见的数据结构的基本实现,使用不同的编程语言可以用不同的语法和方法来实现它们的操作。