第2课数据结构_分类
热度🔥:43 免费课程
授课语音
数据结构分类
1. 介绍
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆和图，分为逻辑结构和物理结构。
1.1 逻辑结构
逻辑结构描述了数据之间的关系和组织方式，主要分为线性结构和非线性结构。
线性结构
线性结构中的数据元素按顺序排列，每个元素有且只有一个前驱和一个后继。主要包括：
数组（Array）：一组相同类型的元素，按顺序存储在内存中。支持随机访问，但插入和删除操作较慢，因为可能需要移动大量元素。
链表（Linked List）：由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的变体包括：
- 单链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。
- 双链表（Doubly Linked List）：每个节点有两个指针，分别指向前一个节点和下一个节点。
- 循环链表（Circular Linked List）：链表的尾节点指向头节点，形成一个环。
栈（Stack）：遵循“后进先出”（LIFO）原则的数据结构。主要操作有推入（push）和弹出（pop）。
队列（Queue）：遵循“先进先出”（FIFO）原则的数据结构。主要操作有入队（enqueue）和出队（dequeue）。它的变体包括：
- 双端队列（Deque）：可以在两端进行插入和删除操作的队列。
- 优先队列（Priority Queue）：每个元素都有一个优先级，按照优先级顺序进行操作。
非线性结构
非线性结构中的数据元素没有线性排列的顺序，元素间的关系更加复杂。主要包括：
树（Tree）：一种分层的数据结构，包含节点和边。每个节点可以有零个或多个子节点。常见的树结构包括：
二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）。
- 完全二叉树（Complete Binary Tree）：除了最后一层外，每层的节点都完全填满，最后一层的节点从左到右依次填充。
- 满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
- 平衡二叉树（Balanced Binary Tree）：每个节点的左右子树的高度差不超过某个阈值（通常为1）。
二叉搜索树（Binary Search Tree, BST）：二叉树的一种，其中左子树的值小于根节点的值，右子树的值大于根节点的值。
- AVL平衡树（Balanced Tree）：自平衡的二叉搜索树，任意节点的左右子树高度差不超过1。
- 红黑树（Red-Black Tree）：自平衡的二叉搜索树，节点颜色限制。
B树（B Tree）：自平衡的多路搜索树，适合存储和检索。每个节点可以有多个子节点，每个节点包含多个键（keys）和子节点指针。
B+树（B+ Tree）：B树的变体，所有键值都存储在叶子节点中，内部节点仅存索引。
堆（Heap）：一种特殊的完全二叉树，用于实现优先队列。分为最大堆（根节点最大）和最小堆（根节点最小）。
图（Graph）：由节点（顶点）和连接节点的边组成的结构。图可以是：
- 无向图（Undirected Graph）：边没有方向，连接两个节点。
- 有向图（Directed Graph）：边有方向，从一个节点指向另一个节点。
- 加权图（Weighted Graph）：边有权值，表示连接的代价或距离。
- 无权图（Unweighted Graph）：边没有权值，只有连接关系。
哈希表 是一种非常重要的数据结构，用于实现高效的插入、删除和查找操作。它通过哈希函数将数据映射到数组中的特定位置，以便在常数时间内完成这些操作。
图示
1.2 物理结构
物理结构描述了数据如何在计算机内存中实际存储。主要分为内存连续结构和内存分散结构。
内存连续结构：数据在内存中是连续存储的。主要包括：
- 数组（Array）：数据元素在内存中连续存储，支持快速随机访问。
内存分散结构：数据在内存中不是连续存储的，而是通过指针或引用连接起来。主要包括：
- 链表（Linked List）：节点在内存中分散存储，每个节点包含数据和指向下一个节点的指针（或双向链表中还包含指向前一个节点的指针）。
所有的数据结构都是基于数组、链表或两者的组合实现的。
2. 代码案例
TypeScript 代码：
// ======================线性结构==========================
// 1. 数组（Array）类
class ArrayStructure {
private size: number; // 数组的大小
private array: number[]; // 使用 TypeScript 的数组类型模拟数组
// 构造函数：初始化指定大小的数组，默认值为 -1
constructor(size: number) {
this.size = size;
this.array = new Array(size).fill(-1); // 初始化数组，默认填充 -1
}
// 设置数组指定位置的值
set(index: number, value: number): void {
if (index >= 0 && index < this.size) {
this.array[index] = value; // 赋值
} else {
throw new Error("Index out of bounds"); // 索引越界异常
}
}
// 获取数组指定位置的值
get(index: number): number {
if (index >= 0 && index < this.size) {
return this.array[index]; // 返回值
} else {
throw new Error("Index out of bounds"); // 索引越界异常
}
}
// 打印数组中的所有元素
print(): void {
console.log(this.array.join(" ")); // 使用 join 打印数组元素
}
}
// 2. 链表（Linked List）
// 2.1 单链表（Singly Linked List）节点类
class Node {
data: number; // 节点的数据
next: Node | null; // 指向下一个节点的指针
// 构造函数：初始化节点数据，指针默认为 null
constructor(data: number) {
this.data = data;
this.next = null; // 默认没有下一个节点
}
}
// 单链表（Singly Linked List）类
class SinglyLinkedList {
private head: Node | null; // 链表的头节点
// 构造函数：初始化链表为空
constructor() {
this.head = null;
}
// 向链表末尾添加新节点
append(data: number): void {
const newNode = new Node(data); // 创建新节点
if (this.head === null) {
this.head = newNode; // 如果链表为空，直接将新节点作为头节点
} else {
let last = this.head;
// 遍历链表找到最后一个节点
while (last.next !== null) {
last = last.next;
}
last.next = newNode; // 将新节点连接到最后
}
}
// 打印链表中的所有节点
print(): void {
let current = this.head;
// 遍历链表，输出每个节点的数据
while (current !== null) {
process.stdout.write(`${current.data} -> `);
current = current.next;
}
console.log("None"); // 输出结束符
}
}
// 2.2 双链表（Doubly Linked List）节点类
class DoublyNode {
data: number; // 节点的数据
next: DoublyNode | null; // 指向下一个节点的指针
prev: DoublyNode | null; // 指向前一个节点的指针
// 构造函数：初始化节点数据，指针默认为 null
constructor(data: number) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// 双链表（Doubly Linked List）类
class DoublyLinkedList {
private head: DoublyNode | null; // 双链表的头节点
// 构造函数：初始化双链表为空
constructor() {
this.head = null;
}
// 向双链表末尾添加新节点
append(data: number): void {
const newNode = new DoublyNode(data); // 创建新节点
if (this.head === null) {
this.head = newNode; // 如果链表为空，直接将新节点作为头节点
} else {
let last = this.head;
// 遍历链表找到最后一个节点
while (last.next !== null) {
last = last.next;
}
last.next = newNode; // 将新节点连接到最后
newNode.prev = last; // 将新节点的前指针指向最后一个节点
}
}
// 打印双链表中的所有节点
print(): void {
let current = this.head;
// 遍历双链表，输出每个节点的数据
while (current !== null) {
process.stdout.write(`${current.data} <-> `);
current = current.next;
}
console.log("None"); // 输出结束符
}
}
// 2.3 循环链表（Circular Linked List）节点类
class CircularNode {
data: number; // 节点的数据
next: CircularNode | null; // 指向下一个节点的指针
// 构造函数：初始化节点数据，指针默认为 null
constructor(data: number) {
this.data = data;
this.next = null;
}
}
// 循环链表（Circular Linked List）类
class CircularLinkedList {
private head: CircularNode | null; // 循环链表的头节点
// 构造函数：初始化循环链表为空
constructor() {
this.head = null;
}
// 向循环链表末尾添加新节点
append(data: number): void {
const newNode = new CircularNode(data); // 创建新节点
if (this.head === null) {
this.head = newNode;
newNode.next = newNode; // 如果链表为空，指向自身，形成循环
} else {
let last = this.head;
// 遍历链表找到最后一个节点
while (last.next !== this.head) {
last = last.next;
}
last.next = newNode; // 将新节点连接到最后
newNode.next = this.head; // 形成循环，最后一个节点指向头节点
}
}
// 打印循环链表中的所有节点
print(): void {
if (this.head === null) {
console.log("Empty List"); // 如果链表为空，输出提示
return;
}
let current = this.head;
// 遍历循环链表，直到回到头节点
do {
process.stdout.write(`${current.data} -> `);
current = current.next;
} while (current !== this.head);
console.log("(back to head)"); // 输出结束符，表明循环回到了头节点
}
}
// 3. 栈（Stack）类
class Stack {
private items: number[]; // 使用数组存储栈的元素
constructor() {
this.items = []; // 初始化栈为空
}
// 向栈中推入一个元素
push(item: number): void {
this.items.push(item); // 使用数组的 push 方法插入元素
}
// 从栈顶弹出一个元素
pop(): number {
if (this.isEmpty()) {
throw new Error("pop from empty stack"); // 如果栈为空，抛出异常
}
return this.items.pop()!; // 弹出栈顶元素
}
// 查看栈顶元素，但不弹出
peek(): number {
if (this.isEmpty()) {
throw new Error("peek from empty stack"); // 如果栈为空，抛出异常
}
return this.items[this.items.length - 1]; // 返回栈顶元素
}
// 判断栈是否为空
isEmpty(): boolean {
return this.items.length === 0; // 判断数组是否为空
}
// 获取栈的大小
size(): number {
return this.items.length; // 返回栈中元素的个数
}
}
// 4. 队列（Queue）类
class Queue {
private items: number[]; // 使用数组存储队列的元素
constructor() {
this.items = []; // 初始化队列为空
}
// 向队列尾部添加一个元素
enqueue(item: number): void {
this.items.push(item); // 使用数组的 push 方法插入元素
}
// 从队列头部删除一个元素
dequeue(): number {
if (this.isEmpty()) {
throw new Error("dequeue from empty queue"); // 如果队列为空，抛出异常
}
return this.items.shift()!; // 从队列头部移除元素
}
// 判断队列是否为空
isEmpty(): boolean {
return this.items.length === 0; // 判断数组是否为空
}
// 获取队列的大小
size(): number {
return this.items.length; // 返回队列中元素的个数
}
}
// ======================非线性结构==========================
// 1. 二叉树（Binary Tree）节点类
class TreeNode {
data: number; // 节点的数据
left: TreeNode | null; // 左子树
right: TreeNode | null; // 右子树
constructor(data: number) {
this.data = data;
this.left = this.right = null; // 默认左右子树为 null
}
}
// 二叉树（Binary Tree）类
class BinaryTree {
private root: TreeNode | null; // 二叉树的根节点
constructor() {
this.root = null; // 初始化二叉树为空
}
// 插入节点（简单实现，按顺序插入）
insert(data: number): void {
if (this.root === null) {
this.root = new TreeNode(data); // 如果树为空，直接插入根节点
} else {
this.insertRec(this.root, data); // 否则递归插入
}
}
// 递归插入节点
private insertRec(node: TreeNode, data: number): void {
if (data < node.data) {
if (node.left === null) {
node.left = new TreeNode(data); // 插入到左子树
} else {
this.insertRec(node.left, data); // 递归插入到左子树
}
} else {
if (node.right === null) {
node.right = new TreeNode(data); // 插入到右子树
} else {
this.insertRec(node.right, data); // 递归插入到右子树
}
}
}
// 中序遍历二叉树
inorder(): void {
this.inorderRec(this.root); // 调用递归方法进行中序遍历
console.log(); // 换行
}
// 递归中序遍历
private inorderRec(node: TreeNode | null): void {
if (node !== null) {
this.inorderRec(node.left); // 先遍历左子树
process.stdout.write(`${node.data} `); // 输出当前节点的数据
this.inorderRec(node.right); // 再遍历右子树
}
}
}
// 2. 堆（Heap）类：最小堆实现
class MinHeap {
private heap: number[]; // 存储堆的数组
constructor() {
this.heap = [];
}
// 向堆中插入元素并调整堆
insert(val: number): void {
this.heap.push(val); // 插入元素到堆的末尾
this.heapifyUp(this.heap.length - 1); // 调整堆
}
// 上浮调整堆
private heapifyUp(index: number): void {
const parent = Math.floor((index - 1) / 2);
if (index > 0 && this.heap[index] < this.heap[parent]) {
// 如果当前节点小于父节点，交换二者
[this.heap[index], this.heap[parent]] = [this.heap[parent], this.heap[index]];
this.heapifyUp(parent); // 递归向上调整
}
}
// 弹出堆顶元素并调整堆
extractMin(): number {
if (this.heap.length === 0) {
throw new Error("extractMin from empty heap");
}
if (this.heap.length === 1) {
return this.heap.pop()!; // 如果堆中只有一个元素，直接弹出
}
const min = this.heap[0]; // 记录堆顶元素
this.heap[0] = this.heap.pop()!; // 弹出堆顶元素，堆的最后一个元素替代堆顶
this.heapifyDown(0); // 调整堆
return min;
}
// 下沉调整堆
private heapifyDown(index: number): void {
let smallest = index;
const left = 2 * index + 1;
const right = 2 * index + 2;
if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
smallest = left;
}
if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
smallest = right;
}
if (smallest !== index) {
// 如果当前节点不满足堆的性质，交换并递归调整
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
this.heapifyDown(smallest);
}
}
}
// 3. 图（Graph）类：邻接表实现
class Graph {
private graph: Map<number, number[]>; // 使用 Map 来表示邻接表
constructor() {
this.graph = new Map();
}
// 向图中添加边
addEdge(u: number, v: number): void {
if (!this.graph.has(u)) {
this.graph.set(u, []);
}
this.graph.get(u)?.push(v); // 添加边 u -> v
}
// 打印图的邻接表
printGraph(): void {
for (const [key, value] of this.graph.entries()) {
console.log(`${key} -> ${value.join(", ")}`);
}
}
}
// ======================示例代码==========================
const main = () => {
// ====================== 测试数组 =======================
const arr = new ArrayStructure(5); // 创建一个大小为 5 的数组
arr.set(0, 10); // 设置数组第一个元素为 10
arr.set(1, 20); // 设置数组第二个元素为 20
arr.print(); // 打印数组内容
// ====================== 测试单链表 =======================
const sll = new SinglyLinkedList();
sll.append(1); // 向链表中添加元素
sll.append(2);
sll.append(3);
sll.print(); // 打印链表内容
// ====================== 测试栈 =======================
const stack = new Stack();
stack.push(10); // 向栈中压入元素
stack.push(20);
console.log(stack.pop()); // 弹出栈顶元素并打印
// ====================== 测试队列 =======================
const queue = new Queue();
queue.enqueue(1); // 向队列中加入元素
queue.enqueue(2);
console.log(queue.dequeue()); // 出队并打印
// ====================== 测试二叉树 =======================
const bt = new BinaryTree();
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.inorder(); // 打印二叉树的中序遍历
// ====================== 测试堆 =======================
const minHeap = new MinHeap();
minHeap.insert(3);
minHeap.insert(1);
console.log(minHeap.extractMin()); // 弹出最小元素并打印
// ====================== 测试图 =======================
const g = new Graph();
g.addEdge(1, 2);
g.addEdge(1, 3);
g.printGraph(); // 打印图的邻接表
};
main(); // 执行示例代码
解释：
- 数组（Array）类：通过 TypeScript 数组实现，可以设置和获取数组中的元素。
- 链表：
- 单链表（Singly Linked List）：支持节点添加和遍历打印。
- 双链表（Doubly Linked List）：支持节点添加并维护前后指针。
- 循环链表（Circular Linked List）：实现循环链表结构，末尾节点指回头节点。
- 栈（Stack）：基于数组的栈实现，支持基本的
push、pop、peek操作。 - 队列（Queue）：基于数组实现的队列，支持
enqueue和dequeue操作。 - 二叉树（Binary Tree）：实现了基本的节点插入和中序遍历功能。
- 堆（MinHeap）：实现了一个最小堆，支持插入元素、提取最小值操作，并自动维护堆的结构。
- 图（Graph）：使用邻接表（
Map<number, number[]>）表示图，支持添加边，并可以打印图的邻接表。
示例输出：
10 20 -1 -1 -1
1 -> 2 -> 3 -> None
20
1
5 3 7
1
1 -> 2, 3
3. 总结
本文概述了常见的数据结构及其分类，分别介绍了逻辑结构和物理结构，并通过代码示例展示了各种数据结构的基本实现。掌握这些数据结构将有助于高效地处理和存储数据。
系列课程：
📱 下载客户端
小程序
安卓APP
iOS APP
📚 视频课程
- Java入门教程 86
- C++入门教程 45
- Python入门教程 33
- JavaScript入门教程 35
- Go入门教程 38
- SQL入门教程 29
- 设计模式入门 23
- 数据结构与算法 30
- C语言入门教程 25
- Redis入门教程 31