Codigo Fuente de Lista Simple Con Cabecera

Tipo Lista Con Cabecera
/***********************************************************/
/* Ejemplo de programa para manejar una: */
/* LISTA SIMPLEMENTE ENLAZADA CON CABECERA, */
/* como Estructura de Datos Dinámica (con punteros). */
/* Incluye: Primitivas de la lista y programa de prueba. */
/* Todo en el mismo fichero. */
/***************************************/
#include
#include
#include

/*Declaración del tipo base de la lista*/
struct element {
long num;
};
/* Tipos de la lista: */
/* Tipo de cada celda de la lista */
struct celda{
struct element elem;
struct celda *sig;
};
/* Tipo lista: Puntero a celda */
typedef struct celda *lista;

/***************************************/
/* Inicializa una lista simplemente enlazada y CON cabecera. */
/* Devuelve -1 en caso de ERROR. */
int Inicializar_lista(lista *list){
if (((*list)=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
(*list)->sig=NULL;
return 0;
}
/***************************************/
/*Devuelve TRUE si la lista está vacía.*/
int Lista_vacia(lista list){
if (list->sig) return 0;
return 1;
}
/***************************************/
/* Inserta el elemento e en la posición pos de la lista ant. */
/* Si pos<=1 inserta en la primera posición. */
/* Si pos>longitud_lista, inserta en la última posición. */
/* Devuelve -1 si no hay memoria suficiente para la inserción. */
int Insertar_pos (lista ant, struct element e, long pos){
lista p, L=ant->sig;
long i=1;
if ((p=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
p->elem=e;
while (L && i
ant=L;
L=L->sig;
i++;
}
ant->sig=p; /* Insertar elemento apuntado por p, entre anterior y L */
p->sig=L;
return 0;
}
/***************************************/
/* Inserta el elemento e en la lista ant ordenadamente por */
/* el campo elem.num */
/* Devuelve -1 si no hay memoria suficiente para la inserción. */
int Insertar_orden (lista ant, struct element e){
lista p, L=ant->sig;
unsigned i=1;
if ((p=(struct celda *) malloc(sizeof(struct celda))) == NULL)
return -1;
p->elem=e;
while (L && e.num>L->elem.num){ /* Hallar posición en la que insertar */
ant=L;
L=L->sig;
i++;
}
ant->sig=p; /* Insertar elemento apuntado por p, entre anterior y L */
p->sig=L;
return 0;
}
/***************************************/
/* Borra el elemento en la posición pos de la lista ant. */
/* Si la pos=1 borra el primer elemento. */
/* Devuelve -1 si no existe la posición: */
/* pila vacía, pos<1>long */
int Borrar_elemento(lista ant, long pos){
lista aux, L=ant->sig;
long i=1;
if (Lista_vacia(ant) || pos<1)
return -1; /* Posición NO válida */
while (L && i
ant=L;
L=L->sig;
i++;
}
if (L){
/* Borrar elemento apuntado por L, teniendo un puntero al anterior */
ant->sig=L->sig;
free(L);
return 0;
}
return -1; /* La lista tiene menos de pos elementos */
}
/***************************************/
/* Devuelve la longitud de la lista list (núm. de elementos). */
long Long_lista(lista list){
long i=0;
list=list->sig;
while (list) {
list=list->sig;
i++;
}
return i;
}
/***************************************/
/* Vacía la lista totalmente, dejándola inicializada. */
/* Tras esta operación NO es necesario inicializarla. */
void Vaciar_lista(lista list){
while (Borrar_elemento (list,1) != -1);
}
/***************************************/
/* Destruye la lista totalmente, liberando toda la memoria. */
/* Tras esto ES necesario Inicializar la lista para reusarla. */
void Destruir_lista(lista *list){
Vaciar_lista(*list);
free(*list); /* Liberar la cabecera */
*list=NULL;
}
/***************************************/
/* Devuelve en e, el elemento que está en la posición pos */
/* de la lista list. */
/* Si no existe esa posición, devuelve -1. En otro caso 0. */
int Leer_element (lista list, long pos, struct element *e){
long i=1;
if (Lista_vacia(list) || pos<1)
return -1;
list=list->sig; /* Nos saltamos la cabecera */
while (list && i
list=list->sig;
i++;
}
if (list){
*e=list->elem;
return 0;
}
return -1;
}
/*************************************/
/* Devuelve la posición de la primera ocurrencia del elemento */
/* e en la lista list, a partir de la posición pos (inclusive).*/
/* Esta ocurrencia será considerada por el campo elem.num */
/* Devuelve 0 si no ha sido encontrada. */
/* Con esta función, cambiando pos, podremos encontrar TODAS */
/* las ocurrencias de un elemento en la lista. */
long Posic_lista(lista list, struct element e, long pos){
long i=1;
list=list->sig; /* Saltar cabecera */
while (list && i
list=list->sig;
i++;
}
if (!list) return 0; /* No existe posición pos, luego... */
while (list && e.num!=list->elem.num) { /* Intentar encontrar el
elemento */
list=list->sig;
i++;
}
if (!list) return 0; /* No encontrado */
return i; /* Encontrado en la posición i */
}
/***************************************/
/* Actualiza la posición pos de la lista list con el elemento e*/
/* Devuelve -1 si no existe esa posición. */
int Actualiza_lista(lista list, struct element e, long pos){
long i=1;
if (Lista_vacia(list) || pos<1)>
list=list->sig; /* Saltar cabecera */
while (list && i
list=list->sig;
i++;
}
if (!list) return -1; /* Posición no existe */
list->elem=e; /* Actualización */
return 0;
}
/* FIN de las PRIMITIVAS de la LISTA SIMPLEMENTE ENLAZADA CON CABECERA */
/***************************************/
/* Imprime un elemento e por la Salida estándar. */
void Imprimir_elemento (struct element e){
printf("%li",e.num);
}
/***************************************/
/* Muestra todos los elementos de la lista list por su orden. */
void mostrar_lista(lista list){
struct element e;
unsigned i=1,tama=Long_lista(list);
while (i<=tama) {
printf("\nElemento %u: ",i);
Leer_element(list,i++,&e);
Imprimir_elemento(e);
}
}
/***************************************/
/* Muestra un menu de opciones. */
void menu(void){
puts("\n\t\t***** MENU *****\n");
puts("\tS. Destruir lista y SALIR.");
puts("\t1. Inicializar lista.");
puts("\t2. Insertar por orden.");
puts("\t3. Insertar por posición.");
puts("\t4. Mostrar lista.");
puts("\t5. Borrar elemento.");
puts("\t6. Longitud lista");
puts("\t7. Ver si está vacía.");
puts("\t8. Ver elemento n-ésimo.");
puts("\t9. Posición de un elemento a partir de una dada.");
puts("\t0. Modificar un elemento en una posición.");
printf("\n\tOpcion: ");
}
/***************************************/
void main(){
lista list;
struct element e;
char opcion='x';
long pos;
Inicializar_lista(&list);

while (opcion!='S' && opcion!='s'){
menu();
opcion=getche();
switch (opcion) {
case 's':
case 'S':Destruir_lista(&list);
break;
case '1':Vaciar_lista(list);
break;
case '2':printf("\nDame número: ");
scanf("%li",&(e.num));
if (Insertar_orden(list,e))
puts("\n\aERROR: No existe memoria suficiente.");
break;
case '3':printf("\nDame número: ");
scanf("%li",&(e.num));
printf("\nDame la posición: ");
scanf("%li",&pos);
if (Insertar_pos(list,e,pos))
puts("\n\aERROR: No existe memoria suficiente.");
break;
case '4':printf("\n----------------");
mostrar_lista(list);
puts("\n----------------");
getch();
break;
case '5':printf("\nDame posición a borrar: ");
scanf("%li",&pos);
if (Borrar_elemento(list,pos))
puts("\n\aERROR: No existe esa posición.");
break;
case '6':printf("\n- Longitud: %u.",Long_lista(list));
break;
case '7':if (Lista_vacia(list))
puts("\n- Lista VACIA.");
else puts("\n- Lista NO VACIA.");
break;
case '8':printf("\nDame posición a leer: ");
scanf("%li",&pos);
if (Leer_element(list,pos,&e))
puts("\n\aERROR: No existe esa posición.");
else
printf("\n- Elemento %li: %li.\n",pos,e.num);
break;

case '9':printf("\nDame número para buscar su posición: ");
scanf("%li",&(e.num));
printf("\nDame la posición a partir de la que buscar: ");
scanf("%li",&pos);
if (!(pos=Posic_lista(list,e,pos)))
puts(
"\n\aERROR: No existe ese elemento a partir de esa posición.");
else
printf(
"\n-La primera posición encontrada de ese elemento es: %i",
pos);
break;
case '0':printf("\nDame número para actualizar: ");
scanf("%li",&(e.num));
printf("\nDame la posición a modificar: ");
scanf("%li",&pos);
if (Actualiza_lista(list,e,pos))
puts("\n\aERROR: No existe esa posición. No se ha
modificado.");
break;
}
}
puts("\n\t***** FIN *****");
}

Estructuras de Datos Dinámicas

Son aquellas cuyo tamaño (longitud, número de elementos...) varía en tiempo de ejecución. Las más famosas son: Listas simplemente enlazadas (con y sin cabecera), Listas doblemente enlazadas (con y sin cabecera), Pilas, Colas, Árboles y Grafos.

Las Listas
Las listas son estructuras de datos que son dinámicas, esto significa que adquieren espacio y liberan espacio a medida que se necesita. sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseabamos cambiar su contenido.

Las listas son estructuras de datos que son dinámicas, esto significa que adquieren espacio y liberan espacio a medida que se necesita. sin embargo, hay una advertencia. Como regla general siempre hay que tener cuidado al manejar direcciones de espacios de memoria, porque es posible que accedamos a una localidad de memoria de la cual no deseabamos cambiar su contenido.

Una lista es un conjunto de nodos que están relacionados. Cada nodo consta de dos partes:
- una donde se almacena la información,
- otra donde se guarda una referencia al siguiente nodo.

La creación de los nodos es dinámica, es decir, se crean nodos (por tanto se reserva memoria para ellos) según se van necesitando. Estos nodos finalmente estarán relacionados por un puntero que los enlaza. Ventaja: como creamos los nodos según los necesitamos, no necesitamos saber a priori la cantidad de datos que se van a manejar.

Sintaxis de un nodo:
Un nodo es una estructura donde se almacena la información y que además tiene una referencia al siguiente nodo:
struct nodo
{
struct nombre_estructura información;
struct nodo *siguiente;
}

Si cada nodo tiene sólo una referencia al nodo siguiente, se dice que la lista está enlazada de forma simple. Si cada nodo tiene dos referencias, una al nodo siguiente y otra al nodo anterior, se dice que la lista está doblemente enlazada.

/*Lista simple*/
está formado por nodos como el siguiente:
struct nodo_articulo
{
art info_articulo;
struct nodo_articulo *sig;
}

/*Lista doble*/
está formado por nodos como el siguiente:
struct nodo_articulo
{
art info_articulo;
struct nodo_articulo *sig;
struct nodo_articulo *ant;
}

Lista Simple


Lista doblemente enlazada


Además si el puntero del último elemento de la lista apunta al principio de la lista, se dice que la lista es circular. Cuando esto no ocurre, el puntero del último elemento de la lista debe tener el valor NULL. Este valor concreto representa que el puntero no está apuntando a ninguna dirección válida.

Lista Circular



Ejemplo: Supongamos que tenemos una aplicación para un registro de estudiantes. En este caso el ejemplo de nodo corresponde al estudiante que va a contener como subcampos la cédula, el nombre, el apellido, la edad y el. indice académico.

Definimos la estructura estudiante:
struct estudiante
{
long cedula;
char *nombre;
char *apellido;
int edad;
float ia;
}

/*Definición de nodo en una lista simple*/
struct nodo_estudiante
{
struct estudiante info;
struct nodo_estudiante *sig;
}

/*Definición de nodo en una lista doblemente enlazada*/
struct nodo_estudiante
{
struct estudiante info;
struct nodo_estudiante *sig;
struct nodo_estudiante *ant;
}

Es importante tener siempre un puntero que referencie el principio de la lista, ya que si se pierde esa referencia se pierde el contenido de toda la lista.

Ejemplo para probar

#include
#include
void main() {
int a, *b;
b = (int *) malloc(sizeof(int)); /* Reserva Mm para UN entero */
if (b == NULL)
printf("No hay memoria suficiente.");
else {
a=5;
*b=6;
printf("Dirección de a: %p. Valor de a: %d\n",&a, a);
printf("Dirección b: %p. valor al que apunta: %d\n",b, *b);
free(b); /* Importante: Liberar la memoria */
}
}

Recursividad

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función.
Se puede decir que la recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:
Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (menores que N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base ( o lo que llamo criterio de parada), se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.
La recursividad es un concepto importante en informática. Muchos algoritmos se pueden describir mejor en términos de recursividad.
Supongamos que P es un procedimiento que contiene una sentencia de Llamada a si mismo o una sentencia de Llamada a un segundo procedimiento que puede eventualmente llamar de vuelta al procedimiento original P. Entonces P se dice que es un procedimiento recursivo. Como el programa no ha de continuar ejecutandose indefinidamente, un procedimiento recursivo ha de tener las dos siguientes propiedades:

1. Debe existir un cierto criterio, llamado criterio base, por el que el procedimiento no se llama así mismo.
2. Cada vez que el procedimiento se llame a si mismo(directa o indirectamente), debe estar mas cerca del criterio base.
   

Un procedimiento recursivo con estas dos propiedades se dice que esta bien definido.

Análogamente, una función se dice que esta definida recursivamente si la definición de la función se refiere a si misma. De nuevo, para que la definición no sea circular, debe tener las dos siguientes propiedades:

1. Debe haber ciertos argumentos, llamados valores base, para los que la función no se refiera a si misma.
2. Cada vez que la función se refiera a si misma, el argumento de la función debe acercarse más al valor base.

Una función recursiva con estas dos propiedades se dice también que esta bien definida.

Tipos.

Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente.
Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.

Características.

Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y una condición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación. Algo muy importante a tener en cuenta cuando se use la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.

Ventajas e inconvenientes

La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta.

El inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.

Ejemplos

function factorial(n : integer): longint;
begin
if n=0 then factorial := 1 (** Criterio base o condici¢n de parada **)
else factorial := n*factorial(n-1); (** simplificaci¢n del problema **)
end;

/*Máximo comun divisor */

function MCD(m,n : integer): integer;
begin
if (m mod n)=0 then MCD := n (* Criterio base o condici¢n de parada **)
else MCD := MCD(n, m mod n); (** simplificaci¢n del problema **)
end;

Ejercicios de recuperación

Para aquellos estudiantes que vienen con baja nota y desean recuperar, les propongo desarrollar uno y sólo uno de los dos ejercicios propuestos en la entrada anterior, especificamente el número 13 y el número 16, ustedes deciden cual hacer.

La entrega es estrictamente individual.
Debe ser entregado impreso o a mano y documentado.
Debe ser entregado para el dia 30/11/2009.

Ejercicios sobre cadenas (string) turbo pascal

Saludos acá les dejo varios ejercicios tipo examen para que los desarrollen, practiquen y tomen fortalezas, adelante muchachos les invito a que los hagan todos y cada uno de ellos

1. Desarrolle una función que devuelva una cadena con un caracter repetido n veces.
2. Implemente una función que elimine los caracteres en blanco a la izquierda de una cadena y retorne esta sin los espacios en blanco a la izquierda.
3. Realice una función que elimine los caracteres en blanco a la derecha de una cadena y retorne ésta sin los blancos a la derecha.
4. Escriba una función que determine si una cadena esta vacia o no.
5. Desarrolle una función que elimine los espacios en blanco a ambos extremos de la cadena.
6. Implemente una función que devuelva una cadena invertida.
7. Un palíndromo es una palabra que se lee igual hacia adelante que hacia atras. Desarrolle una función que determine si una palabra es palíndrome o no.
8. Un número capicúo se refiere a cualquier número que se lee igual de izquierda a derecha y de derecha a izquierda. Escriba una función que determine si un número es capicúo o no.
9. Escriba una función que determine la cantidad de minusculas en una cadena.
10. Escriba una función que determine la cantidad de mayusculas en una cadena.
11. Desarrolle una función que calcule la cantidad de veces que se repite un caracter dado en una cadena.
12. Escriba una función que remplace un caracter por otro en una cadena.
13. desarrolle una función que lea caracter a caracter, mostrandolo por pantalla, mediante el teclado y que valide que el caracter pertenezca a un conjunto valido de caracteres devolviendo la cadena resultante.
14. Realice una función que compare dos cadenas y que devuelva 0 si cad1 es mayor que cad2, 1 si cad1 es igaul a cad2, y 2 si cad1 es mayor que cad2.
15. Desarrolle una función que devuelva una cadena en minusculas.
16. Elabore el conjunto de funciones necesarias para convertir de una base númerica a otra base. Es decir, decimal a binario, decimal a octal, decimal a hexadecimal, octal a binario, octal a hexadecimal, octal a decimal, hexadecimal a binario, hexadecimal a octal, hexadecimal a decimal, binario a decimal, binario a octal y binario a hexadecimal.
    

Si los desarrollan les aseguro que saldran bien..., les sugiero hacer el algoritmo primero y luego la implemtación

STRING (Cadena de caracteres)

El tipo de datos STRING guarda información de texto. Una variable STRING puede tener de 1 a 255 caracteres de longitud, aunque ocupa un byte más que su longitud definida.

Por ejemplo, si se declara una variable STRING de 10 caracteres de longitud (cad:string[10];) la variable ocupa 11 bytes de memoria. Esto se debe a que el primer byte (byte de longitud) de cada variable STRING guarda la longitud de la cadena que en ese momento está contenida en la variable.

Si una variable STRING de 10 caracteres contiene la palabra "hola" el primer byte de memoria tendra el valor binario 4, indicando que la variable contiene cuatro caracteres. En ese caso, los últimos seis caracters de la variable son ignorados por los procedimientos de manipulación de cadenas de turbo pascal.

0 1 2 3 4 5 6 7 8 9 10
4 h o l a } # - X ¬ %

(00000100)Observe que el primer byte (el byte 0) no es el caracter "4", sino el número 4 en binario y que los últimos seis bytes contienen datos aleatorios.

Veamos algunos ejemplos visto en clases con manipulación de cadenas:

(* Funcion que devuelve la posición de un caracter en la cadena especificada *)
function poscar(cadena : string; cual : char) : byte;
var
pos, (* para devolver la posición de la cadena *)
i : byte; (* para recorrer cada caracter de la cadena *)
encontrado : boolean; (* para determinar si encontro el caracter buscado *)
begin
pos := 0;
encontrado := false;
i := 1;
(* ord(cadena[0]) devuelve la longitud de la cadena *)
while (not encontrado) and (i<ord(cadena[0])) do
begin
if (cadena[i]<>cual)
then begin
pos := i;
encontrado := true;
end
else i := i + 1;
end;
poscar := pos; (* retorna el valor de la funcion *)
end;

(* Funcion que cuenta cuantas veces se repite un caracter en una cadena*)
function contarcar(cadena : string; cual : char) : byte;
var
contador, (* para contar el caracter *)
i : byte; (* para recorrer cada caracter de la cadena *)
begin
contador := 0;
(* ord(cadena[0]) devuelve la longitud de la cadena *)
for i := 1 to ord(cadena[0]) do
begin
if (cadena[i]=cual)
then contador := contador + 1
else (* nada que hacer*);
end;
contarcar := contador; (* retorna el valor de la funcion *)
end;

Función Length

Para conocer la longitud de una cadena utilizamos la función Length, la longitud es la cantidad de caracteres que contiene la cadena en un momento determinado.

Su sintaxis es: Length (cadena);

La función regresa un valor entero.


Función Concat

La función concat produce los mismos resultados que la concatenación, es posible incluir cualquier número de cadenas que se necesiten concatenar.

La suma de las cadenas no deberá sobrepasar la longitud que la variable, a la cual se asignará dicha suma, puede manejar. Ejemplo:

Cadena := Concat (Cad1, cad2, cad3);


Función Pos

La función Pos nos sirve para localizar una determinada cadena dentro de otra, en otras palabras para verificar si una cadena es subcadena de otra segunda.

Los parámetros que requiere son: la cadena que se buscará y la cadena donde se buscará la primera:

Pos (Cadena1, Cadena2);

Ejemplo:
Cadena := 'Domingo Lunes Martes Miercoles Jueves Viernes Sabado';
WriteLn(Cadena);
WriteLn(Pos('Lunes', Cadena)); {Muestra 9}
WriteLn(Pos('Jueves', Cadena)); {Muestra 32}
WriteLn(Pos('Ayer', Cadena)); {Muestra 0}

Función Copy

La función copy regresa una subcadena de una variable o constante dada como parámetro. Su sintaxis es:

Copy (Cadena, Inicio, Cantidad);

Donde Cadena es la fuente de la subcadena, Inicio es la posición desde la cual se obtendrá la subcadena y Cantidad es el número de caracteres que se extraerán.

Los valores de Inicio y Cantidad deben ser de tipo entero.

Ejemplo:
Cadena := "Nuevos horizontes";
WriteLn (Copy(Cadena, 8, 10)); {Visualiza: horizontes}

Fución Insert

El procedimiento Insert sirve para insertar una cadena dentro de otra en alguna posición determinada. Sintaxis:

Insert (Cadena1, Cadena2, Posición)

Donde Cadena1 es la que se insertará, Cadena2 es donde se insertará y Posición es el lugar donde se insertará. El parámetro Posición debe ser de tipo entero.

Procedimiento Delete

Este procedimiento elimina un determinado número de caracteres de una cadena. Su sintaxis es:

Delete (Cadena, Inicio, Número)

Cadena es la variable en la cual se eliminarán los caracteres, Inicio es la posición del primer caracter a eliminar y Número es la cantidad de caracteres que se borrarán.

Fución UpCase

La función UpCase regresa la letra mayuscula correspondiente al caracter dado como parámetro. Es muy común trabajando con cadenas que se quiera convertir una que contiene un número a su valor numérico, para poder utilizarlo en operaciones matemáticas, así como convertir un número a su equivalente en una cadena.

Procedimiento Str

El procedimiento Str obtiene una cadena a partir de un valor numérico. Su sintaxis es:

Str(Valor, Cadena)

Donde valor es el número a convertir y Cadena es la variable donde se almacenará la cadena ya convertida.

Procedimiento Val

Este procedimiento convierte una cadena en un valor de tipo numérico, el problema con esta función es que si la cadena no esta formada exclusivamente de números siguiendo las reglas para el tipo de datos que se vallan a obtener se generará un error. Sintaxis:

Val (Cad, Num, Código)

Cadena contiene la cadena que será procesada, Num es la variable de tipo numérico donde se guardará el valor de la cadena y Código es una variable de tipo entero (Integer) que contendrá el valor de 0 si no hubo errores y un valor diferente en caso de que no se haya podido convertir la cadena, el valor de Código representa la posición de la cadena donde ocurrio el error.