Table linéaire
Les tables linéaires sont les structures de données les plus simples et les plus couramment utilisées. Ce sont des séquences finies composées de n éléments de données individuels (nœuds). Parmi eux, le nombre n des éléments de données est la longueur du tableau. Lorsque n est nul, il devient une table vide. Une table linéaire non vide est généralement enregistrée comme:
(a1, a2,…, ai-1, ai, ai + 1,…, an)
1. Stockage séquentiel et algorithme des tables linéaires
Le stockage séquentiel d'une table linéaire fait référence au stockage des éléments de données de la table linéaire en un ensemble d'unités de stockage continues avec des adresses dans leur ordre logique. La table linéaire stockée de cette manière est appelée table séquentielle.
1. Définition structurelle du tableau des commandes
classe publique seqlist {/ * L'espace initial est 10 * / private statique final int list_size = 10; / * Les données du tableau sont utilisées pour stocker les éléments * / private int [] data; / * Le tableau actuel est long, le nombre réel d'éléments stockés * / private int longueur; } 2. Fonctionnement d'insertion
L'opération d'insertion de la table séquentielle fait référence à l'insertion d'un nouvel élément entre le i-1e élément et le i-th element de la table linéaire. Étant donné que les éléments adjacents de la table de séquence sont également adjacents dans la structure physique, leurs relations de stockage physique doivent également subir des changements correspondants. Sauf si i = n + 1, tous les éléments à partir du i-thème élément de la table de commande d'origine doivent être reculés respectivement par 1 position.
/ ** * Insérez un nouvel élément avant le I -th Position dans la table de commande Node * @param List Table de commande * @Param I Insérez la position * @param nœud nouvel élément * / public void insertlist (seqlist list, int i, int node) {if (i <1 || i> list.length + 1) {System.out.Println ("Position Error"); retour; } if (list.length> = list_size) {System.out.println ("Overflow"); retour; } pour (int j = list.length - 1; j> = i - 1; j -) {/ * Démarrez à partir du dernier élément et revenez un par un * / list.data [j + 1] = list.data [j]; } / * Insérer un nouvel élément * / list.data [i-1] = node; / * Ajouter 1 à la longueur du tableau * / list.length ++; } 3. Supprimer l'opération
L'opération de délétion de la table séquentielle fait référence à la suppression du i-tème élément du tableau. Contrairement à l'opération d'insertion, l'insertion déplace l'élément vers l'arrière et l'opération de suppression fait avancer l'élément.
/ ** * Supprimez le i-tth élément de la liste des tableaux de commande et renvoyez l'élément supprimé * @param la table de séquence de liste * @param i élément position * @return node * / public int DeleteleList (seqlist list, int i) {int node = 0; if (i <0 || i> list.length) {System.out.println ("Erreur de position"); Node de retour; } node = list.data [i-1]; for (int j = i; j <list.length; j ++) {/ * élément avant * / list.data [j-1] = list.data [j]; } list.length -; Node de retour;} 4. Table de commande inverse
Tout d'abord, utilisez la moitié de la longueur du tableau comme nombre de fois de contrôle de boucle, échangez le dernier élément du tableau dans l'ordre du premier élément, échangez le deuxième dernier élément de l'ordre du deuxième élément, et ainsi de suite jusqu'à ce que l'échange soit terminé.
/ ** * Table de séquence inverse * @param liste Table de commande originale * Table de séquence @return après inverse * / public seqlist converts (list list) {int node; int length = list.length / 2; pour (int i = 0; i <length; i ++) {/ * Éléments d'échange symétriques * / int j = list.length - 1 - i; node = list.data [i]; list.data [i] = list.data [j]; list.data [j] = nœud; } Retour List; } 2. Storage de chaîne et algorithme des tables linéaires
L'espace de stockage des éléments de données de la structure de stockage de la chaîne qui stocke les tables linéaires peut être continu ou discontinu, de sorte que les nœuds de la liste liés ne sont pas accessibles au hasard. Le stockage de la chaîne est l'une des méthodes de stockage les plus courantes.
Lorsque vous utilisez une structure de stockage de chaîne pour représenter chaque élément de données, en plus de stocker les informations de l'élément lui-même, une adresse qui indique l'emplacement de stockage des éléments suivants est également nécessaire. La table linéaire représentée par cette méthode de stockage est appelée liste liée.
5. Définition structurelle de la liste unique
classe publique LinkList {/ * champ de données * / données charbon privées; / * Élément successif * / liaison privée Suivant;} 6. Algorithme de construction de table
La méthode d'insertion d'en-tête commence par une table vide, lit à plusieurs reprises les données, génère un nouveau nœud, stocke les données de lecture dans le champ de données du nouveau nœud, puis insère le nouveau nœud sur l'en-tête de la liste liée actuelle jusqu'à la fin.
/ ** * Créer une table par insertion d'en-tête * @Param Chars Array de caractères * @return Liste liée unique * / public linkList CreateListf (char [] chars) {linkList node; LinkList head = null; pour (char ch: chars) {/ * postuler pour un nouveau nœud * / node = new linkList (); node.data = ch; / * Pointer vers le nœud successeur * / node.next = head; head = nœud; } / * Retour au nœud de tête * / la tête de retour;} 7. Méthode d'insertion de queue Algorithme de construction de table
L'ordre des nœuds dans la table d'insertion d'en-tête est l'opposé de l'ordre lors de la saisie. Si l'ordre d'entrée est cohérent, la méthode d'insertion de queue peut être utilisée.
/ ** * Méthode d'insertion de queue Pour créer une table * @param char à caractères Array * @return Liste liée unique * / public linkList CreeList (char [] chars) {linkList node; LinkList head = null; LinkList arrière = null; pour (char ch: chars) {node = new linkList (); node.data = ch; if (head == null) {/ * Le nouveau nœud est le nœud de tête * / head = nœud; } else {/ * Le nœud précédent pointe vers le nouveau nœud * / rear.next = node; } / * La queue de la table pointe vers le nouveau nœud * / arrière = nœud; } / * Retour au nœud de tête * / la tête de retour;}Ce qui précède est tout le contenu de cet article. J'espère que cela sera utile à l'apprentissage de tous et j'espère que tout le monde soutiendra davantage Wulin.com.