Mesa lineal
Las tablas lineales son las estructuras de datos más simples y más utilizadas. Son secuencias finitas compuestas de n elementos de datos individuales (nodos). Entre ellos, el número N de los elementos de datos es la longitud de la tabla. Cuando n es cero, se convierte en una mesa vacía. Una tabla lineal no vacía generalmente se registra como:
(a1, a2, ..., ai-1, ai, ai+1, ..., an)
1. Algoritmo de almacenamiento secuencial de tablas lineales
El almacenamiento secuencial de una tabla lineal se refiere al almacenamiento de los elementos de datos de la tabla lineal en un conjunto de unidades de almacenamiento continuo con direcciones en su orden lógico. La tabla lineal almacenada de esta manera se llama tabla secuencial.
1. Definición estructural de la tabla de pedidos
public class seqlist { / * El espacio inicial es 10 * / private static final int list_size = 10; /* Los datos de la matriz se utilizan para almacenar elementos*/ private int [] datos; /* La tabla actual es larga, el número real de elementos almacenados*/ Private int Longin; } 2. Insertar operación
La operación de inserción de la tabla secuencial se refiere a insertar un nuevo elemento entre el elemento I-1th y el elemento I-Th de la tabla lineal. Dado que los elementos adyacentes de la tabla de secuencia también están adyacentes en la estructura física, sus relaciones de almacenamiento físico también deben sufrir cambios correspondientes. A menos que i = n+1, todos los elementos que comienzan desde el elemento i-th de la tabla de pedidos original deben moverse hacia atrás en 1 posición respectivamente.
/** * Inserte un nuevo elemento antes de la posición i-th en el nodo de lista de la tabla de pedidos * @param Tabla de orden de la lista * @param I Insertar posición * @param nodo nuevo elemento */public void insertList (seqlist list, int i, int node) {if (i <1 || i> list.length + 1) {system.println ("error de posición");; devolver; } if (list.length> = list_size) {System.out.println ("Overflow"); devolver; } for (int j = list.length - 1; j> = i - 1; j -) { / * Comience desde el último elemento y retroceda uno por un * / list.data [j+1] = list.data [j]; } /* Insertar nuevo elemento* / list.data [i-1] = nodo; / * Agregar 1 a la longitud de la tabla */ list.length ++; } 3. Eliminar operación
La operación de eliminación de la tabla secuencial se refiere a eliminar el elemento I-Th en la tabla. A diferencia de la operación de inserción, la inserción está moviendo el elemento hacia atrás, y la operación de eliminación está moviendo el elemento hacia adelante.
/*** Elimine el elemento i-th en la lista de la tabla de pedidos y devuelva el elemento eliminado* @param list secuence la tabla* @param I elemento posición* @return node*/public int deletElist (Seqlist List, int i) {int node = 0; if (i <0 || i> list.length) {system.out.println ("error de posición"); nodo de retorno; } nodo = list.data [i-1]; for (int j = i; j <list.length; j ++) { /* elemento hacia adelante* / list.data [j-1] = list.data [j]; } list.length -; nodo de retorno;} 4. Tabla de orden inverso
Primero, use la mitad de la longitud de la tabla como el número de controles de bucle, intercambie el último elemento en la tabla en el orden del primer elemento, intercambie el segundo último elemento en el orden del segundo elemento, y así sucesivamente hasta que se complete el intercambio.
/*** Tabla de secuencia Inverse* @param Lista Tabla de pedido original* @return Tabla de secuencia después de inversa*/public SeqList Converts (SeqList List) {int nodo; int longitud = list.length/2; for (int i = 0; i <longitud; i ++) { /* elementos de intercambio simétrico* / int j = list.length - 1 - i; nodo = list.data [i]; list.data [i] = list.data [j]; list.data [j] = nodo; } Lista de retorno; } 2. Algoritmo de almacenamiento en cadena de tablas lineales
El espacio de almacenamiento de los elementos de datos de la estructura de almacenamiento de cadena que almacena tablas lineales puede ser continuo o discontinuo, por lo que no se puede acceder a los nodos de la lista vinculada al azar. El almacenamiento de la cadena es uno de los métodos de almacenamiento más comunes.
Cuando se usa una estructura de almacenamiento en cadena para representar cada elemento de datos, además de almacenar la información del elemento en sí, también se necesita una dirección que indica la ubicación de almacenamiento de los elementos posteriores. La tabla lineal representada por este método de almacenamiento se llama lista vinculada.
5. Definición estructural de una sola lista vinculada
public class LinkList { /* Data Field* / private Char Data; /* Elemento sucesivo*/ private LinkList Next;} 6. Algoritmo de construcción de mesa
El método de inserción del encabezado comienza con una tabla vacía, lee repetidamente los datos, genera un nuevo nodo, almacena los datos de lectura en el campo de datos del nuevo nodo e inserta el nuevo nodo en el encabezado de la lista vinculada actual hasta que finaliza.
/*** Crear tabla por inserción de encabezado* @param chars Arrray* @return Single Linked List*/public LinkList CreateListf (char [] chars) {LinkList node; Linklist head = null; for (charch: chars) { /* Aplicar un nuevo nodo* / node = new LinkList (); node.data = ch; /* Punto al nodo sucesor*/ node.next = head; cabeza = nodo; } /* Regrese al nodo de cabeza* / return Head;} 7. Algoritmo de construcción de tabla de método de inserción de la cola
El orden de los nodos en la tabla de inserción del encabezado es lo opuesto al orden al ingresar. Si el orden de entrada es consistente, se puede utilizar el método de inserción de la cola.
/*** Método de inserción de cola para crear la tabla* @param Chars Array de caracteres* @return Lista vinculada única*/public LinkList CreateListR (char [] chars) {LinkList node; Linklist head = null; Linklist trasero = nulo; for (charch: chars) {nodo = new LinkList (); node.data = ch; if (head == null) { /* El nuevo nodo es el nodo head* / head = node; } else { /* El nodo anterior apunta al nuevo nodo* / roard.next = node; } /* La cola de la tabla apunta al nuevo nodo* / roard = nodo; } /* Regrese al nodo de cabeza* / return Head;}Lo anterior es todo el contenido de este artículo. Espero que sea útil para el aprendizaje de todos y espero que todos apoyen más a Wulin.com.