El medidor lineal es una estructura lineal, que es una secuencia limitada que tiene el mismo elemento de datos de tipo n (n ≥ 0).
1. Array
La matriz tiene límites superiores e inferiores, y los elementos de la matriz son continuos en los límites superior e inferior.
El diagrama esquemático de la matriz de 10,20,30, 40, 50 50 es el siguiente:
Características de la matriz : los datos son continuos;
La matriz ligeramente más complicada es una matriz multidimensional y una matriz dinámica. Para el lenguaje C, la matriz multidimensional también se realiza a través de una matriz de dimensión. En cuanto a la matriz dinámica, es una matriz de la capacidad del grupo índice que puede crecer dinámicamente; Vector;
En segundo lugar, la lista vinculada de One -Ways <Br /> One -Way (lista única vinculada) es un tipo de lista vinculada.
El diagrama esquemático de una sola lista vinculada es el siguiente:
El cabezal de la cabeza está vacío, el nodo sucesor de la cabeza es "nodo 10" (nodo de datos 10), y el nodo sucesor del "nodo 10" es "nodo 20" (datos con datos 10) ,. ..
Nodo de eliminación de cadena única
Eliminar "Nodo 30"
Antes de eliminar: el nodo sucesor del "nodo 20" es "nodo 30", y el nodo sucesor del "nodo 30" es "nodo 40".
Después de eliminar: el nodo sucesor del "nodo 20" es "nodo 40".
Lista única vinculada nodo agregado
Agregue "nodo 15" entre "nodo 10" y "nodo 20"
Antes de agregar: el nodo sucesor del "nodo 10" es "nodo 20".
Después de agregar: El nodo sucesor del "nodo 10" es "nodo 15", y el nodo sucesor del "nodo 15" es "nodo 20".
La característica de una sola lista vinculada es que la dirección del enlace del nodo es de una manera;
Tercera lista vinculada de dos vías
La lista vinculada de dos vías (lista dual vinculada) es un tipo de lista vinculada. Al igual que una sola lista vinculada, la lista de cadena dual también está compuesta de nodos. Por lo tanto, a partir de cualquier nodo en la lista vinculada de dos vías, puede acceder fácilmente a sus nodos frontales y nodos posteriores. En general, todos construimos una lista circular de dos vías.
El diagrama esquemático de la lista dual vinculada es el siguiente:
El encabezado está vacío, el nodo sucesor de la cabeza es "Nodo 10" (nodo de datos 10); Sucesor El nodo es "Nodo 10"; .
Nodo de eliminación de reloj de doble cadena
Eliminar "Nodo 30"
Antes de eliminar: el nodo sucesor del "nodo 20" es "nodo 30", y el pre -nodo del "nodo 30" es "nodo 20". El nodo sucesor del "nodo 30" es "nodo 40", y el nodo previo del "nodo 40" es "nodo 30".
Después de eliminar: el nodo sucesor del "nodo 20" es "nodo 40", y el nodo previo del "nodo 40" es "nodo 20".
Lista de enlaces dobles Agregar nodos
Agregue "nodo 15" entre "nodo 10" y "nodo 20"
Antes de agregar: el nodo sucesor del "nodo 10" es "nodo 20", y el nodo anterior del "nodo 20" es "nodo 10".
Después de agregar: El nodo sucesor del "nodo 10" es "nodo 15", y el nodo previo del "nodo 15" es "nodo 10". El nodo sucesor del "nodo 15" es "nodo 20", y el nodo anterior del "nodo 20" es "nodo 15".
La implementación de la lista de doble cadena se introduce a continuación, y las tres implementaciones de C/C ++/Java se introducen respectivamente.
1. C Implementar una lista dual vinculada
Implemente el archivo de lista vinculada de dos vías (double_link.h)
#Ifndef_double_link_h#define_double_link_h // Cree una "lista vinculada de dos vías". Éxito, regrese a la cabeza; Éxito, regresar 0; Volver a 1 para el vacío; extern int dlink_is_empty (); Éxito, regrese al puntero del nodo; Extern void* dlink_get (int index); Éxito, regrese al puntero del nodo; extern void* dlink_get_first (); Éxito, regrese al puntero del nodo; extern void* dlink_get_last (); Éxito, regresar 0; extern int dlink_insert (int index, void *pval); Éxito, regresar 0; extern int dlink_insert_first (void *pval); Éxito, regresar 0; extern int dlink_append_last (void *pval); Éxito, regresar 0; Éxito, regresar 0; Éxito, regresar 0;
Double_link.c en una lista vinculada de dos vías
#include <stdio.h> #include <malloc.h>/*** c Lingle La lista vinculada de dos vías puede almacenar datos arbitrarios. ** @Author Skywang* @Date 2013/11/07*/// Nodos de lista vinculados de dos vías typedef struct Tag_node {sTroct tag_node*previo; ¡Tenga en cuenta que el valor de la cabeza no almacena el valor del elemento! Intersección Intersección Nodo estático *phead = nulo; Static int count = 0; Éxito, regrese al puntero del nodo; Nodo estático *create_node (void *pval) {nodo *pnode = null; "); Return null;} // El valor predeterminado, el primer nodo y el último nodo de pnode apuntan a su propio pnode-> prev = pnode-> next = pnode; // El valor del nodo es pvalpnode-> p = PVAL; Éxito, regresar 0; int create_dlink () {// Crea el encabezado phead = create_node (null); Return count == 0;} // Regrese a la "lista vinculada de dos vías" int dlink_size () {return count;} // Obtener el nodo "en la posición de índice en la lista vinculada de dos vías" nodo estático* get_ nodo (nodo (int index) {ifx <0 || índice> = count) {printf ("%s fallido! Index fuera de límite!/n", __func __); if (index <= (count/2)) {int i = 0; Search int j = 0; nodo "nodo estático * g et_first_node () () return get_node (0);} // Obtenga el nodo estático" Último nodo " * get_last_node () {return get_node (count-);} // Obtenga el" elemento de la posición de índice de índice en la lista vinculada de dos vías ". Éxito, retorno de valor del nodo; void * dlink_get (int index) {nodo * pindex = get_node (index); 1 个元素的值 ”void* dlink_get_first () {return dlink_get (0);} // 获取“ 双向链表中最后 1 个元素的值 ”void* dlink_get_last () {return dlink_get (count- 1);} // Inserte "PVAL" en la posición del índice. Éxito, regresar 0; int dlink_insert (int index, void * pval) {// Inserte el encabezado if (index == 0) return dlink_insert_first (pvalt (pval); // Obtenga el nodo del nodo correspondiente a la posición que se insertará. if -> previo-> next = pnode; {nodo *pnod e = create_node (pval); ++; ; Lista de forma vinculada ". Éxito, regresar 0; int dlink_delete (int index) {nodo *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);} // Eliminar un nodo int dlink_delete_last () {return dlink_delete (count-);} // revisit "Lista vinculada de dos vías". Éxito, regresar 0; int destruye_dlink () {if (! ;Programa de prueba de lista vinculada de dos vías (dlink_test.c)
#include <stdio.h> #include "double_link.h"/*** C lenguaje para implementar un programa de prueba de lista vinculada de dos vías. ** (01) int_test ()* Demuestre "datos int" en una lista vinculada de dos vías. * (02) String_teest ()* Demuestre "datos Strine" en una lista vinculada de dos vías. * (03) Object_teest ()* Demuestre el "objeto" en una lista vinculada de dos vías. ** @author Skywang* @Date 2013/11/07* /// Operación de lista vinculada de dos vías ints Data void int_teest () {int iarr [4] = {10, 20, 30, 40}; n -----%s ------ ", __func __); create_dlink (); // Cree una lista vinculada de dos vías dlink_insert (0, & iarr [0]); // Inserte los datos dlink_insert (0, & & IG & & IG & & IG & & & 1]); Data printf ("dlink_is_empty () =%d/n", dlink_is_empty ()); El tamaño de la lista de dos vías de la lista vinculada de dos vías int i; ) dlink_get (i); Veinte "," treinta "," fringf ("/n ----%s ----%s--/n", __func __); 0, sarr [0]); Lista vinculada de dos vías; n ", dlink_size ()); // El tamaño de la lista vinculada de dos vías // imprime todos los datos int i en la lista vinculada de dos vías; char *p; int sz = dlink_size (); for (i = 0; tag_stu {int id; {40, {40, {40, {40, "dan"},};#define arr_stu_size ", __func __); create_dlink (); // Cree una lista vinculada de dos vías dlink_insert (0, y arr_stu [0] ); / Insertar datos dlink_insert (0, y arr_stu [1]) a la lista vinculada de dos vías a la lista de datos de dos vías. "dlink_is_empty () =%d/n", dlink_is_empl ()); Lista de dos vías // todos los datos en la lista vinculada de dos vías int i; ) dlink_get (i); ); / Demuestre "datos int" en una lista vinculada de dos vías. string_test (); objeto_test (); Regresar 0;}Resultado de ejecución
---- int_test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = Thirtlink_get (1) = twentyDlink_get (2) = Ten-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 ++ realiza una lista de cadena dual
Implementar el archivo de lista vinculada del código de dos vías (DoubleLink.h)
#Ifndef double_link_hxx#define double_link_hxx#incluir <ioStream> Uso de Namespace std; Prev, dnode *Next) {this-> value = t; size () intelete_last (); ) {// Crear "velocidad". Nota: ¡No hay datos de almacenamiento en la cabeza! Phead = new DNode <T> (); > :: ~ Doughlink () {// Eliminar todos los nodos dnode <T>* ptmp; ; Eliminar ptmp;} // Eliminar la "cabeza" eliminar phead; Lista de cadena 为空 Template <Class t> int DoubleLink <T> :: is_empty () {return count == 0;} // 获取第 índice 位置的节点 plantilla <class t> dnode <t>* doublelink <t>:: : get_node (int index) {// juicio de la validez de parámetros if (index <0 || índice> = count) {cout << "¡Get Node fallado! / Finding if (index <= count/ 2) {int i = 0; ;} / / Investigación de búsqueda int j = 0; ; Templo <Class t> Trivelink <T> :: get_first () {return get_node (0)-> valor;} // Obtener el valor del último nodo. Posición de índice antes de la plantilla <class t> int doubleLink <T> :: inserta (int index, t t) {ifx == 0) return insert_first (t) ;; > Previo); Plantilla <class t> int doubleLink <T> :: insert_fring (t) {dnode <t>* pnode = new Dnode <T> (t, phead-> next); > Next = pnode; > Prev = pnode; > Next-> prev = pindex-> prev; pindex-> next = pindex-> next; T> int Doublelink <T> :: delete_first () {return del (0);} // 删除最后一个节点 Template <Class t> int Doublelink <t> :: delete_last () {return del (count-);} #EndifArchivo de prueba de la lista vinculada de dos vías (dlinktest.cpp)
#InClude <Iostream> #include "DoubleLink.h" UserSpace std; --- "<< endl; // Cree una lista vinculada de dos vías DoubleLink <int>* pdlink = new DoubleLink <int> (); Pdlink-> Insert (0, 20); // Insertar 20 en la primera posición pdlink-> append_last (10); << "is_empty () =" << pdlink-> is_empty () << endl; << endl; -> get (i) << endl;} void string_test () {string sarr [4] = {"ten", "veinte", "treinta", "cuarenta"}; ---- "" << endl; el segundo elemento en Sarr en el primer Pdlink-> append_last (Sarr [0]); ) ;/ si la lista de dos vías está vacía << "is_empty () =" << pdlink-> is_empty () << endl; () = "<< pdlink-> size () << endl; // Todos los datos int sz = pdlink-> size (); para (int i = 0; i <sz; i ++)" <") = "<< pdlink-> get (i) << endl;} struct stu {int id; char name [20];}; stat stu arr_stu [] = {10," cielo "}, {20 20," Jody "}, {30," Vic "}, {40," dan "},};#define arr_stu_size cout <<"/n ---- Object_test ---- "<< endl; // Cree un dos- Lista de forma vinculada Doublelink <Stu>* PDLink = new DoubleLink <Stu> (); > Append_last (arr_stu [0]); // Agregue el primer elemento en ARR_STU al primer elemento al final del PDLINK vinculado-> insert_fring (arr_stu [2 [2 [2]; // Inserte el tercer elemento en ARR_STU a la primera posición // si la lista vinculada de dos vías está vacía << "is_empty () =" << pdlink-> is_empty () << endl; = "<< pdlink-> size () << endl; // imprima todos los datos int sz = pdlink-> size () en la lista vinculada de dos vías; = 0; i <sz; i ++) {p = pdlink-> get (i); main () {int_teest (); string_test (); objeto_test (); Regresar 0;}Descripción del ejemplo
En el ejemplo anterior, puse la "declaración" y la "implementación" de la lista vinculada de dos vías en el archivo de encabezado. Las especificaciones de programación nos advierten: separar la declaración e implementación del reclamo, y el monto del archivo de encabezado (.h archivo o .hpp) contenía solo la declaración, ¡y fue responsable de la implementación en el archivo de implementación (archivo .cpp)!
Entonces, ¿por qué haces esto? Esto se debe a que en la implementación de una lista vinculada de dos vías, la plantilla se adopta; En pocas palabras, si se declara en DoubleLink.h y se implementa en DoubleLink.cpp; Por razones específicas, puede consultar "por qué los compiladores C ++ no pueden soportar la compilación separada de plantillas".
Resultado de ejecución
---- int_test ---- is_empty () = 0Size () = 3pdlink (0) = 30pdlink (1) = 20pdlink (2) = 10 ---- String_test ----- vacía () = 0Size () = 3pdlink (0) = thIrTypDlink (1) = twentyPdlink (2) = diez ---- objeto_teest ---- is_empty () = 0Size () = 3pdlink (0) = [30, Vic] pdlink (1) = [[[ 20 20, Jody] Pdlink (2) = [10, Sky]
3. Java realiza una lista de cadena dual
Doublelink.java Implementación
/*** Lista vinculada de dos vías de Java. * Nota: Hay una lista vinculada de dos vías en el paquete de colección de Java. / Top Headpate DNode <T> Mhead; {this.Value = valor; Nota: ¡No hay datos de almacenamiento en la cabeza! Mhead = nuevo DNODE <T> (NULL, NULL, NULL); Return mcount;} // Si la lista vinculada está vacía boolean isEmpty () {return mcount == 0;} // El nodo privado dnode <t> getNode (int index) {ifx) {index <0 || index> = McOUNT) tirar nuevo indexOutOfBoundSException (); ;} // 反向查找 dnode <t> rnode = mhead.prev; int rindex = mcount - index -1; para (int j = 0; j <rindex; j ++) rnode = rnode. / Obtenga el valor del nodo de la posición de índice. <T> (t, mhead, mhead.next); T> (t, inode.prev, inode); Public void insertFirst (t t) {insert (0, t);} // Agregue el nodo al final de la lista vinculada del público void appendlast (t t) {dnode <t> nuevo dnode <t> (t, mhead. Prev mhead); .next = inode.next; Nodo public void deletelast () {del (mCount-);}}Programa de prueba (dlinktest.java)
/*** Lista vinculada de dos vías de Java. * Nota: Hay una lista vinculada de dos vías en el paquete de colección que viene con Java. Tabla de dos vías Operación INT INT INT DATIC ANTECHE INT_TEEST () {int [] {10, 20, 30, 40}; = New DoubleLink <integer> (); Primera posición // si la lista vinculada de dos vías es vacía.out.printf ("isEmpty () =%b/n", dlink.isempty ()); d/n ", dlink.size ()); // imprima todos los nodos para (int i = 0; i <dlink.size (); i ++) system.out .println (" dlink ("+i+") = "+dlink.get (i));} private static void string_test () {string [] sarr = {" ten "," veinte "," treinta "," cuarenta ""}; /n ---- string_test ----- "); // Cree una lista vinculada de dos vías Doublelink <String> dlink = new DoubleLink <String> (); [1]); // Inserte el segundo elemento en Sarr en la primera posición dlink.appendLast (Sarr [0]); La primera posición // si la lista vinculada de dos vías es vacía System.out.printf ("isEtimty () =%b/ n", dlink.isempty ());// system.out.printf ("size () =%d/ n ", dlink.size ()); // imprime todos los nodos para (int i = 0; i <dlink.size (); i ++) system.out.println (" dlink ("+i+ ") ="+dlink.get (i));} // El estudiante de clase estática privada de clase interna {estudiante de identificación de cadena privada (int id, string name) {this.id = id; overridePublic String toString () {"+id+", "+nombre+"] ";} tudent [] studers = new student [] {new Student (10," Sky "), New Student (20," Jody "), Nuevo Estudiante (30, "Vic"), Nuevo Estudiante (40, "Dan"),}; Lista de dos vías Doublerink <Sentude> Dlink = New DoubleLink <Enstude> (); El primer elemento en los estudiantes para dlink.insertfirst (estudiantes [estudiantes [estudiantes [2]); printf ("isEmpty () =%b/n", dlink.isempty ()); nodos para (int i = 0; i <dlink.size ()); Static void main (string [] arts) {int_test (); string_test (); objeto_test (); }}Resultado de ejecución
---- int_test ---- isEmpty () = falsesize () = 3dlink (0) = 30dlink (1) = 20dlink (2) = 10 ---- string_test ——- isEmpty () = falsesize () = 3dlink (0) = ThirtyDlink (1) = Twentydlink (2) = diez ---- Object_teest --- isEmpty () = falsize () = 3dlink (0) = [30, Vic] dlink (1) = [20 20 20 , Jody] dlink (2) = [10, cielo]
Lo anterior es todo el contenido de este artículo.