数据结构，数据结构与算法
数据结构，数据结构与算法
线性表：零个或多个数据元素的有限序列（注：以下都是用的整型数据模拟）
一 顺序存储结构（用一段地址连续的存储单元一次存储线性表的数据元素）
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
Outils d'IA chauds
Undresser.AI Undress
Application basée sur l'IA pour créer des photos de nu réalistes
AI Clothes Remover
Outil d'IA en ligne pour supprimer les vêtements des photos.
Undress AI Tool
Images de déshabillage gratuites
Clothoff.io
Dissolvant de vêtements AI
AI Hentai Generator
Générez AI Hentai gratuitement.
Article chaud
Outils chauds
Bloc-notes++7.3.1
Éditeur de code facile à utiliser et gratuit
SublimeText3 version chinoise
Version chinoise, très simple à utiliser
Envoyer Studio 13.0.1
Puissant environnement de développement intégré PHP
Dreamweaver CS6
Outils de développement Web visuel
SublimeText3 version Mac
Logiciel d'édition de code au niveau de Dieu (SublimeText3)
Comparez des structures de données complexes à l'aide de la comparaison de fonctions Java
Apr 19, 2024 pm 10:24 PM
Lors de l'utilisation de structures de données complexes en Java, Comparator est utilisé pour fournir un mécanisme de comparaison flexible. Les étapes spécifiques comprennent : la définition d’une classe de comparaison et la réécriture de la méthode de comparaison pour définir la logique de comparaison. Créez une instance de comparaison. Utilisez la méthode Collections.sort, en transmettant les instances de collection et de comparateur.
Structures de données et algorithmes Java : explication détaillée
May 08, 2024 pm 10:12 PM
Les structures de données et les algorithmes sont à la base du développement Java. Cet article explore en profondeur les structures de données clés (telles que les tableaux, les listes chaînées, les arbres, etc.) et les algorithmes (tels que le tri, la recherche, les algorithmes graphiques, etc.) en Java. Ces structures sont illustrées par des exemples pratiques, notamment l'utilisation de tableaux pour stocker les scores, de listes chaînées pour gérer les listes de courses, de piles pour implémenter la récursion, de files d'attente pour synchroniser les threads, ainsi que d'arbres et de tables de hachage pour une recherche et une authentification rapides. Comprendre ces concepts vous permet d'écrire du code Java efficace et maintenable.
Compréhension approfondie des types de référence en langage Go
Feb 21, 2024 pm 11:36 PM
Les types de référence sont un type de données spécial dans le langage Go. Leurs valeurs ne stockent pas directement les données elles-mêmes, mais l'adresse des données stockées. Dans le langage Go, les types de référence incluent des tranches, des cartes, des canaux et des pointeurs. Une compréhension approfondie des types de référence est cruciale pour comprendre les méthodes de gestion de la mémoire et de transfert de données du langage Go. Cet article combinera des exemples de code spécifiques pour présenter les caractéristiques et l'utilisation des types de référence dans le langage Go. 1. Tranches Les tranches sont l'un des types de référence les plus couramment utilisés dans le langage Go.
Structure de données PHP : l'équilibre des arborescences AVL, maintenant une structure de données efficace et ordonnée
Jun 03, 2024 am 09:58 AM
L'arbre AVL est un arbre de recherche binaire équilibré qui garantit des opérations de données rapides et efficaces. Pour atteindre l'équilibre, il effectue des opérations de virage à gauche et à droite, en ajustant les sous-arbres qui violent l'équilibre. Les arbres AVL utilisent l'équilibrage de hauteur pour garantir que la hauteur de l'arbre est toujours petite par rapport au nombre de nœuds, réalisant ainsi des opérations de recherche de complexité temporelle logarithmique (O (logn)) et maintenant l'efficacité de la structure de données même sur de grands ensembles de données.
Analyse complète du cadre de collecte Java : disséquer la structure des données et révéler le secret d'un stockage efficace
Feb 23, 2024 am 10:49 AM
Présentation de Java Collection Framework L'infrastructure de collection Java est une partie importante du langage de programmation Java. Elle fournit une série de bibliothèques de classes conteneur qui peuvent stocker et gérer des données. Ces bibliothèques de classes de conteneurs ont différentes structures de données pour répondre aux besoins de stockage et de traitement des données dans différents scénarios. L'avantage du framework de collection est qu'il fournit une interface unifiée, permettant aux développeurs d'exploiter différentes bibliothèques de classes de conteneurs de la même manière, réduisant ainsi la difficulté de développement. Structures de données de l'infrastructure de collection Java L'infrastructure de collection Java contient diverses structures de données, chacune ayant ses propres caractéristiques et scénarios applicables. Voici plusieurs structures de données courantes du cadre de collection Java : 1. Liste : Liste est une collection ordonnée qui permet de répéter des éléments. Li
Apprenez en profondeur les secrets des structures de données du langage Go
Mar 29, 2024 pm 12:42 PM
Une étude approfondie des mystères de la structure des données du langage Go nécessite des exemples de code spécifiques. En tant que langage de programmation concis et efficace, le langage Go montre également son charme unique dans le traitement des structures de données. La structure des données est un concept de base en informatique, qui vise à organiser et gérer les données afin qu'elles puissent être consultées et manipulées plus efficacement. En apprenant en profondeur les mystères de la structure des données du langage Go, nous pouvons mieux comprendre comment les données sont stockées et exploitées, améliorant ainsi l'efficacité de la programmation et la qualité du code. 1. Array Array est l'une des structures de données les plus simples
Carte Java révélée : conseils et stratégies pour un accès rapide aux données
Feb 19, 2024 pm 06:21 PM
JavaMap est une structure de données basée sur des paires clé-valeur qui permet aux développeurs de stocker et de récupérer rapidement des données. Les clés d'une Map peuvent être n'importe quel objet et les valeurs peuvent être n'importe quel type de données. Chaque clé de la Map ne peut être associée qu'à au plus une valeur. Si plusieurs valeurs sont définies pour la même clé, seule la dernière valeur définie sera conservée. Il existe deux implémentations principales de Map : HashMap : utilise une table de hachage pour stocker les paires clé-valeur. Les performances de HashMap dépendent de la manière dont la table de hachage est implémentée et, dans la plupart des cas, HashMap fonctionne mieux que TreeMap. TreeMap : utilise des arbres rouge-noir pour stocker les paires clé-valeur. Les performances de TreeMap sont similaires à celles de HashMap, mais dans certains cas, les performances de TreeMap peuvent être
Structures de données PHP SPL : injectez de la vitesse et de la flexibilité dans vos projets
Feb 19, 2024 pm 11:00 PM
Présentation de la bibliothèque de structures de données PHPSPL La bibliothèque de structures de données PHPSPL (Standard PHP Library) contient un ensemble de classes et d'interfaces pour stocker et manipuler diverses structures de données. Ces structures de données comprennent des tableaux, des listes chaînées, des piles, des files d'attente et des ensembles, chacun fournissant un ensemble spécifique de méthodes et de propriétés pour manipuler les données. Tableaux En PHP, un tableau est une collection ordonnée qui stocke une séquence d'éléments. La classe de tableau SPL fournit des fonctions améliorées pour les tableaux PHP natifs, notamment le tri, le filtrage et le mappage. Voici un exemple d'utilisation de la classe array SPL : useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array
