引言

数据结构是计算机科学中的基础概念，对于理解计算机算法和程序设计至关重要。为了帮助读者高效预习数据结构，本文将提供一系列核心笔记，旨在帮助读者快速掌握数据结构的基本概念、常用数据结构和算法。

一、数据结构概述

1.1 数据结构定义

数据结构是组织和管理数据的方式，它决定了数据的存储、检索和更新方法。数据结构可以分为两大类：线性结构和非线性结构。

1.2 数据结构特点

  • 存储方式：数据结构可以存储在数组、链表、树等多种方式。
  • 操作方式：数据结构支持插入、删除、查找等基本操作。
  • 时间复杂度：数据结构操作的时间复杂度是衡量其性能的重要指标。

二、线性结构

2.1 数组

数组是一种基本的数据结构，用于存储固定大小的元素序列。以下是数组的操作示例：

# Python 代码示例：数组操作
array = [10, 20, 30, 40, 50]

# 插入元素
array.append(60)

# 删除元素
del array[0]

# 查找元素
index = array.index(30)

# 打印数组
print(array)

2.2 链表

链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。以下是链表的操作示例：

# Python 代码示例：链表操作
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# 创建链表
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)

# 插入元素
new_node = Node(40)
new_node.next = head.next
head.next = new_node

# 删除元素
head.next.next = head.next.next.next

# 打印链表
current = head
while current:
    print(current.data)
    current = current.next

2.3 栈和队列

栈和队列是特殊的线性结构，遵循后进先出（LIFO）和先进先出（FIFO）的原则。

# Python 代码示例：栈和队列操作
from collections import deque

# 创建栈
stack = [10, 20, 30]
stack.append(40)
stack.pop()

# 创建队列
queue = deque([10, 20, 30])
queue.append(40)
queue.popleft()

三、非线性结构

3.1 树

树是一种非线性结构，由节点组成，每个节点有零个或多个子节点。以下是树的基本操作：

# Python 代码示例：树操作
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.children = []

# 创建树
root = TreeNode(1)
child1 = TreeNode(2)
child2 = TreeNode(3)
root.children.append(child1)
root.children.append(child2)

# 添加子节点
root.children.append(TreeNode(4))

# 遍历树
def traverse_tree(node):
    print(node.data)
    for child in node.children:
        traverse_tree(child)

traverse_tree(root)

3.2 图

图是一种由节点和边组成的数据结构，用于表示实体之间的关系。以下是图的基本操作：

# Python 代码示例：图操作
class Graph:
    def __init__(self):
        self.nodes = {}
    
    def add_edge(self, node1, node2):
        if node1 not in self.nodes:
            self.nodes[node1] = []
        if node2 not in self.nodes:
            self.nodes[node2] = []
        self.nodes[node1].append(node2)
        self.nodes[node2].append(node1)
    
    def display(self):
        for node, edges in self.nodes.items():
            print(f"{node}: {edges}")

# 创建图
graph = Graph()
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.display()

四、总结

通过以上核心笔记，读者可以初步了解数据结构的基本概念、常用数据结构和算法。在预习过程中，建议结合实际案例和代码示例进行学习和实践，以提高对数据结构的理解和应用能力。