Quelle est la structure des données en langage C ? Quelles sont les structures de données communes ?

En langage C, la structure de données fait référence à un ensemble d'éléments de données qui ont une ou plusieurs relations spécifiques les uns avec les autres. Il s'agit d'un moyen pour les ordinateurs de stocker et d'organiser des données communes : structure de données linéaire ; (Tableau, liste chaînée, pile, file d'attente et liste linéaire), structure arborescente (arbre binaire, arbre binaire complet, arbre de recherche binaire, tas), structure graphique (graphe orienté et graphe non orienté).

L'environnement d'exploitation de ce tutoriel : système Windows 7, version c99, ordinateur Dell G3.

Qu'est-ce qu'une structure de données ?

La structure des données est la manière dont les ordinateurs stockent et organisent les données. Une structure de données fait référence à un ensemble d'éléments de données qui ont une ou plusieurs relations spécifiques les uns avec les autres

La mise en œuvre de la plupart des structures de données nécessite l'aide de pointeurs et de types de structure dans le langage C

Passons ensuite au sujet d'aujourd'hui : O(∩_∩)O Plusieurs structures de données courantes

(1) Structure de données linéaire : il existe généralement une relation biunivoque entre les éléments, ce qui est le plus souvent utilisé Un type de structure de données, généralement : tableaux, piles, files d'attente et tables linéaires

(2) Structure arborescente : Il existe une relation hiérarchique entre les nœuds, et un nœud dans chaque couche peut et ne peut être combiné qu'avec Un nœud de la couche supérieure est lié, mais il peut être lié à plusieurs nœuds de la couche suivante en même temps, ce que l'on appelle une relation « un-à-plusieurs ». Les types courants sont : arbre, tas

<.> (3) Structure graphique : Dans la structure graphique, la corrélation entre plusieurs nœuds est autorisée, ce que l'on appelle une relation "plusieurs-à-plusieurs"

Ce qui suit est une brève introduction à chacune de ces structures de données :

1. Structures de données linéaires : les plus typiques sont : les tableaux, les piles, les files d'attente et les listes linéaires

(1) Tableaux et listes chaînées

a. Tableau : stocke un ensemble de données du même type. La longueur du tableau doit être spécifiée à l'avance, comme un tableau unidimensionnel, un tableau bidimensionnel, tableau multidimensionnel, etc.

b. Liste chaînée : La liste chaînée est un type de langage C. Une structure largement utilisée. Elle est implémentée sous la forme d'une mémoire allouée dynamiquement. pour stocker une liste chaînée d'éléments de données. Généralement, un champ de pointeur est ajouté pour chaque élément pour pointer vers les éléments suivants

c, tableau La différence avec une liste chaînée :

À partir d'une structure logique. perspective : les tableaux doivent avoir une longueur fixe définie à l'avance et ne peuvent pas s'adapter à l'augmentation ou à la diminution dynamique des données ; les listes chaînées allouent dynamiquement le stockage et peuvent s'adapter à l'augmentation ou à la diminution dynamique de la situation des données, et les éléments de données peuvent être facilement insérés et. supprimé (lors de l'insertion ou de la suppression d'éléments de données dans le tableau, d'autres éléments de données doivent être déplacés)

Du point de vue du stockage mémoire : (statique) le tableau alloue de l'espace à partir de la pile (en utilisant NEW est créé dans le tas), ce qui est pratique et rapide pour les programmeurs, mais a un petit degré de liberté ; les listes chaînées allouent de l'espace à partir du tas, qui a un grand degré de liberté mais est difficile à demander et à gérer

Depuis le perspective des méthodes d'accès : le tableau est en mémoire Il est stocké en continu, vous pouvez donc utiliser des index d'indice pour un accès aléatoire ; la liste chaînée est une structure de stockage liée, et lors de l'accès aux éléments, elle n'est accessible que de manière séquentielle d'avant en arrière. de manière linéaire, de sorte que l'efficacité d'accès est inférieure à celle des tableaux

(2) Pile, file d'attente et table linéaire : les méthodes de stockage séquentiel et de stockage en chaîne peuvent être utilisées pour le stockage

Stockage séquentiel : à l'aide de la position relative des éléments de données dans l'espace de stockage Position pour représenter la relation logique entre les éléments

Stockage en chaîne : utilisez des pointeurs représentant les adresses de stockage des éléments de données pour représenter la logique relation entre les éléments

a. Pile : autorisée uniquement à la fin de la séquence Opérations, les opérations sur la pile ne peuvent être effectuées qu'en haut de la pile. Généralement, la pile est également appelée dernier en premier. structure linéaire premier entré-dernier sorti

Pile séquentielle : Une pile utilisant une structure de stockage séquentielle est appelée une pile séquentielle, c'est-à-dire qu'elle a besoin d'un espace avec des adresses consécutives est utilisé pour stocker les éléments de la pile. Le type de la pile séquentielle est défini comme suit :

Pile de chaîne : Une pile utilisant une structure de stockage en chaîne est appelée pile de chaîne :

b. File d'attente : les opérations ne sont autorisées qu'aux deux extrémités de la séquence. Généralement, la file d'attente est également appelée structure linéaire premier entré, premier sorti

File d'attente circulaire : A. Une structure de stockage séquentielle est utilisée. La file d'attente doit allouer de l'espace de stockage en fonction de la longueur maximale possible de la file d'attente. Son type est défini comme suit :

File d'attente en chaîne : une file d'attente utilisant. une structure de stockage en chaîne est appelée file d'attente en chaîne et nécessite généralement de définir les pointeurs de tête et de queue uniquement pour les nœuds de tête et de queue de la liste chaînée :

c. : les opérations sont autorisées à n'importe quelle position de la séquence. La position d'opération de la table linéaire n'est pas limitée. Les opérations de table linéaire sont très flexibles, notamment l'insertion et la suppression à n'importe quelle position, ainsi que l'interrogation et la modification d'éléments à n'importe quelle position.

Table séquentielle : une table linéaire représentée par une structure de stockage séquentielle est appelée table séquentielle. Un ensemble d'unités de stockage avec des adresses consécutives est utilisé pour stocker les éléments de données de la table linéaire en une seule fois, c'est-à-dire des emplacements de stockage adjacents. représente la séquence entre deux éléments consécutifs. Afin d'éviter de déplacer des éléments, généralement seule l'insertion et la suppression d'éléments à la fin du tableau sont prises en compte dans la définition de l'interface du tableau de séquence. implémenté de cette manière peut également être appelé table de pile :

Liste linéaire : comprend généralement une liste chaînée simple, une liste chaînée double, une liste chaînée circulaire et une liste chaînée circulaire bidirectionnelle

Liste chaînée simple :

Liste chaînée double :

Comparaison de deux structures de stockage de tableaux linéaires :

Tableaux séquentiels :

Avantages : Dans les tableaux séquentiels, la logique est relative. Deux éléments adjacents sont également physiquement adjacents, ce qui facilite la recherche. La complexité temporelle d'accès à n'importe quel élément est O. (1)

Inconvénients : ne convient pas pour insérer ou supprimer des éléments à n'importe quelle position. Étant donné que les éléments doivent être déplacés, la complexité temporelle moyenne est O(n)

liste chaînée :

.

Avantages : Pour insérer ou supprimer un élément à n'importe quelle position du lien, il suffit de modifier le pointeur correspondant et pas besoin de déplacer l'élément ; Allocation dynamique à la demande, pas besoin de pré-allouer un espace vide continu ; selon la demande maximale

Inconvénients : Il n'est pas pratique de rechercher un élément, vous devez partir du pointeur de tête et rechercher le long du champ du pointeur, donc la complexité temporelle moyenne est O(n) <.>

2. Structure arborescente : Il existe une relation hiérarchique entre les nœuds. Un nœud dans chaque couche ne peut et ne peut être lié qu'à un nœud de la couche précédente, mais il peut également être lié à plusieurs nœuds de la couche suivante. . Les nœuds sont liés, appelés relation « un-à-plusieurs ». Les types courants incluent : arbre, tas

(1) Arbre binaire : un arbre binaire est une structure de données récursive qui contient n (n>=). 0) nœuds. Ensemble fini de points, un arbre binaire a les caractéristiques suivantes :

Un arbre binaire peut être un arbre vide ; chaque nœud d'un arbre binaire a exactement deux sous-arbres, dont un ou deux peuvent être des nœuds. être vide ; chaque nœud dans un arbre binaire. Les positions des sous-arbres gauche et droit ne peuvent pas être inversées. Si les positions des deux sont modifiées, cela deviendra un autre arbre binaire

(2) Arbre binaire complet : démarrage. de la racine, de haut en bas, de gauche à droite, Chaque nœud de l'arbre binaire complet est numéroté en continu de 1 à n Si chaque nœud correspond biunivoque aux nœuds numérotés de 1 à n dans l'arbre binaire complet de. profondeur k, on l'appelle un arbre binaire complet

a. Utiliser une structure de stockage séquentielle : utiliser un tableau unidimensionnel pour stocker un arbre binaire complet. Le numéro du nœud correspond à l'indice du nœud (. par exemple, la racine est 1, alors l'enfant gauche de la racine est 2i=21=2, et l'enfant droit est 2i +1=21+1=2)

b. Adopter une structure de stockage en chaîne :

Liste chaînée binaire :

Liste chaînée ternaire : son nœud a un parent de champ de pointeur de plus que le binaire lié liste, qui permet d'exécuter les parents du nœud et de faciliter la recherche des nœuds parents

Comparaison de deux structures de stockage : Pour un arbre binaire complet, en utilisant un stockage séquentiel La structure peut non seulement économiser de l'espace, mais également utiliser la valeur d'indice de l'élément du tableau pour déterminer la position du nœud dans l'arbre binaire et la relation entre les nœuds, mais en utilisant le stockage séquentiel Stockage de structure : généralement, les arbres binaires ont tendance à gaspiller de l'espace .La structure en chaîne peut surmonter cette lacune

(3) Arbre de recherche binaire : L'arbre de recherche binaire est également appelé arbre de tri binaire, ou arbre binaire vide, ou Un arbre binaire avec les caractéristiques suivantes :

a. Si son sous-arbre gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre gauche sont inférieures à la valeur du nœud racine

b Si le sous-arbre droit de n'est pas vide. , alors les valeurs de tous les nœuds du sous-arbre droit sont supérieures à la valeur du nœud racine

c Ses sous-arbres gauche et droit sont également des arbres de recherche binaires

(4) Équilibré. arbre binaire : Un arbre de recherche binaire équilibré est appelé arbre binaire équilibré. Un arbre binaire équilibré est soit un arbre vide, soit un arbre de recherche binaire avec les propriétés suivantes : son sous-arbre gauche et son sous-arbre droit sont tous deux des arbres binaires équilibrés. la valeur absolue de la différence entre les hauteurs du sous-arbre gauche et du sous-arbre droit ne dépasse pas 1

Le déséquilibre et l'ajustement de l'arbre binaire équilibré peuvent être résumés comme suit quatre situations : type LL, type RR, type LR, type RL

(5) Arbre : Un arbre est un ensemble fini contenant n (n>=0) nœuds Dans toute espèce d'arbre non vide : a. . Il y a et seulement Il y a un nœud spécifique appelé racine

b Lorsque n>1, les nœuds restants peuvent être divisés en m (m>0) ensembles finis mutuellement disjoints T1, T2,... ,Tm , chaque ensemble lui-même est un arbre, et T1, T2,...,Tm sont appelés sous-arbres de la racine

(6) Tas : Un tas est un arbre binaire complet avec les caractéristiques suivantes. Tous ses nœuds non-feuilles ne sont pas plus grands (ni plus petits) que ses nœuds enfants gauche et droit. Si tous les nœuds non-feuilles du tas ne sont pas plus grands que leurs nœuds enfants gauche et droit, on parle de petit tas supérieur (petit tas racine) si tous les nœuds non-feuilles du tas ne sont pas plus petits que leurs nœuds gauche et droit. nœuds enfants, on l'appelle un grand tas supérieur (gros tas racine)

(7) Union-find : Union-find fait référence à un ensemble composé d'un ensemble. de sous-ensembles disjoints, notés : S= {S1, S2, S3,…,Sn}

(8) B-tree

Structure du graphe : Dans la structure du graphe. , la corrélation entre plusieurs nœuds est autorisée. C'est ce qu'on appelle une relation "plusieurs-à-plusieurs" et peut être divisée en graphiques orientés et graphiques non orientés

Recommandation du didacticiel : "Vidéo du didacticiel en langage C "

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!