Was ist die Datenstruktur in C-Sprache? Was sind die gängigen Datenstrukturen?

In der C-Sprache bezieht sich die Datenstruktur auf eine Sammlung von Datenelementen, die eine oder mehrere spezifische Beziehungen zueinander haben. Dabei handelt es sich um die Art und Weise, wie Computer Daten speichern und organisieren: lineare Datenstrukturen (Arrays, verknüpfte Listen, Stapel, Warteschlange und lineare Liste), Baumstruktur (Binärbaum, vollständiger Binärbaum, binärer Suchbaum, Heap), Diagrammstruktur (gerichteter Graph und ungerichteter Graph).

Die Betriebsumgebung dieses Tutorials: Windows 7-System, c99-Version, Dell G3-Computer.

Was ist eine Datenstruktur?

Datenstruktur ist die Art und Weise, wie Computer Daten speichern und organisieren. Eine Datenstruktur bezieht sich auf eine Sammlung von Datenelementen, die eine oder mehrere spezifische Beziehungen zueinander haben. Die Implementierung der meisten Datenstrukturen erfordert die Hilfe von Zeigern und Strukturtypen in der C-Sprache. Kommen wir nun zum heutigen FokusO ( ∩_∩)O Mehrere gängige Datenstrukturen

(1) Lineare Datenstruktur: Es gibt im Allgemeinen eine Eins-zu-Eins-Beziehung zwischen Elementen. Typische Datenstrukturen sind: Array, Stack, Warteschlange und lineare Liste

(2) Baumstruktur: Zwischen Knoten besteht eine hierarchische Beziehung. Ein Knoten in jeder Ebene kann und kann nur mit einem Knoten in der vorherigen Ebene verknüpft sein, er kann jedoch auch mit der nächsten Ebene verknüpft sein. Mehrere Knoten sind verknüpft, was als „Eins-zu-viele“-Beziehung bezeichnet wird: Baum, Heap

(3) Grafische Struktur: In der Diagrammstruktur dürfen mehrere Knoten verknüpft sein, was als „viele“ bezeichnet wird -zu-viele“-Beziehung. „Viele“-Beziehung

Das Folgende ist eine kurze Einführung in jede dieser Datenstrukturen:

1. Lineare Datenstrukturen: Typische sind: Arrays, Stapel, Warteschlangen und lineare Tabellen

(1) Arrays und verknüpfte Liste

a Array: Speichert einen Satz von Daten desselben Typs. Die Länge des Arrays muss im Voraus angegeben werden, z. B. ein eindimensionales Array oder ein zweidimensionales Array , mehrdimensionales Array usw. b Verknüpfte Liste ist eine weit verbreitete Methode in der C-Sprache. Die Struktur wird in Form von dynamisch zugewiesenem Speicher implementiert. Eine Reihe beliebiger Speichereinheiten wird zum Speichern einer verknüpften Liste verwendet von Datenelementen. Im Allgemeinen wird für jedes Element ein Zeigerfeld hinzugefügt, um auf nachfolgende Elemente zu verweisen.

c Der Unterschied zwischen Arrays und verknüpften Listen:

Aus Sicht der logischen Struktur: Das Array muss eine im Voraus definierte feste Länge haben und kann sich nicht an die dynamische Zunahme und Abnahme von Daten anpassen; die verknüpfte Liste führt die Speicherzuweisung dynamisch durch und kann sich an die dynamische Zunahme und Abnahme von Daten anpassen und Datenelemente problemlos einfügen und löschen (beim Einfügen oder Löschen von Datenelementen im Array). , andere Datenelemente müssen verschoben werden)

Aus der Perspektive der Speicherspeicherung: (statische) Arrays weisen Speicherplatz vom Stapel zu (erstellt mit NEW im Heap), was für Programmierer bequem und schnell ist, aber der Freiheitsgrad ist klein; die verknüpfte Liste reserviert Platz vom Heap und der Freiheitsgrad ist groß, aber die Anwendungsverwaltung ist problematischer

Von der Zugriffsmethode: Das Array wird kontinuierlich im Speicher gespeichert, sodass der Indexindex verwendet werden kann Direkter Zugriff; die verknüpfte Liste ist Beim Zugriff auf Elemente kann auf die verkettete Speicherstruktur nur sequentiell von vorne nach hinten zugegriffen werden, sodass die Zugriffseffizienz geringer ist als die von Arrays

(2) Stapel, Warteschlange und lineare Tabelle : Sequentielle Speicherung und Verkettung können verwendet werden. Speichermethode für die Speicherung.

Sequentielle Speicherung: Verwenden Sie die relative Position von Datenelementen im Speicherplatz, um die logische Beziehung zwischen Elementen auszudrücken. Kettenspeicher: Verwenden Sie Zeiger, die die Speicheradressen von Datenelementen darstellen um die logische Beziehung zwischen Elementen auszudrücken

a. Stapeloperationen sind nur am Ende der Sequenz zulässig. Im Allgemeinen wird der Stapel auch als Last-in-First bezeichnet -out oder First-in-last-out-lineare Struktur: Es wird eine sequentielle Speicherstruktur verwendet, das heißt, es wird ein Platz mit fortlaufenden Adressen benötigt, um die Elemente des Stapels zu speichern . Der Typ des sequentiellen Stapels ist wie folgt definiert:

Kettenstapel: Ein Stapel, der eine Kettenspeicherstruktur verwendet, wird als Kettenstapel bezeichnet:

b. Warteschlange: An beiden Enden sind nur Operationen zulässig Im Allgemeinen werden Warteschlangen auch als lineare First-In-First-Out-Strukturen bezeichnet: Warteschlangen, die eine sequentielle Speicherstruktur verwenden, müssen Speicherplatz entsprechend der maximal möglichen Länge der Warteschlange zuweisen wie folgt:

Kettenwarteschlange: Eine Warteschlange, die eine Kettenspeicherstruktur verwendet, wird als Kettenwarteschlange bezeichnet. Im Allgemeinen müssen Sie die Kopf- und Endzeiger nur auf die Kopf- und Endknoten der verknüpften Liste setzen:

c. Bedienung an jeder Position in der Sequenz. Die Bedienung der linearen Tabelle ist auch sehr flexibel B. Elemente an beliebiger Stelle abfragen und ändern

Sequentielle Tabelle: Eine durch eine sequentielle Speicherstruktur dargestellte lineare Tabelle wird als sequentielle Tabelle bezeichnet. Ein Satz von Speichereinheiten mit aufeinanderfolgenden Adressen wird verwendet, um die Datenelemente der linearen Tabelle gleichzeitig zu speichern, dh die benachbarten Speicherorte Die Lücke zwischen zwei Elementen in sequentieller Reihenfolge. Um das Verschieben von Elementen zu vermeiden, wird in der Schnittstellendefinition der Sequenztabelle im Allgemeinen nur das Einfügen und Löschen von Elementen berücksichtigt Methode kann auch als Stapeltabelle bezeichnet werden:

Lineare Tabelle: umfasst im Allgemeinen einfach verknüpfte Liste, doppelt verknüpfte Liste, zirkulär verknüpfte Liste und bidirektional verknüpfte Liste.

Einfach verknüpfte Liste:

Doppelt verknüpft Liste:

Lineare Tabelle Vergleich zweier Speicherstrukturen:

Sequentielle Tabelle:

Vorteile: In der Tabelle sind zwei benachbarte Elemente in der Logik auch an physischen Positionen benachbart, was die Suche erleichtert Die Komplexität des Zugriffs auf ein Element beträgt O(1)

Nachteile: Nicht zum Einfügen oder Löschen an einer beliebigen Position geeignet. Da das Element verschoben werden muss, beträgt die durchschnittliche Zeitkomplexität O(n)

Verknüpfte Liste:

Vorteile : Um ein Element an einer beliebigen Position des Links einzufügen oder zu löschen, müssen Sie nur den entsprechenden Zeiger ändern und das Element nicht bei Bedarf dynamisch verschieben. Es ist nicht erforderlich, einen kontinuierlichen Leerraum entsprechend vorab zuzuweisen die maximale Nachfrage

Nachteile: Um ein Element zu finden, müssen Sie vom Kopfzeiger aus entlang des Zeigerfelds suchen, daher beträgt die durchschnittliche Zeitkomplexität O(n)

2. Baumstruktur: Knoten Dort Es besteht eine hierarchische Beziehung zwischen ihnen. Ein Knoten in jeder Ebene kann nur mit einem Knoten in der vorherigen Ebene verknüpft sein, er kann jedoch auch mit mehreren Knoten in der nächsten Ebene verknüpft sein. Dies wird als „Eins-zu-viele“ bezeichnet " Beziehung. Sie kommt häufig vor. Zu den Typen gehören: Baum, Heap

(1) Binärbaum: Binärbaum ist eine rekursive Datenstruktur, bei der es sich um eine endliche Menge mit n (n>=0) Knoten handelt. Binärbaum weist die folgenden Eigenschaften auf :

Der Binärbaum kann ein leerer Baum sein. Jeder Knoten eines Binärbaums hat genau zwei Teilbäume, von denen einer oder beide leer sein können. Wenn die Positionen der beiden geändert werden, werden sie zum anderen. Ein Binärbaum

(2) Vollständiger Binärbaum: Nummerieren Sie jeden Knoten des vollständigen Binärbaums fortlaufend von oben nach unten und von links nach rechts 1 bis n, wenn jeder Knoten mit der Tiefe von k zusammenhängt. Die von 1 bis n nummerierten Knoten im vollständigen Binärbaum entsprechen eins zu eins, was als vollständiger Binärbaum bezeichnet wird

a Es wird eine sequentielle Speicherstruktur übernommen: a Ein eindimensionales Array wird zum Speichern des vollständigen Binärbaums verwendet, und die Nummer des Knotens hängt mit dem Index des Knotens zusammen (z. B. Die Wurzel ist 1, dann ist das linke Kind der Wurzel 2i = 21 = 2 usw.) das rechte Kind ist 2i+1=21+1=2)

b, unter Verwendung einer Kettenspeicherstruktur:

Binär verknüpfte Liste:

Ternär verknüpfte Liste: Sein Knoten hat ein weiteres übergeordnetes Zeigerfeld als eine binär verknüpfte Liste, die verwendet wird, um die übergeordneten Knoten auszuführen und die Suche nach übergeordneten Knoten zu erleichtern

Vergleich zweier Speicherstrukturen: Für einen vollständigen Binärbaum wird die Reihenfolge verwendet Sparen Sie Platz, verwenden Sie aber auch den Indexwert des Array-Elements, um die Position des Knotens im Binärbaum und die Beziehung zwischen den Knoten zu bestimmen. Die Verwendung einer sequentiellen Speicherstruktur zum Speichern allgemeiner Binärbäume kann jedoch leicht zu Platzverschwendung führen . Die Kettenstruktur kann dieses Problem überwinden

(3) Binärer Suchbaum: Der binäre Suchbaum, auch binärer Sortierbaum genannt, ist entweder ein leerer Binärbaum oder ein Binärbaum mit den folgenden Merkmalen:

a. Wenn sein linker Teilbaum nicht leer ist, sind die Werte aller Knoten im linken Teilbaum kleiner als der Wert des Wurzelknotens

b. Wenn sein rechter Teilbaum nicht leer ist, dann sind die Werte aller Knoten auf Der rechte Teilbaum ist größer als der Wert des Wurzelknotens. Ein ausgeglichener Binärbaum ist entweder ein leerer Baum oder eine binäre Suche mit den folgenden Eigenschaften: Baum: Sein linker und rechter Teilbaum sind beide ausgeglichene Binärbäume, und der absolute Wert des Höhenunterschieds zwischen dem linken Teilbaum und dem rechten Teilbaum gilt nicht 1 überschreiten

Das Ungleichgewicht und die Anpassung eines ausgeglichenen Binärbaums können wie folgt zusammengefasst werden: Vier Situationen: LL-Typ, RR-Typ, LR-Typ, RL-Typ

(5) Baum: Ein Baum ist eine endliche Menge mit n (n>=0) Knoten: a. Und es gibt nur einen bestimmten Knoten namens Wurzel

b. Wenn n>1, können die verbleibenden Knoten in m (m>0) unterteilt werden. gegenseitig disjunkte endliche Mengen T1, T2,...,Tm, wobei jede Menge selbst ein Baum ist und T1, T2,...,Tm Teilbäume der Wurzel genannt werden

(6) Heap: Ein Heap ist ein vollständiger Binärbaum mit den folgenden Eigenschaften. Alle seine Nicht-Blattknoten sind nicht größer (oder nicht kleiner) als seine linken und rechten untergeordneten Knoten. Wenn alle Nicht-Blattknoten im Heap nicht größer sind als ihre linken und rechten untergeordneten Knoten, spricht man von einem kleinen oberen Heap (kleiner Wurzel-Heap). Wenn alle Nicht-Blattknoten im Heap nicht kleiner sind als ihre linken und rechten Untergeordnete Knoten werden als großer Heap (großer Root-Heap) bezeichnet ={S1, S2, S3,…,Sn }

(8) B-Baum

3 Grafische Struktur: In der grafischen Struktur ist eine Korrelation zwischen mehreren Knoten zulässig, was als „many-to-many“ bezeichnet wird „Beziehung, die in gerichtete Graphen und ungerichtete Graphen unterteilt werden kann

Tutorial-Empfehlung: „

C-Sprach-Tutorial-Video“

Das obige ist der detaillierte Inhalt vonWas ist die Datenstruktur in C-Sprache? Was sind die gängigen Datenstrukturen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!