<!DOCTYPE html>
<html>
  <head>
    <meta charset='utf-8'>

    <link rel="stylesheet" type="text/css" 
      href="/assets/css/straybirds.css" media="screen" />
    <link rel="stylesheet" type="text/css" 
      href="/assets/css/pygments.css" media="screen" />

    <!-- MathJax Section Start -->

    <script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
    </script>
    <script>
        MathJax.Hub.Config({
              tex2jax: {
              skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
              }
        });
        MathJax.Hub.Queue(function() {
            var all = MathJax.Hub.getAllJax(), i;
            for(i=0; i < all.length; i += 1) {
                all[i].SourceElement().parentNode.className += ' has-jax';
            }
        });
    </script>

    <!-- MathJax Section End -->

    <!-- Google Analytics Start-->
    <script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-48100787-1', 'minixalpha.github.io');
  ga('send', 'pageview');

</script>

    <!-- Google Analytics End -->

    <title>Monthly archive for 2013/10</title>
  </head>

  <body>
    <div class="container">
      <header>
        <div class="container">
          <h1>
              <a href="/" title="Home Page"> 潇湘夜雨 </a>
          <span class="github-src">
            <a href ="https://github.com/minixalpha/minixalpha.github.io"
               target="_blank"
               title="Fork me on GitHub">
              <img src="/assets/images/GitHub-Mark-Light-32px.png" alt="">
            </a>
          </span>
          </h1>
        </div>
      </header>

      <aside id="left-side">
        <h2> 分类 </h2>
  <ul class="category-list">
      
            
                <li>
                <a href="/categories/源代码阅读"> 源代码阅读 (20) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/设计模式"> 设计模式 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/科研"> 科研 (6) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/思想"> 思想 (2) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/技术"> 技术 (18) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/工具"> 工具 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/虚拟机"> 虚拟机 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/java"> java (11) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/c语言"> c语言 (4) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/读书"> 读书 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/操作系统"> 操作系统 (1) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/英语"> 英语 (10) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/计算机系统"> 计算机系统 (3) </a>
                </li>
            
      
            
                <li>
                <a href="/categories/生活"> 生活 (1) </a>
                </li>
            
      
  </ul>

      </aside>

      <aside id="right-side">
        <h2> 归档 </h2>
  <ul class="archive-list">
    
    
    
        
        
        
        
            
            <li>
                <a href="/2014/08">
                    2014-08 (1)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/07">
                    2014-07 (5)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/05">
                    2014-05 (12)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/04">
                    2014-04 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/03">
                    2014-03 (11)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/02">
                    2014-02 (6)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2014/01">
                    2014-01 (3)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/11">
                    2013-11 (10)
                </a>
            </li>

        
        
    
        
        
        
        
    
        
        
        
        
    
        
        
        
        
            
            <li>
                <a href="/2013/10">
                    2013-10 (3)
                </a>
            </li>

        
        
    
        
        
        
        
            
            <li>
                <a href="/2010/09">
                    2010-09 (1)
                </a>
            </li>

        
        
    
  </ul>

      </aside>

      <article>

<div class="post-list">
    <ul>

    <li>
      <div class="post-title">
        <a href="/%E5%B7%A5%E5%85%B7/2013/10/24/markdonnote.html"> 使用 Markdown</a> </br>
      </div>

      <div class="post-info">
        <ol>
          <li class="post-time">2013-10-24</li> 
          <li class="post-category"> 工具 </li>
        </ol>
      </div>

      <div class="post-preview">
        <h1>为什么使用 Markdown</h1>

<ul>
<li>看上去不错<br></li>
<li>既然看上去不错，为什么不试试呢<br></li>
</ul>

<hr>

<h1>如何使用 Markdonw</h1>

<h2>1. 标题级别</h2>

<h3>效果</h3>

<h1>一级标题</h1>

<h2>二级标题</h2>

<h3>三级标题</h3>

<h3>代码</h3>
<div class="highlight"><pre><code class="text language-text" data-lang="text"># 一级标题  
## 二级标题
### 三级标题
</code></pre></div>
<hr>

<h2>2. 列表</h2>

<h3>效果</h3>

<ul>
<li>列表1</li>
<li>列表2</li>
<li>列表3</li>
</ul>

<h3>代码 (注意星号与文字之间的空格)</h3>
<div class="highlight"><pre><code class="text language-text" data-lang="text">* 列表1
* 列表2
* 列表3
</code></pre></div> 
        <a href="/%E5%B7%A5%E5%85%B7/2013/10/24/markdonnote.html"> Read More ... </a> </br>
      </div>
    </li>

    <li>
      <div class="post-title">
        <a href="/%E6%8A%80%E6%9C%AF/c%E8%AF%AD%E8%A8%80/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F/2013/10/25/charpointerarray.html"> 字符指针与字符数组真正的区别</a> </br>
      </div>

      <div class="post-info">
        <ol>
          <li class="post-time">2013-10-25</li> 
          <li class="post-category">  </li>
        </ol>
      </div>

      <div class="post-preview">
        <h1>字符指针与字符数组真正的区别</h1>

<hr>

<h2>问题缘起</h2>

<p>先看一个示例</p>

<h3>示例1</h3>
<div class="highlight"><pre><code class="c language-c" data-lang="c"><span class="cp">#include &lt;stdio.h&gt;</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="kt">char</span> <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="s">&quot;hello&quot;</span><span class="p">;</span>
    <span class="kt">char</span> <span class="n">q</span><span class="p">[]</span> <span class="o">=</span> <span class="s">&quot;hello&quot;</span><span class="p">;</span>

    <span class="n">printf</span> <span class="p">(</span><span class="s">&quot;p: %s</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">p</span><span class="p">);</span>
    <span class="n">printf</span> <span class="p">(</span><span class="s">&quot;q: %s</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span> <span class="n">q</span><span class="p">);</span>

    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>上面的例子会给出这样的输出</p>
<div class="highlight"><pre><code class="text language-text" data-lang="text">p: hello
q: hello
</code></pre></div>
<p>这样看，<code>char *p</code> 和 <code>char q[]</code> 好像没什么区别, 那么我们再看一个例子</p>

<h3>示例2</h3>
<div class="highlight"><pre><code class="c language-c" data-lang="c"><span class="cp">#include &lt;stdio.h&gt;</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
    <span class="kt">char</span> <span class="o">*</span><span class="n">p</span> <span class="o">=</span> <span class="s">&quot;hello&quot;</span><span class="p">;</span>
    <span class="kt">char</span> <span class="n">q</span><span class="p">[]</span> <span class="o">=</span> <span class="s">&quot;hello&quot;</span><span class="p">;</span>

    <span class="n">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="sc">&#39;s&#39;</span><span class="p">;</span>
    <span class="n">q</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">=</span> <span class="sc">&#39;s&#39;</span><span class="p">;</span>

    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</code></pre></div>
<p>如果你在Linux下，运行时可能得到这样的结果</p>
<div class="highlight"><pre><code class="text language-text" data-lang="text">Segmentation fault (core dumped)
</code></pre></div>
<p>这时候你看到了区别，出现了段错误, 你一定想明白，到底发生了什么，
经过几个小实验，你可能会发现使用 <code>char *p</code> 定义时，p指向的数据是无法改变的。
然后你Google, 别人可能会告诉你  </p>

<ul>
<li>char 指针指向的数据不能修改</li>
<li>char 指针指向的数据没有分配</li>
<li>...</li>
</ul>

<p>你听了还是一头雾水，不能修改是什么意思，没有分配？没有分配为什么能输出?</p>

<p>作为一个好奇心很重的人，你是绝对不能容忍这些问题的困扰的，且听我慢慢道来</p>
 
        <a href="/%E6%8A%80%E6%9C%AF/c%E8%AF%AD%E8%A8%80/%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F/2013/10/25/charpointerarray.html"> Read More ... </a> </br>
      </div>
    </li>

    <li>
      <div class="post-title">
        <a href="/%E6%80%9D%E6%83%B3/2013/10/26/whyds.html"> 为什么我们需要数据结构</a> </br>
      </div>

      <div class="post-info">
        <ol>
          <li class="post-time">2013-10-26</li> 
          <li class="post-category"> 思想 </li>
        </ol>
      </div>

      <div class="post-preview">
        <h1>为什么我们需要数据结构</h1>

<hr>

<p>最近在学习各种数据结构，于是就在想，为什么我们需要数据结构呢？
为什么要设计这么多数据结构？数据结构到底解决了我们什么样的问题？    </p>

<p>我们提到 <a href="http://zh.wikipedia.org/zh-cn/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84">数据结构</a> 时，一般是指计算机科学中的一个概念，
但是从本质上讲，数据结构应该是指对数据的一种组织方式。既然如此，我们没必要非在计算机科学领域中讨论
概念本身，把它放在其它领域中，可能更能加强我们的理解。</p>

<p>就说图书管吧，假如你是一名很久很久以前的图书馆管理员，那时候根本没什么计算机。数据结构？那是什么？</p>

<p>你的任务就是看着图书馆里的一堆书。于是，有一天，图书馆来了一堆书，你把他们堆成一堆，放在馆里。
这时候，有人来借书了，他只能在那一堆书里乱翻，翻来翻去也找不到自己想要的书，因为那是一堆书，
有的书他检查了很多次，有的一次也没检查。</p>

<blockquote>
<p>这时候这堆书是一个集合，不方便遍历。</p>
</blockquote>

<p>时间长了，抱怨的人很多。  </p>

<p>作为一个怕麻烦的管理员，你忍受不了别人的抱怨，于是，你把那 <strong>一堆书</strong> 变成了 <strong>一排书</strong>。</p>

<p>这下好了，来找书的人，只要从书架左边走到右边，按顺序找就好了。只要书在图书馆里，慢慢找总是可以找到。
但是，随着图书馆的书越来越多，这样找实在是太慢了，因为每次都要从第一本书找到最后一本书。</p>

<blockquote>
<p>这时候这堆书是一个列表，方便遍历，但是不方便查找。</p>
</blockquote>

<p>时间长了，抱怨的人很多。</p>

<p>作为一个怕麻烦的管理员，你忍受不了别人的抱怨，于是，你把那 <strong>一排书</strong> 变成了 <strong>很多类书</strong>。</p>

<p>那么，按什么分类呢？按书的大小么？颜色么？退一步讲，分类的依据是什么？</p>

<p>分类是为了加快读者查找书的速度，那么读者查找书的时候，是按什么查找呢？是按书名。所以，我们对书名分类。
按书名分类也有许多种，按书名读音么？按书名笔画吗？按书名字数么？我们很容易想到，按读音分类给读者的压力最小，
也就是查找前的开销最小。否则每次找书之前还要数一下笔画，读者一定又会抱怨。</p>

<p>这时候，我们按读音把书分类，书名第一个字是A的在A书架，是B的在B书架。这下读者查找书的速度大大加快了，
因为一下子就能排除那么多类书，而代价仅仅是想一下书名第一个字的读音。不过，我们马上又发现，有的书架上书实在太多了，
那有什么关系？这个问题我们解决过啊，只要再分类就好了，书名第一个字我们用过了，现在用第二个字。</p>

<p>读者终于大致可以满意了。</p>

<blockquote>
<p>这时候这些书架构成了一个查找树，方便查找。</p>
</blockquote>

<p>另外，我们注意到，其实对于管理员来说，他的负担是增加了的，比如新来了一本书，如果图书馆是一堆书，
只要把新书扔在那一堆里就好了，如果是一排书，要把新书放在这排书的最后，而如果是分好类的书架，
管理员就要先找到这本书的位置，再把新书放在那儿，而不能随便放。好在分类后，我们找新书位置不会花多久，
假如分好类后，读者查找书方便了，但是管理员要把新书放在合适的位置，需要花一年时间，
那这个分类的方法肯定不是一个好方法。   </p>

<p>这告诉我们</p>

<blockquote>
<p>维护数据结构很重要。</p>
</blockquote>

<p>这时候，我们在不知不觉间居然</p>

<h2>设计了一个数据结构</h2>

<p>这时候，我们回到开始时的问题，为什么我们需要数据结构？对应上面的故事，
为什么我们要把一堆书变成多类书？简单地说，这样可以使找书的过程变快。
这正印证了维基百科词条中的那句话。</p>

<blockquote>
<p>数据结构是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。</p>
</blockquote>

<p>回头想想，从一堆书变成多类书的过程，其实就是数据的组织方式发生了变化。我们来抽象一下整个过程。</p>

<ul>
<li>我们有一堆数据D。</li>
<li>数据上最常用的操作是O。</li>
<li>我们的目标是让O很快。</li>
<li>我们设计一个数据结构S来组织数据D。</li>
<li>数据结构S需要额外的信息EI来组织数据D。</li>
<li>数据结构S有性质P，性质P可以使操作O很快。</li>
<li>数据结构除了支持操作O外，还要支持两个最基本的操作，Add:添加数据，Del:删除数据。</li>
<li>数据结构要保持性质P，所以Add,Del需要额外操作EO来保持P。</li>
</ul>

<p>那么，关键的地方就在于:</p>

<blockquote>
<p>根据操作O，找到性质P，设计数据结构S，使S有性质P，同时使额外信息EI，额外操作EO尽量小。</p>
</blockquote>

<p>所以，无论是设计数据结构还是学习数据结构，都要弄清楚，</p>

<ul>
<li>数据结构的关键性质是什么</li>
<li>为什么关键性质可以加快操作</li>
<li>额外信息与额外操作大小如何</li>
</ul>

<p>下面我们探讨一些基本数据结构的特点</p>

<p>数组：数组的关键性质在于元素位置可以通过简单计算马上得到，这个关键性质为随机访问提供了很大的
便利。如果数据大小需要动态扩展，那么使用数组是不方便的，因为动态扩展难以维护数组的关键性质。</p>

<p>数组之所以拥有“元素位置可以通过简单计算得到”这个性质，在于数组在内存中是一片连续的区域，这样
知道数组第一个元素位置，知道每个元素大小，通过一次加法，一次乘法，就可以知道第N个元素的位置。
如果数组需要动态扩展，如果这片连续区域相邻的地方有可用内存，那么额外操作是分配这块区域给数组，
如果相邻位置没有可用内存，需要另找一片足够大的连续区域，作为新数组的位置，同时还要把已有数据
复制过去。</p>
 
        <a href="/%E6%80%9D%E6%83%B3/2013/10/26/whyds.html"> Read More ... </a> </br>
      </div>
    </li>


    </ul>
  </div>
</div>


      </article>

      <div class="comments">
        
      </div>


      <footer>
        Copyright (c) minixalpha 2014
      </footer>

    </div>
  </body>
</html>
