作者主页: 知孤云出岫
目录
- 数据结构实操代码题
- 题目一:实现栈(Stack)
- 题目二:实现队列(Queue)
- 题目三:实现二叉搜索树(BST)
- 题目四:实现链表(Linked List)
- 题目五:实现图的深度优先搜索(DFS)和广度优先搜索(BFS)
![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/94456c97aa434efebf4c97e405727279.png#pic_center)
数据结构实操代码题
题目一:实现栈(Stack)
请实现一个栈的数据结构,支持以下操作:
push(x)
:将元素x压入栈中。pop()
:移除并返回栈顶元素。top()
:返回栈顶元素。is_empty()
:判断栈是否为空。
python">class Stack:def __init__(self):self.items = []def push(self, x):self.items.append(x)def pop(self):if not self.is_empty():return self.items.pop()else:return Nonedef top(self):if not self.is_empty():return self.items[-1]else:return Nonedef is_empty(self):return len(self.items) == 0# 测试代码
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.top()) # 输出: 2
print(stack.pop()) # 输出: 2
print(stack.is_empty()) # 输出: False
print(stack.pop()) # 输出: 1
print(stack.is_empty()) # 输出: True
题目二:实现队列(Queue)
请实现一个队列的数据结构,支持以下操作:
enqueue(x)
:将元素x加入队列。dequeue()
:移除并返回队列头部元素。front()
:返回队列头部元素。is_empty()
:判断队列是否为空。
python">class Queue:def __init__(self):self.items = []def enqueue(self, x):self.items.append(x)def dequeue(self):if not self.is_empty():return self.items.pop(0)else:return Nonedef front(self):if not self.is_empty():return self.items[0]else:return Nonedef is_empty(self):return len(self.items) == 0# 测试代码
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.front()) # 输出: 1
print(queue.dequeue()) # 输出: 1
print(queue.is_empty()) # 输出: False
print(queue.dequeue()) # 输出: 2
print(queue.is_empty()) # 输出: True
题目三:实现二叉搜索树(BST)
请实现一个二叉搜索树的数据结构,支持以下操作:
insert(x)
:插入元素x。search(x)
:查找元素x,返回True或False。inorder()
:中序遍历二叉树。
python">class TreeNode:def __init__(self, key):self.left = Noneself.right = Noneself.val = keyclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, key):if self.root is None:self.root = TreeNode(key)else:self._insert(self.root, key)def _insert(self, root, key):if key < root.val:if root.left is None:root.left = TreeNode(key)else:self._insert(root.left, key)else:if root.right is None:root.right = TreeNode(key)else:self._insert(root.right, key)def search(self, key):return self._search(self.root, key)def _search(self, root, key):if root is None or root.val == key:return root is not Noneif key < root.val:return self._search(root.left, key)else:return self._search(root.right, key)def inorder(self):return self._inorder(self.root, [])def _inorder(self, root, result):if root:self._inorder(root.left, result)result.append(root.val)self._inorder(root.right, result)return result# 测试代码
bst = BinarySearchTree()
bst.insert(3)
bst.insert(1)
bst.insert(2)
bst.insert(5)
print(bst.search(3)) # 输出: True
print(bst.search(4)) # 输出: False
print(bst.inorder()) # 输出: [1, 2, 3, 5]
题目四:实现链表(Linked List)
请实现一个单向链表的数据结构,支持以下操作:
append(x)
:在链表末尾添加元素x。insert(index, x)
:在指定位置插入元素x。delete(index)
:删除指定位置的元素。get(index)
:获取指定位置的元素。
python">class ListNode:def __init__(self, x):self.val = xself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef append(self, x):if not self.head:self.head = ListNode(x)else:current = self.headwhile current.next:current = current.nextcurrent.next = ListNode(x)def insert(self, index, x):if index == 0:new_node = ListNode(x)new_node.next = self.headself.head = new_nodeelse:current = self.headfor _ in range(index - 1):if current is None:returncurrent = current.nextif current is None:returnnew_node = ListNode(x)new_node.next = current.nextcurrent.next = new_nodedef delete(self, index):if self.head is None:returnif index == 0:self.head = self.head.nextelse:current = self.headfor _ in range(index - 1):if current is None:returncurrent = current.nextif current is None or current.next is None:returncurrent.next = current.next.nextdef get(self, index):current = self.headfor _ in range(index):if current is None:return Nonecurrent = current.nextreturn current.val if current else None# 测试代码
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
print(ll.get(1)) # 输出: 2
ll.insert(1, 4)
print(ll.get(1)) # 输出: 4
ll.delete(2)
print(ll.get(2)) # 输出: 3
题目五:实现图的深度优先搜索(DFS)和广度优先搜索(BFS)
请实现一个无向图的数据结构,支持以下操作:
add_edge(u, v)
:添加边u-v。dfs(start)
:从start节点开始进行深度优先搜索。bfs(start)
:从start节点开始进行广度优先搜索。
python">from collections import defaultdict, dequeclass Graph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v):self.graph[u].append(v)self.graph[v].append(u)def dfs(self, start):visited = set()self._dfs(start, visited)return visiteddef _dfs(self, node, visited):if node not in visited:visited.add(node)for neighbor in self.graph[node]:self._dfs(neighbor, visited)def bfs(self, start):visited = set()queue = deque([start])visited.add(start)while queue:node = queue.popleft()for neighbor in self.graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)return visited# 测试代码
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)
g.add_edge(4, 5)
print(g.dfs(1)) # 输出: {1, 2, 3, 4, 5}
print(g.bfs(1)) # 输出: {1, 2, 3, 4, 5}
这些题目涵盖了栈、队列、二叉搜索树、链表和图的基本操作,通过编写这些代码,你可以很好地练习和巩固数据结构的基本概念和应用。