Experimento informático de estructura de datos (programación) (operaciones básicas de listas enlazadas individualmente)
Estamos aprendiendo estructuras de datos. Escribimos todas las operaciones básicas de tablas lineales hace dos semanas y todas se ejecutan correctamente. Incluyendo InitList, DestoryList, ClearList, ListEmpty, ListLength, GetElem, LocateElem, PriorElem, NextElem, ListInsert, ListDelete, ListTraverse
El entorno que compilé es VC 6.0 y hay tres archivos linklist.h linklist.cpp main .cpp En cuanto a cómo usarlo, no diré mucho sobre lo que debes saber.
========================linklist.h================= ============
#include lt;iostreamgt;
usando el espacio de nombres estándar;
#define TRUE 1
#define FALSO 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
# define OVERFLOW -2
typedef int Status;
typedef int ElemType;
//Estructura de almacenamiento de lista enlazada individualmente de tabla lineal
typedef struct LNode
{
ElemType datos
int len
struct LNode * next; } LNode, *LinkList;
void CreateList_L(LinkList amp; L, int n);
int ListLength(LinkList L
Estado ListInsert(LinkList); amp; L, int i, ElemType amp; e);
Estado ListDelete(LinkList amp; L, int i, ElemType amp; e);
ElemType GetElem(LinkList L, int i) ;
Estado EmptyList_L(LinkList L);
int LocateElem(LinkList L, ElemType e);
Estado PriorElem(LinkList L, ElemType curr_e , ElemType amp; e);
Estado NextElem(LinkList L, ElemType curr_e, ElemType amp; e);
Estado ListTraverse(LinkList L
); Estado ClearList_L( LinkList amp; L);
void DestoryList_L(LinkList amp; L);
=================== === =====linklist.cpp========================
#include "linklist.h"
int LISTLEN = 0;
//Ingrese los valores de n elementos en orden inverso
//Cree una lista lineal enlazada individualmente con el nodo principal
void CreateList_L(LinkList & L, int n)
{
L = (LinkList)malloc(sizeof(LNode));
L-gt;len = 0;
L-gt; siguiente = NULL
for(int i = n; igt; 0; --i)
{LinkList p = (LinkList)malloc(sizeof(LNode));
coutlt;lt; "Ingrese el valor del elemento (preinserción):"; p>
cingt; p-gt; datos;
p-gt; next = L-gt; //Insertar en el encabezado de la tabla gt; siguiente = p;
L-gt;
ESCUCHAR
}
}
//Preguntar longitud de la lista
int ListLength(LinkList L)
{
int len1=0;
LinkList p = L -gt; siguiente ;
while(p)
{
p = p-gt; siguiente;
len1;
}
return len1;
//return L-gt;
}
//En la i-ésima lista enlazada Insertar elemento e
// La posición legal de i es: 1 lt = i lt = ListLength(L) 1
Status ListInsert(LinkList amp; ; L, int i , ElemType e)
{
if(ilt; 1 || igt; ListLength(L) 1)
{
coutlt ;lt;"¡Error de inserción! Acceso fuera de límites..."lt;lt;endl;
return ERROR;
}
else
{
int j;
LinkList p = L
for(j = 0; jlt; i-1; ; j) //for loop Después del final, p apuntará al i-1º elemento, es decir, el elemento e debe insertarse después de p
p = p-gt;
LinkList s = (LinkList)malloc( sizeof(LNode));
s-gt; datos = e
s-gt; ;
p-gt; siguiente = s;
L-gt;
devuelve VERDADERO; >
}
//Elimina el elemento i-ésimo de la lista enlazada y usa e para devolver el valor
//El rango legal de i es: 0lt; ; ListLength(L) 1
Estado ListDelete(LinkList amp; L, int i, ElemType amp; e)
{
if(ilt; 1 | | igt; ListLength(L))
{
coutlt;lt;"Acceso fuera de límites..."lt;lt;endl;
return ERROR;
}
else
{
Lista de enlaces p = L
;int j;
for(j = 0; j lt; i-1; j) // Después del bucle for, el puntero p apuntará al nodo predecesor del elemento que se va a eliminar.
p = p-gt; siguiente;
e = p-gt; siguiente-gt;
p-gt; siguiente = q -gt;
L-gt;
libre
return TRUE ;
}
}
//Obtiene el elemento i-ésimo en la tabla
//El el rango de valores legales de i es: 0 lt; i lt; ListLength(L) 1
ElemType GetElem(LinkList L, int i)
{
if (ilt; 1 || igt ; ListLength(L))
{
coutlt;lt;"¡Valor ilegal! No existe tal elemento de secuencia en la lista enlazada"lt;lt ;endl;
return ERROR;
}
else
{
LinkList p = L; /p>
int j;
for(j = 0;jlt;i;j)
p = p-gt;siguiente;
return p-gt;data;
p>
}
}
//Determinar si la lista vinculada está vacía
Estado ListaVacía_L(ListaEnlaces L)
{
if(L-gt; next == NULL)
devuelve VERDADERO
return ERROR;
}
//Encuentre el orden de bits del elemento ubicado e en la lista vinculada y devuélvalo a través de la función
int LocateElem(LinkList L , ElemType e)
{
int i = 0
LinkList p = L
while(p-gt; siguiente; amplificador; p-gt; siguiente-gt; datos != e)
{
p = p-gt; /p>
}
if(p-gt ; next == NULL)
{
coutlt;lt;"Elemento no encontrado en el enlace lista"lt;lt;elt;lt;endl;
devolver ERROR;
}
devolver (i 1);
}
//Encuentra el elemento predecesor directo del elemento actual curr_e y devuelve su valor con e
Status PriorElem(LinkList L, ElemType curr_e, ElemType amp; e)
{
Lista de enlaces p = L;
while(p-gt; next amp; amp; curr_e != p-gt; next-gt; data) > p = p-gt; next; if(p-gt; next == NULL) { coutlt;lt;" en el enlace list ¡El elemento "lt;lt;curr_elt;lt;" no se puede encontrar y su elemento predecesor no se puede encontrar!"lt;lt;endl; return ERROR; } if(p == L) { coutlt;lt; "Element"lt;lt;curr_elt;lt;" es el primer elemento en la lista enlazada, Ninguno Precursor..."lt;lt;endl; return ERROR; } e = p-gt;data; return OK; } /* //Busque el elemento sucesor directo del elemento actual curr_e y use e para devuelve su valor Estado NextElem(LinkList L, ElemType curr_e, ElemType amp; e) { LinkList p = L-gt ; p> //coutlt; p-gt; lt; //coutlt; > if (p == NULL) { coutlt;lt;"¡La lista enlazada es una lista vacía!"lt;lt;endl; return ERROR; } if(p-gt; next == NULL) { coutlt;lt;"Hay es sólo un elemento en la lista enlazada, no hay sucesor..."lt ;lt;endl; return ERROR; } while(p- gt;siguiente amp;amp; curr_e != p-gt;data) { //coutlt;lt;"mientras"lt;lt;endl; p = p-gt;siguiente; } coutlt;lt;"p-gt;data = "lt;lt;p-gt;datalt;lt; endl; if(p-gt;data != curr_e) { coutlt;lt;"111"lt;lt;endl; coutlt;lt;"No se encuentra en la lista vinculada. El elemento "lt;lt;curr_elt;lt;" no puede encontrar su elemento sucesor!"lt;lt;endl; return ERROR ; } if(p-gt; next == NULL amp; curr_e == p-gt; data) { coutlt;lt;"222"lt;lt;endl ; coutlt;lt;"Element"lt;lt;curr_elt;lt;" es el último elemento de la lista enlazada, sin sucesor ..."lt;lt;endl; return ERROR; } coutlt;lt;"333"lt;lt;endl; > e = p-gt; data; return OK; } */ //Encuentra el current El elemento sucesor directo del elemento curr_e, devuelve su valor con e Status NextElem(LinkList L, ElemType curr_e, ElemType amp; e) { Lista de enlaces p = L-gt; siguiente; while(p amp; amp; p-gt; datos != curr_e) p = p-gt; > if(p == L-gt; siguiente) { if(p == NULL) { coutlt;lt;"\nLa lista enlazada es una lista vacía y no se pueden realizar operaciones posteriores!"lt;lt;endl; return ERROR; } else { coutlt;lt;"\nSolo hay un elemento en la lista enlazada y no se puede encontrar su sucesor..."lt;lt; endl; return ERROR; } } if(p == NULL) { coutlt ;lt;"\nEl elemento no se pudo encontrar en la lista enlazada: "lt;lt;curr_elt;lt;endl; return ERROR; } if(p-gt; next == NULL) { coutlt;lt;"\nElemento "lt;lt;curr_elt; lt;" es el último elemento de la lista enlazada, no se puede encontrar su sucesor..."lt;lt;endl; return ERROR; } e = p-gt; next-gt; data; return OK; } //Recorre la lista enlazada Estado ListTraverse(LinkList L) { LinkList p = L-gt if(LISTLEN == 0)
coutlt;lt;"\n¡Todos los contenidos de la lista vinculada, excepto el nodo principal, han sido liberados y es una lista vacía!"lt;lt;endl;
coutlt;lt;"\nFalló el recorrido..."lt;lt;endl;
return ERROR;
}
if(LISTLEN == - 1)
{
coutlt;lt;"\n¡Todos los contenidos han sido publicados y la lista enlazada ha sido destruida!"lt;lt;endl;
coutlt;lt;"\nFalló el recorrido.. ."lt;lt;endl;
return ERROR;
}
while(p != NULL)
{
p>
coutlt;lt;p-gt;datalt;lt;" ";
p = p-gt;next;
}
coutlt;lt;"\n¡Recorrido exitoso!
"lt;lt;endl;
return OK;
}
//Borrar el contenido de la lista enlazada
// El borrado de lista enlazada individualmente se refiere a liberar el espacio de memoria excepto el nodo principal
Estado ClearList_L(LinkList amp; L)
{
LinkList p = L;
while(p-gt; siguiente)
{
Lista de enlaces m = p-gt; siguiente
gratis(p);
p>p = m;
}
L-gt; siguiente = NULL
LISTLEN = 0; >
return OK;
}
//Destruir la lista enlazada
//La liberación de una lista enlazada individualmente significa liberar el espacio de memoria de todos los nodos en la lista enlazada
void DestoryList_L(LinkList amp; L)
{
LinkList p = L
while( p-gt; siguiente)
{
Lista de enlaces m = p-gt; siguiente
gratis
p; = m;
}
//gratis (p);
//gratis (L);
}
==========================main.cpp===== ============= ======
#include "linklist.h"
int main()
{
Lista de enlaces L;
ElemType e;
ElemType curr_e
int
int; status; //Devuelve el estado de ejecución de la función
coutlt;lt;"Ingrese el número de elementos que se crearán:";
cingt;gt;n;
coutlt;lt;endl;
//Crear una lista enlazada individualmente
CreateList_L(L, n);
coutlt;lt;endl;
//Traverse
status = ListTraverse(L);
//Devuelve la longitud de la lista enlazada
coutlt;lt; "\nLa longitud de la lista enlazada individualmente es: "lt;lt;ListLength(L) lt;lt;endl;
//Operación de inserción de la lista enlazada
coutlt;lt ;"\nIngrese la posición donde se debe insertar el elemento: ";
cingt;gt;n;
coutlt;lt;"\nIngrese el valor del elemento insertado: ";
cingt;gt;e;
estado = ListInsert(L, n, e);
if(estado)
coutlt;lt;"\n¡El elemento de la lista enlazada se insertó correctamente!"lt;lt;endl;
else
coutlt;lt;"\n¡La inserción del elemento de la lista enlazada falló! "lt;lt;endl;
>
status = ListTraverse(L);
coutlt;lt;endl;
//Operación de eliminación de lista enlazada individualmente
coutlt;lt;" Introduzca la posición del elemento que desea eliminar: ";
cingt;gt;n;
status = ListDelete(L, n, e);
if (estado)
{
coutlt;lt;"\n¡Eliminación exitosa!";
coutlt;lt;" El elemento eliminado es: "lt ; lt;elt;lt;endl;
}
else
coutlt;lt;"\nError al eliminar..."lt;lt;endl;
status = ListTraverse(L);
coutlt;lt;endl;
//Obtener elementos de una lista enlazada individualmente
coutlt; lt; "Ingrese la posición del elemento que desea obtener en la lista vinculada: ";
cingt;
e = GetElem(L, n; );
if(n gt; 0 amp; n lt; = L-gt; len)
coutlt;lt;"\nNúmero de lista enlazada individualmente "lt;lt; lt;lt ;" el valor del elemento es: "lt;lt;elt;lt;endl;
//Operación vacía de lista enlazada individualmente
status = EmptyList_L(L);
if(status)
coutlt;lt;"\n¡La lista enlazada individualmente es una lista vacía!"lt;lt;endl;
else
coutlt ;lt;"\nLa lista enlazada individualmente no está vacía y contiene elementos."lt;lt;endl;
//Encuentra el elemento posicionado
coutlt;lt; "\nPor favor, introduzca los elementos que se encontrarán: ";
cingt;gt;e;
n = LocateElem(L, e);
if(n )
p>coutlt;lt;"\nLa posición del elemento "lt;lt;elt;lt;" en la lista enlazada es: "lt;lt;nlt;lt;endl;
// Operación precursora
coutlt;lt;"\nNecesita encontrar el valor del elemento de su predecesor: ";
cingt;gt;curr_e;
status = PriorElem( L, curr_e, e);
if(status)
coutlt;lt;"\nEl precursor del elemento "lt;lt;curr_elt;lt ;" es: "lt; lt; lt; endl;
//Operación posterior
coutlt; /p>
cingt; gt; curr_e;
estado = NextElem(L, curr_e, e);
if (estado)
coutlt; lt; "\nElemento El sucesor de "lt;lt;curr_elt;lt;" es: "lt;lt;elt;lt;endl;
//Borrar operación de lista enlazada individualmente
coutlt;lt; "\nLlamar a la función borrar lista enlazada";
status = ClearList_L(L);
coutlt;lt;endl;
status = ListTraverse(L);
//Operación de destrucción de lista enlazada individualmente
p>
coutlt;lt;"\nLlamar a la función de destrucción de lista enlazada";
DestoryList_L(L);
coutlt;lt;endl;
estado = ListTraverse(L);
coutlt;lt;endl;
devuelve 0;
}