第二周习题

**第二周习题**

###1. 数组和链表####1.1 数组的基本操作数组是最常见的数据结构之一。下面是一些关于数组的基本操作的函数：

def print_array(arr):
 """
 打印数组中的元素。
 Args:
 arr (list): 需要打印的数组。
 """
 for i in range(len(arr)):
 print(arr[i])

def swap_array_elements(arr, i, j):
 """
 交换数组中两个元素的值。
 Args:
 arr (list): 需要交换元素的数组。
 i (int): 第一个元素的索引。
 j (int): 第二个元素的索引。
 """
 temp = arr[i]
 arr[i] = arr[j]
 arr[j] = tempdef find_max_array_element(arr):
 """
 找到数组中最大元素的值和索引。
 Args:
 arr (list): 需要查找最大元素的数组。
 Returns:
 tuple: 最大元素的值和索引。
 """
 max_val = arr[0]
 max_idx =0 for i in range(1, len(arr)):
 if arr[i] > max_val:
 max_val = arr[i]
 max_idx = i return max_val, max_idx# 测试函数arr = [3,5,2,7,9]
print_array(arr)
swap_array_elements(arr,1,3)
print_array(arr)
max_val, max_idx = find_max_array_element(arr)
print(f"最大元素值：{max_val}, 索引：{max_idx}")

class Node:
 """
 链表中的一个节点。
 Attributes:
 data (any): 节点存储的数据。
 next (Node): 下一个节点的引用。
 """
 def __init__(self, data=None):
 self.data = data self.next = Noneclass LinkedList:
 """
 链表类。
 Attributes:
 head (Node): 链表头部的引用。
 """
 def __init__(self):
 self.head = Nonedef print_linked_list(linked_list):
 """
 打印链表中的元素。
 Args:
 linked_list (LinkedList): 需要打印的链表。
 """
 current_node = linked_list.head while current_node is not None:
 print(current_node.data)
 current_node = current_node.nextdef append_to_linked_list(linked_list, data):
 """
 向链表尾部追加一个元素。
 Args:
 linked_list (LinkedList): 需要追加元素的链表。
 data (any): 要追加的元素。
 """
 new_node = Node(data)
 if linked_list.head is None:
 linked_list.head = new_node else:
 current_node = linked_list.head while current_node.next is not None:
 current_node = current_node.next current_node.next = new_nodedef delete_from_linked_list(linked_list, data):
 """
 删除链表中某个元素。
 Args:
 linked_list (LinkedList): 需要删除元素的链表。
 data (any): 要删除的元素。
 """
 if linked_list.head is None:
 return elif linked_list.head.data == data:
 linked_list.head = linked_list.head.next return current_node = linked_list.head while current_node.next is not None:
 if current_node.next.data == data:
 current_node.next = current_node.next.next return current_node = current_node.next# 测试函数linked_list = LinkedList()
append_to_linked_list(linked_list,3)
append_to_linked_list(linked_list,5)
append_to_linked_list(linked_list,2)
print_linked_list(linked_list)
delete_from_linked_list(linked_list,5)
print_linked_list(linked_list)

class Stack:
 """
 栈类。
 Attributes:
 items (list): 栈中的元素列表。
 """
 def __init__(self):
 self.items = []

def push_stack(stack, item):
 """
 向栈顶部添加一个元素。
 Args:
 stack (Stack): 需要添加元素的栈。
 item (any): 要添加的元素。
 """
 stack.items.append(item)

def pop_stack(stack):
 """
 从栈顶部移除一个元素。
 Args:
 stack (Stack): 需要移除元素的栈。
 Returns:
 any: 移除的元素。
 """
 if not is_empty_stack(stack):
 return stack.items.pop()
 else:
 raise IndexError("Stack is empty")

def peek_stack(stack):
 """
 查看栈顶部的元素。
 Args:
 stack (Stack): 需要查看元素的栈。
 Returns:
 any: 栈顶部的元素。
 """
 if not is_empty_stack(stack):
 return stack.items[-1]
 else:
 raise IndexError("Stack is empty")

def is_empty_stack(stack):
 """
 检查栈是否为空。
 Args:
 stack (Stack): 需要检查的栈。
 Returns:
 bool: 栈是否为空。
 """
 return len(stack.items) ==0# 测试函数stack = Stack()
push_stack(stack,3)
push_stack(stack,5)
print(pop_stack(stack)) # 输出：5print(peek_stack(stack)) # 输出：3

class Queue:
 """
 队列类。
 Attributes:
 items (list): 队列中的元素列表。
 """
 def __init__(self):
 self.items = []

def enqueue_queue(queue, item):
 """
 向队列尾部添加一个元素。
 Args:
 queue (Queue): 需要添加元素的队列。
 item (any): 要添加的元素。
 """
 queue.items.append(item)

def dequeue_queue(queue):
 """
 从队列头部移除一个元素。
 Args:
 queue (Queue): 需要移除元素的队列。
 Returns:
 any: 移除的元素。
 """
 if not is_empty_queue(queue):
 return queue.items.pop(0)
 else:
 raise IndexError("Queue is empty")

def peek_queue(queue):
 """
 查看队列头部的元素。
 Args:
 queue (Queue): 需要查看元素的队列。
 Returns:
 any: 队列头部的元素。
 """
 if not is_empty_queue(queue):
 return queue.items[0]
 else:
 raise IndexError("Queue is empty")

def is_empty_queue(queue):
 """
 检查队列是否为空。
 Args:
 queue (Queue): 需要检查的队列。
 Returns:
 bool: 队列是否为空。
 """
 return len(queue.items) ==0# 测试函数queue = Queue()
enqueue_queue(queue,3)
enqueue_queue(queue,5)
print(dequeue_queue(queue)) # 输出：3print(peek_queue(queue)) # 输出：5

def linear_search(arr, target):
 """
 使用线性查找找到数组中某个元素。
 Args:
 arr (list): 需要查找的数组。
 target (any): 要查找的元素。
 Returns:
 int: 元素在数组中的索引，-1表示未找到。
 """
 for i in range(len(arr)):
 if arr[i] == target:
 return i return -1# 测试函数arr = [3,5,2,7,9]
print(linear_search(arr,5)) # 输出：1

def binary_search(arr, target):
 """
 使用二分查找找到数组中某个元素。
 Args:
 arr (list): 需要查找的数组。
 target (any): 要查找的元素。
 Returns:
 int: 元素在数组中的索引，-1表示