前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站：人工智能教程

文章目录

一、数据结构1. 线性数据结构2. 非线性数据结构3. 其他重要数据结构

二、定义数据结构1. 数组（Array）2. 链表（LinkedList）3. 栈（Stack）

三、指针、关键字1. 指针链表树

2. 关键字

四、相关链接

一、数据结构

C++作为一种高效的编程语言，提供了丰富的内置数据类型和库，支持各种复杂的数据结构实现。C++中的数据结构主要分为线性数据结构和非线性数据结构两大类，每种数据结构都有其独特的特点和应用场景。

1. 线性数据结构

线性数据结构中的数据元素之间存在一对一的线性关系。常见的C++线性数据结构包括：

数组（Array）

定义：数组是一种聚合数据类型，用于存储相同类型的元素集合。特点：通过索引访问元素，访问速度快（O(1)），但插入和删除操作（尤其是中间位置）可能较慢。数组分为静态数组和动态数组，静态数组在编译时确定大小，不能动态调整；动态数组在运行时分配内存，可以动态调整大小（如使用<code>new和delete操作符，或在C++11及以后版本中使用std::vector）。

链表（Linked List）

定义：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。特点：插入和删除操作（尤其是中间位置）速度快（O(1)），但访问元素可能较慢（需要遍历链表）。链表分为单向链表、双向链表和循环链表等。

栈（Stack）

定义：栈是一种后进先出（LIFO）的数据结构。特点：主要操作包括push（压栈，添加元素到栈顶）、pop（弹栈，移除栈顶元素）和peek（查看栈顶元素）。栈可以使用数组或链表来实现，C++标准模板库（STL）提供了std::stack容器。

队列（Queue）

定义：队列是一种先进先出（FIFO）的数据结构。特点：主要操作包括enqueue（入队，添加元素到队尾）、dequeue（出队，移除队头元素）和front/back（查看队头/队尾元素）。队列也可以使用数组或链表来实现，C++ STL提供了std::queue容器。

2. 非线性数据结构

非线性数据结构中的数据元素之间存在一对多或多对多的关系。常见的C++非线性数据结构包括：

树（Tree）

定义：树是一种层次化的数据结构，由节点组成，每个节点有零个或多个子节点。特点：节点之间的关系是层次和分支的，如二叉树、平衡二叉树、红黑树等。树结构常用于实现排序、搜索和存储层次数据。

图（Graph）

定义：图由节点（或顶点）和边组成，用于表示复杂的关系网络。特点：节点之间的关系是多对多的，常用于表示社交网络、地图等。图分为无向图和有向图，图的表示方法有邻接矩阵和邻接表等。

哈希表（Hash Table）

定义：哈希表是一种通过哈希函数将键映射到存储位置的数据结构。特点：访问速度快（平均时间复杂度为O(1)），常用于实现快速查找、插入和删除操作。

堆（Heap）

定义：堆是一种特殊的树形数据结构，满足堆属性（父节点的值大于或等于（最大堆）或小于或等于（最小堆）其子节点的值）。特点：常用于实现优先队列，如操作系统的任务调度等。C++ STL提供了std::priority_queue容器，它底层通常使用最大堆实现。

3. 其他重要数据结构

字符串（String）：虽然字符串通常不被视为一种独立的数据结构，但在C++中，字符串是一个非常重要的数据类型，常用于表示文本数据。C++标准库提供了std::string类来管理字符串。

二、定义数据结构

在C++中，数据结构是通过类（class）或结构体（struct）来定义的，这些结构包含了数据成员（即属性）和成员函数（即方法），用于操作这些数据。下面我将给出几种常见数据结构的定义及简单案例。

1. 数组（Array）

虽然数组不是通过类或结构体显式定义的，但它是C++中最基本的数据结构之一。不过，为了展示自定义数据结构的思路，我们可以考虑一个封装了动态数组的类（类似于std::vector的简化版）。

#include <iostream>

class DynamicArray { -- -->

private:

int* arr;

int capacity;

int size;

public:

DynamicArray(int capacity = 10) : capacity(capacity), size(0), arr(new int[capacity]) { }

~DynamicArray() {

delete[] arr;

}

void add(int element) {

if (size == capacity) {

// 简化处理，实际应更复杂地处理扩容

capacity *= 2;

int* newArr = new int[capacity];

for (int i = 0; i < size; ++i) {

newArr[i] = arr[i];

}

delete[] arr;

arr = newArr;

}

arr[size++] = element;

}

void print() {

for (int i = 0; i < size; ++i) {

std::cout << arr[i] << " ";

}

std::cout << std::endl;

}

};

int main() {

DynamicArray myArray;

myArray.add(1);

myArray.add(2);

myArray.add(3);

myArray.print(); // 输出: 1 2 3

return 0;

}

2. 链表（LinkedList）

链表是一种动态数据结构，节点包含数据和指向下一个节点的指针。

#include <iostream>

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(nullptr) { }

};

class LinkedList {

private:

ListNode* head;

public:

LinkedList() : head(nullptr) { }

void append(int val) {

ListNode* newNode = new ListNode(val);

if (!head) {

head = newNode;

} else {

ListNode* current = head;

while (current->next) {

current = current->next;

}

current->next = newNode;

}

}

void print() {

ListNode* current = head;

while (current) {

std::cout << current->val << " ";

current = current->next;

}

std::cout << std::endl;

}

~LinkedList() {

// 简化处理，实际应递归删除所有节点

while (head) {

ListNode* temp = head;

head = head->next;

delete temp;

}

}

};

int main() {

LinkedList myList;

myList.append(1);

myList.append(2);

myList.append(3);

myList.print(); // 输出: 1 2 3

return 0;

}

3. 栈（Stack）

栈是一种后进先出（LIFO）的数据结构，可以使用数组或链表实现。

#include <iostream>

#include <vector>

class Stack {

private:

std::vector<int> elements;

public:

void push(int val) {

elements.push_back(val);

}

int pop() {

if (elements.empty()) {

throw std::out_of_range("Stack is empty!");

}

int top = elements.back();

elements.pop_back();

return top;

}

int top() {

if (elements.empty()) {

throw std::out_of_range("Stack is empty!");

}

return elements.back();

}

bool empty() {

return elements.empty();

}

};

int main() {

Stack myStack;

myStack.push(1);

}

三、指针、关键字

在C++中，数据结构和指针、关键字是紧密相关的概念。指针是C++中一个非常强大的特性，它允许程序直接访问和操作内存地址。而关键字则是C++语言预留的、具有特殊含义的单词，它们不能被用作变量名、函数名等标识符。下面我将分别解释指针在数据结构中的应用，以及几个与数据结构紧密相关的C++关键字。

1. 指针

指针在数据结构中扮演着至关重要的角色。它们允许我们动态地创建和操作数据结构，如链表、树和图等。通过使用指针，我们可以构建出复杂的数据结构，这些结构能够高效地存储和访问数据。

链表

在链表中，每个节点都包含数据和指向下一个节点的指针。这些指针允许我们遍历链表，并在需要时插入或删除节点。

struct ListNode {

int val;

ListNode* next;

ListNode(int x) : val(x), next(nullptr) { }

};

树

在树中，每个节点通常包含数据和指向其子节点的指针。这些指针允许我们访问树中的任意节点，并执行诸如搜索、插入和删除等操作。

struct TreeNode {

int val;

TreeNode* left;

TreeNode* right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }

};

2. 关键字

class 和 struct

class 和 struct 关键字用于定义类。在C++中，类和结构体非常相似，但默认情况下，类的成员是私有的（private），而结构体的成员是公共的（public）。然而，这种差异可以通过显式指定成员访问修饰符来覆盖。类和结构体都可用于定义复杂的数据结构。

new 和 delete

new 和 delete 关键字用于在堆上动态地分配和释放内存。这对于创建需要动态大小的数据结构（如动态数组、链表等）非常有用。

private、protected 和 public

这些关键字用于指定类成员的访问级别。在定义类时，它们决定了哪些成员可以从类的外部访问。这对于封装和隐藏数据结构的内部实现细节非常重要。

static

static 关键字在类中有多种用途，包括声明静态成员变量和静态成员函数。静态成员变量在类的所有对象之间共享，而静态成员函数则不能直接访问类的非静态成员。

template

template 关键字用于定义模板类、模板函数等。模板是C++泛型编程的基础，允许我们编写与类型无关的代码。这对于创建可重用且类型安全的数据结构非常有用。

typename

typename 关键字用于在模板定义中指示紧随其后的标识符是一个类型。这在模板编程中尤其有用，因为它可以帮助编译器区分类型名和变量名。

四、相关链接

Visual Studio Code下载地址Sublime Text下载地址「C++系列」C++简介、应用领域「C++系列」C++ 基本语法「C++系列」C++ 数据类型「C++系列」C++ 变量类型「C++系列」C++ 变量作用域「C++系列」C++ 常量知识点-细致讲解「C++系列」C++ 修饰符类型「C++系列」一篇文章说透【存储类】「C++系列」一篇文章讲透【运算符】「C++系列」循环「C++系列」判断「C++系列」函数/内置函数「C++系列」数字/随机数「C++系列」数组「C++系列」字符串「C++系列」指针「C++系列」引用「C++系列」日期/时间「C++系列」输入/输出