第2课数据结构_分类
热度🔥:47 免费课程
授课语音
数据结构分类
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. 代码案例
#include <iostream>
#include <vector>
#include <stdexcept>
#include <map>
#include <queue>
// ====================== 线性结构 ===========================
// 1. 数组（Array）类
class ArrayStructure {
private:
int size; // 数组大小
std::vector<int> array; // 数组数据
public:
// 构造函数，初始化数组
ArrayStructure(int size) {
this->size = size;
array.resize(size, -1); // 初始化数组，默认值为 -1
}
// 设置指定索引的值
void set(int index, int value) {
if (index >= 0 && index < size) {
array[index] = value;
} else {
throw std::out_of_range("Index out of bounds"); // 索引越界错误
}
}
// 获取指定索引的值
int get(int index) {
if (index >= 0 && index < size) {
return array[index];
} else {
throw std::out_of_range("Index out of bounds"); // 索引越界错误
}
}
// 打印数组内容
void print() {
for (int i = 0; i < size; ++i) {
std::cout << array[i] << " "; // 输出数组元素
}
std::cout << std::endl;
}
};
// 2. 链表（Linked List）
// 2.1 单链表（Singly Linked List）节点类
class Node {
public:
int data; // 节点数据
Node* next; // 指向下一个节点的指针
Node(int data) : data(data), next(nullptr) {} // 构造函数，初始化数据和指针
};
// 单链表（Singly Linked List）类
class SinglyLinkedList {
private:
Node* head; // 链表头节点
public:
SinglyLinkedList() : head(nullptr) {} // 构造函数，初始化空链表
// 向链表末尾添加新节点
void append(int data) {
Node* newNode = new Node(data); // 创建新节点
if (head == nullptr) {
head = newNode; // 如果链表为空，直接将头指针指向新节点
} else {
Node* last = head;
while (last->next != nullptr) { // 找到链表的最后一个节点
last = last->next;
}
last->next = newNode; // 将最后一个节点的指针指向新节点
}
}
// 打印链表内容
void print() {
Node* current = head;
while (current != nullptr) { // 遍历链表
std::cout << current->data << " -> "; // 输出节点数据
current = current->next;
}
std::cout << "None" << std::endl; // 输出链表结束标志
}
};
// 2.2 双链表（Doubly Linked List）节点类
class DoublyNode {
public:
int data; // 节点数据
DoublyNode* next; // 指向下一个节点的指针
DoublyNode* prev; // 指向前一个节点的指针
DoublyNode(int data) : data(data), next(nullptr), prev(nullptr) {} // 构造函数
};
// 双链表（Doubly Linked List）类
class DoublyLinkedList {
private:
DoublyNode* head; // 双链表头节点
public:
DoublyLinkedList() : head(nullptr) {} // 构造函数，初始化空链表
// 向双链表末尾添加新节点
void append(int data) {
DoublyNode* newNode = new DoublyNode(data); // 创建新节点
if (head == nullptr) {
head = newNode; // 如果链表为空，直接将头指针指向新节点
} else {
DoublyNode* last = head;
while (last->next != nullptr) { // 找到链表的最后一个节点
last = last->next;
}
last->next = newNode; // 将最后一个节点的指针指向新节点
newNode->prev = last; // 设置新节点的前向指针
}
}
// 打印双链表内容
void print() {
DoublyNode* current = head;
while (current != nullptr) { // 遍历双链表
std::cout << current->data << " <-> "; // 输出节点数据
current = current->next;
}
std::cout << "None" << std::endl; // 输出链表结束标志
}
};
// 2.3 循环链表（Circular Linked List）节点类
class CircularNode {
public:
int data; // 节点数据
CircularNode* next; // 指向下一个节点的指针
CircularNode(int data) : data(data), next(nullptr) {} // 构造函数
};
// 循环链表（Circular Linked List）类
class CircularLinkedList {
private:
CircularNode* head; // 循环链表头节点
public:
CircularLinkedList() : head(nullptr) {} // 构造函数，初始化空链表
// 向循环链表末尾添加新节点
void append(int data) {
CircularNode* newNode = new CircularNode(data); // 创建新节点
if (head == nullptr) {
head = newNode; // 如果链表为空，将头指针指向新节点
newNode->next = newNode; // 新节点的 next 指向自己，形成循环
} else {
CircularNode* last = head;
while (last->next != head) { // 找到链表的最后一个节点
last = last->next;
}
last->next = newNode; // 将最后一个节点的 next 指向新节点
newNode->next = head; // 新节点的 next 指向头节点，完成循环
}
}
// 打印循环链表内容
void print() {
if (head == nullptr) { // 如果链表为空
std::cout << "Empty List" << std::endl;
return;
}
CircularNode* current = head;
do { // 遍历循环链表
std::cout << current->data << " -> "; // 输出节点数据
current = current->next;
} while (current != head); // 循环直到回到头节点
std::cout << "(back to head)" << std::endl; // 输出回到头节点的标志
}
};
// 3. 栈（Stack）类
class Stack {
private:
std::vector<int> items; // 栈内存储的元素
public:
// 压栈操作
void push(int item) {
items.push_back(item);
}
// 弹栈操作
int pop() {
if (isEmpty()) {
throw std::underflow_error("pop from empty stack"); // 栈空时弹栈错误
}
int top = items.back(); // 获取栈顶元素
items.pop_back(); // 弹出栈顶元素
return top;
}
// 查看栈顶元素
int peek() {
if (isEmpty()) {
throw std::underflow_error("peek from empty stack"); // 栈空时查看栈顶错误
}
return items.back(); // 返回栈顶元素
}
// 判断栈是否为空
bool isEmpty() {
return items.empty();
}
// 获取栈的大小
int size() {
return items.size();
}
};
// 4. 队列（Queue）类
class Queue {
private:
std::vector<int> items; // 队列内存储的元素
public:
// 入队操作
void enqueue(int item) {
items.push_back(item);
}
// 出队操作
int dequeue() {
if (isEmpty()) {
throw std::underflow_error("dequeue from empty queue"); // 队列空时出队错误
}
int front = items.front(); // 获取队首元素
items.erase(items.begin()); // 移除队首元素
return front;
}
// 判断队列是否为空
bool isEmpty() {
return items.empty();
}
// 获取队列的大小
int size() {
return items.size();
}
};
// ====================== 非线性结构 ===========================
// 1. 二叉树（Binary Tree）节点类
class TreeNode {
public:
int data; // 节点数据
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(int data) : data(data), left(nullptr), right(nullptr) {} // 构造函数
};
// 二叉树（Binary Tree）类
class BinaryTree {
private:
TreeNode* root; // 树根节点
// 递归插入节点
void insert(TreeNode*& node, int data) {
if (node == nullptr) {
node = new TreeNode(data); // 如果节点为空，创建新节点
} else if (data < node->data) {
insert(node->left, data); // 如果数据小于当前节点，递归插入左子树
} else {
insert(node->right, data); // 如果数据大于当前节点，递归插入右子树
}
}
// 中序遍历
void inorder(TreeNode* node) {
if (node != nullptr) {
inorder(node->left); // 遍历左子树
std::cout << node->data << " "; // 输出节点数据
inorder(node->right); // 遍历右子树
}
}
public:
BinaryTree() : root(nullptr) {} // 构造函数，初始化为空树
// 插入节点
void insert(int data) {
insert(root, data); // 从根节点开始插入
}
// 中序遍历
void inorder() {
inorder(root); // 从根节点开始中序遍历
std::cout << std::endl;
}
};
// 2. 堆（Heap）类
class MinHeap {
private:
std::vector<int> heap; // 存储堆元素
// 向上调整堆
void heapifyUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (heap[index] < heap[parent]) {
std::swap(heap[index], heap[parent]); // 如果当前元素小于父节点，交换
index = parent; // 更新当前索引
} else {
break;
}
}
}
// 向下调整堆
void heapifyDown(int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int smallest = index;
if (leftChild < heap.size() && heap[leftChild] < heap[smallest]) {
smallest = leftChild; // 左子节点更小
}
if (rightChild < heap.size() && heap[rightChild] < heap[smallest]) {
smallest = rightChild; // 右子节点更小
}
if (smallest != index) {
std::swap(heap[index], heap[smallest]); // 交换当前节点与最小子节点
heapifyDown(smallest); // 继续调整
}
}
public:
// 插入元素
void insert(int value) {
heap.push_back(value); // 将元素添加到堆末尾
heapifyUp(heap.size() - 1); // 调整堆
}
// 删除最小元素
int extractMin() {
if (heap.empty()) {
throw std::underflow_error("Heap is empty"); // 堆为空错误
}
int minValue = heap[0]; // 获取最小值
heap[0] = heap.back(); // 将堆尾元素移到堆顶
heap.pop_back(); // 移除堆尾元素
heapifyDown(0); // 调整堆
return minValue;
}
};
// 3. 图（Graph）类
class Graph {
private:
std::map<int, std::vector<int>> adjList; // 图的邻接表表示
public:
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v); // 添加 u -> v 边
adjList[v].push_back(u); // 添加 v -> u 边（无向图）
}
// 打印图的邻接表
void printGraph() {
for (const auto& pair : adjList) {
std::cout << pair.first << " -> ";
for (int neighbor : pair.second) {
std::cout << neighbor << " "; // 输出邻接节点
}
std::cout << std::endl;
}
}
};
// 主函数，测试各种数据结构
int main() {
// ====================== 测试数组 =======================
ArrayStructure arr(5);
arr.set(0, 10);
arr.set(1, 20);
arr.print();
// ====================== 测试单链表 =======================
SinglyLinkedList sll;
sll.append(1);
sll.append(2);
sll.append(3);
sll.print();
// ====================== 测试栈 =======================
Stack stack;
stack.push(10);
stack.push(20);
std::cout << stack.pop() << std::endl;
// ====================== 测试队列 =======================
Queue queue;
queue.enqueue(1);
queue.enqueue(2);
std::cout << queue.dequeue() << std::endl;
// ====================== 测试二叉树 =======================
BinaryTree bt;
bt.insert(5);
bt.insert(3);
bt.insert(7);
bt.inorder();
// ====================== 测试堆 =======================
MinHeap minHeap;
minHeap.insert(3);
minHeap.insert(1);
std::cout << minHeap.extractMin() << std::endl;
// ====================== 测试图 =======================
Graph g;
g.addEdge(1, 2);
g.addEdge(1, 3);
g.printGraph();
return 0;
}
解释：
- 数组（Array）类: 使用
std::vector<int>来模拟动态数组。 - 链表类: 使用普通的指针和类来实现单链表、双链表和循环链表。
- 栈和队列: 使用
std::vector来实现栈和队列。 - 二叉树: 二叉树的实现使用递归方式插入节点并进行中序遍历。
- 堆: 使用
std::vector来实现最小堆，并支持插入和弹出操作。 - 图: 使用
std::map来实现邻接表。
3. 总结
本文概述了常见的数据结构及其分类，分别介绍了逻辑结构和物理结构，并通过代码示例展示了各种数据结构的基本实现。掌握这些数据结构将有助于高效地处理和存储数据。
系列课程：
📱 下载客户端
小程序
安卓APP
iOS APP
📚 视频课程
- Java入门教程 86
- Python入门教程 33
- JavaScript入门教程 35
- C++入门教程 45
- Go入门教程 38
- 数据结构与算法 30
- 设计模式入门 23
- SQL入门教程 29
- C语言入门教程 25
- TypeScript入门教程 19