-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
executable file
·336 lines (294 loc) · 19.9 KB
/
index.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
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
<!doctype html>
<html class="no-js" lang="en">
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>清风明月的笔记</title>
<meta name="description" content="">
<meta name="author" content="Ming">
<link rel="stylesheet" href="/theme/css/foundation.css" />
<link rel="stylesheet" href="/theme/css/normalize.css" />
<link rel="stylesheet" href="/theme/css/pygment/solarized-dark.css" />
<link rel="stylesheet" href="/theme/css/custom.css" />
<!-- Feeds -->
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$', '$'] ],
displayMath: [ ['$$', '$$']],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
},
messageStyle: "none",
"HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</head>
<body>
<div class="off-canvas-wrap" data-offcanvas>
<div class="inner-wrap">
<!-- mobile top bar to activate nav -->
<nav class="tab-bar show-for-small">
<section class="left-small">
<a class="left-off-canvas-toggle menu-icon" ><span></span></a>
</section>
<section class="middle tab-bar-section">
<h1 class="title">清风明月的笔记</h1>
</section>
</nav>
<!-- mobile side bar nav -->
<aside class="left-off-canvas-menu">
<ul class="off-canvas-list">
<li><a href="">Home</a></li>
<li ><a href="/pages/contact.html">Contact</a></li>
<li ><a href="/pages/about.html">About</a></li>
<li><label>Categories</label></li>
<li ><a href="/category/ji-he-suan-fa.html">几何算法</a></li>
<li ><a href="/category/suan-fa.html">算法</a></li>
<!--
<li><label>Links</label></li>
<li><a href="http://coolshell.cn">酷 壳</a></li>
<li><a href="http://blog.codingnow.com">云风的 BLOG</a></li>
<li><a href="http://www.ruanyifeng.com/blog">阮一峰的网络日志</a></li>
-->
<!--
<li><label>Social</label></li>
<li><a href="#"></a></li>
-->
</ul>
</aside>
<!-- top bar nav -->
<nav class="top-bar hide-for-small-only" data-topbar>
<ul class="title-area">
<li class="name">
<h1><a href="/">清风明月的笔记</a></h1>
</li>
</ul>
<section class="top-bar-section">
<ul class="left">
<li><a href="/">Home</a></li>
</ul>
<ul class="right">
····
<li><a href="/pages/contact.html">Contact</a></li>
····
<li><a href="/pages/about.html">About</a></li>
</ul>
</section>
</nav>
<!-- Main Page Content and Sidebar -->
<section class="main-section">
<div class="row main-content">
<!-- Main Page Content and Sidebar -->
<!-- Main Content -->
<div class="medium-9 small-12 columns" role="content">
<article>
<h3><a href="/rotating-calipers-get-min-rectangle.html">旋转卡壳求点集的最小面积外接矩形</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2017-03-12(星期日) 21:56 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/ji-he-suan-fa.html">几何算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/ji-he-suan-fa-suan-fa.html">几何算法,算法</a>, </h6>
<h4 id="_1"><strong> 旋转卡壳算法的历史 </strong></h4>
<p>先转摘一段网上关于旋转卡壳算法的历史</p>
<p>1978年, M.I. Shamos's Ph.D. 的论文"Computational Geometry"标志着计算机科学的这一领域的诞生。 当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法, 即根据多边形的一对点距离的最大值来确定。
后来直径演化为由一对对踵点对来确定。 Shamos提出了一个简单的 O(n) 时间的算法来确定一个凸 ...</p>
<p class="continue"><a href="/rotating-calipers-get-min-rectangle.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/graham-scan-get-convex.html">Graham扫描法求凸包</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2017-03-11(星期六) 18:42 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/ji-he-suan-fa.html">几何算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/ji-he-suan-fa-suan-fa.html">几何算法,算法</a>, </h6>
<p>凸包用不严谨的话来讲,给定二维平面上的点集,凸包就是将最外层的点连接起来构成的凸多边型,它能包含点集中所有的点。</p>
<p>如下图(图片来看网络):</p>
<p><img alt="图一" src="/images/grahamscan/grahamscan1.png"/></p>
<p>算法的主要方法是先排序,然后扫描。</p>
<h4 id="_1"><strong> 点集排序 </strong></h4>
<ol>
<li>选取基点。选择所有点中y坐标最小的点,如果多个点都是最小值,选x坐标最小的点。</li>
<li>剩下的点按与基点构成的向量进行排序。计算向量与x轴的夹角大小来排序,可以使用两个向量叉积来判断第二个向量在第一个向量的左边还是右边。只求向量z轴上的值来判断方向即可。</li>
</ol>
<p>代码如下</p>
<div class="highlight"><pre><span></span><span class="cm">/* </span>
<span class="cm"> * Name: getdist ...</span></pre></div>
<p class="continue"><a href="/graham-scan-get-convex.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/bplus-tree-algorithm-in-c.html">B+树的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-12-18(星期日) 21:36 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>B+树可以看作是B树的一种变形,通常用于数据库和操作系统的文件系统中。</p>
<p>B+树的定义基本与B树相同。区别如下。</p>
<ol>
<li>非叶子结点的子树指针与关键字个数相同</li>
<li>非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间)</li>
<li>为所有叶子结点增加一个链指针</li>
<li>所有关键字都在叶子结点出现</li>
</ol>
<p>插入删除操作与B树有些区别 ...</p>
<p class="continue"><a href="/bplus-tree-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/b-tree-algorithm-in-c.html">B树的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-12-11(星期日) 02:03 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>B树是2-3-4树的延伸,或者说2-3-4树是B树的一种情况。</p>
<p>所以B树的基本操作与2-3-4树相同。2-3-4树其实还是挺重要的一种数据结构,理解2-3-4树更理解了B树和红黑树。前两篇文章作2-3-4树分析时画过图,B树便不再画了,画图其实挺累的。</p>
<p>B树的查询,插入,删除的时间复杂度都是O(lgn)</p>
<p>B树的定义:</p>
<ol>
<li>每个节点最多有m个元素(m + 1个孩子)</li>
<li>每个非叶节点(除根节点)有最少m/2个元素 ...</li></ol>
<p class="continue"><a href="/b-tree-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/rb-tree-algorithm-in-c.html">红黑树的分析与C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-11-10(星期四) 21:14 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<h3 id="_1"><strong> 前言 </strong></h3>
<p>红黑树是比较复杂的一种平衡树结构。容易看得云里雾里,让人望而却步。或是强记下来,终究不能理解而很快忘记了。</p>
<p>感觉开始最让人困惑的就是平白无故就得出了一堆性质,然后根据性质很不明所以地推导各种奇怪的操作步骤。这样几乎不可能理解其中的含义。</p>
<p>这是一个充斥着迷茫和痛苦的过程,我花了20多天的所有空余时间,画了二十几页的草稿。</p>
<p>红黑树来源于2-3-4树,是2-3-4树的一种表现形式。当节点为红色时,即表示此节点和父节点连结为2-3-4树中的一个节点,如下图。</p>
<p><img alt="图一" src="/images/rb_tree/234_rb_tree.png"/></p>
<p>在我的学习中,分析过程大约是:先理解2-3-4树的增加删除 ...</p>
<p class="continue"><a href="/rb-tree-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/234-tree-algorithm-analysis.html">2-3-4树的分析</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-10-25(星期二) 08:49 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>2-3-4树在大部分资料中都简单带过,也很少会去实现。但是对于理解红黑树和B树来说,2-3-4树有非常重要的作用。</p>
<p>我被红黑树的算法折磨了几天,终于转到2-3-4树的学习,才搞明白了红黑树的来由。虽然一般2-3-4树不必实现,但是了解其原理还是很重要的。</p>
<p>2-3-4树是阶为4的B树,同时2-3-4树与红黑树等效。</p>
<p>2-3-4树的名称意味着树的每个节点带着2,3或4个孩子节点。</p>
<ul>
<li>
<p>2节点有1个数据元素,有2个子节点</p>
</li>
<li>
<p>3节点有2个数据元素,有3个子节点</p>
</li>
<li>
<p>4节点有3个数据元素,有4个子节点</p>
</li>
</ul>
<p><img alt="图" src="/images/234_tree/234tree.png"/></p>
<p>2-3-4树的特性 ...</p>
<p class="continue"><a href="/234-tree-algorithm-analysis.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/avl-tree-algorithm-in-c.html">AVL树的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-10-10(星期一) 20:55 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>AVL树是根据它的发明者G.M.Adelson-Velsky和E.M.Landis命名的。
它是最先发明的自平衡二叉查找杩,也被称为高度平衡树。AVL树中任何节点的两个子树的高度最大差别为1。
AVL树的查找,插入,和删除在平均和最坏情况下都是O(log(n))。</p>
<p>AVL树的一般定义:</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">avl_tree_s</span><span class="o">*</span> <span class="n">avl_tree_pt</span><span class="p">;</span>
<span class="k">typedef</span> <span class="k">struct ...</span></pre></div>
<p class="continue"><a href="/avl-tree-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/huffman-tree-algorithm-in-c.html">哈夫曼树的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-10-07(星期五) 22:10 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>哈夫曼树是最优二叉树。定义:给定n个权值作为n个叶子节点,构造一棵二叉树,若树的带树路径长度最小,则这棵树被称为哈夫曼树。如下图。</p>
<p><img alt="图一" src="/images/huffman_tree/huffman.png"/></p>
<p>哈夫曼树涉及的几个概念</p>
<p><strong>路径和路径长度</strong>:在一棵树中,从一个结点往下可以到达孩子或孙子结点之间的通路,称为路径。通路中结点的数目称为路径长度。如15的路径长度是1;5,6,7,8的路径长度是3。</p>
<p><strong>结点的权及带权路径长度</strong>: 若将树中结点赋给一个有着某种含义的数值 ...</p>
<p class="continue"><a href="/huffman-tree-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/pairing-heap-algorithm-in-c.html">pairing堆的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-10-07(星期五) 16:31 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>斐波那契堆编程实现难度较大并且效率没有理论的快(由于它的存储结构和四个指针)。pairing堆可以弥补斐波那契堆的缺点,编程比较简单且时间复杂度跟斐波那契堆相同。</p>
<p>pairing堆是一棵多路树,类似于左倾堆和斜堆,与二项堆和斐波那契堆不同。它的基本操作是两个多路树的连接,所以取名叫pairing堆。</p>
<p>关于pairing堆的完整中文资料比较少,但国外还是挺容易找到的。以下的实现参考cise.ufl.edu一些公开课资料的讲解。</p>
<h3 id="pairing"><strong> pairing堆的数据结构定义 </strong></h3>
<p>pairing堆的数据结构一般如下:</p>
<div class="highlight"><pre><span></span><span class="k">typedef</span> <span class="k">struct</span> <span class="n">pairing_heap_s</span> <span class="o">*</span><span class="n">pairing_heap_pt ...</span></pre></div>
<p class="continue"><a href="/pairing-heap-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<article>
<h3><a href="/fibonacci-heap-algorithm-in-c.html">斐波那契堆的C语言实现</a></h3>
<h6 class="subheader"><span class="label secondary radius">Date</span> 2016-10-06(星期四) 01:01 <span class="label secondary radius">By</span> <a href="/author/ming.html">Ming</a> <span class="label secondary radius">In</span> <a href="/category/suan-fa.html">算法</a> <span class="label secondary radius">Tags</span> <a href="/tag/suan-fa.html">算法</a>, </h6>
<p>斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是:不涉及删除元素的操作仅需要O(1)的平摊运行时间。和二项堆一样,斐波那契堆由一组树构成。这种堆松散地基于二项堆,说松散是因为:如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作,则堆中每棵树就和二项树一样;但是如果执行这两种操作,在一些状态下必须要破坏二项树的特征,比如DECREASE-KEY或DELETE 后,有的树高为k ...</p>
<p class="continue"><a href="/fibonacci-heap-algorithm-in-c.html">阅读全文 »</a></p>
</article>
<hr />
<div class="row" style="margin-bottom: -1.25em;">
<div class="small-12 columns text-center">
<div class="pagination-centered">
<ul class="pagination">
<li class="arrow unavailable"><a href="#">← Previous</a></li>
<li class="current"><a href="/index.html">1</a></li>
<li class=""><a href="/index2.html">2</a></li>
<li class="arrow"><a href="/index2.html">Next →</a></li>
</ul>
</div>
</div>
</div>
</div>
<!-- End Main Content -->
<!-- Sidebar -->
<aside class="medium-3 hide-for-small-only columns">
<div class="panel radius">
<h5>Categories</h5>
<ul class="side-nav">
<li><a href="/category/ji-he-suan-fa.html">几何算法 <span class="label secondary round">2</span></a></li>
<li><a href="/category/suan-fa.html">算法 <span class="label secondary round">13</span></a></li>
</ul>
</div>
<div class="panel radius">
<h5>Tags</h5>
<ul class="tag-cloud">
<li class="label info round"><a href="/tag/ji-he-suan-fa-suan-fa.html">几何算法,算法</a></li>
<li class="label info round"><a href="/tag/suan-fa.html">算法</a></li>
</ul>
</div>
<div class="panel radius">
<h5>Links</h5>
<ul class="side-nav">
<li><a href="http://coolshell.cn">酷 壳</a></li>
<li><a href="http://blog.codingnow.com">云风的 BLOG</a></li>
<li><a href="http://www.ruanyifeng.com/blog">阮一峰的网络日志</a></li>
</ul>
</div>
<!--
<div class="panel radius">
<h5>Social</h5>
<ul class="side-nav">
<li><a href="#"></a></li>
</ul>
</div>
-->
</aside>
<!-- End Sidebar -->
<!-- Main Content -->
<!-- End Main Content -->
<!-- Sidebar -->
<!-- End Sidebar -->
</div>
<!-- Footer -->
<footer class="row">
<div class="">
<hr/>
<p class="text-center">Powered by <a href="http://getpelican.com">Pelican</a> and <a href="http://foundation.zurb.com/">Zurb Foundation</a>. Theme by <a href="http://hamaluik.com">Kenton Hamaluik</a>.</p>
</div>
</footer>
<!-- End Footer -->
</section>
<a class="exit-off-canvas"></a>
</div><!--off-canvas inner-->
</div><!--off-canvas wrap-->
<script src="/theme/js/vendor/jquery.js"></script>
<script src="/theme/js/vendor/modernizr.js"></script>
<script src="/theme/js/foundation.min.js"></script>
<script>
$(document).foundation();
</script>
</body>
</html>