Mostrar Mensajes

Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Información del Perfil

Esta sección te permite ver todos los posts escritos por este usuario. Ten en cuenta que sólo puedes ver los posts escritos en zonas a las que tienes acceso en este momento.

Temas - The Swash

Páginas: [1]

C/C++ / [C] Listas enlazadas.

« en: Sábado 15 de Octubre de 2011, 02:32 »

Información general:
Las listas enlazadas son un recurso dinámico muy potente que nos permite realizar tareas que generalmente podríamos requerir con arrays, pero se impide en objetos estáticos y en dinámicos sería muy complicado.
Una lista enlazada se basa en una estructura, la cual será el esqueleto o prototipo del contenido, y al final requerirá tener un puntero hacia la siguiente estructura del mismo tipo, es decir están enlazadas por su ubicación (dirección de memoria).

Funcionamiento y estructura:
Primero debemos tener la estructura o prototipo en el cual definiremos los datos que emplearemos y como debe ser, un puntero a otra estructura del mismo tipo:

Código: C++

typedef struct _nodo
{
    int valor;
    struct _nodo * pNext;
}_Nodo;

Utilizamos typedef para evitar estar utilizando struct _nodo para todo, así abreviamos y hacemos el código más legible.

Código: C++

typedef _Nodo * _pNodo;

Hay unas bases a tener en cuenta para trabajar con listas enlazadas:

El final de una lista será determinada por un puntero con valor NULL, es decir el último elemento tendrá como siguiente elemento a NULL.
Los elementos se pueden recorrer en un solo sentido (Inicio - Final), debido a que solo tenemos un apuntador al siguiente y no al anterior, las listas que cuentan con esta opción se conocen como doblemente enlazadas. Las trataremos en otro tema.
Es muy importante mantener siempre el valor inicial de la lista, en caso de perderle sería muy difícil de recuperar.
Es muy importante controlar muy bien los punteros hacia los elementos, un simple número distinto y podríamos causar perdida de control sobre el programa.

Recordemos, cada elemento tiene un apuntador al siguiente, por ello se llaman enlazados:

Para trabajar con listas, deberemos implementar una serie de funciones y procedimientos para el manejo de sus elementos entre ellas:

Crear lista nueva.
Insertar elemento (Al inicio, al final y posterior al otro elemento).
Buscar elemento.
Eliminar elementos(El primer elemento, un elemento en base a su dirección).
Imprimir contenido de listas (Este uso ya depende del usuario).

Creación de una lista nueva:
Para crear una nueva lista teniendo en cuenta el prototipo lo que utilizaremos son punteros, por lo cual suele ser más cómodo utilizar un typedef para más comodidad. En cuanto a teoría para crear una nueva lista deberíamos:

Crear una función cuyo tipo de valor de retorno será el mismo del prototipo.
La función creará una estructura dinámica con el tamaño del prototipo (malloc).
Se establecerá un valor inicial para los elementos de la estructura.
El apuntador al siguiente elemento será NULL, esto identificará la lista como vacía.
La función retornará la dirección de la lista creada (valor retornado por malloc).

Código: C++

_pNodo CrearLista(int valor)
{
    _pNodo Lista;
 
    Lista = (_pNodo) malloc (sizeof(_Nodo));
    Lista->valor = valor;
    Lista->pNext = NULL;
 
    return Lista;
}

Inserción de elementos:
Para insertar nuevos elementos deberemos tener una lista previamente creada y contar con su referencia para acceder a ella, además se deberán hacer múltiples comparaciones con fines de prevenir errores, como cuando la lista está vacía, o el lugar donde se va a ingresar el nuevo elemento, etc.

Insertar elemento al final:

La función requerirá el valor del elemento a ingresar y el inicio de la lista.
Crear un nuevo prototipo de estructura, lo llamaremos Nodo.
Comprobar si la lista está vacía, en tal caso simplemente modificar la dirección a la que apunta por el nodo creado (NULL x Dirección nuevo Nodo). En caso de no estar vacía deberemos recorrer todos los elementos hasta reconocer al que apunta al NULL y editar por la dirección del nuevo Nodo.
En caso de recorrer la lista no olvidar utilizar una variable auxiliar para no perder la lista principal.
Al ser un elemento que va al final, estará obligado a tener su campo de siguiente estructura a NULL.
En mi caso bajo utilice la idea de retornar la dirección del nuevo elemento insertado, muchos códigos retornan la misma lista ingresada, cuando en realidad esta no sufre modificaciones y no es útil.

Código: C++

_pNodo InsertarElementoAlFinal(int valor, _pNodo ListaInicial)
{
    _pNodo NuevoNodo;
    _pNodo Auxiliar = ListaInicial;
    NuevoNodo =  malloc(sizeof(_Nodo));
 
    NuevoNodo->valor = valor;
    NuevoNodo->pNext = NULL;
 
    if (ListaInicial->pNext == NULL)
    {
        ListaInicial->pNext = NuevoNodo;
    }
    else
    {
        while(Auxiliar->pNext != NULL)
        {
            Auxiliar =  Auxiliar->pNext;
        }
        Auxiliar->pNext = NuevoNodo;
    }
 
    return NuevoNodo; /* Retornamos dirección del elemento insertado */
}

Inserción de elementos al principio:

La función requerirá el valor del elemento a ingresar y el inicio de la lista.
Crear un nuevo Nodo, asignar el valor correspondiente.
El valor del campo siguiente elemento del Nodo creado deberá ser correspondiente al valor principal de la lista.
Retornamos el nuevo inicio de lista, correspondiente al nuevo Nodo.

Código: C++

_pNodo InsertarElementoAlInicio(int valor, _pNodo ListaInicial)
{
    _pNodo NuevoNodo;
    NuevoNodo = malloc(sizeof(_Nodo));
    NuevoNodo->valor = valor;
    NuevoNodo->pNext = ListaInicial;
 
    return NuevoNodo; /* Retornamos nueva lista inicial */
}

Inserción de un elemento posterior a otro:

La función requerirá el valor del elemento a ingresar y la dirección del elemento anterior a donde ingresaremos el nuevo.
Creamos el nuevo nodo y asignamos los valores correspondientes.
El nuevo Nodo creado ahora apuntará al elemento que apuntaba el Nodo anterior a este.
El Nodo anterior apuntará al nuevo Nodo insertado.
Retornamos la dirección del nuevo Nodo.

Código: C++

_pNodo InsertarElementoPosterior(int valor, _pNodo ElementoAnterior)
{
    _pNodo NuevoNodo;
    NuevoNodo = malloc(sizeof(_Nodo));
 
    NuevoNodo->valor = valor;
    NuevoNodo->pNext = ElementoAnterior->pNext;
 
    ElementoAnterior->pNext = NuevoNodo;
 
    return NuevoNodo; /* Retornamos dirección del elemento insertado */
}

Eliminación de elementos:
La eliminación de elementos también es una función muy importante a la hora de trabajar con listas, sus implementaciones pueden ser muchas debido a la gran cantidad de casos posibles, como eliminar el primer o último elemento, eliminar un elemento según su dirección, posterior a otro, o buscando por valor (Eliminar primero, último o todos). Yo mostraré 2 casos, eliminando el primer elemento y eliminando por dirección del elemento.

Eliminación del primer elemento:

Para esta función únicamente necesitaremos el inicio de lista.
Usaremos una variable auxiliar la cual nos ayudará a almacenar datos temporalmente.
Comprobamos si la lista está vacía, en tal caso dejamos todo igual.
Almacenamos el elemento inicial de lista en la variable auxiliar.
Ahora el inicio de lista apuntará tendrá como valor el elemento al cual apuntaba.
Liberamos el espacio de memoria que contiene la variable auxiliar con free().

Código: C++

_pNodo EliminarPrimerElemento(_pNodo Lista)
{
    _pNodo Auxiliar;
    Auxiliar = Lista;
 
    if (Auxiliar->pNext == NULL)
    {
        return Lista; /* Si no hay más elementos dejamos todo igual */
    }
    Lista = Auxiliar->pNext;
    free(Auxiliar);
 
    return Lista; /* Retornamos la nueva base de la lista */
}

Eliminar elemento por su dirección:

Necesitaremos inicio de lista y dirección del elemento a eliminarla.
Utilizamos una variable auxiliar para buscar el elemento anterior al elemento a eliminar recorriendo toda la lista.
En caso de no encontrar el elemento comparando su dirección retornamos 0 (FALSE)
Comprobamos si el elemento a eliminar es el último, en tal caso el elemento anterior apuntará a NULL, de lo contrario el elemento anterior al que eliminamos apuntará al elemento que apuntaba el elemento que eliminamos.
Liberamos la memoria del elemento a eliminar.
Retornamos 1(TRUE).

Código: C++

int EliminarElemento(_pNodo Elemento, _pNodo Lista)
{
    _pNodo Auxiliar;
    Auxiliar = Lista;
    while (Auxiliar != NULL)
    {
        if (Auxiliar->pNext == Elemento)
        {
            break;
        }
        Auxiliar = Auxiliar->pNext;
    }
    if (Auxiliar == NULL)
    {
        return 0;
    }
    else
    {
        if (Elemento->pNext == NULL)
        {
            Auxiliar->pNext = NULL;
        }
        else
        {
            Auxiliar->pNext = Elemento->pNext;
        }
 
        free(Elemento);
        return 1;
    }
}

Búsqueda de elementos:
La búsqueda de elementos generalmente se realiza para localizar la posición de un objeto comparando su valor, ya que si se tiene su dirección simplemente haciendo referencia podríamos acceder a su contenido.

Búsqueda por valor:

Necesitaremos el valor a buscar y el inicio de lista.
Utilizaremos una variable auxiliar para no perder el inicio de la lista.
Recorremos toda la lista y vamos comparando si cada elemento es igual al buscado.
Una vez localizado simplemente retornamos la dirección del elemento.
Si no se lo encuentra se retornará NULL.

Código: C++

_pNodo BuscarElemento(int valor, _pNodo Lista)
{
    _pNodo Auxiliar;
 
    Auxiliar = Lista;
    while(Auxiliar != NULL)
    {
        if (Auxiliar->valor == valor)
        {
            break;
        }
        Auxiliar = Auxiliar->pNext;
    }
    return Auxiliar; /* Retornamos dirección del elemento encontrado */
}

Bueno, espero hayan comprendido el articulo y prometo trabajar más estructuras de datos.
Hasta la próxima.

Saludos.

C/C++ / [C] sCopy - Ejemplo de manejo de ejecutables

« en: Miércoles 29 de Diciembre de 2010, 23:40 »

Código: C

#include <stdio.h>
#include <stdlib.h>
 
/* @autor The Swash
   @thanks psicosis
*/
int sCopy(char * Source, char * Dest);
 
main(){
       int result;
       result = sCopy("C:\Replace.exe","C:\Raimees.exe");
       printf("%i",result);
       getchar();
       }
 
 
int sCopy(char * Source, char * Dest){
    FILE * FSrc; //Puntero al archivo de origen;
    FILE * Dst;  //Puntero al archivo de destino;
    char * Buffer; //Puntero al Buffer que almacenara la información del archivo origen;
    int Size = 0; //Variable que almacenara el tamaño del archivo;
    int Readed; //Variable que almacenara la cantidad de bytes leidos;
    int Writed; //Variable que almacenara la cantidad de bytes escritos;
 
    FSrc = fopen(Source, "rb"); //Abrimos el archivo de origen en modo lectura;
    Dst = fopen(Dest,"wb"); //Creamos el nuevo archivo;
 
    if ((FSrc == NULL) || (Dst == NULL)) //Condición que verifica si alguno de los 2 archivos no se pudo abrir;
    {
        return -1; //Si no se pudo abrir algo de los 2, retornamos -1 y salimos;
    }
    else //De lo contrario;
    {
        while(fgetc(FSrc) != EOF) //Mientras el caracter obtenido sea distinto al final del archivo;
        {
            Size++; //Aumentamos en 1 la variable Size, la cual como dijimos almacenara el tamaño del archivo;
        }
        rewind(FSrc); //Volvemos a la posición inicial del archivo para leer desde el principio
        Buffer = (char *) malloc(Size * sizeof(char)); //Generamos un espacio en memoria con el tamaño del archivo;
        Readed = fread(Buffer,sizeof(char),Size,FSrc); //Leemos el archivo y el resultado(bytes leidos) se almacenara en Readed;
        if (Readed = Size) //Si la cantidad de bytes leidos es igual al tamaño del archivo;
        {
            Writed = fwrite(Buffer,sizeof(char),Size,Dst); //Escribimos el nuevo archivo y almacenamos la cantidad de bytes escritosen Writed;
            if (Writed == Size) //Si la cantidad de bytes escritos es igual al tamaño del archivo;
            {
                free(Buffer); //Liberamos el espacio de memoria ocupado;
                fclose(FSrc); //Cerramos el archivo de origen;
                fclose(Dst); //Cerramos el archivo de destino;
                return 0; //Retornamos 0 es decir todo se realizó con éxito.
            }
            else //Si la cantidad de bytes escritos es distitan al tamaño del archivo, es posible que algo aya fallado;
            {
                free(Buffer); //Liberamos el espacio de memoria ocupado;
                fclose(FSrc); //Cerramos el archivo de origen;
                fclose(Dst); //Cerramos el archivo de destino;
                return -1; //Retornamos -1 diciendo que algo fallo y no se realizo correctamente;
            }
        }
        else //Si la cantidad de bytes escritos es distitan al tamaño del archivo, es posible que algo aya fallado;
        {
           free(Buffer); //Liberamos el espacio de memoria ocupado;
           fclose(FSrc); //Cerramos el archivo de origen;
           fclose(Dst); //Cerramos el archivo de destino;
           return -1; //Retornamos -1 diciendo que algo fallo y no se realizo correctamente;
        }
    }
}
 

Les dejo esta función explicada, sencillamente copia un archivo binariamente.
Saludos.

Páginas: [1]

SoloCodigo