Le compteur linéaire est une structure linéaire, qui est une séquence limitée qui a le même élément de données N (n ≥ 0).
1. Array
Le tableau a des limites supérieures et inférieures, et les éléments du réseau sont continus dans les limites supérieures et inférieures.
Le diagramme schématique du tableau de 10,20,30, 40, 50 50 est le suivant:
Caractéristiques du tableau : les données sont continues; la vitesse d'accès aléatoire est rapide.
Le réseau légèrement plus compliqué est un tableau multidimensionnel et un tableau dynamique. Pour la langue C, le tableau multidimensionnel est également réalisé via un tableau unique. En ce qui concerne le tableau dynamique, il s'agit d'un tableau de la capacité du groupe d'index qui peut croître dynamiquement; Vector; pour Java, la collection de la collection est concernée.
Deuxièmement, la liste liée à une voie <Br /> Liste liée à une voie (liste liée unique) est un type de liste liée.
Le diagramme schématique d'une seule liste liée est le suivant:
La tête de la tête est vide, le nœud successeur de la tête est "nœud 10" (nœud de données 10), et le nœud successeur de "Node 10" est "Node 20" (données avec les données 10) ,. ..
Node de suppression à chaîne unique
Supprimer "nœud 30"
Avant la suppression: le nœud successeur de "Node 20" est "Node 30", et le nœud successeur de "Node 30" est "Node 40".
Après la suppression: le nœud successeur de "Node 20" est "Node 40".
Liste unique liée au nœud
Ajouter "Node 15" entre "Node 10" et "Node 20"
Avant d'ajouter: le nœud successeur de "Node 10" est "Node 20".
Après avoir ajouté: le nœud successeur de "Node 10" est "Node 15", et le nœud successeur de "Node 15" est "Node 20".
La caractéristique d'une seule liste liée est que la direction de liaison du nœud est une seule voie par rapport au tableau, la vitesse d'accès aléatoire de la liste de chaîne unique est lente, mais la liste des données de la liste liée à une seule fois est élevée.
Troisième liste liée à deux voies
La liste liée à deux voies (Liste liée à double) est un type de liste liée. Comme une seule liste liée, la liste de la chaîne double est également composée de nœuds. Par conséquent, à partir de n'importe quel nœud de la liste liée à deux voies, vous pouvez facilement accéder à ses nœuds à débordement et aux nœuds suivants. Généralement, nous construisons tous une liste liée à deux voies circulaires.
Le diagramme schématique de la liste liée à double est la suivante:
L'en-tête est vide, le nœud successeur de la tête est "nœud 10" (nœud de données 10); successeur Le nœud est "Node 10"; .
Node de suppression de montre à double chaîne
Supprimer "nœud 30"
Avant la suppression: le nœud successeur de "Node 20" est "Node 30", et le pré-node de "Node 30" est "Node 20". Le nœud successeur de "Node 30" est "Node 40", et le pré-node de "Node 40" est "Node 30".
Après la suppression: le nœud successeur de "Node 20" est "Node 40", et le pré-node de "Node 40" est "Node 20".
Liste à double liaison ajoutant des nœuds
Ajouter "Node 15" entre "Node 10" et "Node 20"
Avant d'ajouter: le nœud successeur de "Node 10" est "Node 20", et le nœud précédent de "Node 20" est "Node 10".
Après avoir ajouté: le nœud successeur de "Node 10" est "Node 15", et le pré-node de "Node 15" est "Node 10". Le nœud successeur de "Node 15" est "Node 20", et le nœud précédent de "Node 20" est "Node 15".
La mise en œuvre de la liste des chaînes doubles est introduite ci-dessous et les trois implémentations de C / C ++ / Java sont introduites respectivement.
1. C Implémentez une liste liée à double
Implémentation du fichier de liste lié à deux deux ans (double_link.h)
# Ifndef_double_link_h # define_double_link_h // Créer une "liste liée à deux-voies". Succès, retour à la tête; SUCCÈS, RETOUR 0; Retour à 1 pour le vide; extern int dlink_is_empty (); Succès, retournez au pointeur de nœud; Extern void * dlink_get (int index); Succès, retournez au pointeur de nœud; extern void * dlink_get_first (); Succès, retournez au pointeur de nœud; extern void * dlink_get_last (); Succès, retour 0; autrement, retour -1. extern int dlink_insert (int index, void * pval); Succès, retour 0; autrement, retour -1. extern int dlink_insert_first (void * pval); Succès, retour 0; autrement, retour -1. extern int dlink_append_last (void * pval); Succès, retour 0; Sinon, retourne à -1Extern int dlink_delete (int int Succès, retour 0; Sinon, retournez -1Extern dans dlink_delete_first (); Succès, retour 0; sinon, retourne à -1Extern int dlink_delete_last (); #
Double_link.c dans une liste liée à deux voies
#include <stdio.h> #include <malloc.h> / *** C Lingle Linge Linked Liste peut stocker des données arbitraires. ** @author skywang * @ date 2013/11/07 * /// nœuds de liste liés à deux Notez que la valeur de la tête ne stocke pas la valeur de l'élément! Intersection Intersection Node statique * PHEAD = NULL; Static int count = 0; Succès, retournez au pointeur de nœud; Node statique * create_node (void * pval) {node * pnode = null; pnode = (node *) malloc (sizeof (node)); "); Return null;} // par défaut, le premier nœud et le dernier nœud de pnode pointent vers son propre pnode-> prev = pnode-> next = pnode; // la valeur du nœud est pvalpnode-> p = PVAL; / Créer une "liste liée à deux voies". Succès, retour 0; autrement, retour -1. int create_dlink () {// Créer l'en-tête PHEAD = CREATE_NODE (null); Return count == 0;} // revient à la "liste liée à deux ans" int dlink_size () {return count;} // Obtenez le "nœud dans la position d'index dans la liste liée à deux-voies" nœud statique * get_ Node (Node (int index) {ifx <0 || index> = count) {printf ("% s a échoué! Index Out of Bound! / N", __func __); if (index <= (count / 2)) {int i = 0; nœud * pnode = phad-> suivant; Recherchez int J = 0; nœud "nœud statique * g et_first_node () () return get_node (0);} // obtient le" dernier nœud "nœud statique * get_last_node () {return get_node (count-);} // Obtenez l'élément de position d'index Dans la liste liée à double sens ". Succès, renvoyer la valeur du nœud; autrement, renvoyer -1. void * dlink_get (int index) {node * pindex = get_node (index); 1 个元素的值 ”void * dlink_get_first () {return dlink_get (0);} // 获取“ 双向链表中最后 1 个元素的值 ”void * dlink_get_last () {return dlink_get (count- 1);} // Insérez "PVAL" dans la position d'index. Succès, retour 0; autrement, retour -1. int dlink_insert (int index, void * pval) {// insérer l'en-tête if (index == 0) return dlink_insert_first (pValt (pval); // obtenez le nœud de nœud correspondant à la position à insérer. if! Pindex) return -1; // 创建 创建 创建 节点 节点 ”nœud * pnode = create_node (pval); if (! pnode) return -1; pnode-> prev = pindex-> prev; pnode-> next = pindex; pindex; -> prev-> next = pnode; {Node * Pnod E = Create_Node (PVAL); ++; Retour 0;} // insérer "Pval" dans la position finale int dlink_append_last (void * pval) {node * pnode = create_node (pval); ; LISTE LIENNE DE LA WAY ". Succès, retour 0; autrement, retour -1. int dlink_delete (int index) {node * pindex = get_node (index); > next-> prev = pindex-> prev; pindex-> prev-> next = pindex-> next; free (pindex); count -; return 0;} // 删除第一个节点 int dlink_delete_first () {return dlink_delete (0);} // supprimer un nœud int dlink_delete_last () {return dlink_delete (count-);} // revisiter "Liste liée à deux voies". Succès, retour 0; autrement, retour -1. int destrust_dlink () {if (! phad) {printf ("% s a échoué! dlink est null! / n", __func __); ;Programme de test de liste lié à deux voies (dlink_test.c)
#include <stdio.h> #include "double_link.h" / *** c Langue pour implémenter un programme de test de liste lié à deux voies. ** (01) Int_test () * Démontrer "INT DATA" dans une liste liée à deux voies. * (02) string_teest () * Démontrer "Données de ruban" dans une liste liée à deux voies. * (03) Object_teest () * Démontrez l'objet "dans une liste liée à deux voies. ** @Author Skywang * @Date 2013 / 11/07 * /// Liste liée à deux voies Operation int data void int_teest () {int iarr [4] = {10, 20, 30, 40}; n ---- -% s ------ ", __func __); create_dlink (); // créer une liste liée à deux voies dlink_insert (0, & iarr [0]); // insérer les données dlink_insert (0, & & ig & & ig & & ig & & & & 1]); data printf ("dlink_is_empty () =% d / n", dlink_is_empty ()); La taille de la liste liée à deux voies de la liste liée à deux voies int i; int * p; ) dlink_get (i); propf ("dlink_get (% d) =% d / n", i, * p)} destrust_dlink ();} void string_test () {char * sarr [4] = {"ten", " vingt "," trente "," fringf ("/ n ----% s ----% s- - / n", __func __); 0, Sarr [0]); Liste liée à deux ans; n ", dlink_size ()); // la taille de la liste liée à deux voies // imprime toutes les données int i dans la liste liée à deux voies; char * p; int sz = dlink_size (); for (i = 0; TAGE_STU {int id; Char Name [20];} Stu; {40, {40, {40, {40, "Dan"},}; # define arr_stu_size ", __func __); create_dlink (); // créer une liste liée à deux voies dlink_insert (0, & arr_stu [0] ); "dlink_is_empty () =% d / n", dlink_is_empll ()); Liste liée à deux ans // toutes les données de la liste liée à deux ans int i; ) dlink_get (i); ); string_test (); object_test (); // démontre "objet" dans une liste liée à deux voies. Retour 0;}Résultat de course
---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = ThirtyDlink_get (1) = TwentyDlink_get (2) = Ten - - object_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30, Vic] dlink_get (1) = [20, jody] dlink_get (2) = [10, sky]
2. C ++ réalise la liste des chaînes doubles
Implémentez le fichier de liste lié à deux deux voies (Doublelink.h)
#Ifndef double_link_hxx # Définir Double_Link_hxx # include <ioStream> Utilisation de Namespace std; Prev, dnode * suivant) {this-> value = t; size (); int IS_EMPTY (); int delete_last (); ) {// Créer "Speed". Remarque: il n'y a pas de données de stockage sur la tête! PHEAD = NOUVEAU DNODE <T> (); > :: ~ DoughLink () {// Supprimez tous les nœuds dnode <t> * ptmp; ; chain list为空template<class T>int DoubleLink<T>::is_empty(){return count==0;}// 获取第index位置的节点template<class T>DNode<T>* DoubleLink<T>: : get_node (int index) {// La validité du paramètre de jugement if (index <0 || index> = count) {cout << "Get Node a échoué! L'index dans Bound!" / Rechercher si (index <= 2) {int i = 0; ;} / / Revers de la recherche int j = 0; ; Temple <class T> TriveLink <T> :: get_first () {return get_node (0) -> valeur;} // Obtenez la valeur du dernier nœud. Position d'index avant le modèle <classe T> int DoubleLink <T> :: insert (int index, t t) {ifx == 0) return insert_first (t) ;; > Précédent); Pindex-> NEXT = PNODE; Template <classe T> int DoubleLink <T> :: insert_fring (t) {dnode <t> * pnode = new dnode <t> (t, phead-> suivant); > Next = pnode; > Prev = pnode; > Next-> prev = Pindex-> prev; T> int Doublelink <T> :: Delete_First () {return del (0);} // 删除最后一个节点 Template <class T> int Doublelink <T> :: Delete_last () {return del (count-);} #EndifFichier de test de liste lié à deux voies (dlinktest.cpp)
#include <iostream> #include "DoubleLink.h" Userspace std; --- "<< endl; // Créer une liste liée à deux voies Doublelink <nt> * pdlink = new Doublelink <nt> (); pdLink-> insert (0, 20); // insérer 20 dans la première position PDLINK-> APPEND_LAST (10); << "is_empty () =" << pdLink-> is_empty () << endl; << endl; toutes les données int sz = pdlink-> size (); -> get (i) << endl;} void string_test () {String sarr [4] = {"ten", "vingt", "trente", "quarante"}; ---- "" << endl; Le deuxième élément de Sarr dans le premier pdLink-> APPEND_LAST (SARR [0]); ); Position // La liste liée à deux voies est vide << "IS_EMPTY () =" << PDLINK-> IS_EMPTY () << endl; () = "<< pdLink-> size () << endl; // toutes les données int sz = pdlink-> size (); for (int i = 0; i <sz; i ++)" <") = "<< pdLink-> get (i) << endl;} struct stu {int id; name char [20];}; statique Stu arr_stu [] = {10," ciel "}, {20 20," Jody "}, {30" Liste liée DoubleLink <Stu> * pdLink = new DoubleLink <Stu> (); > APPEND_LAST (arr_stu [0]); à la première position // si la liste liée à deux voies est vide << "is_empty () =" << pdlink-> is_empty () << endl; = "<< pdLink-> size () << endl; // imprime toutes les données int sz = pdLink-> size () dans la liste liée à deux voies; = 0; i <sz; i ++) {p = pdLink-> get (i); main () {int_teest (); string_test (); object_test (); // démontre "objet" dans une liste liée à deux voies. Retour 0;}Exemple description
Dans l'exemple ci-dessus, j'ai mis la "déclaration" et "implémentation" de la liste liée à deux voies dans le fichier d'en-tête. Les spécifications de programmation nous avertissent: séparez la déclaration et l'implémentation de la réclamation, et le montant du fichier d'en-tête (fichier .h ou .hpp) ne contenait que l'instruction et était responsable de l'implémentation dans le fichier d'implémentation (fichier .cpp)!
Alors pourquoi faites-vous cela? En effet, dans la mise en œuvre d'une liste liée à deux voies, le modèle est adopté; et le compilateur C ++ ne prend pas en charge la compilation distincte du modèle! Pour le dire simplement, s'il est déclaré dans Doublelink.h et implémenté dans DoubleLink.cpp; lorsque nous créons un objet de Doublelink dans d'autres catégories, l'erreur sera compilée. Pour des raisons spécifiques, vous pouvez vous référer à "Pourquoi les compilateurs C ++ ne peuvent pas prendre en charge la compilation distincte des modèles".
Résultat de course
---- int_test ---- is_empty () = 0size () = 3pdlink (0) = 30pdlink (1) = 20pdLink (2) = 10 ---- String_test ----- vide () = 0size () = 3PDLink (0) = ThirtyPdLink (1) = TwentyPdLink (2) = Ten ---- Object_teest ---- is_Empty () = 0size () = 3pdLink (0) = [30, Vic] Pdlink (1) = [ 20 20, Jody] pdlink (2) = [10, ciel]
3. Java réalise la liste des chaînes doubles
Mise en œuvre de Doublelink.java
/ *** Liste liée à deux voies de Java. * Remarque: il y a une liste liée à deux voies dans le package de collection de Java. / Top Headpate DNODE <T> MORD; {this.value = valeur; Remarque: il n'y a pas de données de stockage sur la tête! Mhead = new Dnode <T> (null, null, null); Return mcount;} // si la liste liée est vide booléen isEmpty () {return mcount == 0;} // le nœud privé dnode <t> getNode (int index) {ifx) {index <0 || Mcount) New IndexOutofboundSexception (); ;} // 反向查找 dnode <T> rnode = mhead.prev; int rindex = mcount - index -1; pour (int j = 0; j <rindex; j ++) rnode = rnode. / Obtenez la valeur du nœud de la position d'index. <T> (T, Mhead, mhead.Next); T> (t, inode.prev, inode); Public void insertFirst (t t) {insert (0, t);} // ajouter le nœud à la fin de la liste liée du public void appendlast (t t) {dnode <t> new DNODE <T> (t, mhead. Précédent Mhead); Mhead. .next = inode.next; Node public void deletelast () {del (mcount-);}}Programme de test (dlinktest.java)
/ *** Liste liée à deux voies de Java. * Remarque: il y a une liste liée à deux voies dans le package de collection qui est livré avec Java. Opération de table liée à deux ans int Data STATIC VOID INT_TEEST () {int [] {10, 20, 30, 40}; = New DoubleLink <inte Première position // Si la liste liée à deux voies est le système vide.out.printf ("iSempty () =% b / n", dlink.isempty ()); d / n ", dlink.size ()); // imprime tous les nœuds pour (int i = 0; i <dlink.size (); i ++) System.out .println (" dlink ("+ i +") = "+ dlink.get (i));} private static void string_test () {string [] sarr = {" ten "," vingt "," trente "," quarante ""}; / n ---- String_test ---- "); // Créer une liste liée à deux voies Doublelink <string> dlink = new Doublelink <string> (); [1]); // insérer le deuxième élément de Sarr dans la première position dlink.appendLast (sarr [0]); La première position // Si la liste liée à deux voies est un système vide.out.printf ("iSempty () =% b / n", dlink.isempty ()); / / system.out.printf ("size () =% d / n ", dlink.size ()); // imprime tous les nœuds pour (int i = 0; i <dlink.size (); i ++) System.out.println (" dlink ("+ i + ") =" + dlink.get (i));} // la classe interne private static student {private String student (int id, string name) {this.id = id; ouverridePublic String toString () {"+ id +", "+ name +"] ";} Tudent [] studers = new student [] {new étudiant (10," ciel "), nouveau étudiant (20," jody "), nouveau Student (30, "Vic"), New Student (40, "Dan"),}; Liste liée à deux voies Doublerink <Student> dlink = new DoubleLink <Student> (); Le premier élément des étudiants à Dlink.insertFirst (étudiants [étudiants [étudiants [2]); printf ("isempty () =% b / n", dlink.isempty ()); nœuds pour (int i = 0; i <dlink.size ()); i ++) {System.out.println ("dlink (" + i + ") =" + dlink.get (i));}} Static void main (String [] arts) {int_test (); string_test (); object_test (); // démontre "objet" dans une liste liée à deux voies. }}Résultat de course
---- int_test ---- isEmpty () = falseSize () = 3DLink (0) = 30DLink (1) = 20DLink (2) = 10 ---- String_test ——-- iSempty () = falseize () = 3DLink (0) = ThirtyDlink (1) = TwentyDLink (2) = Ten ---- Object_teest --- isEmpty () = FalseSize () = 3DLink (0) = [30, Vic] dlink (1) = [20 20 , Jody] dlink (2) = [10, ciel]
Ce qui précède est tout le contenu de cet article.