search

Home >php教程 >php手册 >数据结构，数据结构与算法

数据结构，数据结构与算法

WBOY
WBOYOriginal
2016-06-13 08:42:17933browse

数据结构，数据结构与算法

线性表：零个或多个数据元素的有限序列（注：以下都是用的整型数据模拟）

一 顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
　　1.1 三个属性:存储空间的起始位置；最大存储容量；当前长度
　　注：数组长度是存放线性表的存储空间的长度（一般是不变的），不过语言可以动态增加容量，会带来性能损耗；
　　　　线性表长度是数据元素的个数；
　　　　线性表是从1开始数的，对应数组0的位置
　　1.2 获取元素、插入元素、删除元素(代码中展示)

　　1.3 顺序结构优缺点：
　　　　优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任一位置元素
　　　　缺点：插入和删除操作需要移动大量的元素；当线性表长度裱花较大时，难以确定存储空间容量；造成存储空间'碎片'

<span>    //</span><span>用一维数组模拟线性表</span>
    <span>class</span><span> Sequential_Structure
    {
        </span><span>//</span><span>线性表的长度</span>
        <span>private</span> <span>$num</span> = 0<span>;
        </span><span>//</span><span>数组长度</span>
        <span>private</span> <span>$len</span> = 0<span>;
        </span><span>//</span><span>数组模拟</span>
        <span>private</span> <span>$arr</span> = <span>array</span><span>();

        </span><span>/*</span><span>*
          * 初始化结构
          * @param Int $len 最大数组长度
          * @param Array $arr 数组
          * @return 
          </span><span>*/</span>
        <span>public</span> <span>function</span> __construct(<span>$len</span>, <span>Array</span> <span>$arr</span><span>)
        {
            </span><span>$this</span>->len = <span>$len</span><span>;
            </span><span>$length</span> = <span>count</span>(<span>$arr</span><span>);
            </span><span>if</span>(<span>$length</span> > 0 && <span>$length</span> <= <span>$len</span><span>)
            {
                </span><span>$this</span>->arr = <span>$arr</span><span>;
                </span><span>$this</span>->num = <span>$length</span><span>;
            }
        }

        </span><span>/*</span><span>*
          * 获取线性表元素
          * @param Int $i 需要获取的第几个元素
          * @return 
          </span><span>*/</span>
        <span>public</span> <span>function</span> get_elem(<span>$i</span><span>)
        {
            </span><span>if</span>(<span>$this</span>->num == 0 || <span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->num) <span>//</span><span>判断查找是否合理</span>
                <span>return</span> <span>false</span><span>;
            </span><span>return</span> <span>$this</span>->arr[<span>$i</span>-1];    <span>//</span><span>返回数据，时间复杂度O(1)</span>
<span>        }

        </span><span>/*</span><span>*
          * 插入元素（顺序结构中，插入元素后，后面所有的数据都要后移，平均时间复杂度O(1)）:
          * 如果插入位置不合理，失败
          * 如果线性长度大于数组长度，则返回错误或者动态增加容量
          * 从最后一个元素开始向前遍历到第i个位置，分别将它们向后移动一个位置
          * 将元素插入i位置
          * @param Int $i 需要插入到第几个元素
          * @param Int $elem 插入的节点
          * @return bool
          </span><span>*/</span>
        <span>public</span> <span>function</span> insert_elem(<span>$i</span>,  <span>$elem</span><span>)
        {
            </span><span>if</span>(<span>$this</span>->num == <span>$this</span>->len) <span>//</span><span>顺序线性表已满</span>
                <span>return</span> <span>false</span><span>;
            </span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > (<span>$this</span>->num+1)) <span>//</span><span>i不在范围之内</span>
                <span>return</span> <span>false</span><span>;
            </span><span>if</span> (<span>$i</span> <= <span>$this</span>->num)  <span>//</span><span>若数据插入位置不在表尾</span>
<span>            {
                </span><span>for</span>(<span>$k</span> = <span>$this</span>->num-1; <span>$k</span> >= <span>$i</span>-1; --<span>$k</span>) <span>//</span><span>后面所有元素往后移动一位</span>
                    <span>$this</span>->arr[<span>$k</span>+1] = <span>$this</span>->arr[<span>$k</span><span>];
            }
            </span><span>$this</span>->arr[<span>$i</span>-1] = <span>$elem</span>; <span>//</span><span>插入元素</span>
            ++<span>$this</span>-><span>num;
            </span><span>return</span> <span>true</span><span>;
        }

        </span><span>/*</span><span>*
          * 删除元素（顺序结构中，插入元素后，后面所有的数据都要前移，平均时间复杂度O(1)）:
          * 如果删除位置不合理，失败
          * 将元素删除
          * 从最后删除元素开始向后遍历到最后，分别将它们向前移动一个位置
          * @param Int $i 需要仓储的第几个元素
          * @return bool
          </span><span>*/</span>
        <span>public</span> <span>function</span> delete_elem(<span>$i</span><span>)
        {
            </span><span>if</span>(<span>$this</span>->num == 0) <span>//</span><span>线性表为空</span>
                <span>return</span> <span>false</span><span>;
            </span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->num) <span>//</span><span>删除位置不正确</span>
                <span>return</span> <span>false</span><span>;
            </span><span>if</span>(<span>$i</span> < <span>$this</span>->num) <span>//</span><span>删除位置不是表尾</span>
<span>            {
                </span><span>for</span>(<span>$k</span> = <span>$i</span>; <span>$k</span> < <span>$this</span>->num; ++<span>$k</span>) <span>//</span><span>前移</span>
                    <span>$this</span>->arr[<span>$k</span>-1] = <span>$this</span>->arr[<span>$k</span><span>];
            }    
            </span><span>unset</span>(<span>$this</span>->arr[<span>$this</span>->num-1<span>]);
            </span>--<span>$this</span>-><span>num;
            </span><span>return</span> <span>true</span><span>;
        }

        </span><span>/*</span><span>*
          * 获取顺序表
          * @return 
          </span><span>*/</span>    
        <span>public</span> <span>function</span><span> get_arr()
        {
            </span><span>return</span> <span>$this</span>-><span>arr;
        }

        </span><span>/*</span><span>*
          * 获取长度
          * @return 
          </span><span>*/</span>    
        <span>public</span> <span>function</span><span> get_len()
        {
           </span><span>return</span> <span>array</span>('num' => <span>$this</span>->num , 'len' => <span>$this</span>-><span>len);
        }
    }
    
    </span><span>$link</span> = <span>new</span> Sequential_Structure(10,[1,4,8,7<span>]);
    </span><span>echo</span> <span>$link</span>->get_elem(2<span>);
    </span><span>var_dump</span>(<span>$link</span>->insert_elem(5,5<span>));
    </span><span>var_dump</span>(<span>$link</span>-><span>get_arr());
    </span><span>var_dump</span>(<span>$link</span>-><span>get_len());
    </span><span>var_dump</span>(<span>$link</span>->delete_elem(1<span>));
    </span><span>var_dump</span>(<span>$link</span>-><span>get_arr());
    </span><span>var_dump</span>(<span>$link</span>->get_len());
<span>输出:<br />boolean</span> <span>true</span>
<span>array</span> (size=5<span>)
  </span>0 => int 1
  1 => int 4
  2 => int 8
  3 => int 7
  4 => int 5
<span>array</span> (size=2<span>)
  </span>'num' => int 5
  'len' => int 10
<span>boolean</span> <span>true</span>
<span>array</span> (size=4<span>)
  </span>0 => int 4
  1 => int 8
  2 => int 7
  3 => int 5
<span>array</span> (size=2<span>)
  </span>'num' => int 4
  'len' => int 10

 

 

二 链表存储结构（n个节点链结成一个链表）
　　2.1 单链表（用数组模拟）
　　　　2.1.1 链表中第一个结点的存储位置为头指针(通常为了方便对链表进行操作，会在单链表的第一个结点前附设一个头结点)
　　　　　　注 头指针：指向链表第一个结点的指针，若链表有头结点，这是指向头结点的指针；无论链表是否为空，头指针不为空
　　　　　　　 头结点：放在第一元素的结点之前

<span>/*</span><span>*
      *    用一维数组模拟线性表
      * array('data'=>data,'cur'=>cur) data为存放数据，cur为下个数组元素下标
      </span><span>*/</span>
    <span>class</span><span> Simple_Link
    {
        </span><span>//</span><span>数组长度</span>
        <span>private</span> <span>$len</span> = 0<span>;
        </span><span>//</span><span>数组模拟</span>
        <span>private</span> <span>$arr</span> = <span>array</span><span>();
        </span><span>//</span><span>数组中空闲的下标</span>
        <span>private</span> <span>$space_arr</span> = <span>array</span><span>();

        </span><span>/*</span><span>*
          * 初始化结构
          * @param Int $len 最大数组长度
          * @param Array $arr 数组
          * @return 
          </span><span>*/</span>
        <span>public</span> <span>function</span> __construct(<span>$len</span>, <span>Array</span> <span>$arr</span><span>)
        {
            </span><span>$this</span>->len = <span>$len</span><span>;
            </span><span>$length</span> = <span>count</span>(<span>$arr</span><span>);
            </span><span>$this</span>->arr[0]['data'] = <span>$length</span><span>;
            </span><span>$this</span>->arr[0]['cur'] = 0<span>;
            </span><span>for</span>(<span>$i</span> = 0; <span>$i</span> < <span>$length</span>; ++<span>$i</span><span>)
                </span><span>$this</span>->arr[<span>$i</span>]['cur'] = <span>$i</span>+1;  <span>//</span><span>模拟链表的指向</span>
            
            <span>if</span>(<span>$length</span><span>)
                </span><span>$this</span>->arr[<span>$length</span>]['cur'] = 0;  <span>//</span><span>最后一个结点指针空</span>
            
            <span>for</span>(<span>$i</span> = <span>$length</span> + 1; <span>$i</span> <= <span>$len</span>-<span>$length</span> ; ++<span>$i</span>) <span>//</span><span>空闲数组</span>
                <span>array_unshift</span>(<span>$this</span>->space_arr,<span>$i</span><span>);  
        }

        </span><span>/*</span><span>*
          * 获取线性表元素：
          * 初始化$j从1开始
          * 当$j<$i，遍历链表
          * @param Int $i 需要获取的第几个元素
          * @return 
          </span><span>*/</span>
        <span>public</span> <span>function</span> get_elem(<span>$i</span><span>)
        {
            </span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$this</span>->arr[0]['data'<span>]) 
                </span><span>return</span> <span>false</span><span>;
            </span><span>$j</span> = 1<span>;
            </span><span>$cur</span> = <span>$this</span>->arr[0]['cur'];  <span>//</span><span>指向第一个结点</span>
            <span>while</span>(<span>$j</span> < <span>$i</span><span>)
            {
                </span><span>$cur</span> = <span>$this</span>->arr[<span>$cur</span>]['cur'<span>];
                </span>++<span>$j</span><span>;
            }
　　　　　　　　
            </span><span>return</span> <span>$this</span>->arr[<span>$cur</span>]['data'<span>];
        }

        </span><span>/*</span><span>*
          * 插入元素:
          * 初始化$j从1开始
          * 当$j<$i，遍历链表
          * 将元素插入i位置
          * @param Int $i 需要插入到第几个元素
          * @param Int $elem 插入的节点
          * @return bool
          </span><span>*/</span>
        <span>public</span> <span>function</span> insert_elem(<span>$i</span>, <span>$elem</span><span>)
        {
            </span><span>$len</span> = <span>$this</span>->arr[0]['data'] + 1<span>;
            </span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$len</span><span>) 
                </span><span>return</span> <span>false</span><span>;
            </span><span>$j</span> = <span>$this</span>->malloc(); <span>//</span><span>获取空闲下标</span>
            <span>if</span>(!<span>$j</span><span>)
                </span><span>return</span> <span>false</span><span>;
            </span><span>$this</span>->arr[<span>$j</span>]['data'] = <span>$elem</span><span>;
            
            </span><span>$k</span> = 1<span>;
            </span><span>$index</span> = 0<span>;
            </span><span>$cur</span> = !<span>empty</span>(<span>$this</span>->arr[0]['cur']) ? <span>$this</span>->arr[0]['cur'] : 0;  <span>//</span><span>指向第一个结点</span>
            <span>while</span>(<span>$k</span> < <span>$i</span><span>)
            {
                </span><span>//</span><span>记录当前cur和下一个cur</span>
                <span>$index</span> = <span>$cur</span><span>;  
                </span><span>$cur</span> = <span>$this</span>->arr[<span>$index</span>]['cur'<span>];
                </span>++<span>$k</span><span>;
            }
            </span><span>//</span><span>改变指针指向</span>
            <span>$this</span>->arr[<span>$index</span>]['cur'] = <span>$j</span><span>;
            </span><span>$this</span>->arr[<span>$j</span>]['cur'] = <span>$cur</span><span>;

            </span>++<span>$this</span>->arr[0]['data'<span>];
            </span><span>return</span> <span>true</span><span>;

        }

        </span><span>/*</span><span>*
          * 删除元素:
          * 初始化$j从1开始
          * 当$j<$i，遍历链表
          * 将i位置删除
          * @param Int $i 需要删除第几个元素
          * @return bool
          </span><span>*/</span>
        <span>public</span> <span>function</span> delete_elem(<span>$i</span><span>)
        {
            </span><span>$len</span> = <span>$this</span>->arr[0]['data'<span>];
            </span><span>if</span>(<span>$i</span> < 1 || <span>$i</span> > <span>$len</span><span>) 
                </span><span>return</span> <span>false</span><span>;
            
            </span><span>$k</span> = 1<span>;
            </span><span>$index</span> = 0<span>; 
            </span><span>$cur</span> = !<span>empty</span>(<span>$this</span>->arr[0]['cur']) ? <span>$this</span>->arr[0]['cur'] : 0;  <span>//</span><span>指向第一个结点</span>
            <span>while</span>(<span>$k</span> < <span>$i</span><span>)
            {
                </span><span>//</span><span>记录当前cur和下一个cur</span>
                <span>$index</span> = <span>$cur</span><span>;  
                </span><span>$cur</span> = <span>$this</span>->arr[<span>$index</span>]['cur'<span>];
                </span>++<span>$k</span><span>;
            }
            </span><span>//</span><span>改变指针指向</span>
            <span>$this</span>->arr[<span>$index</span>]['cur'] = <span>$this</span>->arr[<span>$cur</span>]['cur'<span>];
        
            </span><span>$this</span>->free(<span>$cur</span><span>);
            </span><span>unset</span>(<span>$this</span>->arr[<span>$cur</span><span>]);
            </span>--<span>$this</span>->arr[0]['data'<span>];
            </span><span>return</span> <span>true</span><span>;
        }

        </span><span>/*</span><span>*
          * 获取空闲的结点下标，也就是相当于申请一个空结点
          * @return 
          </span><span>*/</span>
        <span>private</span> <span>function</span><span> malloc()
        {
            </span><span>if</span>(<span>empty</span>(<span>$this</span>-><span>space_arr))
                </span><span>return</span> <span>false</span><span>;
            </span><span>return</span> <span>array_pop</span>(<span>$this</span>-><span>space_arr);
        }

        </span><span>/*</span><span>*
          * 释放结点
          * @param Int $cur 需要回收的结点下标
          </span><span>*/</span>
        <span>private</span> <span>function</span> free(<span>$cur</span><span>)
        {
            </span><span>array_push</span>(<span>$this</span>->space_arr, <span>$cur</span><span>);
        }

        </span><span>/*</span><span>*
          * 打印
          * @return 
          </span><span>*/</span>    
        <span>public</span> <span>function</span><span> print_arr()
        {
            </span><span>$i</span> = 0<span>;
            </span><span>if</span>(!<span>empty</span>(<span>$this</span>->arr[0]['data'<span>]))
            {    </span><span>while</span>(<span>$this</span>->arr[<span>$i</span>]['cur'<span>])
                {
                    </span><span>$i</span> = <span>$this</span>->arr[<span>$i</span>]['cur'<span>];
                    </span><span>echo</span> <span>$this</span>->arr[<span>$i</span>]['data'].' '<span>;
                }
            }
        }

        </span><span>/*</span><span>*
          * 获取长度
          * @return 
          </span><span>*/</span>    
        <span>public</span> <span>function</span><span> get_len()
        {
           </span><span>return</span> <span>array</span>('num' => <span>$this</span>->arr[0]['data'] , 'len' => <span>$this</span>-><span>len);
        }
    }

    </span><span>$link</span> = <span>new</span> Simple_Link(10,<span>array</span><span>());
    </span><span>var_dump</span>(<span>$link</span>->insert_elem(1,5<span>));
    </span><span>var_dump</span>(<span>$link</span>->insert_elem(2,4<span>));
    </span><span>var_dump</span>(<span>$link</span>->insert_elem(1,6<span>));
    </span><span>var_dump</span>(<span>$link</span>->delete_elem(3<span>));
    </span><span>echo</span> <span>$link</span>-><span>print_arr();
    </span><span>var_dump</span>(<span>$link</span>-><span>get_len());
        
        输出：
        </span><span>boolean</span> <span>true</span>
        <span>boolean</span> <span>true</span>
        <span>boolean</span> <span>true</span>
        <span>boolean</span> <span>true</span>
        6 5
        <span>array</span> (size=2<span>)
          </span>'num' => int 2
          'len' => int 10

 

Statement：
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Previous article：[PHP学习日志]简单Session的使用，php学习日志sessionNext article：Yii2的相关学习记录，alert等美化、confirm异步、session中的flash及小部件的使用（六），yii2confirm

Related articles

See more