Quelle est la différence entre la matrice et la liste?
6 Réponses :
Bien qu'il y ait rien comme une liste Array: accès aléatoire, taille prédéfinie. D'autres langues comme, disent python, peuvent avoir la liste des s et Commentaires utiles ci-dessous:
Vous pouvez ajouter des listes de matrices. Listes qui sont en interne un tableau qui est doublé en cas de besoin et réduit de moitié lorsque seulement 1/4 complet. Cela donne O (1) pour ajouter, supprimer, obtenir (index) amortis. - lasseespeholt
liste in c en soi mais Vous pouvez certainement parler d'une liste liée à la mise en œuvre.
Liste liée: Accès séquentiel, taille au moment de l'exécution.
s et s inbuilt et leur signification peut différer.
de Python n'est pas une liste liée. Et la distinction entre Python Liste et (code> est est peut stocker tout ce que la matrice ne peut stocker que des types primitifs ( int , float , etc.). - KennyTM
La liste de Python n'est pas une liste liée. Et la distinction entre Python list et array est la liste peut stocker n'importe quoi tandis que tableau ne peut stocker que des types primitifs (int , flotter, etc.).
Vous pouvez ajouter des listes de matrices. Listes qui sont en interne un tableau qui est doublé en cas de besoin et réduit de moitié lorsque seulement 1/4 complet. Cela donne O (1) pour ajouter, supprimer, obtenir (index) amortis.
"Liste" de Python est en fait quelles autres langues appellent une matrice (de taille dynamique).
Les gars, avec la ligne Python, je suggérais seulement qu'il y a des langues qui viennent avec une distinction et un type intégré.
Il n'existe pas de liste standard en C ++, ce qui est une chose en C ++, où il est implémenté comme un Liste à double liaison .
Les principales différences sont que les matrices ont accès aléatoire - Vous pouvez accéder à tout membre du tableau dans O (1) heure (c.-à-d. Si a était un tableau, a [4] ) et avoir une taille pré-définie lors de la compilation. Les listes liées ont un accès séquentiel - pour accéder à un élément, vous devez faire boucler la liste jusqu'à ce que vous obteniez dans l'élément que vous souhaitez (c.-à-d. Si B était une liste liée, pour accéder au 5ème élément de < Code> B Il vous faudrait itération à travers des éléments 0, 1, 2, 3 et 4) et la taille peut être cultivée et réduite de manière dynamique.
@Stephen: Bien que je puisse souligner que des tableaux peuvent également avoir leurs tailles définies au moment de l'exécution à l'aide de la répartition de la mémoire dynamique - il ne a doit être défini à la compilation, il appartient au programmateur de choisir
La taille de chaque élément est fixée à l'heure de la compilation. Le fait que vous puissiez créer de manière dynamique une ne pas changer le fait que la recherche est O (1)
@bguiz Autant que j'étais au courant, des tableaux purs ont leurs tailles fixées au moment de la compilation. Voulez-vous dire faire quelque chose comme utiliser MALLOC et un pointeur sur un type pour faire l'allocation de mémoire dynamique?
@Stephen: Il y a aussi des VLAS en C99. À tout le monde, à l'exception de Microsoft, C99 est "actuel" C, et C89 est "vieux" C. mais je pense que Bguiz a fait simplement dire malloc .
@Stephen @steve Jessop: idk à propos de C, en C ++ Si vous utilisez l'opérateur Nouveau lors de l'initialisation d'un tableau, il est créé sur le tas, pas la pile et sa taille est déterminée au moment de l'exécution.
in c , une matrice est une région de taille fixe de stockage contiguë contenant plusieurs objets, l'une après l'autre. Ce tableau est un "objet" dans le sens que c donne au mot - essentiellement juste une certaine mémoire qui représente quelque chose. Un objet pourrait simplement être un Vous pouvez distinguer légèrement entre les objets et le tableau types . Souvent, les gens utilisent des objets qui sont attribués avec Donc, quand je dis qu'un tableau est une taille fixe, je veux dire que la taille ne peut pas changer une fois la matrice créée, ce qui inclut les VLAS. Il y a C'est ce qu'est un tableau. Le langage de programmation C ne définit rien appelé une liste. Je ne peux pas vraiment comparer quelque chose qui est bien défini, avec quelque chose qui n'est pas défini ;-) généralement "liste" signifierait un Liste liée , mais dans certains contextes ou dans d'autres langues, cela signifie d'autres choses.
Pour cette affaire, dans d'autres langues "Array" pourrait signifier d'autres choses, bien que je ne puisse pas penser à une langue dans laquelle cela signifie quelque chose de très différent d'un tableau C.
Si votre question n'a vraiment rien à voir avec c et est une question de structures de données langagnes-agnostiques, "Quelle est la différence entre une matrice et une liste liée?", alors c'est un duplicata de ceci:
int .
MALLOC et utilisés via un pointeur sur le premier élément. Mais C a également des types spécifiques pour les érayes de différentes tailles, ainsi que pour des tableaux de longueur variable, dont la taille est définie lors de leur création. Les VLAS ont un nom légèrement trompeur: la taille n'est que "variable" en ce sens qu'elle n'est pas fixée au moment de la compilation. Il ne peut pas changer pendant la durée de vie de l'objet.
realloc , qui renvoie logiquement un pointeur sur un nouveau tableau qui remplace l'ancien, mais peut parfois renvoyer la même adresse transmise, après avoir modifié la taille de la matrice en place. RealLoc fonctionne sur les allocations de mémoire, pas sur les tableaux en général.
"Je ne peux pas penser immédiatement à une langue où [Array] signifie quelque chose de très différent d'un tableau C." Regardez la structure de données «Array» de PHP; C'est le plus différent que je puisse penser.
Une caractéristique souvent appréciée des structures de données liées est que vous pouvez les utiliser dans des situations où la mémoire est très fragmentée en raison de la garantie de mémoire contiguë entre les éléments. Par exemple, vous pourriez avoir 100 Mo d'espace libre, mais seulement dire une exécution maximale de mémoire de longueur libre de 10 Mo. Dans ce cas, vous ne pouvez créer qu'un tableau de taille 10 Mo, mais peut-être une liste liée potentiellement plus grande puisque vous pourrez utiliser chaque manche de mémoire libre qui était suffisamment grande pour contenir un seul noeud.
pour la matrice, il a une taille fixe comme nous écrivons, Insertion et suppression est plus facile dans la liste que dans la matrice
Raison: nous pouvons simplement utiliser pour modifier les pointeurs pour insérer et supprimer pour la liste liée, mais pour l'insertion de matrice et la suppression nécessite Shifftright and Shiftleft
Liste liée utilise un nœud de tête factice pour éviter des cas spéciaux d'insertion dans une liste vide ou en supprimant le dernier nœud d'une liste de la taille de l'unité; Et, il utilise des liens doubles pour permettre itération dans les deux sens. Le coût bien sûr est l'espace supplémentaire nécessaire pour contenir le nœud factice (coût minimal) et le lien précédent supplémentaire en plus le lien suivant habituel pour chaque nœud (coût beaucoup plus important).
En tableau, nous pouvons ajouter à l'aide de son accès aléatoire
dans la liste liée, la référence au nœud de la queue est tout simplement en tête de tête.prev, qui nous donne la possibilité d'ajouter à la liste en temps constant (sans avoir à itérer pour trouver la référence de la queue, ou avoir à maintenir un séparé référence queue).
Mais dans la matrice, nous devons réapparaître le tableau avant d'insérer.
tableau a la flexibilité nécessaire pour atteindre l'accès aléatoire contrairement à la liste liée.
La liste liée a des problèmes,
Il consomme un stockage de mémoire supplémentaire pour le pointeur que nous utilisons!
Complexité du temps de O (N) au lieu de O (1) comme dans la graisse
La traversée inversée est difficile pour la liste liée et si nous utilisons une liste doublement liée, un autre pointeur signifie plus de stockage de mémoire supplémentaire
restriction de tas aussi bien! La mémoire n'est attribuée que s'il y a de l'espace disponible dans le tas. Si la mémoire insuffisante, la mémoire ne sera pas créée.
Array a des problèmes comme,
une chance de gaspillage de mémoire ou de pénurie.
J'espère que cela vous aidera! :)
tableau n'a que des types de données similaires (c'est-à-dire) qu'ils sont de nature homogène. Nous ne pouvons avoir qu'un éventail de chaînes, d'entiers, etc. La taille de la matrice est prédéfinie.
Mais dans le cas de la liste
Il y a des listes en C? Je veux dire, mis à part les centaines d'exemples de livres minimalistes de listes liées?