好的，我们来系统梳理一下 计算机数据结构（Data Structures），并结合 Python 代码示例，让你边学理论边实践。内容会覆盖基础概念、线性结构、非线性结构、查找与排序算法。

一、数据结构的定义

数据结构是计算机中 组织、存储和管理数据的方式，它不仅影响存储效率，还直接影响算法的时间复杂度和空间复杂度。

  • 数据（Data）：可以处理的原始元素
  • 数据结构（Data Structure）：数据之间的逻辑关系和组织方式
  • 操作（Operations）：对数据结构进行插入、删除、查找、修改等操作

二、数据结构分类

1. 线性结构（Linear Structure）

数据元素呈线性排列，一般有前驱和后继关系。

数据结构特点常用操作
数组（Array）定长，索引访问快访问、遍历、修改
链表（Linked List）动态分配，插入删除快插入、删除、查找
栈（Stack）后进先出（LIFO）push, pop, peek
队列（Queue）先进先出（FIFO）enqueue, dequeue
双端队列（Deque）两端都可操作push, pop, appendleft

2. 非线性结构（Non-linear Structure）

数据元素呈层次或网状结构，没有固定前后顺序。

数据结构特点应用
树（Tree）层次关系文件系统、表达式树
二叉树（Binary Tree）每个节点最多两个子节点二叉搜索树、堆
图（Graph）节点和边路径规划、社交网络

3. 查找表结构

  • 散列表（Hash Table）：通过哈希函数快速定位数据
  • 字典 / 映射（Dictionary / Map）：键值对存储，快速查找

三、常用操作与代码示例（Python）

1. 数组 / 列表

# Python 列表即动态数组
arr = [1, 2, 3, 4, 5]

# 访问
print(arr[2])  # 3

# 插入
arr.append(6)
arr.insert(2, 10)

# 删除
arr.pop()        # 删除最后一个
arr.remove(10)   # 删除值为10的元素

# 遍历
for val in arr:
    print(val)

2. 链表（单链表）

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

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

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def traverse(self):
        curr = self.head
        while curr:
            print(curr.val, end=" -> ")
            curr = curr.next
        print("None")

# 测试
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.traverse()  # 1 -> 2 -> 3 -> None

3. 栈

stack = []

# 压栈
stack.append(1)
stack.append(2)

# 出栈
print(stack.pop())  # 2

# 查看栈顶
print(stack[-1])    # 1

4. 队列

from collections import deque

queue = deque()

# 入队
queue.append(1)
queue.append(2)

# 出队
print(queue.popleft())  # 1

5. 二叉搜索树

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

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=" ")
        inorder(root.right)

# 测试
root = None
for v in [5, 3, 7, 2, 4, 6]:
    root = insert(root, v)
inorder(root)  # 2 3 4 5 6 7

6. 哈希表（字典）

# Python 字典实现哈希表
hash_table = {}
hash_table["apple"] = 3
hash_table["banana"] = 5

# 查找
print(hash_table.get("apple"))  # 3

# 遍历
for key, value in hash_table.items():
    print(key, value)

四、常用算法

  1. 排序
    • 冒泡排序、选择排序、插入排序
    • 快速排序、归并排序（效率高）
# 快速排序示例
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    left = [x for x in arr[1:] if x < pivot]
    right = [x for x in arr[1:] if x >= pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

arr = [5,2,9,1,5,6]
print(quick_sort(arr))  # [1,2,5,5,6,9]
  1. 查找
    • 线性查找、二分查找（适用于有序数组）
# 二分查找
def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

arr = [1,2,3,4,5]
print(binary_search(arr, 3))  # 2

五、总结

核心知识点：

  1. 数据结构是组织和管理数据的方式，直接影响算法效率
  2. 线性结构：数组、链表、栈、队列
  3. 非线性结构：树、图
  4. 查找表：哈希表、字典
  5. 基本操作：插入、删除、查找、遍历
  6. 常用算法：排序和查找

明白，我帮你做一个 Python 数据结构实验套件，集成 数组、链表、栈、队列、二叉树、哈希表，并提供交互式操作界面，可以直接运行。

下面是完整示例代码：

# data_structures_experiment.py

from collections import deque

# ---------- 数组操作 ----------
def array_demo():
    arr = []
    while True:
        print("\n数组操作: 1-插入 2-删除 3-遍历 4-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            val = int(input("输入值: "))
            arr.append(val)
        elif choice == "2":
            val = int(input("删除值: "))
            if val in arr:
                arr.remove(val)
            else:
                print("值不存在")
        elif choice == "3":
            print("数组:", arr)
        else:
            break

# ---------- 链表操作 ----------
class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

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

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def remove(self, val):
        curr = self.head
        prev = None
        while curr:
            if curr.val == val:
                if prev:
                    prev.next = curr.next
                else:
                    self.head = curr.next
                return True
            prev = curr
            curr = curr.next
        return False

    def traverse(self):
        curr = self.head
        res = []
        while curr:
            res.append(curr.val)
            curr = curr.next
        print("链表:", res)

def linkedlist_demo():
    ll = LinkedList()
    while True:
        print("\n链表操作: 1-插入 2-删除 3-遍历 4-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            val = int(input("输入值: "))
            ll.append(val)
        elif choice == "2":
            val = int(input("删除值: "))
            if not ll.remove(val):
                print("值不存在")
        elif choice == "3":
            ll.traverse()
        else:
            break

# ---------- 栈操作 ----------
def stack_demo():
    stack = []
    while True:
        print("\n栈操作: 1-压栈 2-出栈 3-查看栈顶 4-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            val = int(input("压入值: "))
            stack.append(val)
        elif choice == "2":
            if stack:
                print("出栈:", stack.pop())
            else:
                print("栈空")
        elif choice == "3":
            if stack:
                print("栈顶:", stack[-1])
            else:
                print("栈空")
        else:
            break

# ---------- 队列操作 ----------
def queue_demo():
    queue = deque()
    while True:
        print("\n队列操作: 1-入队 2-出队 3-查看队列 4-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            val = int(input("入队值: "))
            queue.append(val)
        elif choice == "2":
            if queue:
                print("出队:", queue.popleft())
            else:
                print("队列空")
        elif choice == "3":
            print("队列:", list(queue))
        else:
            break

# ---------- 二叉搜索树操作 ----------
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    return root

def inorder_bst(root):
    if root:
        inorder_bst(root.left)
        print(root.val, end=" ")
        inorder_bst(root.right)

def bst_demo():
    root = None
    while True:
        print("\nBST操作: 1-插入 2-中序遍历 3-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            val = int(input("输入值: "))
            root = insert_bst(root, val)
        elif choice == "2":
            print("中序遍历:", end=" ")
            inorder_bst(root)
            print()
        else:
            break

# ---------- 哈希表操作 ----------
def hashtable_demo():
    ht = {}
    while True:
        print("\n哈希表操作: 1-插入/更新 2-查找 3-删除 4-查看所有 5-返回上级")
        choice = input("选择操作: ")
        if choice == "1":
            key = input("键: ")
            val = input("值: ")
            ht[key] = val
        elif choice == "2":
            key = input("查找键: ")
            print("值:", ht.get(key, "不存在"))
        elif choice == "3":
            key = input("删除键: ")
            if key in ht:
                del ht[key]
            else:
                print("键不存在")
        elif choice == "4":
            print("哈希表内容:", ht)
        else:
            break

# ---------- 主菜单 ----------
def main():
    while True:
        print("\n=== 数据结构实验套件 ===")
        print("1-数组 2-链表 3-栈 4-队列 5-二叉搜索树 6-哈希表 0-退出")
        choice = input("选择数据结构: ")
        if choice == "1":
            array_demo()
        elif choice == "2":
            linkedlist_demo()
        elif choice == "3":
            stack_demo()
        elif choice == "4":
            queue_demo()
        elif choice == "5":
            bst_demo()
        elif choice == "6":
            hashtable_demo()
        elif choice == "0":
            print("退出实验套件")
            break
        else:
            print("无效选项")

if __name__ == "__main__":
    main()

✅ 功能特点

  1. 交互式菜单：可选择数据结构操作
  2. 支持基础操作：插入、删除、查找、遍历
  3. 覆盖数据结构：数组、链表、栈、队列、二叉搜索树、哈希表
  4. 可直接运行：python data_structures_experiment.py