正文

轻松掌握数据结构：实用补充习题及详解

/0 浏览量
0521

1. 习题一：链表操作

题目描述： 实现一个单链表，支持插入、删除和查找操作。

代码示例：

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, value):
        new_node = ListNode(value)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:
            current = current.next
        current.next = new_node

    def delete(self, value):
        if not self.head:
            return
        if self.head.value == value:
            self.head = self.head.next
            return
        current = self.head
        while current.next and current.next.value != value:
            current = current.next
        if current.next:
            current.next = current.next.next

    def search(self, value):
        current = self.head
        while current:
            if current.value == value:
                return True
            current = current.next
        return False

解题思路： 首先定义一个ListNode类，用于创建链表节点。然后定义一个LinkedList类，实现链表的插入、删除和查找功能。

2. 习题二：栈与队列的实现

题目描述： 使用数组实现一个栈和队列。

代码示例：

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if not self.items:
            return None
        return self.items.pop()

    def peek(self):
        if not self.items:
            return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        if not self.items:
            return None
        return self.items.pop()

    def is_empty(self):
        return len(self.items) == 0

解题思路： 使用Python列表的append和pop方法来实现栈的后进先出（LIFO）特性，使用insert和pop方法来实现队列的先进先出（FIFO）特性。

3. 习题三：二叉树的遍历

题目描述： 实现二叉树的先序、中序和后序遍历。

代码示例：

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def preorder_traversal(root):
    if not root:
        return []
    return [root.value] + preorder_traversal(root.left) + preorder_traversal(root.right)

def inorder_traversal(root):
    if not root:
        return []
    return inorder_traversal(root.left) + [root.value] + inorder_traversal(root.right)

def postorder_traversal(root):
    if not root:
        return []
    return postorder_traversal(root.left) + postorder_traversal(root.right) + [root.value]

解题思路： 定义一个TreeNode类来创建二叉树节点。然后分别实现先序、中序和后序遍历函数，通过递归的方式遍历树的每个节点。

4. 习题四：哈希表实现

题目描述： 使用哈希表实现一个简单的字符串匹配算法。

代码示例：

class HashTable:
    def __init__(self, size=100):
        self.size = size
        self.table = [None] * self.size

    def hash(self, key):
        return hash(key) % self.size

    def insert(self, key, value):
        index = self.hash(key)
        if self.table[index] is None:
            self.table[index] = [(key, value)]
        else:
            self.table[index].append((key, value))

    def search(self, key):
        index = self.hash(key)
        if self.table[index] is not None:
            for k, v in self.table[index]:
                if k == key:
                    return v
        return None

解题思路： 定义一个HashTable类，其中包含一个哈希表和哈希函数。通过哈希函数计算键的索引，将键值对插入到哈希表中。在查找时，根据键的索引在哈希表中查找对应的值。

以上是几个常用的数据结构习题及其详解，通过练习这些习题，可以帮助你更好地理解和掌握数据结构。

-- 展开阅读全文 --