简单算法

空间复杂度

类似于时间复杂度的讨论，一个算法的空间复杂度(SpaceComplexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异，有的算法只需要占用少量的临时工作单元，而且不随问题规模的大小而改变，我们称这种算法是“就地\”进行的，是节省存储的算法，有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法就属于这种情况。

分析一个算法所占用的存储空间要从各方面综合考虑。如对于递归算法来说，一般都比较简短，算法本身所占用的存储空间较少，但运行时需要一个附加堆栈，从而占用较多的临时工作单元；若写成非递归算法，一般可能比较长，算法本身占用的存储空间较多，但运行时将可能需要较少的存储单元。

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n).若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

快排

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//不稳定</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> adjustArray(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> a[], <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> first, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> end)<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//first,end均为下标</span> { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x = a[first]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> l = first, r = end; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (l < r) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//选择第一个元素作为基准，将小于他的元素放入左边，大于等于他的元素放入右边，排序不稳定</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (l<r&&a[r]>= x) r--; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (l < r) { a[l] = a[r]; l++;<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//将a[l]坑填好后，不再管a[l]所以，l++</span> } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (l < r&&a[l] < x) l++; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (l < r) { a[r] = a[l]; r--;<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//将a[r]坑填好后，不再管a[r]所以，r--</span> } } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//退出时，l等于r,将x填到这个坑中.</span> a[l] = x; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> l; } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//[first,end]</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> quickSort(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> a[],<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> first, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> end )<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//first,end均为下标</span> { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (first < end) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = adjustArray(a, first, end); quickSort(a, first, i - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>); quickSort(a, i + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, end); } }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li></ul>

归并

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> mergeVector(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> &a, <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> &tmp, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> left_first, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> left_last,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> right_first ,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> right_last) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> tmp_first = left_first; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> first = left_first; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> last = right_last;; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (left_first <= left_last&&right_first <= right_last) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (a[left_first] < a[right_first]) tmp[tmp_first++] = a[left_first++]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> tmp[tmp_first++] = a[right_first++]; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (left_first <= left_last) tmp[tmp_first++] = a[left_first++]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (right_first <= right_last) tmp[tmp_first++] = a[right_first++]; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = first; i <=last; i++) a[i] = tmp[i]; } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//[firs,last]</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> mergeSort(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> &a, <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> &tmp, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> first, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> last) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (first < last) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> center = first + (last-first) / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>; mergeSort(a, tmp, first, center); mergeSort(a, tmp, center + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, last); mergeVector(a, tmp, first, center,center+<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, last); } }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li></ul>

插入排序

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//n^2 数组默认为非降序排列</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> insertSort(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> &vec) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//第一层循环一次遍历向量中第2个元素至最后一个元素</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> p = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; p < vec.size(); p++) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> temp = vec[p]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//将被遍历元素与之前所有元素（这些元素已经排序！）比较，从后往前遍历，找到合适位置并插入</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//如果元素比他大，则继续向前寻找比他小的元素，并将大元素向后移动</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (j = p; j ><span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span> && temp<vec[j-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>]; j--) { vec[j] = vec[j - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>]; } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//j为插入合适位置</span> vec[j] = temp; } }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li></ul>

希尔排序

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//希尔排序,非稳定，复杂度优于等于o（n^2）,与gap选择方式有关</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> shellsort(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>&a) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> gap = a.size() / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>; gap > <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; gap /= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = gap; i < a.size(); i++) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> temp = a[i]; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//谢尔排序与插入排序的共同之处</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = i; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (; j >= gap&& temp< a[j - gap]; j -= gap) a[j] = a[j - gap]; a[j] = temp; } }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li></ul>

冒泡排序

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> bubbleSort(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> a[], <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> n)<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//n代表数组大小</span> { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//遍历一次数组，最大的一个数沉到数组末尾，n个数需要n-1次遍历</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <=n - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i++) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//n个数据需要进行n-1次交换</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= n - i;j++) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (a[j-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>] >a[j]) swap(a[j-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>], a[j]); } } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//如果对于已经排好序的数组，使用第一种方法，复杂度为O(n^2),此法可以做到O(n)</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> BubbleSort2(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> a[], <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> n) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> k = n-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">bool</span> flag = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">true</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (flag) { flag = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">false</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= k; j++) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (a[j - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>] > a[j]) { swap(a[j - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>], a[j]); flag = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">true</span>; } k--; } } </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li></ul>

二分查找

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//在[start,end]范围内寻找</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> binary_search(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> arr[], <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> start, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> end, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> key) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//start和end有可能重合，重合时start所对应的值有可能就是key，所以不能含等于号，</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//比如数组{1,2,3}查找1，</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (start > end) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> mid = start + (end - start) / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//直接平均可能會溢位，所以用此算法</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (arr[mid] > key) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> binary_search(arr, start, mid - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, key); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (arr[mid] < key) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> binary_search(arr, mid + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, end, key); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> mid; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//最後檢測相等是因為多數搜尋狀況不是大於要不就小於</span> } <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//法2</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> binary_search1(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> arr[], <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> start, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> end, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> key) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//int mid;</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (start <= end) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> mid = start + (end - start) / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;"><span class="hljs-xmlDocTag" style="box-sizing: border-box;">///</span>/直接平均可能會溢位，比如end和start为MAX_INT</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (arr[mid] < key) start = mid + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (arr[mid] > key) end = mid - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> mid; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//最後檢測相等是因為多數搜尋狀況不是大於要不就小於</span> } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li></ul>

前序遍历

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> TreeNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; TreeNode *left; TreeNode *right; TreeNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x) :val(x), left(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>), right(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) {} }; <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>pre(TreeNode *root) { <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> result; <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">stack</span><TreeNode *></span> sta; TreeNode *p = root; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!root) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> result; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> sta.push(root); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span>(!sta.empty()) { p = sta.top(); sta.pop(); result.push_back(p->val); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p->right) sta.push(p->right); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p->left) sta.push(p->left); } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> result; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li></ul>

中序遍历

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> TreeNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; TreeNode *left; TreeNode *right; TreeNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x) :val(x), left(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>), right(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) {} }; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//左树节点一定比右子树节点排在前边</span> <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>inorder(TreeNode *root) { <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> result; <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">stack</span><TreeNode *></span> sta; TreeNode *p = root; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (root = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> result; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (p != <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>||!sta.empty())<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//</span> { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p != <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) { sta.push(p); p = p->left; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> { p = sta.top(); sta.pop(); result.push_back(p->val); p = p->right; } } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> result; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li></ul>

后序遍历

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> TreeNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; TreeNode *left; TreeNode *right; TreeNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x) :val(x), left(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>), right(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) {} }; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//后序遍历</span> <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> postorderTraversal(TreeNode* root) { <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span> vec; <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">stack</span><TreeNode *></span> sta; TreeNode *p=root; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p=<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> vec; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> sta.push(p); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (!sta.empty()) { p = sta.top(); sta.pop(); vec.insert(vec.begin(), p->val); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p->left) sta.push(p->left); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (p->right) sta.push(p->right); } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> vec; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li></ul>

层序遍历

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> TreeNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; TreeNode *left; TreeNode *right; TreeNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x) :val(x), left(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>), right(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>) {} }; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//层序遍历</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> travel(TreeNode *p, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> level, <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>></span>&result) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!p) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> ; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (level > result.size()) result.push_back(<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>()); result[level - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>].push_back(p->val); travel(p->left, level + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, result); travel(p->right, level + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, result); } <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>></span>level(TreeNode *root) { <span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-stl_container" style="box-sizing: border-box;"><span class="hljs-built_in" style="color: rgb(102, 0, 102); box-sizing: border-box;">vector</span><<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span>></span>></span>result; travel(root, <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>, result); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> result; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li></ul>

链表反转

<code class="hljs perl has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">struct ListNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*next</span>; ListNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>) : val(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>), <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>(nullptr) { } }; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>正确 ListNode* reverseList(ListNode* head) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!head||!head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*dummy</span> = new ListNode(INT_MAX); dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*prev</span> = head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*cur</span> = head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (cur) { prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = cur; cur = prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span> } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; } ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*reverseBetween</span>(ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*head</span>, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">m</span>, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> n) { ListNode beg(-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>); ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*prev</span> = &beg; prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = head; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; j < <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">m</span> - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j++) prev = prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*newHead</span> = prev; prev = prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*cur</span> = prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < n - <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">m</span>; i++)//交换的次数等于节点距离 { prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = newHead-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; newHead-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = cur; cur = prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> beg.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li><li style="box-sizing: border-box; padding: 0px 5px;">41</li><li style="box-sizing: border-box; padding: 0px 5px;">42</li></ul>

排序的链表中删除重复的节点

<code class="hljs perl has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">struct ListNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*next</span>; ListNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>) : val(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>), <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>(nullptr) {} }; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>删除排好序的链表中的重复节点 ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*deleteDuplicates</span>(ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*head</span>) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!head || !head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*prev</span> = head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*cur</span>=head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (prev->val == cur->val) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (cur&&prev->val == cur->val) cur = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> deleteDuplicates(cur); } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> { prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = deleteDuplicates(prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> prev; } }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li></ul>

排序的链表中删除重复节点，使每个节点只出现一次

<code class="hljs perl has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;">struct ListNode { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> val; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*next</span>; ListNode(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>) : val(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>), <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>(nullptr) {} }; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>法<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span> ListNode* deleteDuplicates(ListNode* head) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!head) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> nullptr; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*dummy</span> = new ListNode(-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>); dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*prev</span> = head; ListNode <span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*cur</span> = head-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (cur) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (cur&&prev->val == cur->val) { prev-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span> = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>;<span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span> cur = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (cur) { prev = cur; cur = cur-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; } } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> dummy-><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">next</span>; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li></ul>

任意进制转换

<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">void</span> Convert(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">string</span> &pSrc, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">string</span> &pDst, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> src, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> dst, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> &len) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i,t, number = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> temp; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; pSrc[i] != <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>; i++) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (pSrc[i] >= <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span> && pSrc[i] <= <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'9'</span>) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 如果是数字</span> { t = pSrc[i] - <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 否则就是字母</span> { t = pSrc[i] - <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'A'</span> + <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span>; } number = number * src + t; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 将源进制数组转换成十进制数</span> } i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (number) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 进行进制转换</span> { t = number % dst; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (t >= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span> && t <= <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">9</span>) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 如果是数字</span> { pDst[i++] = t + <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 那么就是字母</span> { pDst[i++] = t - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span> + <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'A'</span>; } number /= dst; } len = i; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">// 将转换完成的进制数按自然顺序排放</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j, k; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> ( j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>, k = i - <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; k >= j; j++, k--) { temp = pDst[j]; pDst[j] = pDst[k]; pDst[k] = temp; } pDst[i] = <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li><li style="box-sizing: border-box; padding: 0px 5px;">41</li><li style="box-sizing: border-box; padding: 0px 5px;">42</li><li style="box-sizing: border-box; padding: 0px 5px;">43</li></ul>

字符串转换成整数

<code class="hljs rust has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> atoi(string <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> num = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>.size(); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>, digital = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> sign = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i]==<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">' '</span> && i < num) i++;<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//str[i]==' '不等同于！str[i]</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i] == <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'+'</span>) i++; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i] == <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'-'</span>) { sign = -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i++; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span> (; i < num;i++) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i]<<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span> || <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i]><span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'9'</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">break</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (digital>INT_MAX / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span> || (digital == INT_MAX / <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span> && (<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i] - <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span>) > INT_MAX % <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span>)) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> sign == <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span> ? INT_MAX : INT_MIN; digital = digital * <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">10</span> + <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">str</span>[i] - <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'0'</span>; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> sign*digital; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li></ul>

字符串拷贝函数

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * Strcpy(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * destination, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * source) { <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//首先需要检查目的指针与源指针是否为空！</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!destination) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!source) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> destination; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> *temp = destination; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> ((*destination++ = *source++) != <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>) ; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> temp; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li></ul>

字符串连接函数

<code class="hljs cpp has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * Strcat(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * destination, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * source) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!destination) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">nullptr</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (!source) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> destination; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> *temp = destination; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (*destination != <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>) destination++; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> ((*destination++ = *source++) != <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>) ; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> temp; }</code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li></ul>

字符串比较函数

<code class="hljs rust has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//字符串比较,逐一比较每一个字符，如果相等则继续比较下一个，知道遇到不相等字符或结尾字符，</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//如果遇到结尾还未比较出结果，则长字符串大</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Strcmp(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * str1, <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">char</span> * str2) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">assert</span>(str1&&str2); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">while</span> (*str1 == *str2) { <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span> (*str1 == <span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">'\0'</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; str1++; str2++; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> *str1 - *str2 > <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span> ? <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>:-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; }</code>