数据结构，数据结构与算法_PHP教程
数据结构，数据结构与算法
线性表：零个或多个数据元素的有限序列（注：以下都是用的整型数据模拟）
一 顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
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> <= <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
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
AI Hentai Generator
Generate AI Hentai for free.
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
Compare complex data structures using Java function comparison
Apr 19, 2024 pm 10:24 PM
When using complex data structures in Java, Comparator is used to provide a flexible comparison mechanism. Specific steps include: defining the comparator class, rewriting the compare method to define the comparison logic. Create a comparator instance. Use the Collections.sort method, passing in the collection and comparator instances.
In-depth understanding of reference types in Go language
Feb 21, 2024 pm 11:36 PM
Reference types are a special data type in the Go language. Their values do not directly store the data itself, but the address of the stored data. In the Go language, reference types include slices, maps, channels, and pointers. A deep understanding of reference types is crucial to understanding the memory management and data transfer methods of the Go language. This article will combine specific code examples to introduce the characteristics and usage of reference types in Go language. 1. Slices Slices are one of the most commonly used reference types in the Go language.
Java data structures and algorithms: in-depth explanation
May 08, 2024 pm 10:12 PM
Data structures and algorithms are the basis of Java development. This article deeply explores the key data structures (such as arrays, linked lists, trees, etc.) and algorithms (such as sorting, search, graph algorithms, etc.) in Java. These structures are illustrated through practical examples, including using arrays to store scores, linked lists to manage shopping lists, stacks to implement recursion, queues to synchronize threads, and trees and hash tables for fast search and authentication. Understanding these concepts allows you to write efficient and maintainable Java code.
PHP data structure: The balance of AVL trees, maintaining an efficient and orderly data structure
Jun 03, 2024 am 09:58 AM
AVL tree is a balanced binary search tree that ensures fast and efficient data operations. To achieve balance, it performs left- and right-turn operations, adjusting subtrees that violate balance. AVL trees utilize height balancing to ensure that the height of the tree is always small relative to the number of nodes, thereby achieving logarithmic time complexity (O(logn)) search operations and maintaining the efficiency of the data structure even on large data sets.
Full analysis of Java collection framework: dissecting data structure and revealing the secret of efficient storage
Feb 23, 2024 am 10:49 AM
Overview of Java Collection Framework The Java collection framework is an important part of the Java programming language. It provides a series of container class libraries that can store and manage data. These container class libraries have different data structures to meet the data storage and processing needs in different scenarios. The advantage of the collection framework is that it provides a unified interface, allowing developers to operate different container class libraries in the same way, thereby reducing the difficulty of development. Data structures of the Java collection framework The Java collection framework contains a variety of data structures, each of which has its own unique characteristics and applicable scenarios. The following are several common Java collection framework data structures: 1. List: List is an ordered collection that allows elements to be repeated. Li
Learn the secrets of Go language data structures in depth
Mar 29, 2024 pm 12:42 PM
In-depth study of the mysteries of Go language data structure requires specific code examples. As a concise and efficient programming language, Go language also shows its unique charm in processing data structures. Data structure is a basic concept in computer science, which aims to organize and manage data so that it can be accessed and manipulated more efficiently. By in-depth learning the mysteries of Go language data structure, we can better understand how data is stored and operated, thereby improving programming efficiency and code quality. 1. Array Array is one of the simplest data structures
Java Map Revealed: Tips and Strategies for Fast Data Access
Feb 19, 2024 pm 06:21 PM
JavaMap is a key-value pair-based data structure that allows developers to quickly store and retrieve data. The keys of a Map can be any object, and the values can be any type of data. Each key in the Map can only be associated with at most one value. If multiple values are set for the same key, only the last set value will be retained. There are two main implementations of Map: HashMap: uses a hash table to store key-value pairs. The performance of HashMap depends on how the hash table is implemented, and in most cases HashMap performs better than TreeMap. TreeMap: uses red-black trees to store key-value pairs. The performance of TreeMap is similar to HashMap, but in some cases, the performance of TreeMap can be
PHP SPL data structures: Inject speed and flexibility into your projects
Feb 19, 2024 pm 11:00 PM
Overview of the PHPSPL Data Structure Library The PHPSPL (Standard PHP Library) data structure library contains a set of classes and interfaces for storing and manipulating various data structures. These data structures include arrays, linked lists, stacks, queues, and sets, each of which provides a specific set of methods and properties for manipulating data. Arrays In PHP, an array is an ordered collection that stores a sequence of elements. The SPL array class provides enhanced functions for native PHP arrays, including sorting, filtering, and mapping. Here is an example of using the SPL array class: useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array
