Wondershare EdrawMind
Mindmap-Galerie Grundkonzepte von Datenstrukturen und Algorithmen
- 8
Grundkonzepte von Datenstrukturen und Algorithmen
Einführung in die beiden Hauptaspekte Datenstruktur und Algorithmus. Datenstrukturen umfassen hauptsächlich lineare Strukturen und nichtlineare Strukturen. Zu den linearen Strukturen gehören lineare Listen, Stapel, Warteschlangen, Zeichenfolgen, Arrays, Matrizen, verallgemeinerte Listen usw. Zu den nichtlinearen Strukturen gehören Bäume, Binärbäume, Wälder, Diagramme usw. Zu den Operationen von Datenstrukturen gehören hauptsächlich Suchen und Sortieren. In Bezug auf Algorithmen werden hauptsächlich herkömmliche Algorithmen wie die Divide-and-Conquer-Methode, die dynamische Programmiermethode usw. sowie Data-Mining-Algorithmen und intelligente Optimierungsalgorithmen usw. vorgestellt.
Bearbeitet um 2022-06-30 12:23:27
- Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells
Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
- Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
- Systemanalytiker – Software-Anforderungsentwicklung
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
Grundkonzepte von Datenstrukturen und Algorithmen
- Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells
Welche Preismethoden gibt es für Projektunteraufträge im Rahmen des EPC-Generalvertragsmodells? EPC (Engineering, Procurement, Construction) bedeutet, dass der Generalunternehmer für den gesamten Prozess der Planung, Beschaffung, Konstruktion und Installation des Projekts verantwortlich ist und für die Testbetriebsdienste verantwortlich ist.
- Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen
Die Wissenspunkte, die Java-Ingenieure in jeder Phase beherrschen müssen, werden ausführlich vorgestellt und das Wissen ist umfassend. Ich hoffe, es kann für alle hilfreich sein.
- Systemanalytiker – Software-Anforderungsentwicklung
Das Software-Anforderungs-Engineering ist ein Schlüsselkapitel für Systemanalytiker. Zu den Kapiteln „Anforderungserhebung“ und „Anforderungsanalyse“ gehören häufig Veröffentlichungen.
- Für Sie empfohlen
- Gliederung
![[Studiennotizen] Datenstrukturbaum](https://edrawcloudpublicus.s3.amazonaws.com/work/5635373/2024-5-15/1715741862/thumb.png?x-oss-process=image/resize,w_300,m_lfit)
Anmerkungen zu den Wissenspunkten der linearen Tabellenstapelwarteschlange zur Datenstruktur
- 4
Datenstruktur
Datenstruktur
Konzept
Definition
Es handelt sich um eine Sammlung von Datenelementen und der Beziehung zwischen den Elementen und der Konstruktionsmethode
Die Beziehung zwischen Elementen ist die logische Struktur von Daten
Die Speicherung von Datenelementen und Beziehungen zwischen Elementen wird als Speicherstruktur (/physikalische Struktur) bezeichnet.
Drei Elemente
logische Struktur
Speicherstruktur
Betrieb
Nach logischer Struktur klassifizieren
lineare Struktur
nichtlineare Struktur
Baumstruktur
Diagrammstruktur
Über „Lineare Struktur“
Definition
Wird verwendet, um Datenbeziehungen mit einem einzelnen Vorgänger und Nachfolger in der objektiven Welt zu beschreiben
Merkmale
Es besteht eine lineare Beziehung zwischen Datenelementen, d. h. die Elemente sind „nacheinander“ angeordnet.
Einstufung
linearer Tisch
Definition
Es ist eine endliche Folge von n (n≥0) Elementen (strukturell unteilbar), normalerweise ausgedrückt als (a1,a2,...,an)
Grundoperationen
einfügen
löschen
Finden
Speicherstruktur
sequentielle Speicherung
Verwenden Sie eine Reihe von Speichereinheiten mit aufeinanderfolgenden Adressen, um Datenelemente sequentiell in der linearen Tabelle zu speichern
Der Speicherort des i-ten Elements ai
LOC(ai) = LOC(a1) (i-1) x L
Kettenspeicher
Speichern Sie Datenelemente mithilfe von Knoten, die durch Zeiger verknüpft sind
Knotenstruktur
Datenfeld
Wird zum Speichern des Werts des Datenelements verwendet
Zeigerfeld
Wird zum Speichern der Positionsinformationen des unmittelbaren Vorgängers oder unmittelbaren Nachfolgers des aktuellen Elements verwendet
Einstufung
Lineare verknüpfte Liste (oder einseitig verknüpfte Liste)
Es gibt nur ein Zeigerfeld im Knoten
Doppelt verknüpfte Liste
Jeder Knoten hat 2 Zeiger
zirkuläre verknüpfte Liste
Der Zeiger des Knotens am Ende der Tabelle zeigt auf den Knoten am Kopf der Tabelle
statische verknüpfte Liste
Verwenden Sie Arrays, um die verknüpfte Speicherstruktur linearer Listen zu beschreiben
Stapel
Definition
Das Speichern und Abrufen von Daten kann nur über ein Ende erfolgen (LIFO, Last In First Out, LIFO).
Grundoperationen
Initialisierungsstapel InitStack(S)
Feststellen, dass der Stapel leer ist IsEmpty(S)
Auf den Stapel schieben Push(S, x)
Pop(S)
Lesen Sie das oberste Element des Stapels Top(S)
Speicherstruktur
sequentielle Speicherung
Kettenspeicher
Anwendung
Ausdrucksbewertung
Halterung passend
Konvertieren eines rekursiven Prozesses in einen nicht rekursiven Prozess
Warteschlange
Definition
Elemente können nur an einem Ende der Tabelle eingefügt und am anderen Ende der Tabelle gelöscht werden (First In First Out, FIFO)
Grundoperationen
Initialisieren Sie die Warteschlange InitQueue(Q)
Richterteam leer IsEmpty(Q)
Enqueue EnQueue(Q, x)
DelQueue(Q) aus der Warteschlange entfernen
Lesen Sie das Kopfelement der Warteschlange FrontQue(Q)
Speicherstruktur
sequentielle Speicherung
sequentielle Warteschlange
kreisförmige Warteschlange
Kettenspeicher
Kettenwarteschlange
Zeichenfolge
Definition
Nur eine begrenzte Zeichenfolge. Im Allgemeinen wird es als S = 'a1a2 ... an' aufgezeichnet, wobei S der Zeichenfolgenname und die Zeichenfolge nach = der Zeichenfolgenwert ist
Basiskonzept
Leerer String; Leerzeichen-String-Gleichheit;
Grundoperationen
Zuweisungsoperation StrAssign(s, t)
Verkettungsoperation Concat(s, t)
Stringlänge StrLength(s)
String-Vergleich StrCompare(s, t)
Teilstring SubString(s, start, len) finden
Speicherstruktur
sequentielle Speicherung
Kettenspeicher
Mustervergleich
Definition
Der Positionierungsvorgang von Teilzeichenfolgen wird als Zeichenfolgenmustervergleich bezeichnet.
Teilzeichenfolge wird auch Musterzeichenfolge genannt
Matching-Algorithmus
Naiver Mustervergleichsalgorithmus
Brut-Foss-Algorithmus
Verbesserter Mustervergleichsalgorithmus
KMP-Algorithmus
Förderung
Array
Definition
Ein Array ist hinsichtlich der Dimensionen eine Erweiterung einer linearen Liste fester Länge, d. h. die Elemente in einer linearen Liste sind ebenfalls eine lineare Liste.
Ein N-dimensionales Array ist eine „isomorphe“ Datenstruktur, wobei jedes Datenelement denselben Typ und eine konsistente Struktur aufweist.
Merkmale
Feste Anzahl von Datenelementen
Datenelemente haben den gleichen Typ
Die tiefgestellte Beziehung von Datenelementen unterliegt Ober- und Untergrenzen und die tiefgestellten Indizes sind geordnet
Grundoperationen
Greifen Sie anhand einer Reihe von Indizes auf Datenelemente zu
Ändern Sie das Datenelement anhand einer Reihe von Indizes
Speicherstruktur
sequentielle Speicherung
Matrix
Definition
Eine Matrix ist ein mathematisches Objekt. Hier untersuchen wir hauptsächlich, wie verschiedene Operationen an der Matrix effizient ausgeführt werden können und gleichzeitig Speicherplatz gespart wird.
Einstufung
spezielle Matrix
Die Verteilung von Elementen mit demselben Wert oder 0 Elementen in der Matrix unterliegt bestimmten Regeln.
Einstufung
Symmetrische Matrix
diagonale Matrix
Dreiecksmatrix
spärliche Matrix
Elemente mit demselben Wert oder 0 Elementen sind unregelmäßig in der Matrix verteilt
Lagerung
Verwenden Sie Triplet (i, j, aij), um die Zeilennummer, Spaltennummer und den Wert eines Elements zu speichern
Speicherstruktur
sequentielle Speicherung
Dreifachsequenztabelle
Kettenspeicher
vernetzte Liste
verallgemeinerte Tabelle
Definition
ist eine endliche Folge bestehend aus 0 oder mehr Einzelelementen oder Unterlisten
Länge
Anzahl der Elemente
Tiefe
Die maximale Anzahl von Klammerebenen, die nach der Erweiterung in einer verallgemeinerten Tabelle enthalten sind
Grundoperationen
einfügen
löschen
Finden
Speicherstruktur
Kettenspeicher
Über „Nichtlineare Struktur“
Baum
Definition
Ein Datenelement kann null bis ein unmittelbares Vorgängerelement und zwei oder mehr unmittelbare Nachfolgerelemente haben.
Ein Baum ist eine endliche Menge von n(n≥0) Knoten
Die Definition eines Baums ist rekursiv. Es gibt nur einen Knoten, der als „Wurzel“ bezeichnet wird, und die übrigen Knoten werden als „Unterbäume“ des Wurzelknotens bezeichnet.
logische Struktur
Zwischen Elementen besteht eine hierarchische Beziehung
Basiskonzept
Eltern
Der Wurzelknoten des untergeordneten Knotens
Kind
Die Wurzel des Teilbaums eines Knotens wird als Kind des Knotens bezeichnet.
Bruder
Knoten mit denselben Eltern sind Brüder voneinander
Blattknoten
Endknoten, Grad ist 0
interner Knoten
Nicht-terminaler Knoten oder Verzweigungsknoten, Grad ist nicht 0
Grad des Knotens
Die Anzahl der Teilbäume eines Knotens
Knotenebene
Die Wurzel ist Ebene 1, die untergeordneten Elemente der Wurzel sind Ebene 2 und so weiter.
Baumhöhe
Die maximale Anzahl der Schichten in einem Baum wird als Höhe (oder Tiefe) des Baums erfasst
Geordnete und ungeordnete Bäume
Wenn die Teilbäume der Knoten im Baum geordnet sind, handelt es sich um einen geordneten Baum, andernfalls handelt es sich um eine ungeordnete Zahl.
Speicherstruktur
Elternvertretung
Kindervertretung
Vertretung des Kindesbruders
Es bietet die Möglichkeit, eine Konvertierung zwischen Bäumen, Binärbäumen und Wäldern zu realisieren.
Grundoperationen
Traverse
Weg
Zuerst Root-Traversierung
Besuchen Sie zuerst den Wurzelknoten des Baums und durchlaufen Sie dann nacheinander jeden Teilbaum der Wurzel.
Back-Root-Traversal
Durchlaufen Sie zunächst nacheinander jeden Unterbaum der Wurzel und besuchen Sie dann den Wurzelknoten.
Andere Segmente
Binärbaum
Definition
Ein Binärbaum ist eine endliche Menge von n(n≥0) Knoten
Die Definition eines Binärbaums ist rekursiv. Es besteht aus einem Wurzelknoten und zwei disjunkten Binärbäumen, die als linker bzw. rechter Teilbaum bezeichnet werden.
Haupteigenschaften
Es gibt höchstens 2(i-1)-te Potenzknoten auf der i-ten Ebene (i≥1) des Binärbaums
Ein Binärbaum mit der Höhe k (k≥1) hat höchstens 2 k-1 Knoten.
Einstufung
vollständiger Binärbaum
In jeder Ebene gibt es keine leeren Knoten
vollständiger Binärbaum
Bis auf die letzte Etage sind alle anderen Etagen belegt.
Die Knoten der letzten Ebene werden von links nach rechts platziert und können nicht leer gelassen werden.
unvollständiger Binärbaum
Speicherstruktur
sequentielle Speicherung
Speichern Sie die Knoten im Binärbaum in einer geeigneten Reihenfolge in einem Satz von Speicherzellen mit aufeinanderfolgenden Adressen.
Nehmen Sie einen vollständigen Binärbaum mit der Wurzelknotennummer 1 an. Wenn es einen Knoten mit der Nummer i gibt, dann
Wenn i=1, dann ist der Knoten der Wurzelknoten und hat keine Eltern.
Wenn i>1, dann ist der Elternknoten dieses Knotens ⌊ i/2 ⌋
Wenn 2i≤n, dann ist das linke Kind des Knotens 2i, andernfalls gibt es kein linkes Kind
Wenn 2i 1≤n, dann ist das rechte Kind des Knotens 2i 1, andernfalls gibt es kein rechtes Kind
Kettenspeicher
Lagerung
Der Knoten enthält Datenelemente, übergeordnete Elemente, die Wurzel des linken Teilbaums und die Wurzel des rechten Teilbaums.
Verfügbarer Speicher für binär verknüpfte Listen oder dreifach verknüpfte Listen
Grundoperationen
Traverse
Definition
Der Prozess, jeden Knoten im Baum gemäß einer bestimmten Strategie zu besuchen und ihn nur einmal zu besuchen
Der Prozess des Durchlaufens eines Binärbaums besteht im Wesentlichen darin, die Knoten im Baum nach bestimmten Regeln in einer linearen Reihenfolge anzuordnen.
Weg
(1) Gemäß der Konvention, zuerst den linken Teilbaum und dann den rechten Teilbaum zu durchlaufen, abhängig vom Standort des besuchten Wurzelknotens,
3 Möglichkeiten verfügbar
Durchquerung vorbestellen
Inorder-Durchquerung
Postorder-Durchquerung
(2) Durchqueren der Schichtreihenfolge (Zugriff von oben nach unten, von links nach rechts, Schicht für Schicht)
Andere Segmente
Hinweis Binärbaum
Definition
Fügen Sie in den Speicherinformationen von Binärbaumknoten direkte Vorgänger- und direkte Nachfolgerinformationen hinzu
optimaler Binärbaum
Definition
Auch als Huffman-Baum bekannt, handelt es sich um einen Baum mit der kürzesten gewichteten Pfadlänge.
Basiskonzept
Weg
Ein Pfad von einem Knoten zu einem anderen im Baum
Pfadlänge
Anzahl der Zweige auf dem Pfad
gewichtete Pfadlänge des Knotens
Die Länge des Pfades vom Knoten zur Wurzel des Baums multipliziert mit der Gewichtung des Knotens
Baumpfadlänge
Die Summe der Pfadlängen von der Wurzel zu jedem Blatt
Die gewichtete Pfadlänge des Baums
Die Summe der gewichteten Pfadlängen aller Blattknoten im Baum
Konstruktionsalgorithmus
(1) Wählen Sie im Binärbaumsatz die beiden Bäume mit dem kleinsten Gewicht als linken und rechten Teilbaum aus (derjenige mit dem kleineren Gewicht der beiden wird als linker Teilbaum platziert), um einen neuen Binärbaum zu erstellen der linken und rechten Teilbäume sind Die Summe der Gewichte der Punkte wird als Gewicht des Wurzelknotens des neuen Binärbaums verwendet; (2) Löschen Sie diese beiden Bäume aus der Menge und fügen Sie den neu erstellten Baum hinzu. Wiederholen Sie die oben genannten Schritte.
Anwendung
Huffman-Codierung
veranschaulichen
Wald
Definition
Bäume und Wälder werden gegenseitig rekursiv definiert
Grundoperationen
Traverse
Weg
Durchquerung vorbestellen
Besuchen Sie zuerst den Wurzelknoten des ersten Baums im Wald und durchqueren Sie dann der Reihe nach den Unterbaumwald des Wurzelknotens des ersten Baums. Der letzte Befehl durchquert den Wald der verbleibenden Bäume
Inorder-Durchquerung
Durchqueren Sie zunächst der Reihe nach den Unterbaumwald des ersten Baums im Wald und besuchen Sie dann den Wurzelknoten des ersten Baums. Schließlich durchquert man der Reihe nach den Wald, der aus den verbleibenden Bäumen besteht.
Konvertierung zwischen Bäumen, Binärbäumen und Wäldern
Baum in Binärbaum umwandeln
Schritt
(1) Eine Linie hinzufügen: Fügen Sie eine Verbindung zwischen Geschwisterknoten hinzu
(2) Leitungsentfernung: Der Knoten behält nur die Verbindung mit dem ersten Knoten bei
(3) Ebenenanpassung (Rotation): Drehen Sie den Baumwurzelknoten als Achse, sodass sich der erste untergeordnete Knoten an der linken untergeordneten Position und der Geschwisterknoten an der rechten untergeordneten Position befindet.
Wald in Binärbaum umwandeln
Schritt
(1) Jeder Baum im Wald wird in einen Binärbaum umgewandelt
(2) Der erste Binärbaum bewegt sich nicht und der Wurzelknoten des nächsten Binärbaums wird als rechtes untergeordnetes Element des Wurzelknotens des vorherigen Binärbaums verwendet und verbunden.
Konvertieren Sie einen Binärbaum in einen Baum
Schritt
(1) Fügen Sie eine Zeile hinzu: n rechte untergeordnete Knoten des linken untergeordneten Knotens eines Knotens sind alle untergeordneten Knoten dieses Knotens und verbunden.
(2) Zeilenentfernung: Löschen Sie die Verbindungen zwischen allen Knoten im ursprünglichen Binärbaum und ihren rechten untergeordneten Knoten
(3) Niveauanpassung (Rotation)
Konvertieren Sie einen Binärbaum in einen Wald
Schritt
(1) Trennen Sie den Binärbaum
Löschen Sie ausgehend vom Stammknoten alle rechten untergeordneten Verbindungen
(2) Konvertieren Sie den Binärbaum in einen Baum
Bild
Definition
Die Anzahl der Vorgängerknoten und Nachfolgerknoten eines Knotens ist unbegrenzt.
Graph G(Graph) ist ein Tupel bestehend aus den Mengen V(Scheitelpunkt) und E(Kante), bezeichnet als G=(V, E)
V ist eine nicht leere endliche Menge von Eckpunkten (Datenelementen)
E ist eine endliche Menge von Kanten (Beziehungen zwischen Datenelementen)
Basiskonzept
Scheitelgrad
Ausgeben
Die Anzahl der mit dem Scheitelpunkt verbundenen Kanten ist die Summe aus In-Grad und Out-Grad und wird mit D(v) bezeichnet.
Grad
ist die Anzahl der gerichteten Kanten, die am Scheitelpunkt enden, aufgezeichnet als ID(v)
aus Grad
Dies ist die Anzahl der gerichteten Kanten, die von diesem Scheitelpunkt ausgehen und als OD(v) aufgezeichnet werden.
Weg
Scheitelpunktsequenz vom Scheitelpunkt vp zum Scheitelpunkt vq
Pfadlänge
Nummer auf dem Weg
Schleife oder Ring
Der Pfad, bei dem der erste Scheitelpunkt und der letzte Scheitelpunkt identisch sind
Wenn die verbleibenden Eckpunkte des Pfades unterschiedlich sind, spricht man von einem einfachen Pfad
Nebenhandlung
Verbundene Diagramme und verbundene Komponenten
verbundener Graph
Zwei beliebige Knoten sind verbundene ungerichtete Graphen
verbundenen Komponenten
Maximal verbundener Teilgraph dieses Graphen
Stark verbundener Graph und stark verbundene Komponenten
Stark verbundener Graph
Zwei beliebige Knoten sind verbundene gerichtete Graphen
Stark verbundene Komponente
Maximal verbundener Teilgraph dieses Graphen
Netz
Diagramm mit Seitengewichten
gerichteter Baum
Ein gerichteter Graph, bei dem ein Scheitelpunkt einen In-Grad von 0 und die übrigen Scheitelpunkte einen In-Grad von 1 haben
Spannbaum
Minimaler zusammenhängender Teilgraph des Graphen (ohne Zyklen)
Der Spannbaum eines Diagramms ist nicht eindeutig
Kürzester Weg mit einem einzigen Quellpunkt
Einstufung
gerichteter Graph
Jede Kante hat eine Richtung
Die Beziehung zwischen Scheitelpunkten wird durch <vi, vj> dargestellt
Das bedeutet, dass vi zu vj eine gerichtete Kante hat (auch Bogen genannt)
vi ist der Startpunkt der gerichteten Kante, der sogenannte Bogenschwanz
vj ist der Endpunkt der gerichteten Kante, der Bogenkopf genannt wird
Andere Segmente
gerichteter azyklischer Graph
Gerichteter Graph ohne Zyklen
Ungerichteter Graph
Jede Kante hat keine Richtung
Die Beziehung zwischen Scheitelpunkten wird durch (vi, vj) dargestellt.
vollständige Grafik
Jeder Scheitelpunkt hat eine Kante mit anderen Scheitelpunkten
Einstufung
Gerichteter vollständiger Graph
ungerichteter vollständiger Graph
Speicherstruktur
Notation der Adjazenzmatrix
Darstellung verknüpfter Adjazenzlisten
Grundoperationen
Traverse
Definition
Unter Graph-Traversierung versteht man den Prozess, bei dem man von einem bestimmten Scheitelpunkt aus beginnt und alle Scheitelpunkte im Diagramm entlang eines bestimmten Suchpfads nur einmal besucht.
Weg
Tiefensuche (DFS)
Wenn möglich, suchen und greifen Sie zuerst in Tiefenrichtung zu
Breitensuche (BFS)
Suchen Sie nach Möglichkeit zunächst in horizontaler Richtung
Über „Minimal Spanning Tree“
Definition
Bei einem verbundenen Netzwerk werden die Kanten gewichtet, und jede Kante des Spannbaums wird ebenfalls gewichtet.
Der minimale Spannbaum ist der Spannbaum mit dem geringsten Gewicht
Basiskonzept
Spannbaum rechts
Die Summe der Gewichte jeder Kante des Spannbaums
Häufig verwendete Algorithmen zur Lösung minimaler Spannbäume
Prims Algorithmus
Kruskals Algorithmus
Zum Thema „Kürzester Weg aus einer Hand“
Definition
Dies bedeutet, dass bei einem gegebenen gewichteten gerichteten Graphen G und einem Quellpunkt v0 der kürzeste Weg von v0 zu den verbleibenden Eckpunkten in G ermittelt werden muss
Häufig verwendete Lösungsalgorithmen
Dijkstras Algorithmus
Floyds Algorithmus
Anwendung
AOV-Netzwerk (Activity On Vertex-Netzwerk)
Definition
Ein gerichteter Graph, der Scheitelpunkte zur Darstellung von Aktivitäten und gerichtete Kanten zur Darstellung von Prioritätsbeziehungen zwischen Aktivitäten verwendet.
Gezielte Zyklen sollten nicht im AOV-Netzwerk erscheinen
Prüfen Sie, ob es eine Schleife im AOV-Netzwerk gibt
Methode
Konstruieren Sie für einen gerichteten Graphen eine topologisch geordnete Folge seiner Eckpunkte. Wenn alle Eckpunkte im Graphen in seiner topologisch geordneten Folge liegen, gibt es keinen Zyklus.
Schritt
(1) Wählen Sie einen Scheitelpunkt im Netzwerk mit einem In-Grad von 0 aus und geben Sie ihn aus
(2) Löschen Sie den Scheitelpunkt und alle zugehörigen Bögen aus dem Netzwerk
(3) Wiederholen Sie die beiden obigen Schritte, bis im Netzwerk keine Scheitelpunkte mit einem In-Grad von 0 vorhanden sind.
(4) Ergebnis
Wenn alle Scheitelpunkte ausgegeben wurden, ist die gesamte topologische Sortierung abgeschlossen, was darauf hinweist, dass keine Schleife vorhanden ist.
Wenn noch Scheitelpunkte vorhanden sind, die nicht ausgegeben wurden, und die verbleibenden Scheitelpunkte alle Vorgängerscheitelpunkte haben, kann die topologische Sortierung zu diesem Zeitpunkt nicht fortgesetzt werden, was darauf hinweist, dass eine Schleife vorliegt.
AOE-Netzwerk (Activity On Edge-Netzwerk)
Definition
Ein gerichteter Graph, in dem Ereignisse durch Eckpunkte, Aktivitäten durch gerichtete Kanten und die Dauer der Aktivität durch die Gewichte an den Kanten dargestellt werden.
Die für das gesamte Projekt benötigte Zeit entspricht der Länge des längsten Pfades vom Startscheitelpunkt bis zum Endscheitelpunkt.
Basiskonzept
Das durch den Scheitelpunkt dargestellte Ereignis ist ein Zeichen dafür, dass einige Aktivitäten abgeschlossen wurden und einige Aktivitäten gestartet werden können.
Quelle
Der Startscheitelpunkt mit Grad 0
Treffpunkt
Endscheitelpunkt ohne Grad 0
Kritischer Pfad
Der längste Weg von der Quelle zur Senke
Alle Aktivitäten auf dem kritischen Pfad sind kritische Aktivitäten
Der Zeitpunkt des Scheitelpunktereignisses
Der früheste Auftrittszeitpunkt des Scheitelpunktereignisses ve(j)
Die späteste Auftrittszeit des Scheitelpunktereignisses vl(i)
Operationen an Datenstrukturen
Finden
Basiskonzept
veranschaulichen
Die Suche ist eine häufig verwendete Grundoperation
Nachschlagwerk
Bezieht sich auf eine Sammlung von Datenelementen (oder Datensätzen) desselben Typs
Schlüsselwörter
Ist der Wert eines Datenelements eines Datenelements (oder Datensatzes)
Wird verwendet, um dieses Datenelement zu identifizieren (identifizieren).
primäres Schlüsselwort
Ein Schlüsselwort, das ein Datenelement eindeutig identifiziert
sekundäre Schlüsselwörter
bezieht sich auf ein Schlüsselwort, das mehrere Datenelemente identifizieren kann
Suchergebnisse
Suche erfolgreich
Die Suche ist fehlgeschlagen
durchschnittliche Suchlänge
Die erwartete Häufigkeit, mit der der Suchvorgang mit dem angegebenen Schlüsselwortwert verglichen werden muss
Grundlegende Operationen von Nachschlagetabellen
statische Nachschlagetabelle
Fragen Sie ab, ob ein bestimmtes Datenelement in der Nachschlagetabelle enthalten ist
Rufen Sie verschiedene Attribute eines Datenelements ab
dynamische Nachschlagetabelle
Fügen Sie ein Datenelement ein
Löschen Sie ein Datenelement
Über „Statische Nachschlagetabelle“
Methode finden
Einstufung
Sequentielle Suche
halbe Suche
Prozessanalyse
Der Suchvorgang kann durch einen Binärbaum beschrieben werden
Konstruktionsmethode des Entscheidungsbaums für die binäre Suche (Binärbaum).
(1) Nehmen Sie die mittlere Positionsnummer des aktuellen Suchintervalls als Wurzel
(2) Die Datensatzseriennummern in der linken Hälfte der Untertabelle und der rechten Hälfte der Untertabelle werden als Knoten im linken Teilbaum bzw. rechten Teilbaum der Wurzel verwendet.
Suchen Sie in Blöcken
Über „Dynamische Nachschlagetabelle“
Merkmale
Die Tabellenstruktur selbst wird während des Suchvorgangs dynamisch generiert
Klassifizierung der Tabellenstruktur
Binärer Sortierbaum
Definition
Auch als binärer Suchbaum bekannt
es kann ein leerer Baum sein
Oder ein Binärbaum mit den folgenden Eigenschaften
Wenn der linke Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert des Wurzelknotens
Wenn der rechte Teilbaum nicht leer ist, sind die Werte aller Knoten im rechten Teilbaum größer als der Wert des Wurzelknotens
Die linken und rechten Teilbäume selbst sind binär sortierte Bäume.
ausgeglichener Binärbaum
Definition
Auch als AVL-Baum bekannt
es kann ein leerer Baum sein
Oder ein Binärbaum mit den folgenden Eigenschaften
Der absolute Wert der Differenz zwischen den Höhen des linken und rechten Teilbaums überschreitet nicht 1
Die linken und rechten Teilbäume selbst sind ausgeglichene Binärbäume
arbeiten
einfügen
Einweg-Auswuchtbehandlung für die rechte Seite vom Typ LL
Einweg-Auswuchtbehandlung für die linke Hand vom Typ RR
LR-Typ, zuerst links und dann rechts, Zwei-Wege-Rotationsausgleichsverarbeitung
RL-Typ zuerst rechts und dann links, Zwei-Wege-Rotationsausgleichsverarbeitung
B_Baum der Ordnung m
Definition
es kann ein leerer Baum sein
Oder ein M-Baum mit den folgenden Eigenschaften
Jeder Knoten im Baum hat höchstens m Teilbäume
...
roter schwarzer Baum
Hash-Tabelle (oder Hash-Tabelle)
Definition
Die Speicheradresse des Datensatzes wird durch Berechnung einer Funktion (sogenannte Hash-Funktion) mit dem Schlüssel des Datensatzes als unabhängiger Variable ermittelt.
Das heißt, basierend auf der festgelegten Hash-Funktion H (Schlüssel) und der Konfliktbehandlungsmethode wird ein Satz von Schlüsselwörtern einem begrenzten kontinuierlichen Adresssatz (Intervall) zugeordnet und das „Bild“ des Schlüsselworts im Adresssatz als verwendet einen Speicherort in der Tabelle
Dieser Zuordnungsprozess wird als Hashing oder Hashing bezeichnet
Der resultierende Speicherort wird Hash-Adresse oder Hash-Adresse genannt
Basiskonzept
Über Hash-Kollisionen
Für eine bestimmte Hash-Funktion H und die beiden Schlüssel K1 und K2 spricht man von einem Konflikt, wenn K1≠K2 und H(K1)=H(K2).
Schlüsselwörter mit demselben Hash-Funktionswert werden als Synonyme für diese Hash-Funktion bezeichnet.
Allgemein gesagt
Kollisionen können nur so weit wie möglich reduziert, aber nicht vollständig vermieden werden, da die Hash-Funktion das Bild vom Schlüsselwortsatz zum Adresssatz darstellt
Die Hash-Funktion ist ein komprimiertes Bild und Kollisionen sind unvermeidlich
Hauptthemen, die es zu berücksichtigen gilt
So erstellen Sie eine Hash-Funktion
Gängige Methoden
direkte Adressierungsmethode
digitale Analyse
Quadrat-Medium-Methode
Faltmethode
Zufallszahlenmethode
Division mit Restrestverfahren
Probleme, die gelöst werden sollten
Die Hash-Funktion sollte eine komprimierte Bildfunktion sein, die stärker komprimiert sein sollte, um Speicherplatz zu sparen
Die Hash-Funktion sollte über gute Hashing-Eigenschaften verfügen und Schlüsselwörter möglichst gleichmäßig auf verschiedene Speichereinheiten im Speicherbereich abbilden
So lösen Sie Konflikte
Gängige Methoden
offene Adressierungsmethode
Kettenadressmethode
aufwärmen
Erstellen Sie einen öffentlichen Überlaufbereich
Grundoperationen
Finden
Konzept
Berechnen Sie die Speicheradresse des zu prüfenden Datensatzes mit derselben Hash-Funktion und Konfliktbehandlungsmethode wie beim Speichern von Elementen.
durchschnittliche Suchlänge
es hängt davon ab
Hash-Funktion
Wie man mit Konflikten umgeht
Füllfaktor der Hash-Tabelle
Über den „Hash-Tabellenfüllfaktor“
Definition
α = Anzahl der in die Tabelle geladenen Datensätze / Länge der Hash-Tabelle
Sortieren
Basiskonzept
Definition
Angenommen, der Inhalt der Datei mit n Datensätzen sei {R1, R2,…,R} und die entsprechenden Schlüsselwörter seien {k1,k2,…,kn}. Nach dem Sortieren wird eine Anordnung {Rj1, Rj2,…,Rjn} ermittelt, Sorgen Sie dafür, dass ihre Schlüsselwörter die folgende zunehmende (oder abnehmende) Beziehung erfüllen: kj1≤kj2≤...≤kjn (oder kj1≥kj2≥...≥kjn).
Stabilität der Sortiermethode
Stabile Sortiermethode
Zeichnet Ri und Rj mit demselben Schlüsselwort auf, Ri steht vor Rj. Nach dem Sortieren bleibt die Reihenfolge von Ri und Rj unverändert.
Instabile Sortiermethode
Zeichnet Ri und Rj mit demselben Schlüsselwort auf, Ri steht vor Rj. Nach dem Sortieren kann sich die Reihenfolge von Ri und Rj ändern
Grundoperationen
(1) Vergleichen Sie die Größe der Schlüsselwörter.
(2) Abhängig von der Speichermethode muss der Speicherort der Aufzeichnung möglicherweise verschoben werden.
Einstufung
Interne Sortierung
Einfache Sortierung
direkte Einfügungssortierung
Blasensortierung
Einfache Auswahlsortierung
Hill-Sorte
Heap-Sortierung
Schnelle Sorte
Zusammenführen, sortieren
Zwei-Wege-Zusammenführungssortierung
Radix-Sortierung
externe Sortierung
grundlegende Methode
Methodenklassifizierung
k-way ausgewogene Zusammenführung
Algorithmus
Basiskonzept
Algorithmentheorieforschung
Algorithmenentwurfstechniken (/Strategie)
Beantworten Sie die Frage: „Wie entwickelt man einen Algorithmus zur Lösung eines bestimmten Problems?“
Algorithmische Analysetechniken
Beantworten Sie die Frage: „Ist der Algorithmus gut genug?“
Definition
Ein Algorithmus ist eine Beschreibung der Schritte zur Lösung eines bestimmten Problems. Es handelt sich um eine endliche Folge von Anweisungen. Jede dieser Anweisungen repräsentiert eine oder mehrere Operationen.
5 wichtige Eigenschaften von Algorithmen
Endlichkeit
Sicherheit
Durchführbarkeit
eingeben
Ausgabe
Über „Algorithmendesign“
Haupttechnik
Divide-and-Conquer-Methode, dynamische Programmiermethode, Greedy-Methode, Backtracking-Methode, Branch-and-Bound-Methode, Wahrscheinlichkeitsalgorithmus, Approximationsalgorithmus
Über „Algorithmische Analyse“
einige analytische Kriterien
Korrektheit, Zuverlässigkeit, Einfachheit und Verständlichkeit des Algorithmus
Die zeitliche und räumliche Komplexität des Algorithmus
Algorithmusdarstellung
Natürliche Sprache
Flussdiagramm
Programmiersprache
Pseudocode
Über „Zeitkomplexität“
analysieren
Definition
Dabei wird hauptsächlich die Laufzeit des Algorithmus analysiert, also die Anzahl der Grundoperationen, die für die Ausführung des Algorithmus erforderlich sind.
Methode
Erstellen Sie eine Funktion T(n) mit der Eingabeskala n als unabhängige Variable, um die Zeitkomplexität des Algorithmus darzustellen.
Je nach Eingabe gibt es drei Situationen
Best-Case-Szenario
Worst-Case-Szenario
durchschnittliche Situation
progressives Symbol
ist eine weitere Abstraktion der obigen T(n)-Methode, die nur die Wachstumsrate der Laufzeit (oder Wachstumsgröße genannt) berücksichtigt.
Analytische Methode
O Mark
Asymptotische Obergrenzenanalyse
Beispiel:
Ω-Symbol
Schrittweise nächste Analyse
Θ-Symbol
Asymptotische Obergrenzen- und asymptotische Untergrenzenanalyse, d. h. asymptotische Kompaktgrenzenanalyse
Algorithmusstruktur
Im Allgemeinen kann unterteilt werden in
nicht rekursive Form
rekursive Form
Hauptmethoden der Zeitkomplexitätsanalyse
Substitutionsmethode
rekursive Baummethode
Hauptmethode
Konventioneller Algorithmus
Teile und herrsche
Die Grundidee
Zerlegen Sie ein großes Problem, das schwer direkt zu lösen ist, in eine Reihe kleinerer identischer Probleme, sodass diese einzeln zerlegt, geteilt und bewältigt werden können
Rekursion
Dies bedeutet, dass sich die Unterroutine direkt oder indirekt über eine Reihe von Aufrufanweisungen aufruft.
Grundelemente
Randbedingungen
Rekursiver Modus
Die wichtigsten Schritte
Die Schritte des Divide-and-Conquer-Algorithmus auf jeder Rekursionsebene
(1) Zersetzung
(2) Lösen
(3) Zusammenführen
Anwendung
Zusammenführen, sortieren
Maximale Felder und Fragen
dynamische Programmierung
Die Grundidee
Zerlegen Sie ein großes Problem, das schwer direkt zu lösen ist, in eine Reihe kleinerer identischer Probleme und greifen Sie jedes einzelne an. Im Gegensatz zum Teilen und Herrschen sind Teilprobleme oft nicht unabhängig
Speichern Sie Antworten zu gelösten Teilproblemen in einer Tabelle und rufen Sie sie bei Bedarf ab
Die wichtigsten Schritte
(1) Finden Sie die Eigenschaften der optimalen Lösung heraus
(2) Definieren Sie rekursiv den Wert der optimalen Lösung
(3) Berechnen Sie den optimalen Wert von unten nach oben
(4) Konstruieren Sie eine optimale Lösung basierend auf den Informationen, die Sie bei der Berechnung des optimalen Werts erhalten
Anwendung
0-1 Rucksackproblem
Längste gemeinsame Teilsequenz (LCS)
gierige Methode
Die Grundidee
Die Strategie besteht darin, Entscheidungen nur auf der Grundlage der aktuell verfügbaren Informationen zu treffen und lokal (/näherungsweise) optimale Lösungen zu erhalten.
Algorithmusform
rekursiver Greedy-Algorithmus
iterativer Greedy-Algorithmus
Anwendung
Probleme bei der Aktivitätsauswahl
Rucksackproblem
Zurückverfolgen
Die Grundidee
Nach der Bestimmung der Organisationsstruktur des Lösungsraums beginnt die Backtracking-Methode am Startknoten (Wurzelknoten) und durchsucht den gesamten Lösungsraum tiefenorientiert. Bis die erforderliche Lösung gefunden ist oder keine aktiven Knoten im Lösungsraum vorhanden sind
Das Lösungsziel besteht darin, alle Lösungen zu finden, die die Einschränkungen erfüllen
Lösungsraum
Sollte mindestens eine (optimale) Lösung des Problems enthalten
Wird im Allgemeinen in Form eines Baums oder Diagramms ausgedrückt
Begrenzungsfunktion
Da der Lösungsraum oft sehr groß ist, müssen für eine effektive Suche einige Knoten während des Suchvorgangs beschnitten werden. Entwerfen Sie eine Begrenzungsfunktion zum Beschneiden des Urteils (Beschneiden so früh und so weit wie möglich).
Die wichtigsten Schritte
(1) Definieren Sie den Lösungsraum des Problems
(2) Bestimmen Sie die Lösungsraumstruktur, die leicht zu durchsuchen ist
(3) Durchsuchen Sie den Lösungsraum tiefenorientiert
Bewertungsrahmen
Rekursiver Weg
nicht rekursiv
Anwendung
0-1 Rucksackproblem
n Queen-Problem
Branch-and-Bound-Methode
Die Grundidee
Ähnlich wie bei der Backtracking-Methode handelt es sich auch hier um einen Algorithmus, der im Lösungsraumbaum T des Problems nach der Lösung des Problems sucht.
Durchsuchen Sie den Lösungsraum nach dem Prinzip „Breite zuerst“ oder „Least Cost First“.
Das Lösungsziel besteht darin, eine (optimale) Lösung zu finden, die die Randbedingungen erfüllt
Begrenzungsfunktion
Klassifiziert nach verschiedenen Möglichkeiten zur Auswahl des nächsten Erweiterungsknotens aus der Tabelle der aktiven Punkte
Queued (FIFO, First In First Out) Branch-and-Bound-Methode
Prioritätswarteschlangenzweig und gebundene Methode
Wahrscheinlichkeitsalgorithmus
Die Grundidee
Wenn der Algorithmus bestimmte Schritte ausführt, können Sie nach dem Zufallsprinzip auswählen, wie als nächstes vorgegangen werden soll, wobei die Wahrscheinlichkeit geringer ist, dass die Ergebnisse fehlerhaft sind, und auf Kosten dessen eine erhebliche Verkürzung der Laufzeit des Algorithmus erzielt wird.
Einstufung
Numerischer Wahrscheinlichkeitsalgorithmus
Monte-Carlo-Algorithmus
Las Vegas-Algorithmus
Sherwood-Algorithmus
Approximationsalgorithmus
Die Grundidee
Geben Sie die Suche nach der optimalen Lösung auf und ersetzen Sie die optimale Lösung durch eine annähernd optimale Lösung im Austausch für eine Vereinfachung des Algorithmusdesigns und eine Reduzierung der Zeitkomplexität
Maß für die Leistung
Die zeitliche Komplexität des Algorithmus
Der Grad der Annäherung an die Lösung
Data-Mining-Algorithmus
Data-Mining
Basiskonzept
Es handelt sich um ein interdisziplinäres Fach, das Methoden des maschinellen Lernens verwendet, um eine Vielzahl von Daten (Datenbankdaten, Data Warehouse-Daten, Webdaten usw.) zu analysieren und zu extrahieren.
Kern
ist ein Algorithmus
Die Hauptfunktion
Einstufung
zurückkehren
Vereinsregeln
Clusterbildung
Intelligenter Optimierungsalgorithmus
Überblick
Optimierungstechnologie
Es handelt sich um eine auf Mathematik basierende Anwendungstechnologie, mit der optimale Lösungen für verschiedene technische Probleme gelöst werden können.
Im Bereich der Optimierung werden diese Algorithmuskonstruktionen aufgrund der Intuitivität und des natürlichen Mechanismus häufig als „intelligente Optimierungsalgorithmen“ oder „moderne heuristische Algorithmen“ bezeichnet.
Bestehende Optimierungsalgorithmen
Künstliches neuronales Netzwerk (ANN)
Prinzip
Ein dynamisches System mit einer gerichteten Graphtopologie, das Informationen verarbeitet, indem es auf kontinuierliche oder diskontinuierliche Eingabezustände reagiert.
Einstufung
Feedforward- und Feedback-Netzwerke
Einstufung
Mehrschichtiges vorwärtsgerichtetes neuronales Netzwerk basierend auf dem BP-Algorithmus
tiefes maschinelles Lernen
Deep Belief Networks (DBNs)
Faltungs-Neuronale Netze (CNNs)
genetischen Algorithmus
Simulierter Annealing-Algorithmus (SA)
Tabu-Suchalgorithmus (TS)
Ameisenkolonie-Algorithmus
Partikelschwarm-Optimierungsalgorithmus (PSO)