masyarakat Belajar Perpustakaan Alatan Masa lapang
cari
Melayu
Rumah > pembangunan bahagian belakang > tutorial php > 数据结构 --- 线性表学习（php模拟） 数据结构与算法 数据结构 严蔚敏 c# 树形数据结

数据结构 --- 线性表学习（php模拟） 数据结构与算法 数据结构 严蔚敏 c# 树形数据结

WBOY
Lepaskan： 2016-07-29 08:54:03
asal
1115 orang telah melayarinya

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

一 顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
　　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> $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());
Salin selepas log masuk

<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
Salin selepas log masuk

二 链表存储结构（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
Salin selepas log masuk

以上就介绍了数据结构 --- 线性表学习（php模拟），包括了数据结构,---方面的内容，希望对PHP教程有兴趣的朋友有所帮助。

Label berkaitan：
struktur data
sumber：php.cn
Artikel sebelumnya：PHP PSR-3 日志接口规范 中文版 Artikel seterusnya：用php写ftp爬虫 php ftp服务器 ftp php代码 phpstorm ft
Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Artikel terbaru oleh pengarang
Isu terkini
Tatasusunan PHP yang diperoleh daripada parameter URL tidak berkelakuan seperti yang diharapkan Saya mempunyai parameter URL yang mengandungi id kategori dan saya mahu menganggapnya seba...
daripada 2024-04-06 22:09:02
0
1
1428
Tetapkan ahli persendirian kelas sebagai parameter pembina classFoo{#satu#dua#tiga#empat#lima#enam#tujuh#lapan#sembilan#sepuluh#sebelas#dua belas#tig...
daripada 2024-04-06 21:48:47
0
1
637
Ungkapan biasa untuk memadankan perkataan Saya mempunyai skrip di mana saya cuba memadankan nama kerja baharu dengan nama kerja sedi...
daripada 2024-04-06 21:24:04
0
1
606
Pilih produk berkaitan woocommerce menggunakan taksonomi tersuai dengan hierarki 3 tahap Saya mempunyai kedai woocommerce dengan klasifikasi tersuai "Sukan". Klasifikasi...
daripada 2024-04-06 20:05:30
0
1
544
Kira jumlah medan dalam jadual lain menggunakan pertanyaan MySQL SQL Saya mempunyai skema seperti ini: Jadual pengguna dengan atribut "user_id" dan &...
daripada 2024-04-06 19:39:29
0
1
441
Topik-topik yang berkaitan
Lagi>
Cadangan popular
Tutorial Popular
Lagi>
Tutorial berkaitan
Cadangan popular
Kursus terkini
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan