Community Learn Tools Library Leisure
search
English
Home > Backend Development > PHP Tutorial > Data structure --- Linear table learning (php simulation) Data structure and algorithm Data structure Yan Weimin c# tree data structure

Data structure --- Linear table learning (php simulation) Data structure and algorithm Data structure Yan Weimin c# tree data structure

WBOY
Release： 2016-07-29 08:54:03
Original
1112 people have browsed it

Linear table: a finite sequence of zero or more data elements (Note: The following are all simulated with integer data)

A sequential storage structure (use a storage unit with a continuous address to store the data elements of the linear table at a time)
1.1 Three attributes: the starting position of the storage space; the maximum storage capacity; the current length
Note: The array length is the length of the storage space to store the linear table (generally unchanged), but the language can dynamically increase the capacity, which will bring To reduce performance loss;
The length of the linear table is the number of data elements;
The linear table starts counting from 1, corresponding to the position of array 0
1.2 Obtaining elements, inserting elements, and deleting elements (shown in the code)

1.3 Sequential structure Advantages and disadvantages:
Advantages: No need to add additional storage space to express the logical relationship between elements in the table; elements at any position in the table can be quickly accessed
Disadvantages: Insertion and deletion operations require moving a large number of elements; when linear When the table length is large, it is difficult to determine the storage space capacity; resulting in storage space 'fragmentation'

<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());
Copy after login

<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
Copy after login

Two linked list storage structure (n nodes are linked into a linked list)
　　2.1 Single linked list (simulated with arrays) )
　　2.1.1 The storage location of the first node in the linked list is the head pointer (usually in order to facilitate the operation of the linked list, a head node is attached before the first node of the singly linked list)
　　Note the head pointer: points to The pointer to the first node of the linked list. If the linked list has a head node, this is the pointer to the head node; no matter whether the linked list is empty or not, the head pointer is not empty. Head node: placed before the node of the first element. 

<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>
Copy after login

The above introduces the data structure --- linear table learning (php simulation), including the data structure --- aspects. I hope it will be helpful to friends who are interested in PHP tutorials.

Related labels：
data structure
source：php.cn
Previous article：PHP PSR-3 日志接口规范 中文版 Next article：Use php to write ftp crawler php ftp server ftp php code phpstorm ft
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Latest Issues
PHP arrays obtained from URL parameters do not behave as expected I have a URL parameter that contains the category ID and I want to treat it as an array li...
From 2024-04-06 22:09:02
0
1
1428
Set a private member of a class as a constructor parameter classFoo{#one#two#three#four#five#six#seven#eight#nine#ten#eleven#twelve#thirteen#fourteen...
From 2024-04-06 21:48:47
0
1
637
Regular expression to match words I have a script where I am trying to match new job names with existing job names in a data...
From 2024-04-06 21:24:04
0
1
606
Select woocommerce related products using custom taxonomy with 3 level hierarchy I have a woocommerce store with a custom classification of "Sports". The classif...
From 2024-04-06 20:05:30
0
1
544
Calculate the sum of fields in another table using MySQL SQL query I have a schema like this: User table with attributes "user_id" and "userna...
From 2024-04-06 19:39:29
0
1
441
Related Topics
More>
Popular Recommendations
Popular Tutorials
More>
Related Tutorials
Popular Recommendations
Latest courses
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template