数据结构,数据结构与算法
数据结构,数据结构与算法
线性表:零个或多个数据元素的有限序列(注:以下都是用的整型数据模拟)
一 顺序存储结构(用一段地址连续的存储单元一次存储线性表的数据元素)
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

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen



Bei der Verwendung komplexer Datenstrukturen in Java wird Comparator verwendet, um einen flexiblen Vergleichsmechanismus bereitzustellen. Zu den spezifischen Schritten gehören: Definieren einer Komparatorklasse und Umschreiben der Vergleichsmethode, um die Vergleichslogik zu definieren. Erstellen Sie eine Komparatorinstanz. Verwenden Sie die Methode „Collections.sort“ und übergeben Sie die Sammlungs- und Komparatorinstanzen.

Datenstrukturen und Algorithmen sind die Grundlage der Java-Entwicklung. In diesem Artikel werden die wichtigsten Datenstrukturen (wie Arrays, verknüpfte Listen, Bäume usw.) und Algorithmen (wie Sortier-, Such-, Diagrammalgorithmen usw.) ausführlich untersucht. Diese Strukturen werden anhand praktischer Beispiele veranschaulicht, darunter die Verwendung von Arrays zum Speichern von Bewertungen, verknüpfte Listen zum Verwalten von Einkaufslisten, Stapel zum Implementieren von Rekursionen, Warteschlangen zum Synchronisieren von Threads sowie Bäume und Hash-Tabellen für schnelle Suche und Authentifizierung. Wenn Sie diese Konzepte verstehen, können Sie effizienten und wartbaren Java-Code schreiben.

Referenztypen sind ein spezieller Datentyp in der Go-Sprache. Ihre Werte speichern nicht direkt die Daten selbst, sondern die Adresse der gespeicherten Daten. In der Go-Sprache umfassen Referenztypen Slices, Karten, Kanäle und Zeiger. Ein tiefes Verständnis der Referenztypen ist entscheidend für das Verständnis der Speicherverwaltungs- und Datenübertragungsmethoden der Go-Sprache. In diesem Artikel werden spezifische Codebeispiele kombiniert, um die Merkmale und Verwendung von Referenztypen in der Go-Sprache vorzustellen. 1. Slices Slices sind einer der am häufigsten verwendeten Referenztypen in der Go-Sprache.

Der AVL-Baum ist ein ausgewogener binärer Suchbaum, der schnelle und effiziente Datenoperationen gewährleistet. Um ein Gleichgewicht zu erreichen, führt es Links- und Rechtsdrehungen durch und passt Teilbäume an, die das Gleichgewicht verletzen. AVL-Bäume nutzen den Höhenausgleich, um sicherzustellen, dass die Höhe des Baums im Verhältnis zur Anzahl der Knoten immer klein ist, wodurch Suchoperationen mit logarithmischer Zeitkomplexität (O(logn)) erreicht werden und die Effizienz der Datenstruktur auch bei großen Datensätzen erhalten bleibt.

Überblick über das Java Collection Framework Das Java Collection Framework ist ein wichtiger Teil der Programmiersprache Java. Es stellt eine Reihe von Containerklassenbibliotheken bereit, die Daten speichern und verwalten können. Diese Containerklassenbibliotheken verfügen über unterschiedliche Datenstrukturen, um den Datenspeicher- und -verarbeitungsanforderungen in verschiedenen Szenarien gerecht zu werden. Der Vorteil des Sammlungsframeworks besteht darin, dass es eine einheitliche Schnittstelle bietet, die es Entwicklern ermöglicht, verschiedene Containerklassenbibliotheken auf die gleiche Weise zu betreiben, wodurch die Entwicklungsschwierigkeiten verringert werden. Datenstrukturen des Java-Sammlungsframeworks Das Java-Sammlungsframework enthält eine Vielzahl von Datenstrukturen, von denen jede ihre eigenen einzigartigen Eigenschaften und anwendbaren Szenarien aufweist. Im Folgenden sind einige gängige Datenstrukturen des Java Collection Frameworks aufgeführt: 1. Liste: Liste ist eine geordnete Sammlung, die die Wiederholung von Elementen ermöglicht. Li

Eine eingehende Untersuchung der Geheimnisse der Datenstruktur der Go-Sprache erfordert spezifische Codebeispiele. Als prägnante und effiziente Programmiersprache zeigt die Go-Sprache auch ihren einzigartigen Charme bei der Verarbeitung von Datenstrukturen. Datenstruktur ist ein Grundkonzept der Informatik, das darauf abzielt, Daten so zu organisieren und zu verwalten, dass sie effizienter abgerufen und bearbeitet werden können. Indem wir uns eingehend mit den Geheimnissen der Datenstruktur der Go-Sprache befassen, können wir besser verstehen, wie Daten gespeichert und verarbeitet werden, und so die Programmiereffizienz und Codequalität verbessern. 1. Array Array ist eine der einfachsten Datenstrukturen

JavaMap ist eine auf Schlüssel-Wert-Paaren basierende Datenstruktur, die es Entwicklern ermöglicht, Daten schnell zu speichern und abzurufen. Die Schlüssel einer Karte können beliebige Objekte sein und die Werte können beliebige Datentypen sein. Jeder Schlüssel in der Karte kann höchstens einem Wert zugeordnet werden. Wenn mehrere Werte für denselben Schlüssel festgelegt werden, wird nur der zuletzt festgelegte Wert beibehalten. Es gibt zwei Hauptimplementierungen von Map: HashMap: verwendet eine Hash-Tabelle zum Speichern von Schlüssel-Wert-Paaren. Die Leistung von HashMap hängt davon ab, wie die Hash-Tabelle implementiert wird. In den meisten Fällen ist die Leistung von HashMap besser als die von TreeMap. TreeMap: verwendet Rot-Schwarz-Bäume zum Speichern von Schlüssel-Wert-Paaren. Die Leistung von TreeMap ähnelt der von HashMap, in einigen Fällen kann die Leistung von TreeMap jedoch ähnlich sein

Überblick über die PHPSPL-Datenstrukturbibliothek Die PHPSPL-Datenstrukturbibliothek (Standard PHP Library) enthält eine Reihe von Klassen und Schnittstellen zum Speichern und Bearbeiten verschiedener Datenstrukturen. Zu diesen Datenstrukturen gehören Arrays, verknüpfte Listen, Stapel, Warteschlangen und Mengen, von denen jede einen bestimmten Satz von Methoden und Eigenschaften zum Bearbeiten von Daten bereitstellt. Arrays In PHP ist ein Array eine geordnete Sammlung, die eine Folge von Elementen speichert. Die SPL-Array-Klasse bietet erweiterte Funktionen für native PHP-Arrays, einschließlich Sortierung, Filterung und Zuordnung. Hier ist ein Beispiel für die Verwendung der SPL-Array-Klasse: useSplArrayObject;$array=newArrayObject(["foo","bar","baz"]);$array
