線形テーブル: 0 個以上のデータ要素の有限シーケンス (注: 以下はすべて整数データでシミュレートされています)
順次ストレージ構造 (線形テーブルのデータ要素を格納するために連続アドレスを持つストレージ ユニットを使用します)
1.1 3 つの属性: ストレージスペースの開始位置、最大ストレージ容量、現在の長さ
注: 配列の長さは線形テーブルを格納するストレージスペースの長さですが、言語は動的に容量を増やすことができるため、パフォーマンスの低下を軽減できます。
線形テーブルの長さはデータ要素の数です。
線形テーブルは、配列 0 の位置に対応して 1 からカウントされます。
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
2つのリンクリストの格納構造(n個のノードがリンクリストにリンクされている)
2.1 単一のリンクリスト(配列でシミュレート) )
2.1.1 リンクリストの最初のノードの格納場所は先頭ポインタ(通常はリンクリストの操作を容易にするために、単一リンクリストの最初のノードの前にヘッドノードが付けられます)
ヘッドポインタに注意してください: リンクリストの最初のノードへのポインタの場合。 head ノード、これはヘッド ノードへのポインタです。リンクされたリストが空であるかどうかに関係なく、ヘッド ポインタは最初の要素のノードの前に配置されます。
上記は、データ構造を含む線形テーブル学習 (PHP シミュレーション) の側面を紹介しました。PHP チュートリアルに興味のある友人に役立つことを願っています。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
