// La asignación estática define la tabla de secuencia. El espacio de almacenamiento es estático y el tamaño se fija desde el principio. #define MaxSize 10//Definir la longitud máxima estructura typedef { ElemType data[MaxSize]; //Utiliza una "matriz" estática para almacenar elementos de datos int length; //Longitud actual de la tabla de secuencia }SqList; // Definición de tipo de lista de secuencia (método de asignación estática) ElemType se refiere al tipo de datos definido por usted mismo, como int, double //Tabla de secuencia de inicialización #incluir<stdio.h> #definir tamaño máximo10 estructura typedef { int datos[MaxSize]; longitud interna; }ListaCuad; void ListaInit(SqList &L){ para(int i=0;i<MaxSize;i) L.data[i]=0; //Establece todos los elementos de datos a los valores iniciales predeterminados L.length=0; //Establece la longitud inicial de la tabla de secuencia en 0 } int principal(){ SqList L; //Declarar una lista de secuencia InitList(L): //Lista de secuencia de inicialización ... devolver 0; } // Tabla de secuencia de implementación de asignación dinámica, el tamaño se puede cambiar #incluir<stiod.h> #define InitSize 10 //Longitud máxima predeterminada estructura typedef { int *data; //Puntero que indica una matriz asignada dinámicamente int MaxSize; //Capacidad máxima de la tabla de secuencia int length; //Longitud actual de la tabla de secuencia }SeqList; //Definición de lista de secuencias int principal(){ SeqList L; //Declarar una lista de secuencia ListaInit(L): //Inserta varios elementos aleatoriamente en la tabla de secuencia de la red AumentarTamaño(L,5); devolver 0; } void ListaInit(ListaSeq &L){ //Utiliza la función malloc para solicitar un espacio de almacenamiento continuo L.data(int *)malloc(InitSize*sizeof(int)); L.longitud=0; L.MaxSize=InitSize; } //Aumentar la longitud de la matriz dinámica void AumentarTamaño(SeqList &L,int len){ int *p=L.datos; L.data(int *)malloc((L.MaxSize len)*sizeof(int)): for(int i=0;i<L.length;i ){ L.data[i]=p[i]; //Copiar datos a una nueva área } L.MaxSize=L.MaxSize len; //La longitud máxima de la tabla de secuencia aumenta en len; free(p); //Libera el espacio de memoria original }

L.data=(ElemType *)malloc(tamaño de ElemType *InitSize) La función malloc devuelve un puntero, que debe convertirse en un puntero al tipo de elemento de datos que definió.

ListInsert(&L,I,e), inserta el elemento especificado e en la i-ésima posición

//Inserción secuencial de elementos de tabla #definir tamaño máximo 10 estructura typedef { Datos ElemType[MaxSize]; longitud interna; }ListaCuad; void ListInsert(SqList &L,int I,int e){ for(int j=L.length;j>I;j--){ //Mover el elemento i-ésimo y los elementos subsiguientes hacia atrás L.datos[j]=L.datos[j-1]; } L.data[i-1]=e; //Coloca e en la i-ésima posición L.longitud; //Longitud 1 } int principal(){ ListaSq L; ListaInit(L): //Omitido aquí, puedes insertar una serie de elementos. ListaInsertar(L,3,3); devolver 0; } // Para evitar insertar elementos sin retroalimentación, por ejemplo, si la memoria está llena, se debe modificar la función Insertar para que tenga un valor de retorno. bool ListInsert(SqList &L,int I,int e){ si(i<1 || i>L.longitud 1) falso retorno; si(L.longitud>=MaxSize) falso retorno; para(int j=L.length;j>i;j--) L.datos[j]=L.datos[j-1]; L.datos[i-1]=e; L.longitud; falso retorno; }

ListDelete(SqList &L,int i,int &e), elimina el elemento en la posición i en la tabla L y devuelve el valor del elemento

//Eliminar tabla de secuencia bool ListDelete(SqList &L,int i,int &e){ if(i<1 || i>L.length 1) //Determina si el rango de i es válido falso retorno; e=L.datos[i-1]; para(int j=1;j<L.length;j) L.datos[j-1]=L.datos[j]; L.longitud--; devolver verdadero; } int principal(){ ListaSq L; ListaInit(L); int e=-1; si(ListDelete(L,3,e)) printf("Eliminar el tercer elemento, el valor del elemento eliminado es =%d/n",e); demás pprintf("El orden de bits i es ilegal, la eliminación falló "); devolver 0; }

GetElem(L,i), obtiene el valor del elemento en la i-ésima posición en la tabla L

//Buscar por bit //Asignación estática #definir tamaño máximo estructura typedef { ElemType data[MaxSize]; //Utiliza una "matriz" estática para almacenar elementos de datos int length; //Longitud actual de la tabla de secuencia }SqList; // Definición de tipo de lista de secuencia (método de asignación estática) ElemType GetElem(SqList L,int i){ return L.data[i-1]; //Llama a la función GetElem() para devolver el valor del i-ésimo elemento } //Asignación dinámica #definirtamañoinicial estructura typedef { TipoElem *datos; int Tamaño máximo; longitud interna; }ListaSeq; ElemType GetElem(SeqList L,int i){ devolver L.datos[i-1]; }

LocateElem(L,e), encuentra el elemento con el valor de palabra clave dado en la tabla L

//Buscar por valor #defineInitSize 10 estructura typedef { TipoElem *datos; int Tamaño máximo; longitud interna; }ListaSeq; //Encuentra el elemento cuyo valor del primer elemento es igual a e en la lista de secuencia L y devuelve su orden de bits int LocalizarElem(SeqList L,ElemType e){ para(int i=0;i<L.longitud,i) si(int i=0;o<L.length;i) return i 1; // El valor del elemento marcado i en la matriz es igual a e y su orden de bits se devuelve i 1 return 0; //Salir del ciclo, indicando que la búsqueda falló }

Complejidad del tiempo: mejor O (1), peor O (n), promedio O (n)

Además de almacenar elementos de datos, cada nodo también almacena un puntero al siguiente nodo.

estructura LNodo{ datos ElemType; //Definir el tipo de nodo de lista enlazada única struct LNode *next;//Cada nodo almacena un elemento de datos } struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode)); // Cada vez que se agrega un nuevo nodo, solicita un espacio de nodo en la memoria y usa el puntero p para apuntar a este nodo. También puedes usar typedef struct LNode LNode; en lugar de LNode *p=(LNode *)maloc(sizeof(LNode));

// Libro de texto, define una lista enlazada individualmente typedef struct LNode{} //Definir el tipo de nodo de lista enlazada única datos ElemType; //campo de datos struct LNode *siguiente; //campo de puntero LNode,*LinkList; //Se cambia el nombre de LNode, *LinkList es el puntero a este nodo. Utilice LNode * para enfatizar que se trata de un nodo. Utilice LinkList para enfatizar que se trata de una lista enlazada individualmente

nodo líder

Sin nodo principal

insertar

borrar

búsqueda bit a bit

Buscar por valor

Encuentra la longitud de la mesa.

Paso 1: Inicializar una lista enlazada individualmente Paso 2: Retire un elemento de datos a la vez e insértelo en la cabecera/pie de la mesa.

método de inserción de la cola

Método de inserción de la cabeza

Lista enlazada individualmente: una lista enlazada individualmente no se puede recuperar a la inversa, lo que a veces resulta inconveniente. Lista doblemente enlazada: puede avanzar y retroceder, reducir la densidad de almacenamiento

//Inicialización de lista doblemente enlazada (nodo principal) bool InitDLinkList(DLinklist &L){ L=(DNodo *)malloc(tamañode(DNodo)); si(L==NULL) flash de retorno; L->anterior=NULL; L->siguiente=NULL; devolver verdadero; } anular pruebaDLinkList(){ //Inicializa lista doblemente enlazada DLista de enlaces L; InitDLinkList(L); //...Siguiente código } estructura typedef DNodo{ datos de tipo elemento; estructura DNodo *anterior,*siguiente; }DNodo,*DLista de enlaces; //Determinar si la lista doblemente enlazada está vacía (nodo principal) bool Vacío(DLinklist L){ si(L->siguiente==NULL) devolver verdadero; demás falso retorno; }

//Inserción en lista doblemente enlazada bool InsertNextDNode(DNodo *p,DNodo *s){ s->next=p->next; //Insertar nodo *s después del nodo *p p->siguiente->anterior=s; s->antes=p; p->siguiente=s; }

//Eliminar lista doblemente enlazada bool EliminarSiguienteNodoD(NodoD *p){ if(p==NULL) devuelve flash; DNode *q=p->next; //Encontrar el nodo sucesor q de p if(q==NULL) return false //p no tiene un nodo sucesor p->siguiente=q->siguiente; if(q->next!=NULL) //El nodo q no es el último nodo q->siguiente->anterior=p; free(q); //Liberar espacio de nodo devolver verdadero; } anular DestoryList(DLinklist &L){ // Bucle para liberar cada nodo de datos mientras(L->siguiente!=NULL) EliminarSiguienteDNodo(L); free(L); //Libera el nodo principal L=NULL; //El puntero de la cabeza apunta a NULL }

//recorrido de lista doblemente enlazada while(p!=NULL){ //Recorrido hacia atrás //Hacer el procesamiento correspondiente para el nodo p p=p->siguiente; } while(p!=NULL){ //Recorrido hacia adelante p=p->prioe; } while(p->prioe!=NULL){ //Recorrido hacia adelante, omitir el nodo principal p=p->antes; }

Lista enlazada única: a partir de un nodo, solo se pueden encontrar los nodos posteriores, pero se desconocen los nodos anteriores. Lista circular individualmente enlazada: a partir de un nodo, puede encontrar cualquier otro nodo.

//Definir lista circular enlazada individualmente typedef struct LNode{ //Definir el tipo de nodo de lista enlazada única datos ElemType; //Cada nodo almacena un elemento de datos struct LNode *next; //los datos apuntan al siguiente nodo }LNodo,*ListaEnlaces; //Inicializa una lista circular enlazada individualmente bool ListaInit(ListaEnlaces &L){ L=(LNode *)malloc(sizeof(LNode)); //Asignar un nodo principal if(L==NULL) //Memoria insuficiente, la asignación falló falso retorno; L->next = L; //El nodo principal Next apunta al nodo principal devolver verdadero; } //Determinar si la lista circular individualmente enlazada está vacía bool Vacío(ListaEnlaces L){ si(L->siguiente==L) devolver verdadero; demás flash de retorno; } // Determinar si el nodo p es el nodo final de la lista circular individualmente enlazada bool isTail(ListaEnlaces L,NodoL *p){ si(p->siguiente==L) devolver verdadero; demás falso retorno; }

//Inicializa lista circular doble enlazada vacía bool InitDLinkList(DLinklist &L){ L=(DNode *)malloc(sizeof(DNode)); //Asignar un nodo principal if(L==NULL) //Memoria insuficiente, la asignación falló falso retorno; L->prior=L; // La prioridad del nodo principal apunta al nodo principal L->next=L; // el siguiente del nodo principal apunta al nodo principal devolver verdadero; } anular pruebaDLinkList(){ //Inicializa lista circular doble enlazada DLista de enlaces L; InitDLinkList(L); //...Siguiente código } //Determinar si la lista circular doblemente enlazada está vacía bool Vacío(DLinklist){ si(L->siguiente==L) devolver verdadero; demás falso retorno; } //Determinar si el nodo p es el nodo final de la lista circular doblemente enlazada bool isTail(DLinklist L,DNodo *p){ si(p->siguiente==L) devolver verdadero; demás falso retorno; } estructura typedef DNodo{ datos de tipo elemento; estructura DNodo *anterior,*siguiente; }DNodo,*DLista de enlaces;

Lista enlazada individualmente: cada nodo se asigna aleatoriamente en la memoria. Lista enlazada estática: asigne una parte completa de espacio de memoria continua y cada nodo se coloque en el centro.

//Definir lista enlazada estática #definir tamaño máximo 10 typedef sreuct{} datos de tipo elemento; int siguiente; } anular pruebaSLinkList(){ estructura Nodo a[MaxSize]; //...código posterior } //También puedes crear una lista enlazada estática con el siguiente código #define MaxSize 10 //Longitud máxima de la lista enlazada estática typedef struct{ // Definición del tipo de estructura de lista enlazada estática datos ElemType; //elementos de datos de almacenamiento int next; // subíndice de matriz del siguiente elemento } ListaEnlaceS[TamañoMax]; prueba nulaSLinkLst(){} ListaEnlaceS a; //...Siguiente código }

Todas son tablas lineales y estructuras lineales.

Ventajas de las tablas de secuencia: admiten acceso aleatorio y alta densidad de almacenamiento. Desventajas: es inconveniente asignar grandes áreas de espacio continuo y es inconveniente cambiar la capacidad. Ventajas de las listas vinculadas: los espacios pequeños y discretos son fáciles de asignar y la capacidad es fácil de cambiar. Desventajas: sin acceso aleatorio, baja densidad de almacenamiento.

Creación de tabla de secuencia: Es necesario preasignar un gran espacio contiguo. Si el espacio asignado es demasiado pequeño, será inconveniente ampliar la capacidad más adelante; si el espacio asignado es demasiado grande, se desperdiciarán recursos de memoria. Asignación estática: matriz estática, capacidad inmutable Asignación dinámica: matriz dinámica (malloc, gratuita), la capacidad se puede cambiar, pero requiere mover una gran cantidad de elementos, lo que lleva mucho tiempo. Destrucción: modifique la longitud = 0, el espacio asignado estáticamente se recuperará automáticamente, la aplicación malloc asignada dinámicamente debe liberarse manualmente Insertar/eliminar elementos requiere mover los elementos siguientes hacia adelante o hacia atrás. La complejidad del tiempo es O (n) y la sobrecarga de tiempo proviene principalmente de elementos en movimiento. Si el elemento móvil es grande, el coste del tiempo de movimiento es elevado. Búsqueda: Búsqueda bit a bit: O(1). Buscar por valor: O(n). Si los elementos de la tabla están ordenados, se pueden encontrar en tiempo O(log2n).

Creación de lista enlazada: Solo necesita asignar un nodo principal (también puede omitir el nodo principal y solo declarar un puntero principal), que se puede expandir fácilmente más adelante. Destruir: elimina cada nodo por turno (gratis) Insertar/eliminar elementos solo requiere modificar el puntero. La complejidad del tiempo es O (n), y la sobrecarga de tiempo proviene principalmente de encontrar el elemento objetivo. El coste de tiempo para encontrar elementos es menor. Búsqueda: Búsqueda bit a bit: O(n). Buscar por valor: O(n).

Utilice una lista secuencial o una lista vinculada: la longitud de la lista es difícil de estimar y, a menudo, es necesario agregar, restar o eliminar elementos, así que utilice una lista vinculada. La longitud de la tabla se puede estimar y hay muchas operaciones de consulta (búsqueda), así que utilice una tabla secuencial. Pregunta: Describa la lista de secuencia y la lista vinculada... ¿Cuál es mejor usar la lista de secuencia o la lista vinculada? Las estructuras lógicas de las listas de secuencia y las listas enlazadas son resultados lineales y ambas pertenecen a listas lineales. Sin embargo, las estructuras de almacenamiento de los dos son diferentes. La tabla de secuencia usa almacenamiento secuencial... (características, ventajas y desventajas) la lista vinculada usa almacenamiento en cadena... (ventajas y desventajas). Debido al uso de diferentes métodos de almacenamiento, la eficiencia de implementación de las operaciones básicas también es diferente. Al inicializar... al insertar un elemento de datos... al eliminar un elemento de datos... al buscar un elemento de datos...

Implementado usando "matriz estática"

Una vez determinado el tamaño, no se puede cambiar.

Implementado usando "matriz dinámica"

L.data=(ElemType *)malloc (tamaño de (El;emType)* tamaño)

Cuando la tabla de secuencia está llena, se puede utilizar malloc para expandir dinámicamente el rendimiento máximo de la tabla de secuencia.

Es necesario copiar los elementos de datos a una nueva área de almacenamiento y utilizar la función gratuita para liberar el área original.

Puede encontrar el i-ésimo elemento en tiempo O(1)

Definición (cómo implementarla en código)

Implementación de operaciones básicas.

lista única

lista doblemente enlazada

lista circular enlazada

lista enlazada estática

Inserte el elemento e en la i-ésima posición de L

Mejor O(1), peor O(n), promedio O(n)

Elimina el i-ésimo elemento de L y devuélvelo con e

Mejor O(1), peor O(n), promedio O(n)

Obtenga el valor del elemento en la posición i en la tabla L

Utilice el subíndice de la matriz para obtener el i-ésimo elemento L.data[i-1]

La mejor/peor/complejidad temporal promedio es O(1)

Encuentre el elemento cuyo valor del primer elemento sea igual a e en la lista de secuencia L y devuelva su orden de bits

Buscar comenzando desde el primer elemento y retrocediendo

La mejor complejidad temporal es O(1)

Peor complejidad de tiempo O(n)

Complejidad de tiempo promedio O (n)

Juicio de tabla vacía: L == NULL

Código fácil de escribir

Juicio de tabla vacía: L->next==NULL;

Escribir código es inconveniente

nodo líder

Sin nodo principal