> For the complete documentation index, see [llms.txt](https://cccs.viyi.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cccs.viyi.cc/2-cheng-xu-she-ji/2.5-shu-ju-jie-gou-data-structures.md).

# 2.5 数据结构（Data Structures）

数据结构是用于表示算法所处理的数据在内存中存储的格式，当数据是结构化的，会更便于读取。

不同的数据结构有不同的特性，适用于不同的场景,正确选择数据结构会让工作更为简单。

大多数编程语言自带了预先做好的数据结构，比如 C++ 中的「标准模板库」（Standard Template Library）和 Java 中的「Java 类库」（Java Class Library）。

## 2.5.1 数组（Array）

### 数组

数组又名列表（list）或是向量（Vector），其连续存储在内存中，可存储多个值。

数组中不同值使用下标（index）区分，下标从 0 开始，使用方括号 \[ ] 表示所访问数组的数值。e.g 数组 j 的第一个元素为 j\[0]，第三个元素为 j\[2]。

本质上是通过计算第一个元素地址的**偏移量**，来得到数组中其他元素的地址。注意区分数组中第 5 个数字和数组中下标为 5 的数，前者下标为 4，后者实际为第六个数。

数组用途广泛，几乎所有的编程语言都自带了很多函数来处理数据，比如数组排序函数。

### 字符串

字符串（string）是由字母、数字、标点等组成的数组，以二进制值 \0 （null）结尾。处理字符串的常见函数有 strcat，其接受两个数组，将第二个放在第一个结尾处。

### 矩阵

数组仅能操作一维数据，二维及以上数据需要使用**矩阵（Matrix）**。以二维矩阵为例，取值需要 2 个下标，如 j\[2]\[1] :

![矩阵](/files/lHggkm7L1tqN6NTqDB5E)

## 2.5.2 结构体（struct）

结构体是指将几个逻辑上有关系的变量打包在一起的结构，比如将银行卡和余额打包在一个称为一个结构体放入数组中。

但数组创建时则大小固定，无法动态增加，同时其按序排列，在中间插入某值需移动后续诸多值，着实不便。因而可以使用结构体建立新的数据结构消除相关限制。

## 2.5.3 链表

通常采用名为 node 的结构体构建，节点（node）是变量（variable）和指针（pointer）构成的结构体，指针是指向一个内存地址的特殊变量。

![node](/files/jgdkDiEmgdbZxxCL3Kun)

### 单链表（linked list）

多个节点可以组成链表（linked list），通过链表中的每个节点指向下一个节点来实现灵活性。下图所示为「循环链表」（circular linked），若最后一个指针为 0(null)，则为非循环列表。

链表的大小可以动态增减，插入也比数组更加容易，只需改变指针即可（如下图）。在链表中，重新排序、两端缩减、分割以及倒序等操作也很容易进行。

![链表插入](/files/2JTRPeltqkkpBGQRB2MB)

### 队列（queue）

一种可以使用链表构建的复杂数据结构，采用「先进先出」（First-In First-Out, FIFO）的原则。

处理完一个数据则可以其「出队」（dequeue），将数据加入队列则称为「入队」（enqueue）。入队需要遍历整个链表直至结尾，然后将原先结尾节点的指针指向要加入的节点。

### 栈（stacks）

栈是一种「后进先出」（Last-In First-Out, LIFO）的数据结构，类似于放羽毛球进筒里。栈中数据的出入称为「进栈」（push）和「出栈」（pop）。

## 2.5.4 树（tree）

在 node 的基础上再新增一个指针可以构造出树：

![树的结构体](/files/jgYJcRbzqBDkcMqkTL7A)

抽象来看，可以将最高的节点称为「根节点」（root），节点下的所有节点称为「子节点」（children），任何子节点的直属上层节点称为「父节点」（parent node），没有任何子节点的节点（i.e. 树结束的地方）叫做「叶节点」（leaf）。

![树](/files/Bds1A9D7ozUUoeOLptXS)

上图这种每个节点最多只有两个节点的树称为「二叉树」（binary tree），这是一种特殊的树。树的节点个数是任意的，甚至我们可以在 node 中使用链表来存储所有的子节点。

树的特性是从根到叶是单向进行，而非循环。若数据随意连接，则构成 2.4.4 节中提过的图（graph），图的指向任意，可以使用多个指针的 node 来表示。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cccs.viyi.cc/2-cheng-xu-she-ji/2.5-shu-ju-jie-gou-data-structures.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.