Mesa unicada simulada
Tabla lineal:
Las tablas lineales (también llamadas tablas secuenciales) son las estructuras de datos más básicas, más simples y más utilizadas.
La relación entre los elementos de datos en una tabla lineal es una relación uno a uno, es decir, excepto para el primer y último elemento de datos, otros elementos de datos están conectados al final.
La estructura lógica de las tablas lineales es simple, lo cual es fácil de implementar y operar.
En aplicaciones prácticas, las tablas lineales se utilizan en forma de tablas lineales especiales, como pilas, colas y cadenas.
Las características básicas de la estructura lineal son:
1. Debe haber un "primer elemento" único en la colección;
2. Debe haber un "último elemento" único en la colección;
3. Excepto por el último elemento, hay un sucesor único (último elemento);
4. Excepto por el primer elemento, hay una unidad frontal única (pieza delantera).
Lista vinculada: lista vinculada
Una lista vinculada es una estructura de almacenamiento no continua y no secuencial en una unidad de almacenamiento físico. El orden lógico de los elementos de datos es que cada elemento de datos implementado a través del orden de enlace del puntero en la lista vinculada está contenido en un "punto de enlace".
Un enlace es un objeto de una clase, y este tipo se puede llamar enlace. Hay muchos enlaces similares en la lista vinculada, y cada enlace contiene un campo referenciado al siguiente enlace.
El objeto de lista vinculado en sí contiene una referencia al primer nodo de enlace. (Si no hay primero, no se puede ubicar)
Una lista vinculada no puede acceder directamente a los elementos de datos como una matriz (usando subíndices), pero debe posicionarse con la relación entre datos, es decir, acceder al siguiente enlace referenciado por el nodo de enlace, y luego el siguiente, hasta que se acceda a los datos requeridos y se accede a la complejidad de tiempo de insertar e insertar los datos requeridos en el cabezal (1),, porque solo el que solo se accede a los datos se accede a los nodo específico, y insertar el nodo específico, y insertar el nodo específico, y insertar el nodo específico, y insertarlo después de insertar el nodo específico, y insertarlo, y insertar el nodo específico, y insertarlo después del nodo específico. Estas operaciones requieren un promedio de búsqueda de la mitad de los nodos en la lista vinculada, con una eficiencia de O (N).
Lista única vinculada:
Una tabla lineal está representada por "secuencia de nodos" y se llama lista lineal vinculada (lista vinculada única)
Es una estructura de datos de acceso en cadena, que utiliza un conjunto de unidades de almacenamiento con direcciones arbitrarias para almacenar elementos de datos en una tabla lineal. (Este conjunto de células de memoria puede ser continuo o discontinuo)
La estructura del nodo de enlace:
Datos de datos de datos que almacena valores de nodo; campo de puntero (campo de cadena) que almacena la referencia del nodo Siguiente
La lista vinculada vincula los n nodos de la tabla lineal en su orden lógico a través del dominio de enlace de cada nodo.
Una lista vinculada con solo un campo de enlace por nodo se llama una sola lista de enlaces. En una dirección, solo hay referencias a nódulos posteriores.
/*** Lista única vinculada: método de inserción del encabezado y primera salida* El lado izquierdo de la lista vinculada se llama cabezal de cadena y el lado derecho se llama la cola de la cadena. * El método de inserción del encabezado para construir una sola lista vinculada se obtiene al ver el extremo derecho de la lista vinculada como se solucionó, y la lista vinculada continúa extendiéndose a la izquierda. * Lo primero que proviene del método de inserción del encabezado es el nodo de cola * @author Stone */ public class SingLelinkedList <T> {enlace privado <t> primero; // El primer nodo público SingLelinkedList () {} public boolean isEtimty () {return primero == null; } public void insertFirst (t data) {// Insertar en el cabezal del enlace de cadena <T> newlink = new Link <T> (datos); newlink.next = primero; // La siguiente del nuevo nodo apunta al nodo anterior primero = newlink; } enlace público <t> deleteFirst () {// Eliminar el enlace del encabezado de cadena <T> temp = primero; primero = first.next; // Cambiar el primer nodo para devolver temp; } enlace público <t> find (t t) {link <t> find = primero; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return Find; } enlace público <t> delete (t t) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = primero; primero = first.next; // Cambiar el primer nodo a la siguiente temperatura de retorno del nodo; }} Enlace <t> p = primero; Enlace <t> q = primero; while (! P.data.equals (t)) {if (p.next == null) {// regístrese hasta el final de la cadena pero no encontrado return null; } else {q = p; P = P.Next; }} q.next = p.next; regreso p; } public void displayList () {// transip system.out.println ("list (primero-> último):"); Enlace <t> corriente = primero; while (current! = null) {current.displaylink (); actual = current.next; }} public void displaylisterverse () {// enlace transversal inverso <t> p = primero, q = first.next, t; Mientras que (q! = null) {// se invierte el puntero, el orden de datos atravesado es hacia atrás t = q.next; // NO3 if (p == primero) {// Cuando es el encabezado original, el .next de la cabeza debe estar vacío p.next = null; } Q.Next = P; // NO3 -> NO1 PUNTER REVERSE P = Q; // El inicio es inversa q = t; // NO3 Start} // En el if en el bucle anterior, primero. Después de la inversión, P se asigna a First First = P; DisplayList (); } enlace de clase <T> {// Datos de punto t de enlace; // enlace de campo de datos <t> Siguiente; // Pointer posterior, enlace de dominio de cadena de nodo (t Data) {this.data = data; } void displayLink () {System.out.println ("Los datos son" + data.ToString ()); }} public static void main (string [] args) {SingLelinkedList <integer> list = new SingLelinkedList <Integer> (); list.insertFirst (33); list.insertFirst (78); list.insertFirst (24); list.insertFirst (22); list.insertFirst (56); list.displayList (); list.deleteFirst (); list.displayList (); System.out.println ("Find:" + list.find (56)); System.out.println ("Find:" + list.find (33)); System.out.println ("Eliminar Find:" + list.delete (99)); System.out.println ("Eliminar Find:" + list.delete (24)); list.displayList (); System.out.println ("--- Reverse ----"); list.displaylisterverse (); }}Imprimir
List (first-->last): the data is 56 the data is 22 the data is 24 the data is 78 the data is 33 List (first-->last): the data is 22 the data is 24 the data is 78 the data is 33 find:null find:linked_list.SingleLinkedList$Link@4b71bbc9 delete find:null delete encontrar: linked_list.singlelinkedlist$link@17dfafd1 list (primero-> último): los datos son 22 los datos son 78 Los datos son 33 --- reverso --- lista (primero-> último): los datos son 33 los datos son 78 los datos son 22
Lista única vinculada: Método de inserción de la cola, de nuevo en primer lugar: si se soluciona el extremo izquierdo de la lista vinculada, la lista vinculada continúa extendiéndose a la derecha, este método para establecer una lista vinculada se llama método de inserción de cola.
Al crear una lista vinculada con el método de inserción de la cola, el puntero de la cabeza se fija, por lo que se debe configurar un puntero de cola para extenderse a la derecha de la lista vinculada.
Lo primero que proviene del método de inserción de la cola es el nodo principal.
clase pública SingLelinkedList2 <T> {enlace privado <t> head; // El primer nodo público SingLelinkedList2 () {} public boolean isEtimty () {return head == null; } public void InsertLast (t data) {// Insertar enlace <T> newlink = new Link <T> (datos); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newlink; } else {link <t> roard = null; while (nextp! = null) {trasero = nextp; nextp = nextp.next; } rond.next = newlink; }} else {head = newlink; }} enlace público <t> deletelast () {// Eliminar la cola del enlace de cadena <T> p = head; Enlace <t> q = head; Mientras que (p.next! = null) {// El siguiente nodo de P no está vacío, Q es igual a la actual P (es decir, Q es el anterior y P es el siguiente). Cuando el bucle termina, Q es igual al penúltimo extremo de la cadena Q = P; P = P.Next; } // Eliminar q.next = null; regreso p; } enlace público <t> find (t t) {link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return Find; } enlace público <t> delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // Cambiar el primer nodo para devolver temp; }} Enlace <t> p = head; Enlace <t> q = head; while (! P.data.equals (t)) {if (p.next == null) {// significa que el retorno nulo no se ha encontrado al final de la cadena; } else {q = p; P = P.Next; }} q.next = p.next; regreso p; } public void displayList () {// Travel System.out.println ("List (Head-> Last):"); Enlace <t> current = head; while (current! = null) {current.displaylink (); actual = current.next; }} public void displayListerverse () {// enlace transversal inverso <t> p = head, q = head.next, t; while (q! = null) {// El puntero se invierte, y el orden de datos atravesado es hacia atrás t = q.next; // NO3 if (p == head) {// Cuando es el encabezado original, el .next de la cabeza debe estar vacío p.next = null; } Q.Next = P; // NO3 -> NO1 PUNTER REVERSE P = Q; // El inicio es inversa q = t; // NO3 Start} // En el if en el bucle anterior, head.next está vacío, cuando Q es nulo y no ejecuta el bucle, p es el elemento de datos más original. Después de la inversión, P se asigna a Head Head = P; DisplayList (); } enlace de clase <T> {// Datos de punto t de enlace; // enlace de dominio de datos <t> Siguiente; // Puntinero sucesivo, enlace de dominio de cadena de nodo (t Data) {this.data = data; } void displayLink () {System.out.println ("Los datos son" + data.ToString ()); }} public static void main (string [] args) {SingLelinkedList2 <integer> list = new SingLelinkedList2 <Integer> (); list.insertlast (33); list.insertlast (78); list.insertlast (24); list.insertlast (22); list.insertlast (56); list.displayList (); list.deletelast (); list.displayList (); System.out.println ("Find:" + list.find (56)); System.out.println ("Find:" + list.find (33)); System.out.println ("Eliminar Find:" + list.delete (99)); System.out.println ("Eliminar Find:" + list.delete (78)); list.displayList (); System.out.println ("---- Reverse -----"); list.displaylisterverse (); }}Imprimir
Lista (Head-> Last): los datos son 33 los datos son 78 Los datos son 24 los datos son 22 Los datos son 56 LIST (Head-> Último): los datos son 33 los datos son 78 los datos son 24 los datos son 22 encontrar: NULL Find: Linked_list.singLelinkedList2$ encontrar: linked_list.singlelinkedlist2$link@17dfafd1 list (head-> último): los datos son 33 los datos son 24 los datos son 22 --- reverso --- list (cabeza-> último): los datos son 22 los datos son 24 los datos son 33
Simule una lista vinculada de doble extremo para implementar colas con listas vinculadas
Lista vinculada de doble extremo:
La lista vinculada de doble extremo es muy similar a la lista vinculada tradicional. Solo tiene un nuevo atributo agregado, es decir, una referencia al último enlace es trasero.
De esta manera, insertar al final de la cadena será muy fácil. Simplemente cambie la siguiente trasera al nodo recién agregado, sin bucle para buscar el último nodo, por lo que hay InsertFirst e InsertLast
Al eliminar el encabezado de la cadena, solo necesita cambiar el punto de referencia; Al eliminar la cola de la cadena, debe vaciar el siguiente nodo del penúltimo nodo.
No hay puntos de referencia, por lo que se necesita un bucle para leer la operación
/ *** Lista vinculada de doble extremo* @author Stone*/ public class dosEndPointList <T> {Link private <t> head; // Primer enlace privado de nodo <T> trasero; // Tail Pointer public TwoEndPointList () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isEtimty () {return head == null; } public void insertFirst (t data) {// Inserte en el cabezal del enlace de cadena <T> newlink = new Link <T> (datos); newlink.next = head; // La siguiente del nuevo nodo apunta al cabezal de nodo anterior = newlink; } public void InsertLast (t data) {// Insertar enlace <T> newlink = new Link <T> (datos); if (head == null) {roard = null; } if (trasero! = null) {rond.next = newlink; } else {head = newlink; head.next = trasero; } trasero = newlink; // La próxima vez que se inserta, inserte desde la parte trasera} public t deletreadeade () {// Elimina el encabezado de la cadena if (isEmpty ()) return null; Enlace <t> temp = head; head = head.next; // Cambie el primer nodo en el siguiente nodo if (head == null) {<span style = "white-space: pre"> </span> roard = head; } return temp.data; } public t find (t t) {if (isEmpty ()) {return null; } Enlace <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} if (find == null) {return null; } return find.data; } public t eliminar (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // Cambiar el primer nodo al siguiente nodo return temp.data; }} Enlace <t> p = head; Enlace <t> q = head; while (! P.data.equals (t)) {if (p.next == null) {// indica que el retorno nulo no se ha encontrado al final de la cadena; } else {q = p; P = P.Next; }} q.next = p.next; regresar p.data; } public void displayList () {// Travel System.out.println ("List (Head-> Last):"); Enlace <t> current = head; while (current! = null) {current.displaylink (); actual = current.next; }} public void displaylisterverse () {// Inverse Traversal if (isEmpty ()) {return; } Enlace <t> p = head, q = head.next, t; while (q! = null) {// El puntero se invierte, y el orden de datos atravesado es hacia atrás t = q.next; // NO3 if (p == head) {// Cuando es la cabeza original, el .next de la cabeza debe estar vacío p.next = null; } Q.Next = P; // NO3 -> NO1 PUNTER REVERSE P = Q; // El inicio es inversa q = t; // NO3 Start} // En el if en el bucle anterior, head.next está vacío, y cuando Q está nulo y no ejecuta el bucle, P es el elemento de datos más original. Después de la inversión, P se asigna a Head Head = P; DisplayList (); } enlace de clase <T> {// Datos del nodo T de enlace; // enlace de dominio de datos <t> Siguiente; // Puntinero sucesivo, enlace de dominio de cadena de nodo (t Data) {this.data = data; } void displayLink () {System.out.println ("Los datos son" + data.ToString ()); }} public static void main (string [] args) {twoEndPointList <Integer> list = new TwoEndPointList <Integer> (); list.insertlast (1); list.insertFirst (2); list.insertlast (3); list.insertFirst (4); list.insertlast (5); list.displayList (); list.deletehead (); list.displayList (); System.out.println ("Find:" + list.find (6)); System.out.println ("Find:" + list.find (3)); System.out.println ("Eliminar Find:" + list.delete (6)); System.out.println ("Eliminar Find:" + list.delete (5)); list.displayList (); System.out.println ("--- Reverse ----"); list.displaylisterverse (); }}Imprimir
Lista (Head-> Last): los datos son 4 los datos son 2 Los datos son 1 Los datos son 3 Los datos son 5 List (Head-> Last): Los datos son 2 Los datos son 1 Los datos son 3 los datos son 5 Buscar: NULL Find: 3 Eliminar Find: NULL Eliminar Find: 5 Lista (Head-> Los datos son 2 Los datos son 1 Los datos son 3 --- Lista --- Lista (Head-> Última): El último): el último los datos es 2 Los datos son 2 Los datos son 2 Los datos son 2 los datos.
Use listas vinculadas para implementar la pila y use la lista vinculada única antes de insertarla.
Esta clase usa una lista vinculada de doble extremo para implementar:
Public Class LinkStack <T> {DataS private TwoEndpointList <T>; public LinkStack () {datas = new TwoEndPointList <T> (); } // Poner en la pila public void push (t data) {dataS.insertFirst (datos); } // Poner la pila public t pop () {return dataS.deletehead (); } // Verifique la parte superior de la pila public t Peek () {return dataS.peekhead (); } // si la pila es pública vacía boolean isEmpty () {return dataS.isEmpty (); } public static void main (string [] args) {LinkStack <Integer> stack = new LinkStack <Integer> (); para (int i = 0; i <5; i ++) {stack.push (i); } para (int i = 0; i <5; i ++) {Integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } para (int i = 0; i <6; i ++) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); } System.out.println ("----"); para (int i = 5; i> 0; i--) {stack.push (i); } para (int i = 5; i> 0; i--) {entero peek = stack.peek (); System.out.println ("Peek:" + Peek); } para (int i = 5; i> 0; i--) {Integer pop = stack.pop (); System.out.println ("Pop:" + Pop); }}}Imprimir
Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 Pop: 4 Pop: 3 Pop: 2 Pop: 1 Pop: 1 Pop: 0 Pop: Null --- Peek: 1 Peek: 1 Peek: 1 Peek: 1 Pop: 1 Pop: 1 Pop: 2 Pop: 3 Pop: 4 Pop: 5 Pop: 5
La cola de implementación de la lista vinculada se implementa utilizando una lista vinculada de doble extremo:
public class LinkQueue <t> {private twoEndpointList <t> list; public LinkQueue () {list = new TwoEndpointList <T> (); } // Inserte la cola de la cola public void insert (t data) {list.insertLast (datos); } // elimina el jefe del equipo public t remove () {return list.deletehead (); } // Ver el jefe del equipo public t peek () {return list.peekhead (); } public boolean isEtimty () {return list.isEmpty (); } public static void main (string [] args) {Linkqueue <integer> queue = new LinkQueue <Integer> (); para (int i = 1; i <5; i ++) {queue.insert (i); } para (int i = 1; i <5; i ++) {integer peek = queue.peek (); System.out.println ("Peek:" + Peek); } para (int i = 1; i <5; i ++) {integer remove = queue.remove (); System.out.println ("eliminar:" + eliminar); } System.out.println ("----"); para (int i = 5; i> 0; i--) {queue.insert (i); } para (int i = 5; i> 0; i--) {entero peek = queue.peek (); System.out.println ("Peek2:" + Peek); } para (int i = 5; i> 0; i--) {Integer Remete = queue.remove (); System.out.println ("eliminar:" + eliminar); }}}Imprimir
Peek: 1 Peek: 1 Peek: 1 Peok: 1 Peak: 1 Retire: 1 Retire: 2 Retire: 3 Retire: 4 --- Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Eliminar: 5 Eliminar: 4 Eliminar: 3 Eliminar: 2 Eliminar: 1