目錄
数据结构,数据结构与算法
首頁 後端開發 php教程 数据结构,数据结构与算法_PHP教程

数据结构,数据结构与算法_PHP教程

Jul 12, 2016 am 08:54 AM
資料結構

数据结构,数据结构与算法

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

一 顺序存储结构(用一段地址连续的存储单元一次存储线性表的数据元素)
  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           
登入後複製

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/1119062.htmlTechArticle数据结构,数据结构与算法 线性表:零个或多个数据元素的有限序列(注:以下都是用的整型数据模拟) 一 顺序存储结构(用一段地址连...
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前 By 尊渡假赌尊渡假赌尊渡假赌

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

使用Java函數比較進行複雜資料結構比較 使用Java函數比較進行複雜資料結構比較 Apr 19, 2024 pm 10:24 PM

Java中比較複雜資料結構時,使用Comparator提供靈活的比較機制。具體步驟包括:定義比較器類,重寫compare方法定義比較邏輯。建立比較器實例。使用Collections.sort方法,傳入集合和比較器實例。

Java資料結構與演算法:深入詳解 Java資料結構與演算法:深入詳解 May 08, 2024 pm 10:12 PM

資料結構與演算法是Java開發的基礎,本文深入探討Java中的關鍵資料結構(如陣列、鍊錶、樹等)和演算法(如排序、搜尋、圖演算法等)。這些結構透過實戰案例進行說明,包括使用陣列儲存分數、使用鍊錶管理購物清單、使用堆疊實現遞歸、使用佇列同步執行緒以及使用樹和雜湊表進行快速搜尋和身份驗證等。理解這些概念可以編寫高效且可維護的Java程式碼。

深入了解Go語言中的引用類型 深入了解Go語言中的引用類型 Feb 21, 2024 pm 11:36 PM

引用類型在Go語言中是一種特殊的資料類型,它們的值並非直接儲存資料本身,而是儲存資料的位址。在Go語言中,引用型別包括slices、maps、channels和指標。深入了解引用類型對於理解Go語言的記憶體管理和資料傳遞方式至關重要。本文將結合具體的程式碼範例,介紹Go語言中引用類型的特點和使用方法。 1.切片(Slices)切片是Go語言中最常用的引用類型之一

PHP資料結構:AVL樹的平衡之道,維持高效有序的資料結構 PHP資料結構:AVL樹的平衡之道,維持高效有序的資料結構 Jun 03, 2024 am 09:58 AM

AVL樹是一種平衡二元搜尋樹,確保快速且有效率的資料操作。為了實現平衡,它執行左旋和右旋操作,調整違反平衡的子樹。 AVL樹利用高度平衡,確保樹的高度相對於節點數始終較小,從而實現對數時間複雜度(O(logn))的查找操作,即使在大型資料集上也能保持資料結構的效率。

Java集合框架全解析:解剖資料結構,揭秘高效率儲存之道 Java集合框架全解析:解剖資料結構,揭秘高效率儲存之道 Feb 23, 2024 am 10:49 AM

Java集合框架概述Java集合框架是Java程式語言的重要組成部分,它提供了一系列可以儲存和管理資料的容器類別庫。這些容器類別庫具有不同的資料結構,可以滿足不同場景下的資料儲存和處理需求。集合框架的優點在於它提供了統一的接口,使得開發人員可以使用相同的方式來操作不同的容器類別庫,從而降低了開發難度。 Java集合框架的資料結構Java集合框架中包含多種資料結構,每種資料結構都有其獨特的特性和適用場景。以下是幾種常見的Java集合框架資料結構:1.List:List是一個有序的集合,它允許元素重複。 Li

深入學習Go語言資料結構的奧秘 深入學習Go語言資料結構的奧秘 Mar 29, 2024 pm 12:42 PM

深入學習Go語言資料結構的奧秘,需要具體程式碼範例Go語言作為一門簡潔、高效的程式語言,在處理資料結構方面也展現了其獨特的魅力。數據結構是電腦科學中的基礎概念,它旨在組織和管理數據,使得數據能夠更有效地被存取和操作。透過深入學習Go語言資料結構的奧秘,我們可以更好地理解資料的儲存方式和操作方法,從而提高程式效率和程式碼品質。一、數組數組是最簡單的資料結構之一

Java Map揭秘:實現資料快速存取的技巧與策略 Java Map揭秘:實現資料快速存取的技巧與策略 Feb 19, 2024 pm 06:21 PM

JavaMap是一個基於鍵值對的資料結構,它允許開發人員快速儲存和檢索資料。 Map的鍵可以是任何對象,而值可以是任何類型的資料。 Map中每個鍵最多只能與一個值相關聯,如果對同一個鍵設定多個值,則只會保留最後設定的值。 Map有兩種主要實作:HashMap:使用散列表來儲存鍵值對。 HashMap的效能取決於散列表的實作方式,在大多數情況下,HashMap的效能優於TreeMap。 TreeMap:使用紅黑樹來儲存鍵值對。 TreeMap的效能與HashMap相似,但在某些情況下,TreeMap的效能可

PHP SPL 資料結構:為你的專案注入速度與彈性 PHP SPL 資料結構:為你的專案注入速度與彈性 Feb 19, 2024 pm 11:00 PM

PHPSPL資料結構庫概述PHPSPL(標準php庫)資料結構庫包含一組類別和接口,用於儲存和操作各種資料結構。這些資料結構包括數組、鍊錶、堆疊、佇列和集合,每個資料結構都提供了一組特定的方法和屬性,用於操縱資料。數組在PHP中,數組是儲存一系列元素的有序集合。 SPL數組類別提供了對原生的PHP數組進行加強的功能,包括排序、過濾和映射。以下是使用SPL陣列類別的範例:useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array

See all articles