-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathdate-structure.html
287 lines (287 loc) · 70.7 KB
/
date-structure.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0zdB.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8491109c4ae2ac88bbf9659a4f6d5ed2.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/Y0xvg.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/470d00578173666b5183f4631e51a421.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg" as="image" fetchpriority="high"><link rel="canonical" href="https://jiankychen.github.io/date-structure"><title>数据结构简介</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">数据结构简介</h1><div class="meta"><span class="item" title="创建时间：2022-03-26 22:28:41"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-03-26T22:28:41+08:00">2022-03-26</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>9.1k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>8 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0zdB.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8491109c4ae2ac88bbf9659a4f6d5ed2.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/Y0xvg.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/470d00578173666b5183f4631e51a421.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Data-Structure/" itemprop="item" rel="index" title="分类于Data Structure"><span itemprop="name">Data Structure<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/date-structure.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><p>数据结构是为实现对计算机数据有效使用的各种数据组织形式，旨在降低各种算法计算的时间与空间复杂度</p>
<p>常见的数据结构可分为 <em>线性数据结构</em> 与 <em>非线性数据结构</em> ，具体包括：<strong>数组</strong> 、 <strong>链表</strong> 、 <strong>栈</strong> 、 <strong>队列</strong> 、 <strong>树</strong> 、 <strong>图</strong> 、 <strong>散列表</strong> 、 <strong>堆</strong></p>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/1.webp" alt=""></p>
<blockquote>
<p>不要对数据结构的使用浅尝辄止，而要深挖起内部原理</p>
</blockquote>
<h2 id="数组"><a class="anchor" href="#数组">#</a> 数组</h2>
<p>数组是将相同类型的元素存储于 <strong>连续内存空间</strong> 的数据结构，其长度不可变。构建数组时需要在初始化时给定长度，例如：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> array<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre></pre></td></tr><tr><td data-num="3"></td><td><pre><span class="token keyword">int</span> array<span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p><strong>可变数组</strong> （<strong>标准库类型 <code>vector</code> </strong> ）是经常使用的数据结构，其基于数组和扩容机制实现，相比普通数组更加灵活。常用操作有：<strong>访问元素</strong>（下标运算符、范围 <code>for</code> 、迭代器）、<strong>添加元素</strong>（成员函数 <code>push_back</code> ）、<strong>删除元素</strong>（成员函数 <code>erase</code> 和 <code>remove</code> ），例如：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> array <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">2</span>，<span class="token number">3</span>，<span class="token number">1</span>，<span class="token number">0</span>，<span class="token number">2</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre></pre></td></tr><tr><td data-num="3"></td><td><pre>array<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 添加元素 2 到末尾</span></pre></td></tr><tr><td data-num="4"></td><td><pre></pre></td></tr><tr><td data-num="5"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token double-colon punctuation">::</span>iterator it<span class="token punctuation">;</span> <span class="token comment">// 迭代器</span></pre></td></tr><tr><td data-num="6"></td><td><pre>it <span class="token operator">=</span> array<span class="token punctuation">.</span><span class="token function">begin</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token number">4</span><span class="token punctuation">;</span> <span class="token comment">//it 指向第 5 个元素</span></pre></td></tr><tr><td data-num="7"></td><td><pre>array<span class="token punctuation">.</span><span class="token function">erase</span><span class="token punctuation">(</span>it<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 删除 it 指向的元素</span></pre></td></tr></tbody></table></figure><p>详情可见于<br>
<a href="https://jiankychen.github.io/posts/cddca394/"> C++：标准库类型 vector</a><br>
<a target="_blank" rel="noopener" href="https://blog.csdn.net/JIAN_ZANG1125/article/details/120642243?spm=1001.2101.3001.6650.1&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-1.pc_relevant_aa&utm_relevant_index=2">vector 删除元素的方法</a></p>
<h2 id="链表"><a class="anchor" href="#链表">#</a> 链表</h2>
<p>链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是 <strong>非连续</strong> 的</p>
<p>每一个节点由两部分组成，一个是数据域，另一个是指针域</p>
<p>链表的入口节点称为头节点，即， <code>head</code></p>
<h3 id="链表的类型"><a class="anchor" href="#链表的类型">#</a> 链表的类型</h3>
<h4 id="单链表"><a class="anchor" href="#单链表">#</a> 单链表</h4>
<p>单链表中，每个节点的指针域存放的是指向下一个节点的指针，最后一个节点的指针域指向 <code>null</code></p>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/2-1.webp" alt=""></p>
<p>单链表的节点对象具有两个成员变量：<strong>值</strong> <code>val</code> 、 <strong>后继节点指针</strong> <code>next</code></p>
<p>单链表中的节点只能指向节点的下一个节点</p>
<h4 id="双链表"><a class="anchor" href="#双链表">#</a> 双链表</h4>
<p>双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点</p>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/2-2.webp" alt=""></p>
<p>双链表既可以向前查询，又可以向后查询</p>
<h4 id="循环链表"><a class="anchor" href="#循环链表">#</a> 循环链表</h4>
<p>链表首尾相连</p>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/2-3.webp" alt=""></p>
<p>循环链表可以用来解决约瑟夫环问题</p>
<h3 id="链表的存储方式"><a class="anchor" href="#链表的存储方式">#</a> 链表的存储方式</h3>
<p>链表在内存空间中的分布并不是连续的，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理</p>
<p>链表通过指针域的指针来链接在内存中的各个节点</p>
<h3 id="链表的定义"><a class="anchor" href="#链表的定义">#</a> 链表的定义</h3>
<p>以单链表为例，定义链表的节点：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 单链表</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">struct</span> <span class="token class-name">ListNode</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="3"></td><td><pre> <span class="token keyword">int</span> val<span class="token punctuation">;</span> <span class="token comment">// 节点值</span></pre></td></tr><tr><td data-num="4"></td><td><pre> ListNode <span class="token operator">*</span>next<span class="token punctuation">;</span> <span class="token comment">// 后继节点指针</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">val</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">next</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span> <span class="token comment">// 节点的构造函数</span></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre></pre></td></tr><tr><td data-num="8"></td><td><pre></pre></td></tr><tr><td data-num="9"></td><td><pre><span class="token comment">// // Definition for singly-linked list.</span></pre></td></tr><tr><td data-num="10"></td><td><pre><span class="token comment">// struct ListNode {</span></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token comment">// int val;</span></pre></td></tr><tr><td data-num="12"></td><td><pre><span class="token comment">// ListNode *next;</span></pre></td></tr><tr><td data-num="13"></td><td><pre><span class="token comment">// ListNode() : val(0), next(nullptr) {}</span></pre></td></tr><tr><td data-num="14"></td><td><pre><span class="token comment">// ListNode(int x) : val(x), next(nullptr) {}</span></pre></td></tr><tr><td data-num="15"></td><td><pre><span class="token comment">// ListNode(int x, ListNode *next) : val(x), next(next) {}</span></pre></td></tr><tr><td data-num="16"></td><td><pre><span class="token comment">// };</span></pre></td></tr></tbody></table></figure><p>C++ 默认会生成一个构造函数，但是这个构造函数不会初始化任何成员变量</p>
<p>如果不自行定义构造函数，而仅仅使用默认构造函数，那么在初始化的时候就不能直接给变量赋值</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 自行定义构造函数时节点的初始化操作</span></pre></td></tr><tr><td data-num="2"></td><td><pre>ListNode<span class="token operator">*</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre><span class="token comment">// 使用默认构造函数时节点的初始化操作</span></pre></td></tr><tr><td data-num="5"></td><td><pre>ListNode<span class="token operator">*</span> head <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>head<span class="token operator">-></span>val <span class="token operator">=</span> <span class="token number">5</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>建立链表需要实例化每个节点，并构建各节点的引用指向</p>
<p>注：需要用箭头运算符（ <code>-></code> ），其含义为 解引用 + 成员访问</p>
<h3 id="链表的操作"><a class="anchor" href="#链表的操作">#</a> 链表的操作</h3>
<h4 id="删除节点"><a class="anchor" href="#删除节点">#</a> 删除节点</h4>
<p>以删除 D 节点为例：只要将 C 节点的 <code>next</code> 指针 指向 E 节点即可</p>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/2-4.webp" alt="删除节点"></p>
<p>注意，D 节点依然留在内存中，只不过是没有在这个链表里而已。可以再手动释放这个 D 节点的这块内存</p>
<h4 id="插入节点"><a class="anchor" href="#插入节点">#</a> 插入节点</h4>
<p>以插入 F 节点为例：将 C 节点的 <code>next</code> 指针指向 F 节点，并将 F 节点的 <code>next</code> 指针指向 D 节点<br>
<img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/2-5.webp" alt="插入节点"></p>
<p>可以看出链表的增添和删除都是 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span> 操作，也不会影响到其他节点</p>
<p>但是要注意，若要删除第五个节点，需要从头节点查找到第四个节点通过 <code>next</code> 指针进行删除操作，查找的时间复杂度是 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></p>
<h3 id="性能分析"><a class="anchor" href="#性能分析">#</a> 性能分析</h3>
<p>链表与数组的特性对比：</p>
<table>
<thead>
<tr>
<th style="text-align:center"></th>
<th style="text-align:center">插入 / 删除操作的时间复杂度</th>
<th style="text-align:center">查询操作的时间复杂度</th>
<th style="text-align:center">适用场景</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">数组</td>
<td style="text-align:center"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></td>
<td style="text-align:center"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></td>
<td style="text-align:center">数据量固定，频繁查询，较少增删</td>
</tr>
<tr>
<td style="text-align:center">链表</td>
<td style="text-align:center"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord">1</span><span class="mclose">)</span></span></span></span></td>
<td style="text-align:center"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></td>
<td style="text-align:center">数据量不固定，频繁增删，较少查询</td>
</tr>
</tbody>
</table>
<p>数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组</p>
<p>链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景</p>
<p><a target="_blank" rel="noopener" href="https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E5%8D%95%E9%93%BE%E8%A1%A8">代码随想录：链表理论基础</a></p>
<h2 id="stl"><a class="anchor" href="#stl">#</a> STL</h2>
<p>STL 是 Standard Template Library 的简称，即，标准模板库</p>
<p>STL 可分为容器（containers）、迭代器（iterators）、空间配置器（allocator）、配接器（adapters）、算法（algorithms）、仿函数（functors）六个部分</p>
<p>在 C++ 标准中，STL 被组织为下面的 13 个头文件: <code><algorithm></code> 、 <code><deque></code> 、 <code><functional></code> 、 <code><iterator></code> 、 <code><vector></code> 、 <code><list></code> 、 <code><map></code> 、 <code><memory></code> 、 <code><numeric></code> 、 <code><queue></code> 、 <code><set></code> 、 <code><stack></code> 和 <code><utility></code></p>
<p>STL 的版本很多，其中，三个最为普遍的 STL 版本：</p>
<ul>
<li>
<p>HP STL 是 C++ STL 的第一个实现版本，而且开放源代码。其他版本的 C++ STL 一般是以 HP STL 为蓝本实现出来的。不过，现在已经很少直接使用此版本的 STL 了</p>
</li>
<li>
<p>PJ STL（全称为 P.J. Plauger STL）由 P.J.Plauger 参照 HP STL 实现出来的，是 HP STL 的一个继承版本。PJ STL 被 Visual C++ 编译器所采用，但不是开源的</p>
</li>
<li>
<p>SGI STL 也是 HP STL 的一个继承版本，和 HP STL 一样，SGI STL 也是开源的，其源代码的可读性可非常好。被 Linux 下的 C++ 编译器 GCC 所采用</p>
</li>
</ul>
<p>接下来介绍的 栈 和 队列 也是 SGI STL 里面的数据结构</p>
<h2 id="栈"><a class="anchor" href="#栈">#</a> 栈</h2>
<p>栈（stack）是一种具有 <strong>后进先出</strong>（last in first out）特点的抽象数据结构，使用前需要引入 <code>stack</code> 头文件</p>
<p>栈不提供迭代器，也不允许遍历</p>
<p>栈依赖于底层容器完成所有工作，对外提供统一的接口。其中，底层容器是可插拔的，即，我们可以控制使用何种容器来实现栈的功能</p>
<p>因此，在 STL 中，栈往往不被归类为 容器 ，而被归类为 容器适配器（container adapter）</p>
<p>栈的底层实现可以是 <code>vector</code> ， <code>deque</code> ， <code>list</code> ，主要使用 数组 和 链表 的底层实现。<strong>对于 SGI STL ，如果不指定，则默认使用 <code>deque</code> 作为底层容器</strong></p>
<blockquote>
<p><code>deque</code> 是一个双向队列，，只要封住一端、开通另一端，即可实现栈的逻辑</p>
</blockquote>
<p>我们可以指定 vector 为栈的底层实现，其初始化语句为：</p>
<pre><code>std::stack<int, std::vector<int>> stk; // 使用 vector 为底层容器的栈
</code></pre>
<p>栈常用的成员函数：</p>
<ul>
<li>
<p><code>push()</code> ：在最顶层加入元素</p>
</li>
<li>
<p><code>pop()</code> ：移除顶层元素</p>
</li>
<li>
<p><code>top()</code> ：返回最顶层数据的值，但不移除它</p>
</li>
<li>
<p><code>empty()</code> ：判断栈是否为空</p>
</li>
<li>
<p><code>size()</code> ：返回栈的大小</p>
</li>
</ul>
<p>须注意：</p>
<ul>
<li>
<p><strong> <code>pop()</code> 没有返回值</strong></p>
</li>
<li>
<p><strong> <code>top()</code> 具有返回值，并且，可以通过 <code>top()</code> 修改栈顶元素值，即， <code>top()</code> 可以作为左值</strong></p>
</li>
</ul>
<p>参考：<a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/stack/stack/?kw=stack">cplusplus：std::stack</a></p>
<p>如下图所示，通过 <strong>入栈</strong> <code>push()</code> ，<strong>出栈</strong> <code>pop()</code> ，展示了栈的先入后出特性</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>stack<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> stk<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 1 入栈</span></pre></td></tr><tr><td data-num="3"></td><td><pre>stk<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 2 入栈</span></pre></td></tr><tr><td data-num="4"></td><td><pre>stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 2 出栈</span></pre></td></tr><tr><td data-num="5"></td><td><pre>stk<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 1 出栈</span></pre></td></tr></tbody></table></figure><p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/3.webp" alt=""></p>
<h2 id="队列"><a class="anchor" href="#队列">#</a> 队列</h2>
<p>队列（queue）是一种具有 <strong>先进先出</strong>（first in first out）特点的抽象数据结构，使用前需先引入 <code>queue</code> 头文件</p>
<p>队列不提供迭代器，不允许有遍历行为</p>
<p>STL 队列 也不被归类为 容器 ，而被归类为 容器适配器（container adapter）</p>
<p>队列的底层实现可以是 <code>deque</code> 和 <code>list</code> 。<strong>对于 SGI STL ，如果不指定，则默认使用 <code>deque</code> 作为底层容器</strong></p>
<p>可以指定 <code>list</code> 为栈的底层实现，其初始化语句为：</p>
<pre><code>std::queue<int, std::list<int>> que; // 使用 list 为底层容器
</code></pre>
<p>队列常用的成员函数：</p>
<ul>
<li>
<p><code>push()</code> ：在队尾插入元素</p>
</li>
<li>
<p><code>pop()</code> ：移除队首元素</p>
</li>
<li>
<p><code>front()</code> ：返回队首元素</p>
</li>
<li>
<p><code>back()</code> ：返回队尾元素</p>
</li>
<li>
<p><code>empty()</code> ：判断队列是否为空</p>
</li>
<li>
<p><code>size()</code> ：返回队列中元素的数量</p>
</li>
</ul>
<p>注意：</p>
<ul>
<li><strong> <code>pop()</code> 没有返回值</strong></li>
<li><strong> <code>front()</code> 具有返回值，并且，可以通过 <code>front()</code> 修改队首元素值，即， <code>front()</code> 可以作为左值</strong></li>
</ul>
<p><a target="_blank" rel="noopener" href="http://www.cplusplus.com/reference/queue/queue/">cplusplus：std::queue</a></p>
<p>如下图所示，通过常用操作 <strong>入队</strong> <code>push()</code> ，<strong>出队</strong> <code>pop()</code> ，展示了队列的先入先出特性</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> que<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 1 入队</span></pre></td></tr><tr><td data-num="3"></td><td><pre>que<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 元素 2 入队</span></pre></td></tr><tr><td data-num="4"></td><td><pre>que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 出队 -> 元素 1</span></pre></td></tr><tr><td data-num="5"></td><td><pre>que<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 出队 -> 元素 2</span></pre></td></tr></tbody></table></figure><p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/4.webp" alt=""></p>
<p>此外， <code>queue</code> 还提供了一些运算符。较为常用的是：使用赋值运算符 <code>=</code> 为 <code>queue</code> 赋值</p>
<p>例如</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre>queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> q1<span class="token punctuation">,</span> q2<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>q1<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre>q2 <span class="token operator">=</span> q1<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>cout <span class="token operator"><<</span> q2<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator"><<</span> endl<span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><h3 id="双端队列"><a class="anchor" href="#双端队列">#</a> 双端队列</h3>
<h3 id="循环队列"><a class="anchor" href="#循环队列">#</a> 循环队列</h3>
<p>可参考 <a target="_blank" rel="noopener" href="https://oi-wiki.org/ds/queue/">OI Wiki：队列</a></p>
<h2 id="树"><a class="anchor" href="#树">#</a> 树</h2>
<p>树是一种非线性数据结构，根据子节点数量可分为 <strong>二叉树</strong> 和 <strong>多叉树</strong> ，最顶层的节点称为 <strong>根节点</strong> <code>root</code></p>
<p>以二叉树为例，每个节点包含三个成员变量：<strong>值</strong> <code>val</code> 、<strong>左子节点</strong> <code>left</code> 、<strong>右子节点</strong> <code>right</code></p>
<p>二叉树节点的定义：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">struct</span> <span class="token class-name">TreeNode</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> val<span class="token punctuation">;</span> <span class="token comment">// 节点值</span></pre></td></tr><tr><td data-num="3"></td><td><pre> TreeNode <span class="token operator">*</span>left<span class="token punctuation">;</span> <span class="token comment">// 左子节点</span></pre></td></tr><tr><td data-num="4"></td><td><pre> TreeNode <span class="token operator">*</span>right<span class="token punctuation">;</span> <span class="token comment">// 右子节点</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">val</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">left</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">right</span><span class="token punctuation">(</span><span class="token constant">NULL</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>访问成员变量时需要用箭头运算符（ <code>-></code> ），其含义为 解引用 + 成员访问</p>
<p>建立二叉树需要实例化每个节点，并构建各节点的子节点指针</p>
<p>例如：</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 初始化节点</span></pre></td></tr><tr><td data-num="2"></td><td><pre>TreeNode <span class="token operator">*</span>n1 <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// 根节点 root</span></pre></td></tr><tr><td data-num="3"></td><td><pre>TreeNode <span class="token operator">*</span>n2 <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre>TreeNode <span class="token operator">*</span>n3 <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre></pre></td></tr><tr><td data-num="6"></td><td><pre><span class="token comment">// 构建子节点指针</span></pre></td></tr><tr><td data-num="7"></td><td><pre>n1<span class="token operator">-></span>left <span class="token operator">=</span> n2<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>n1<span class="token operator">-></span>right <span class="token operator">=</span> n3<span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>详情可见 <a href="https://jiankychen.github.io/posts/e85d694a">二叉树</a></p>
<h2 id="堆"><a class="anchor" href="#堆">#</a> 堆</h2>
<p>堆是一种基于 <strong>完全二叉树</strong> 的数据结构，可使用数组实现</p>
<p>以堆为原理的排序算法称为 <strong>堆排序</strong> ，基于堆实现的数据结构为 <strong>优先级队列</strong></p>
<p><strong>优先级队列</strong> ：结点之间的关系是由结点的优先级决定的，而不是由入队的先后次序决定。优先级高的先出队，优先级低的后出队</p>
<p>堆分为 <strong>最小化堆</strong> 和 <strong>最大化堆</strong></p>
<ul>
<li>最大化堆 ：任意节点的值小于等于其父节点的值（根节点最大）</li>
<li>最小化堆 ：任意节点的值大于等于其父节点的值（根节点最小）</li>
</ul>
<p>通过使用 <strong>优先级队列</strong> 的 <strong>压入</strong> <code>push()</code> 和 <strong>弹出</strong> <code>pop()</code> 操作，即可完成 <strong>堆排序</strong></p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token comment">// 初始化最小化堆</span></pre></td></tr><tr><td data-num="2"></td><td><pre>priority_queue<span class="token operator"><</span><span class="token keyword">int</span><span class="token punctuation">,</span> vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span><span class="token punctuation">,</span> greater<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> heap<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre><span class="token comment">// 元素入堆</span></pre></td></tr><tr><td data-num="5"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">push</span><span class="token punctuation">(</span><span class="token number">8</span><span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre></pre></td></tr><tr><td data-num="11"></td><td><pre><span class="token comment">// 元素出堆（从小到大）</span></pre></td></tr><tr><td data-num="12"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// -> 1</span></pre></td></tr><tr><td data-num="13"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// -> 2</span></pre></td></tr><tr><td data-num="14"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// -> 4</span></pre></td></tr><tr><td data-num="15"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// -> 6</span></pre></td></tr><tr><td data-num="16"></td><td><pre>heap<span class="token punctuation">.</span><span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">// -> 8</span></pre></td></tr></tbody></table></figure><p>详情可见 <a href="https://jiankychen.github.io/posts/a21107fc">优先级队列</a></p>
<h2 id="哈希表"><a class="anchor" href="#哈希表">#</a> 哈希表</h2>
<p>哈希表（Hash table ，也被称为散列表）是根据关键码的值而直接进行访问的数据结构</p>
<p>哈希表可以近似理解成数组，哈希表中的关键码就是数组的索引下标，通过下标可以直接访问数组的元素</p>
<p><strong>一般哈希表都是用来快速判断一个元素是否出现集合当中</strong></p>
<h3 id="哈希函数"><a class="anchor" href="#哈希函数">#</a> 哈希函数</h3>
<p>哈希函数（hash function）以关键码的值为参数，将关键码映射为哈希表的索引，即，函数的值即为存储元素的下标</p>
<h3 id="哈希碰撞"><a class="anchor" href="#哈希碰撞">#</a> 哈希碰撞</h3>
<p>哈希碰撞是指：不同的关键码映射到同一个地址</p>
<p>两种解决方案：</p>
<ul>
<li>线性探测法：当散列发生冲突时，探测下一个单元，直到发现一个空单元，于是元素将存储在该空单元</li>
<li>拉链法：将碰撞的节点组成一个链表</li>
</ul>
<h3 id="常见的哈希结构"><a class="anchor" href="#常见的哈希结构">#</a> 常见的哈希结构</h3>
<p>三种哈希结构</p>
<ul>
<li>数组</li>
<li>set （集合）</li>
<li>map （映射）</li>
</ul>
<p>详情可见 <a href="https://jiankychen.github.io/posts/850f2080">哈希表</a></p>
<h2 id="图"><a class="anchor" href="#图">#</a> 图</h2>
<p>图是一种非线性结构，由 <strong>顶点</strong> <code>vertex</code> 和 <strong>边</strong> <code>edge</code> 组成</p>
<p>根据边是否区分方向，图可分为 <strong>有向图</strong> 和 <strong>无向图</strong> ， 这里以无向图为例进行介绍</p>
<p>如下图所示，此无向图的 顶点 和 边 集合分别为</p>
<ul>
<li>
<p>顶点集合： <code>vertices = {1, 2, 3, 4, 5}</code></p>
</li>
<li>
<p>边集合： <code>edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}</code></p>
</li>
</ul>
<p><img loading="lazy" data-src="AL-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%80%E4%BB%8B/6.webp" alt=""></p>
<p>表示图的方法通常有两种：</p>
<ol>
<li>
<p>邻接矩阵 ：使用数组 <code>vertices</code> 存储顶点，邻接矩阵 <code>edges</code> 存储边。其中， <code>edges[i][j]</code> 表示节点 <code>vertices[i]</code> 和节点 <code>vertices[j]</code> 之间是否有边</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> vertices<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre><span class="token keyword">int</span> edges<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator"><</span><span class="token operator">!</span><span class="token operator">--</span>swig<span class="token number">0</span><span class="token operator">--</span><span class="token operator">></span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure></li>
<li>
<p>邻接表 ：使用数组 <code>vertices</code> 存储顶点，邻接表 <code>edges</code> 存储边。其中， <code>edges</code> 是一个二维容器，第一维的 i 代表顶点 <code>vertices[i]</code> ，第二维 <code>edges[i]</code> 存储顶点 <code>vertices[i]</code> 对应的边集合，例如， <code>edges[0] = [1,2,3,4]</code> 表示 <code>vertices[0]</code> 的边集合为 <code>[1,2,3,4]</code></p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">int</span> vertices<span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="2"></td><td><pre>vector<span class="token operator"><</span>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">>></span> edges<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre></pre></td></tr><tr><td data-num="4"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> edge_1 <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> edge_2 <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="6"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> edge_3 <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="7"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> edge_4 <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="8"></td><td><pre>vector<span class="token operator"><</span><span class="token keyword">int</span><span class="token operator">></span> edge_5 <span class="token operator">=</span> <span class="token punctuation">{</span><span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="9"></td><td><pre>edges<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>edge_1<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="10"></td><td><pre>edges<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>edge_2<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="11"></td><td><pre>edges<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>edge_3<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="12"></td><td><pre>edges<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>edge_4<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr><tr><td data-num="13"></td><td><pre>edges<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span>edge_5<span class="token punctuation">)</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure></li>
</ol>
<blockquote>
<p>邻接矩阵的大小只与节点数量有关，即 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mi>N</mi><mn>2</mn></msup></mrow><annotation encoding="application/x-tex">N^2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.10903em;">N</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span> ，其中 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>N</mi></mrow><annotation encoding="application/x-tex">N</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.10903em;">N</span></span></span></span> 为节点数量</p>
<p>当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费（此时邻接矩阵为稀疏矩阵）</p>
<p>因此，<strong>邻接表</strong> 适合存储 <strong>顶点较多、边较少</strong> 的 稀疏图 ，<strong>邻接矩阵</strong> 适合存储 <strong>顶点较少、边较多</strong> 的 稠密图</p>
</blockquote>
<p>详情可见 <a href="https://jiankychen.github.io/posts/ee040603">图</a></p>
<p>参考资料：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/leetbook/read/illustration-of-algorithm/50e446/">力扣：图解算法数据结构</a></li>
<li><a target="_blank" rel="noopener" href="http://www.cplusplus.com/">cplusplus</a></li>
</ul>
</div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 23:07:42" itemprop="dateModified" datetime="2024-06-08T23:07:42+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/date-structure.html" title="数据结构简介">https://jiankychen.github.io/date-structure.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/leetcode-vectors.html" rel="prev" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/65d0bfef68566882ce0560cab2e87921.jpg" title="LeetCode - 数组专题"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>Coding</span><h3>LeetCode - 数组专题</h3></a></div><div class="item right"><a href="/sort-algorithm.html" rel="next" itemprop="url" data-background-image="https://i.imgtg.com/2023/03/09/Y0hOs.jpg" title="排序"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>排序</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E7%BB%84"><span class="toc-number">1.</span> <span class="toc-text"> 数组</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8"><span class="toc-number">2.</span> <span class="toc-text"> 链表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E7%B1%BB%E5%9E%8B"><span class="toc-number">2.1.</span> <span class="toc-text"> 链表的类型</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-number">2.1.1.</span> <span class="toc-text"> 单链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%8F%8C%E9%93%BE%E8%A1%A8"><span class="toc-number">2.1.2.</span> <span class="toc-text"> 双链表</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8"><span class="toc-number">2.1.3.</span> <span class="toc-text"> 循环链表</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AD%98%E5%82%A8%E6%96%B9%E5%BC%8F"><span class="toc-number">2.2.</span> <span class="toc-text"> 链表的存储方式</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-number">2.3.</span> <span class="toc-text"> 链表的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%93%BE%E8%A1%A8%E7%9A%84%E6%93%8D%E4%BD%9C"><span class="toc-number">2.4.</span> <span class="toc-text"> 链表的操作</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%88%A0%E9%99%A4%E8%8A%82%E7%82%B9"><span class="toc-number">2.4.1.</span> <span class="toc-text"> 删除节点</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E8%8A%82%E7%82%B9"><span class="toc-number">2.4.2.</span> <span class="toc-text"> 插入节点</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90"><span class="toc-number">2.5.</span> <span class="toc-text"> 性能分析</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#stl"><span class="toc-number">3.</span> <span class="toc-text"> STL</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%88"><span class="toc-number">4.</span> <span class="toc-text"> 栈</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%98%9F%E5%88%97"><span class="toc-number">5.</span> <span class="toc-text"> 队列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E7%AB%AF%E9%98%9F%E5%88%97"><span class="toc-number">5.1.</span> <span class="toc-text"> 双端队列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BE%AA%E7%8E%AF%E9%98%9F%E5%88%97"><span class="toc-number">5.2.</span> <span class="toc-text"> 循环队列</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A0%91"><span class="toc-number">6.</span> <span class="toc-text"> 树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A0%86"><span class="toc-number">7.</span> <span class="toc-text"> 堆</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8"><span class="toc-number">8.</span> <span class="toc-text"> 哈希表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E5%87%BD%E6%95%B0"><span class="toc-number">8.1.</span> <span class="toc-text"> 哈希函数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E7%A2%B0%E6%92%9E"><span class="toc-number">8.2.</span> <span class="toc-text"> 哈希碰撞</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%B8%E8%A7%81%E7%9A%84%E5%93%88%E5%B8%8C%E7%BB%93%E6%9E%84"><span class="toc-number">8.3.</span> <span class="toc-text"> 常见的哈希结构</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%BE"><span class="toc-number">9.</span> <span class="toc-text"> 图</span></a></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/binary-search.html" rel="bookmark" title="二分查找">二分查找</a></li><li><a href="/binary-tree.html" rel="bookmark" title="二叉树">二叉树</a></li><li><a href="/algorithm-complexity.html" rel="bookmark" title="算法复杂度">算法复杂度</a></li><li class="active"><a href="/date-structure.html" rel="bookmark" title="数据结构简介">数据结构简介</a></li><li><a href="/sort-algorithm.html" rel="bookmark" title="排序">排序</a></li><li><a href="/recursive.html" rel="bookmark" title="递推与递归">递推与递归</a></li><li><a href="/dynamic-programming.html" rel="bookmark" title="动态规划">动态规划</a></li><li><a href="/priority-queue.html" rel="bookmark" title="优先级队列">优先级队列</a></li><li><a href="/hash-table.html" rel="bookmark" title="哈希表">哈希表</a></li><li><a href="/graphics-theory.html" rel="bookmark" title="图">图</a></li><li><a href="/KMP.html" rel="bookmark" title="KMP 算法">KMP 算法</a></li><li><a href="/traverse.html" rel="bookmark" title="回溯">回溯</a></li><li><a href="/Dijkstra.html" rel="bookmark" title="Dijkstra">Dijkstra</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/sort-algorithm.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/leetcode-vectors.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a></div><span><a href="/vscode-intro.html">vscode 使用</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-vectors.html">C++ 字符串、向量和数组</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-hashtable.html">LeetCode - 哈希表专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-dynamicprogramming.html">LeetCode - 动态规划专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-oop.html">Python 面向对象</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-modules.html">Python 异常、模块、包</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/binary-tree.html">二叉树</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-pandas.html">pandas 基础</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/traverse.html">回溯</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Tutorial/" title="分类于Tutorial">Tutorial</a><i class="ic i-angle-right"></i><a href="/categories/Tutorial/LaTeX/" title="分类于LaTeX">LaTeX</a></div><span><a href="/latex-citation.html">LaTeX：跨 tex 文件的交叉引用</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/date-structure`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>