软考中级复习篇章：数据结构部分的复习

软考中级快速通过篇章：数据结构部分的复习

一、引言

在软考中级的备考过程中，数据结构是极为重要的一个部分。它不仅是计算机科学的基础，也是软考中考查的重点知识领域。扎实掌握数据结构相关内容，对于顺利通过软考中级考试起着关键作用。本文将对数据结构部分的核心知识点进行全面总结，并配以简单的习题练习，帮助大家快速高效地复习这一板块，为软考中级考试做好充分准备。

二、数据结构基础概念

（一）数据结构的定义

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它主要研究数据的逻辑结构、存储结构以及在这些结构上定义的运算。

• 逻辑结构：描述数据元素之间的逻辑关系，如线性结构（线性表、栈、队列等）、非线性结构（树、图等）。

• 存储结构：数据在计算机中的存储方式，常见的有顺序存储、链式存储、索引存储和散列存储。

（二）数据类型

• 原子类型：其值不可再分的数据类型，如整型、实型、字符型等。

• 结构类型：由若干个数据项组成，其值可以再分解为若干个数据项，例如数组、结构体等。

三、线性表

（一）线性表的定义与特点

线性表是具有相同数据类型的 n 个数据元素的有限序列（n≥0），记为 (a1, a2, …, an)。它具有以下特点：

• 有且仅有一个第一个元素和最后一个元素。

• 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

（二）顺序表

• 定义：用一组地址连续的存储单元依次存储线性表中的数据元素，这种存储结构的线性表称为顺序表。

• 优点：可以随机存取表中任一元素，存储密度高。

• 缺点：插入和删除操作需要移动大量元素，效率较低。

例如，在一个顺序表中插入元素的代码实现（以 C 语言为例）：

#include <stdio.h> 
#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; 
} SqList; // 在顺序表L的第i个位置插入元素e 
int ListInsert(SqList *L, int i, int e) { int j; if (i < 1 || i > L->length + 1) return 0; if (L->length >= MAXSIZE) return 0; for (j = L->length; j >= i; j--) L->data[j] = L->data[j - 1]; L->data[i - 1] = e; L->length++; return 1; 
} 

（三）链表

• 单链表：每个节点除了存放数据元素外，还需要存放一个指向其后继节点的指针。

• 双链表：在单链表的基础上，每个节点增加一个指向其前驱节点的指针，使得链表可以双向遍历。

• 循环链表：链表的最后一个节点的指针指向头节点，形成一个环。

下面是单链表插入节点的代码示例（以 C 语言为例）：

#include <stdio.h> 
#include <stdlib.h> typedef struct LNode { int data; struct LNode *next; 
} LNode, *LinkList; // 在单链表L中第i个位置插入元素e 
int ListInsert(LinkList *L, int i, int e) { int j = 1; LinkList p = *L, s; if (i == 1) { s = (LinkList)malloc(sizeof(LNode)); s->data = e; s->next = p; *L = s; return 1; } while (p && j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) return 0; s = (LinkList)malloc(sizeof(LNode)); s->data = e; s->next = p->next; p->next = s; return 1; 
} 

四、栈和队列

（一）栈

• 定义：是一种只允许在一端进行插入和删除操作的线性表，按照后进先出（LIFO, Last In First Out）的原则组织数据。

• 栈的操作：初始化、入栈、出栈、取栈顶元素、判断栈是否为空等。

• 应用场景：表达式求值、括号匹配、函数调用等。

以下是一个简单的栈操作的代码实现（以 C 语言为例）：

#include <stdio.h> 
#include <stdlib.h> typedef struct Stack { int *data; int top; int size; 
} Stack; // 初始化栈 
Stack* initStack(int size) { Stack *s = (Stack*)malloc(sizeof(Stack)); s->data = (int*)malloc(size * sizeof(int)); s->top = -1; s->size = size; return s; 
} // 判断栈是否为空 
int isEmpty(Stack *s) { return s->top == -1; 
} // 入栈 
int push(Stack *s, int e) { if (s->top == s->size - 1) return 0; s->data[++(s->top)] = e; return 1; 
} // 出栈 
int pop(Stack *s, int *e) { if (isEmpty(s)) return 0; *e = s->data[(s->top)--]; return 1; 
} // 取栈顶元素 
int getTop(Stack *s, int *e) { if (isEmpty(s)) return 0; *e = s->data[s->top]; return 1; 
} 

（二）队列

• 定义：是一种只允许在一端进行插入，而在另一端进行删除操作的线性表，按照先进先出（FIFO, First In First Out）的原则组织数据。

• 队列的操作：初始化、入队、出队、取队头元素、判断队列是否为空等。

• 应用场景：广度优先搜索、打印任务排队等。

以循环队列为例，其代码实现如下（以 C 语言为例）：

#include <stdio.h> 
#include <stdlib.h> typedef struct { int *data; int front; int rear; int size; 
} SqQueue; // 初始化队列 
SqQueue* initQueue(int size) { SqQueue *q = (SqQueue*)malloc(sizeof(SqQueue)); q->data = (int*)malloc(size * sizeof(int)); q->front = q->rear = 0; q->size = size; return q; 
} // 判断队列是否为空 
int isEmpty(SqQueue *q) { return q->front == q->rear; 
} // 入队 
int enQueue(SqQueue *q, int e) { if ((q->rear + 1) % q->size == q->front) return 0; q->data[q->rear] = e; q->rear = (q->rear + 1) % q->size; return 1; 
} // 出队 
int deQueue(SqQueue *q, int *e) { if (isEmpty(q)) return 0; *e = q->data[q->front]; q->front = (q->front + 1) % q->size; return 1; 
} // 取队头元素 
int getFront(SqQueue *q, int *e) { if (isEmpty(q)) return 0; *e = q->data[q->front]; return 1; 
} 

五、串

（一）串的定义与存储

串是由零个或多个字符组成的有限序列，又称为字符串。串的存储方式有顺序存储和链式存储。

• 顺序存储：用一组地址连续的存储单元存储串中的字符序列。

• 链式存储：用链表存储串中的字符序列，每个节点可以存储一个或多个字符。

（二）串的基本操作

求串长、串连接、子串定位、串比较等。

例如，求串长的代码实现（以 C 语言为例）：

#include <stdio.h> int StrLength(char *s) { int len = 0; while (s[len]!= '\0') len++; return len; 
} 

六、数组和广义表

（一）数组

• 定义：数组是由 n 个相同类型的数据元素构成的有限序列，每个数据元素称为数组元素，每个元素在 n 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

• 数组的存储：对于一维数组，按顺序存储；对于多维数组，有行优先存储和列优先存储两种方式。

例如，二维数组行优先存储的地址计算公式：对于二维数组 A [m][n]，假设每个元素占 L 个存储单元，起始地址为 LOC (A [0][0])，则元素 A [i][j] 的存储地址为 LOC (A [i][j]) = LOC (A [0][0]) + (i * n + j) * L。

（二）广义表

• 定义：广义表是线性表的推广，是由零个或多个单元素或子表所组成的有限序列。

• 特点：广义表可以是递归的，即广义表可以是其自身的子表；广义表的元素可以是不同类型的。

例如，广义表 LS = (a, (b, (c, d)), e)，其中 a、e 是单元素，(b, (c, d)) 是子表。

七、树和二叉树

（一）树的基本概念

• 树的定义：树是 n（n≥0）个节点的有限集合。当 n = 0 时，称为空树；在任意一棵非空树中，有且仅有一个特定的称为根的节点，当 n > 1 时，其余节点可分为 m（m > 0）个互不相交的有限集 T1, T2, …, Tm，其中每个集合本身又是一棵树，并且称为根的子树。

• 树的基本术语：节点的度、树的度、叶子节点、分支节点、层次、深度等。

（二）二叉树

• 二叉树的定义：二叉树是 n（n≥0）个节点的有限集合，该集合或者为空集（空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

• 二叉树的性质：

• • 在二叉树的第 i 层上至多有 2^(i - 1) 个节点（i≥1）。
• • 深度为 k 的二叉树至多有 2^k - 1 个节点（k≥1）。
• • 对任何一棵二叉树 T，如果其终端节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2 + 1。

• 特殊二叉树：满二叉树、完全二叉树。

（三）二叉树的遍历

• 先序遍历：先访问根节点，再先序遍历左子树，最后先序遍历右子树。

• 中序遍历：先中序遍历左子树，再访问根节点，最后中序遍历右子树。

• 后序遍历：先后序遍历左子树，再后序遍历右子树，最后访问根节点。

• 层序遍历：从根节点开始，逐层从左到右访问节点。

以下是二叉树先序遍历的递归代码实现（以 C 语言为例）：

#include <stdio.h> 
#include <stdlib.h> typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; 
} BiTNode, *BiTree; // 先序遍历二叉树 
void PreOrderTraverse(BiTree T) { if (T) { printf("%c ", T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } 
} 

（四）线索二叉树

• 线索二叉树的定义：为了能方便地找到二叉树中节点的前驱和后继，引入线索二叉树的概念。对二叉树的节点进行某种遍历，使其变为一个有序的线性序列，在这个序列中，每个节点有且仅有一个前驱和一个后继。对于没有前驱或后继的节点，用线索（指针）指向其前驱或后继。

• 线索二叉树的构造：通过遍历二叉树，在遍历过程中修改空指针，使其指向该节点的前驱或后继。

（五）树和森林

• 树与二叉树的转换：可以将树转换为二叉树，以便利用二叉树的算法来处理树的问题。转换方法是：树中每个节点的第一个孩子作为其在二叉树中的左孩子，该节点的下一个兄弟作为其在二叉树中的右孩子。

• 森林与二叉树的转换：先将森林中的每棵树转换为二叉树，然后将第一棵二叉树的根作为整个二叉树的根，依次将后一棵二叉树作为前一棵二叉树的右子树。

（六）哈夫曼树

• 哈夫曼树的定义：给定 n 个权值作为 n 个叶子节点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。

• 哈夫曼树的构造：根据给定的 n 个权值，构造 n 棵只有一个节点的二叉树，组成森林 F；在 F 中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，其根节点的权值为左右子树根节点权值之和；在 F 中删除这两棵树，并将新的二叉树加入 F；重复上述步骤，直到 F 中只剩下一棵树，这棵树就是哈夫曼树。

八、图

（一）图的基本概念

• 图的定义：图是由顶点集 V 和边集 E 组成，记为 G = (V, E)，其中 V (G) 表示图 G 中顶点的有限非空集；E (G) 表示图 G 中顶点之间的关系（边）集合。

• 图的基本术语：有向图、无向图、弧、顶点的度、入度、出度、路径、回路等。

（二）图的存储结构

• 邻接矩阵：用一个二维数组来表示图中顶点之间的邻接关系。对于无向图，邻接矩阵是对称矩阵；对于有向图，邻接矩阵不一定对称。

• 邻接表：对图中的每个顶点建立一个单链表，链表中的节点表示与该顶点相邻接的顶点。

（三）图的遍历

• 深度优先搜索（DFS）：类似于树的先序遍历，从图中某个顶点 v 出发，访问此顶点，然后从 v 的未被访问的邻接点出发深度优先遍历图，直至图中所有和 v 有路径相通的顶点都被访问到。

• 广度优先搜索（BFS）：类似于树的层序遍历，从图中某顶点 v 出发，在访问了 v 之后依次访问 v 的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问的顶点的邻接点” 先于 “后被访问的顶点的邻接点” 被访问，直至图中所有已被访问的顶点的邻接点都被访问到。

（四）最小生成树

• 定义：对于一个带权连通无向图 G=(V, E)，生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设 R 为 G 的所有生成树的集合，若 T 为 R 中权值之和最小的生成树，则 T 称为 G 的最小生成树。

• 构造算法：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

（五）最短路径

• 单源最短路径：从一个源点到其余各顶点的最短路径。常用的算法有迪杰斯特拉（Dijkstra）算法。

• 每对顶点之间的最短路径：计算图中每对顶点之间的最短路径。常用的算法有弗洛伊德（Floyd）算法。

第二篇

1. 数据结构概述

1.1 数据结构的基本概念

数据结构是计算机存储、组织数据的方式，它涉及到数据的逻辑结构、存储结构以及数据的运算。数据结构的选择直接影响程序的效率和性能。

详细分析：

• 逻辑结构：描述数据元素之间的逻辑关系，如线性关系、树形关系、图形关系等。
• 存储结构：描述数据在计算机中的存储方式，如顺序存储、链式存储、索引存储等。
• 数据运算：包括插入、删除、查找、排序等操作。

示例：

• 逻辑结构：数组是一种线性结构，元素之间是一对一的关系。
• 存储结构：数组通常采用顺序存储，元素在内存中是连续存放的。
• 数据运算：数组的查找操作时间复杂度为$O(1)$，插入和删除操作时间复杂度为$O(n)$。

1.2 数据结构的分类

数据结构可以分为线性结构、非线性结构和集合结构。

详细分析：

• 线性结构：元素之间存在一对一的线性关系，如数组、链表、栈、队列。
• 非线性结构：元素之间存在一对多或多对多的关系，如树、图。
• 集合结构：元素之间没有明显的逻辑关系，如哈希表、集合。

示例：

• 线性结构：链表中的每个节点只有一个前驱和一个后继。
• 非线性结构：树中的每个节点可以有多个子节点。
• 集合结构：哈希表中的元素通过哈希函数映射到不同的位置。

1.3 数据结构的应用

数据结构广泛应用于数据库、操作系统、编译器设计、网络通信等领域。

详细分析：

• 数据库：B树、哈希表用于索引和数据存储。
• 操作系统：队列用于任务调度，栈用于函数调用。
• 编译器设计：语法树用于语法分析。
• 网络通信：图用于路由算法。

示例：

• 数据库：MySQL使用B+树作为索引结构，提高查询效率。
• 操作系统：Linux内核使用红黑树管理内存块。

---

2. 线性结构

2.1 数组

数组是一种线性数据结构，它用一组连续的内存空间来存储相同类型的数据。

详细分析：

• 定义：数组是一种静态数据结构，大小固定。
• 操作：
  • 插入：在指定位置插入元素，需要移动后续元素。
  • 删除：删除指定位置的元素，需要移动后续元素。
  • 查找：通过索引直接访问元素。
• 时间复杂度：
  • 查找：$O(1)$
  • 插入/删除：$O(n)$

示例：

# 数组的插入操作
arr = [1, 2, 3, 4, 5]
arr.insert(2, 10)  # 在索引2处插入10
print(arr)  # 输出: [1, 2, 10, 3, 4, 5]

2.2 链表

链表是一种动态数据结构，它通过指针将一组零散的内存块串联起来。

详细分析：

• 定义：链表是一种动态数据结构，大小可以动态调整。
• 类型：
  • 单链表：每个节点只有一个指针指向下一个节点。
  • 双链表：每个节点有两个指针，分别指向前一个节点和后一个节点。
  • 循环链表：尾节点的指针指向头节点，形成一个环。
• 操作：
  • 插入：在指定位置插入节点，只需修改指针。
  • 删除：删除指定位置的节点，只需修改指针。
  • 查找：需要从头节点开始遍历。
• 时间复杂度：
  • 查找：$O(n)$
  • 插入/删除：$O(1)$

示例：

# 单链表的插入操作
class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef insert(self, data, position):new_node = Node(data)if position == 0:new_node.next = self.headself.head = new_nodeelse:current = self.headfor _ in range(position - 1):if current is None:raise IndexError("Position out of range")current = current.nextnew_node.next = current.nextcurrent.next = new_node# 使用示例
ll = LinkedList()
ll.insert(1, 0)
ll.insert(2, 1)
ll.insert(3, 1)

2.3 栈

栈是一种后进先出（LIFO）的数据结构。

详细分析：

• 定义：栈是一种受限的线性结构，只允许在一端进行插入和删除操作。
• 操作：
  • 入栈（push）：将元素压入栈顶。
  • 出栈（pop）：将栈顶元素弹出。
• 应用：
  • 函数调用栈：用于保存函数调用的上下文。
  • 表达式求值：用于中缀表达式转后缀表达式。

示例：

# 栈的实现
class Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):if not self.is_empty():return self.items.pop()raise IndexError("Pop from empty stack")def is_empty(self):return len(self.items) == 0# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # 输出: 2

2.4 队列

队列是一种先进先出（FIFO）的数据结构。

详细分析：

• 定义：队列是一种受限的线性结构，只允许在一端插入，在另一端删除。
• 类型：
  • 普通队列：基本的FIFO队列。
  • 循环队列：通过循环利用数组空间，解决普通队列的空间浪费问题。
  • 优先队列：元素按优先级出队，通常使用堆实现。
• 操作：
  • 入队（enqueue）：将元素插入队尾。
  • 出队（dequeue）：将队头元素删除。
• 应用：
  • 任务调度：操作系统中的任务调度队列。
  • 缓冲区管理：网络通信中的数据传输缓冲区。

示例：

# 队列的实现
from collections import dequeclass Queue:def __init__(self):self.items = deque()def enqueue(self, item):self.items.append(item)def dequeue(self):if not self.is_empty():return self.items.popleft()raise IndexError("Dequeue from empty queue")def is_empty(self):return len(self.items) == 0# 使用示例
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
print(queue.dequeue())  # 输出: 1

---

3. 非线性结构

3.1 树

树是一种层次结构，由节点和边组成。

详细分析：

• 定义：树是一种非线性结构，每个节点可以有多个子节点。
• 类型：
  • 二叉树：每个节点最多有两个子节点。
  • 二叉搜索树：左子树的所有节点值小于根节点，右子树的所有节点值大于根节点。
  • 平衡二叉树：左右子树的高度差不超过1，如AVL树、红黑树。
• 遍历方式：
  • 前序遍历：根节点 -> 左子树 -> 右子树。
  • 中序遍历：左子树 -> 根节点 -> 右子树。
  • 后序遍历：左子树 -> 右子树 -> 根节点。
  • 层次遍历：按层次从上到下，从左到右遍历。
• 应用：
  • 文件系统：目录树结构。
  • 数据库索引：B树、B+树用于数据库索引。

示例：

# 二叉树的遍历
class TreeNode:def __init__(self, data):self.data = dataself.left = Noneself.right = Nonedef pre_order_traversal(root):if root:print(root.data, end=" ")pre_order_traversal(root.left)pre_order_traversal(root.right)# 使用示例
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
pre_order_traversal(root)  # 输出: 1 2 3

3.2 图

图是由节点和边组成的非线性结构。

详细分析：

• 定义：图是一种复杂的非线性结构，节点之间可以有任意关系。
• 类型：
  • 有向图：边有方向。
  • 无向图：边没有方向。
  • 加权图：边有权重。
• 遍历方式：
  • 深度优先搜索（DFS）：沿着一条路径深入，直到不能再深入为止，然后回溯。
  • 广度优先搜索（BFS）：按层次遍历，先访问离起点最近的节点。
• 应用：
  • 社交网络：用户之间的关系图。
  • 路径规划：地图导航中的最短路径算法。

示例：

# 图的深度优先搜索
from collections import defaultdictclass Graph:def __init__(self):self.graph = defaultdict(list)def add_edge(self, u, v):self.graph[u].append(v)def dfs(self, v, visited):visited.add(v)print(v, end=" ")for neighbor in self.graph[v]:if neighbor not in visited:self.dfs(neighbor, visited)# 使用示例
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
g.dfs(2, set())  # 输出: 2 0 1 3

---

4. 集合结构

4.1 哈希表

哈希表是一种通过哈希函数将键映射到值的数据结构。

详细分析：

• 定义：哈希表通过哈希函数将键映射到数组的索引，从而实现快速查找。
• 操作：
  • 插入：通过哈希函数计算索引，将键值对存储在数组中。
  • 删除：通过哈希函数计算索引，删除对应的键值对。
  • 查找：通过哈希函数计算索引，直接访问对应的值。
• 时间复杂度：
  • 平均$O(1)$，最坏$O(n)$（哈希冲突时）。
• 应用：
  • 字典：Python中的dict类型就是基于哈希表实现的。
  • 缓存：缓存系统中常用哈希表存储键值对。

示例：

# 哈希表的实现
class HashTable:def __init__(self, size):self.size = sizeself.table = [[] for _ in range(size)]def _hash(self, key):return hash(key) % self.sizedef insert(self, key, value):index = self._hash(key)for kvp in self.table[index]:if kvp[0] == key:kvp[1] = valuereturnself.table[index].append([key, value])def get(self, key):index = self._hash(key)for kvp in self.table[index]:if kvp[0] == key:return kvp[1]raise KeyError(f"Key {key} not found")# 使用示例
ht = HashTable(10)
ht.insert("name", "Alice")
print(ht.get("name"))  # 输出: Alice

4.2 集合

集合是一种不包含重复元素的数据结构。

详细分析：

• 定义：集合是一种无序的数据结构，元素之间没有重复。
• 操作：
  • 并集：两个集合的所有元素。
  • 交集：两个集合共有的元素。
  • 差集：一个集合有而另一个集合没有的元素。
• 应用：
  • 数据去重：去除列表中的重复元素。
  • 集合运算：如并集、交集、差集等。

示例：

# 集合的操作
set1 = {1, 2, 3}
set2 = {3, 4, 5}
print(set1.union(set2))  # 输出: {1, 2, 3, 4, 5}
print(set1.intersection(set2))  # 输出: {3}
print(set1.difference(set2))  # 输出: {1, 2}

---

5. 习题练习

5.1 数组习题

1. 找出数组中的最大值和最小值：

   def find_max_min(arr):return max(arr), min(arr)
   

2. 将数组中的元素逆序排列：

   def reverse_array(arr):return arr[::-1]
   

5.2 链表习题

1. 实现单链表的插入和删除操作：

   class Node:def __init__(self, data):self.data = dataself.next = Noneclass LinkedList:def __init__(self):self.head = Nonedef insert(self, data, position):new_node = Node(data)if position == 0:new_node.next = self.headself.head = new_nodeelse:current = self.headfor _ in range(position - 1):if current is None:raise IndexError("Position out of range")current = current.nextnew_node.next = current.nextcurrent.next = new_nodedef delete(self, position):if position == 0:self.head = self.head.nextelse:current = self.headfor _ in range(position - 1):if current is None:raise IndexError("Position out of range")current = current.nextcurrent.next = current.next.next
   

2. 判断链表是否有环：

   def has_cycle(head):slow = headfast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False
   

5.3 栈和队列习题

1. 使用栈实现一个简单的计算器：

   def calculate(expression):stack = []for char in expression:if char.isdigit():stack.append(int(char))else:b = stack.pop()a = stack.pop()if char == '+':stack.append(a + b)elif char == '-':stack.append(a - b)elif char == '*':stack.append(a * b)elif char == '/':stack.append(a // b)return stack.pop()
   

2. 使用队列实现一个任务调度系统：

   from collections import dequeclass TaskScheduler:def __init__(self):self.queue = deque()def add_task(self, task):self.queue.append(task)def run_task(self):if self.queue:return self.queue.popleft()return None
   

5.4 树习题

1. 实现二叉树的遍历算法：

   def in_order_traversal(root):if root:in_order_traversal(root.left)print(root.data, end=" ")in_order_traversal(root.right)
   

2. 判断二叉树是否为平衡二叉树：

   def is_balanced(root):def check_height(node):if not node:return 0left_height = check_height(node.left)right_height = check_height(node.right)if abs(left_height - right_height) > 1:return -1return max(left_height, right_height) + 1return check_height(root) != -1
   

5.5 图习题

1. 实现图的深度优先搜索（DFS）和广度优先搜索（BFS）：

   def bfs(graph, start):visited = set()queue = deque([start])while queue:vertex = queue.popleft()if vertex not in visited:print(vertex, end=" ")visited.add(vertex)queue.extend(graph[vertex] - visited)
   

2. 找出图中的最短路径：

   from collections import dequedef shortest_path(graph, start, end):queue = deque([(start, [start])])while queue:(vertex, path) = queue.popleft()for next_vertex in graph[vertex] - set(path):if next_vertex == end:return path + [next_vertex]else:queue.append((next_vertex, path + [next_vertex]))return None
   

5.6 哈希表习题

1. 实现一个简单的哈希表，并处理冲突：

   class HashTable:def __init__(self, size):self.size = sizeself.table = [[] for _ in range(size)]def _hash(self, key):return hash(key) % self.sizedef insert(self, key, value):index = self._hash(key)for kvp in self.table[index]:if kvp[0] == key:kvp[1] = valuereturnself.table[index].append([key, value])def get(self, key):index = self._hash(key)for kvp in self.table[index]:if kvp[0] == key:return kvp[1]raise KeyError(f"Key {key} not found")
   

第三篇

2. 线性表
   顺序表（数组）
   定义：顺序表使用一段连续的内存空间来存储元素，每个元素通过下标来访问。
   特点：
   优点：
   支持随机访问，查找效率高。
   内存空间连续，利用率较高。
   缺点：
   插入和删除操作需要移动大量元素，效率较低。
   固定大小，可能会浪费空间或出现空间不足的问题。
   链表
   定义：链表是一种由节点组成的数据结构，每个节点包含数据和一个指向下一个节点的指针。
   特点：
   优点：
   动态分配内存，避免空间浪费。
   插入和删除操作高效，不需要移动大量元素。
   缺点：
   查找操作需要遍历链表，效率低。
   每个节点需要额外的存储空间来存储指针。
   应用：

顺序表适用于需要频繁查找、但修改较少的场景。
链表适用于需要频繁插入和删除元素的场景。
3. 栈与队列
栈（Stack）
定义：栈是一种后进先出（LIFO）结构，元素只能从栈顶插入或删除。
常见操作：
push: 压栈，将元素添加到栈顶。
pop: 弹栈，从栈顶移除元素。
peek: 查看栈顶元素。
应用：

栈常用于处理递归问题、表达式求值、括号匹配等。
队列（Queue）
定义：队列是一种先进先出（FIFO）结构，元素只能从队尾插入，从队头删除。
常见操作：
enqueue: 入队，将元素添加到队尾。
dequeue: 出队，从队头移除元素。
front: 查看队头元素。
应用：

队列常用于任务调度、资源管理、广度优先搜索等。
4. 树与图
树
定义：树是一种层次结构的数据结构，节点之间存在一对多的关系。每个节点有一个父节点和多个子节点。
类型：
二叉树：每个节点最多有两个子节点。
平衡二叉树（AVL树、红黑树）：自平衡二叉树，保证树的高度平衡，使查找、插入和删除的时间复杂度保持在O(logn)。
堆：完全二叉树的特例，用于实现优先队列。
应用：

树常用于存储有层级关系的数据，例如文件系统、数据库索引、表达式求值等。
图
定义：图是由顶点和边组成的集合，顶点代表数据，边表示数据之间的关系。
类型：
无向图：边没有方向。
有向图：边有方向。
带权图：边有权值。
应用：

图常用于社交网络、路径规划、网络流量分析等问题。
5. 常见算法
数据结构的学习不仅仅是掌握不同类型的数据存储方式，还要学习如何使用合适的算法来处理这些数据。常见的算法包括排序、查找和图算法。

排序算法
冒泡排序：比较相邻元素并交换，直到数组有序。时间复杂度O(n²)。
快速排序：基于分治法，选择一个基准元素，分割成小于基准和大于基准的两部分，递归处理。时间复杂度O(nlogn)。
归并排序：也基于分治法，将数组分割成更小的部分，再合并。时间复杂度O(nlogn)。
应用：

排序算法用于将无序数据排序，广泛应用于数据库、文件系统等。
查找算法
顺序查找：逐个元素比较，时间复杂度O(n)。
二分查找：在有序数组中，利用分治法不断缩小查找范围，时间复杂度O(logn)。
应用：

查找算法用于从数据集合中找到特定元素。
图算法
深度优先搜索（DFS）：从一个顶点开始，沿着图的边进行深度搜索，直到遍历到所有可达节点。常用于图的遍历、拓扑排序等。
广度优先搜索（BFS）：从一个顶点开始，沿着图的边进行广度搜索，直到遍历到所有可达节点。常用于最短路径算法、社交网络分析等。
6. 数据结构的应用
数据结构不仅仅是理论知识，它们广泛应用于各类实际问题的解决中。掌握如何选择合适的数据结构和算法能够大大提高程序的效率。常见的应用包括：

栈和队列：用于递归处理、括号匹配、任务调度、资源分配等。
树：用于数据库索引、文件系统、XML解析等。
图：用于网络拓扑、路径规划、社交网络分析等