搜尋
首頁後端開發php教程資料結構 --- 線性表學習（php模擬） 資料結構與演算法 資料結構 嚴蔚敏 c# 樹狀資料結
資料結構 --- 線性表學習（php模擬） 資料結構與演算法 資料結構 嚴蔚敏 c# 樹狀資料結
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Jul 29, 2016 am 08:54 AM
資料結構

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

一順序儲存結構（用一段位址連續的儲存單元一次儲存線性表的資料元素）
　　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> $len<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> $i > <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> $i > (<span>$this</span>->num+1)) <span>//</span><span>i不在范围之内</span><span>return</span><span>false</span><span>;
            </span><span>if</span> (<span>$i</span> $this->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> $i > <span>$this</span>->num) <span>//</span><span>删除位置不正确</span><span>return</span><span>false</span><span>;
            </span><span>if</span>(<span>$i</span> $this->num) <span>//</span><span>删除位置不是表尾</span><span>            {
                </span><span>for</span>(<span>$k</span> = <span>$i</span>; <span>$k</span> $this->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> $length; ++<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> $len-<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<span>*/</span><span>public</span><span>function</span> get_elem(<span>$i</span><span>)
        {
            </span><span>if</span>(<span>$i</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> $i<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<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> $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> $i<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<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> $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> $i<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

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

陳述
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn
相關文章
Java中的二叉树结构详解Java中的二叉树结构详解Jun 16, 2023 am 08:58 AM

二叉树是计算机科学中常见的数据结构，也是Java编程中常用的一种数据结构。本文将详细介绍Java中的二叉树结构。一、什么是二叉树？在计算机科学中，二叉树是一种树形结构，每个节点最多有两个子节点。其中，左侧子节点比父节点小，右侧子节点则比父节点大。在Java编程中，常用二叉树表示排序，搜索以及提高对数据的查询效率。二、Java中的二叉树实现在Java中，二叉树

Python 实现栈的几种方式及其优劣Python 实现栈的几种方式及其优劣May 19, 2023 am 09:37 AM

​​想了解更多关于开源的内容，请访问：​​​​51CTO开源基础软件社区​​​​https://ost.51cto.com​​一、栈的概念栈由一系列对象对象组织的一个集合，这些对象的增加和删除操作都遵循一个“后进先出”（LastInFirstOut，LIFO）的原则。在任何时刻只能向栈中插入一个对象，但只能取得或者删除只能在栈顶进行。比如由书构成的栈，唯一露出封面的书就是顶部的那本，为了拿到其他的书，只能移除压在上面的书，如图：栈的实际应用实际上很多应用程序都会用到栈，比如：网络浏览器将最近浏览

PHP8中会支持的数据结构，将为你的代码提供更大空间PHP8中会支持的数据结构，将为你的代码提供更大空间Jun 21, 2023 am 08:13 AM

PHP是一种广泛使用的脚本语言，被广泛用于Web开发，服务器端编程以及命令行编程等。随着PHP不断更新和发展，它也日益成为一个更强大的编程工具，为用户提供了更多的功能和更多的工具来开发高质量的应用程序。其中，数据结构是一个非常重要的领域，一种有效的数据结构可以大大提高程序的性能和可读性。在这篇文章中，我们将讨论PHP8中支持的新数据结构，这些新的数据结构将让

如何解决Java中遇到的代码性能优化问题如何解决Java中遇到的代码性能优化问题Jun 29, 2023 am 10:13 AM

如何解决Java中遇到的代码性能优化问题随着现代软件应用的复杂性和数据量的增加，对于代码性能的需求也变得越来越高。在Java开发中，我们经常会遇到一些性能瓶颈，如何解决这些问题成为了开发者们关注的焦点。本文将介绍一些常见的Java代码性能优化问题，并提供一些解决方案。一、避免过多的对象创建和销毁在Java中，对象的创建和销毁是需要耗费资源的。因此，当一个方法

Java语言中的数据结构与算法介绍Java语言中的数据结构与算法介绍Jun 10, 2023 pm 01:37 PM

随着计算机科学的不断发展，数据结构与算法成为了计算机科学领域中最为基础、重要的模块。数据结构是一种组织和存储数据的方式，它是解决问题的基础。算法则是计算机科学的核心，它是指在计算机程序中解决问题的方法和技术。Java作为一种广泛应用的编程语言，其自带的数据结构和算法库是非常强大的，赋予了开发人员更多的力量。一、数据结构Java中提供了多种数据结构，包括数组

go语言有哪些数据结构go语言有哪些数据结构Dec 16, 2022 pm 02:00 PM

go语言数据结构有四大类：1、基础类型，包括整型（有符号和无符号整数）、浮点数、复数、字符串（由不可变的字节序列构成）、布尔值（只有true和false两个值）；2、聚合类型，包括数组、结构体（是由任意个任意类型的变量组合在一起的数据类型）；3、引用类型，包括指针、slice（是一个拥有相同元素的可变长度序列）、map、function、channel；4、接口类型。

c语言中数据结构是什么？常见数据结构有哪些？c语言中数据结构是什么？常见数据结构有哪些？Nov 03, 2020 am 11:38 AM

c语言中，数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它是计算机存储、组织数据的方式；常见数据结构有：线性数据结构（数组、链表、栈、队列和线性表）、树形结构（二叉树、完全二叉树、二叉查找树、堆）、图形结构（有向图和无向图）。

Java语言常见算法实现方法Java语言常见算法实现方法Jun 11, 2023 pm 05:51 PM

Java语言是目前应用最广泛的编程语言之一，在计算机领域中应用广泛。在Java中，算法是一种非常重要的概念，从最初的排序算法到数据结构和算法的实现，都涉及到了Java语言的一些常用方法。本文将重点讲解Java语言中常见的算法实现方法，包括排序算法、搜索算法、字符串匹配算法以及树形结构的处理方法等，以便初学者更好的掌握Java语言的算法实现。一、排序算法排序算

See all articles

熱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.能量晶體解釋及其做什麼（黃色晶體）
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫：如何復興隊友
4 週前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險：如何獲得巨型種子
4 週前By尊渡假赌尊渡假赌尊渡假赌
擊敗分裂小說需要多長時間？
3 週前ByDDD
R.E.P.O.保存文件位置：在哪里以及如何保護它？
3 週前ByDDD
顯示更多

熱工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

記事本++7.3.1

記事本++7.3.1

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

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合，這些清單在安全評估過程中經常使用，而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表，幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上，他就可以存取所需的每種類型的清單。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

EditPlus 中文破解版

EditPlus 中文破解版

體積小，語法高亮，不支援程式碼提示功能

顯示更多

熱門話題

gmail信箱登陸入口在哪裡
7333
9
Java教學
1627
14
CakePHP 教程
1352
46
Laravel 教程
1264
25
PHP教程
1209
29
顯示更多