1. 线性表
1.1 习题解答
1.1.1 单链表的插入操作
题目：编写一个函数，实现单链表的插入操作。
解答：
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def insert_node(head, value, position):
new_node = ListNode(value)
if position == 0:
new_node.next = head
return new_node
current = head
for _ in range(position - 1):
if not current:
raise IndexError("Position out of range")
current = current.next
new_node.next = current.next
current.next = new_node
return head
# 测试
head = ListNode(1, ListNode(2, ListNode(3)))
head = insert_node(head, 4, 2)
while head:
print(head.value, end=' ')
head = head.next
1.1.2 双向链表的删除操作
题目：编写一个函数，实现双向链表的删除操作。
解答：
class DoublyListNode:
def __init__(self, value=0, prev=None, next=None):
self.value = value
self.prev = prev
self.next = next
def delete_node(head, position):
if position == 0:
return head.next if head.next else None
current = head
for _ in range(position):
if not current:
raise IndexError("Position out of range")
current = current.next
current.prev.next = current.next
if current.next:
current.next.prev = current.prev
return head
# 测试
head = DoublyListNode(1, None, DoublyListNode(2, DoublyListNode(3)))
head = delete_node(head, 1)
while head:
print(head.value, end=' ')
head = head.next
1.2 实战案例
案例：实现一个循环链表，并实现以下功能：
- 插入元素
- 删除元素
- 查找元素
class CircularLinkedList:
def __init__(self):
self.head = None
def insert(self, value):
new_node = ListNode(value)
if not self.head:
self.head = new_node
new_node.next = new_node
else:
tail = self.head
while tail.next != self.head:
tail = tail.next
tail.next = new_node
new_node.next = self.head
def delete(self, value):
if not self.head:
return
current = self.head
while True:
if current.value == value:
if current.next == self.head:
self.head = None
else:
current.prev.next = current.next
current.next.prev = current.prev
return
current = current.next
if current == self.head:
break
def search(self, value):
current = self.head
while True:
if current.value == value:
return True
current = current.next
if current == self.head:
break
return False
# 测试
cll = CircularLinkedList()
cll.insert(1)
cll.insert(2)
cll.insert(3)
print(cll.search(2)) # 输出：True
cll.delete(2)
print(cll.search(2)) # 输出：False
2. 栈和队列
2.1 习题解答
2.1.1 栈的压栈和出栈操作
题目：编写一个函数，实现栈的压栈和出栈操作。
解答：
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
if not self.items:
raise IndexError("Stack is empty")
return self.items.pop()
# 测试
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 输出：2
print(stack.pop()) # 输出：1
2.1.2 队列的入队和出队操作
题目：编写一个函数，实现队列的入队和出队操作。
解答：
class Queue:
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.append(item)
def dequeue(self):
if not self.items:
raise IndexError("Queue is empty")
return self.items.pop(0)
# 测试
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue()) # 输出：1
print(queue.dequeue()) # 输出：2
2.2 实战案例
案例：实现一个循环队列，并实现以下功能：
- 入队
- 出队
- 判断队列是否为空
class CircularQueue:
def __init__(self, size):
self.items = [None] * size
self.head = 0
self.tail = 0
self.size = size
def enqueue(self, value):
if (self.tail + 1) % self.size == self.head:
raise IndexError("Queue is full")
self.items[self.tail] = value
self.tail = (self.tail + 1) % self.size
def dequeue(self):
if self.head == self.tail:
raise IndexError("Queue is empty")
value = self.items[self.head]
self.items[self.head] = None
self.head = (self.head + 1) % self.size
return value
def is_empty(self):
return self.head == self.tail
# 测试
cq = CircularQueue(3)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue()) # 输出：1
print(cq.is_empty()) # 输出：False
cq.dequeue()
cq.dequeue()
print(cq.is_empty()) # 输出：True