資料結構 --- 線性表學習（php模擬）資料結構與演算法資料結構嚴蔚敏 c# 樹狀資料結-php教程-PHP中文網

線性表：零個或多個資料元素的有限序列（註：以下都是用的整型資料模擬）

一順序儲存結構（用一段位址連續的儲存單元一次儲存線性表的資料元素）
　　1.1 三個屬性:儲存空間的起始位置；最大儲存容量；目前長度
　　註：陣列長度是存放線性表的儲存空間的長度（一般是不變的），不過語言可以動態增加容量，會帶來效能損耗；
　　　　線性表長度是資料元素的個數；
　　　　線性表是從1開始數的，對應數組0的位置
　『1.2 獲取元素、插入元素、刪除元素代碼中展示優缺點：

　　　　優點：無須為表示表中元素之間的邏輯關係而增加額外的存儲空間；可以快速地訪問表中任一位置元素

　　　　：插入和刪除操作需要移動大量的元素；當線性缺點錶長度裱花較大時，難以確定儲存空間容量；造成儲存空間'碎片'

<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           </span></span>

登入後複製

以上就介紹了資料結構 --- 線性表學習（php模擬），包含了資料結構,---方面的內容，希望對PHP教程有興趣的朋友有所幫助。