| Ver tema anterior :: Ver siguiente tema | | Autor | Mensaje |
|---|
juanel
Registrado: 24 Ene 2005
Mensajes: 236
|  Publicado: 25/04/2005 8:08 am | | | Título: Listas vinculadas |
| hola, me estoy internadno en el tema de las listas vinculadas.
Alguien me podria decir que tipo de programa puedo hacer utilizando estas mismas, para practicar.
SAludos  |
| | Volver arriba | |  | juanel
Registrado: 24 Ene 2005
Mensajes: 236
| | Publicado: 26/04/2005 10:03 am | | | Título: |
| tmb les pregunto: ¿que es una pila?
Saludos |
| | Volver arriba | | | jorgext
Registrado: 11 Oct 2004
Mensajes: 6
| | Publicado: 26/04/2005 10:10 am | | | Título: |
| | juanel escribió: | tmb les pregunto: ¿que es una pila?
Saludos |
Si es la pila qe pienso, te puedes referir al stack, que el la parte de la memoria donde se almacenan las variables temporales (que existen sólo mientras se ejecuta la función en que existen)
más información aquí:
o también te puedes referir a trabajo con colas:
|
| | Volver arriba | | | | grandzam
Registrado: 10 Feb 2005
Mensajes: 132
| | Publicado: 26/04/2005 9:08 pm | | | Título: |
| Las slistas enlazadas o vinculadas, se utilizan mucho, para manejar de mejor manera el stack que es un segmento de la memoria... llamada pila...
bueno... por ejemplo podría utilizarce para resolución de polinomios, para ordenar datos, utilizando el método hash... y bueno la idea es que puedas manejar la memoria de una manera dinámica, no como en los arreglos en los que tienes que declararle un tamaño máximo a un arreglo... y por ejemplo si declaras un arreglo de 1000 elementos y solo utilizas 100, imaginate todo el espacio que estarías desperdiciando.... con el manejo dinámico de la memoria, puedes cambiar el tamaño de los datos en tiempo de ejecución, mientras que en los arreglos no....
Bueno ojalá te sirva de algo lo que te dije... pero de todos modos sigue investigando, nunca te quedes con lo que te dice una persona... nunca te quedes con lo que te dicen los profesores... |
| | Volver arriba | | | areku
Registrado: 09 Feb 2005
Mensajes: 58
Ubicación: Hermosillo Sonora México
| | Publicado: 26/04/2005 10:00 pm | | | Título: |
| Creo que a las pilas a las que te refieres no son el stack de la memoria, sino al LIFO (Last In First Out). tmb esta la cola (FIFO First in First Out), pero este no es pila  . Pero la pila esa que creo yo que tu mencionas funciona como una lista. solo que aqui se van apilando los datos y el primero en meter a la pila será el ultimo en salir...
me explike?
 
Editado por mala ortografia... |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 3099
Ubicación: Mexico
| | Publicado: 27/04/2005 3:55 am | | | Título: Re: Listas vinculadas |
| | juanel escribió: | hola, me estoy internadno en el tema de las listas vinculadas.
Alguien me podria decir que tipo de programa puedo hacer utilizando estas mismas, para practicar. |
Podrias crear una calculadora sencilla que utilizara una pila implementada mediante una lista vinculada.
Tambien si estas estudiando listas vinculadas un tutorial muy bueno sobre estas (pero en ingles) lo puedes encontrar en la pagina de la Stanford CS Education Library: Linked List Basics y Linked List Problems.
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | | juanel
Registrado: 24 Ene 2005
Mensajes: 236
| | Publicado: 27/04/2005 7:29 am | | | Título: |
| justo enconte un lugar que se llama C con Clase, ahi estoy aprendiendo algo de listas vinculdas, colas, pilas y arboles.
A las listas vinculadas si pero a las pilas y colas no les veo ninguna utilidad, que se puede hacer con ellas.
Y como es eso de la calculadora con listas???
SAludos |
| | Volver arriba | | | juanel
Registrado: 24 Ene 2005
Mensajes: 236
| | Publicado: 27/04/2005 12:01 pm | | | Título: |
| me retracto lo que dije con las pilas y las colas. 
aca hice un programa que usa pilas.
Se trata de un programa que pasa de numero decimal a romano.
Este programa va analizando primero las unidades y despues la decenas, etc.
como cada vez que analizo un digito no puedo imprimir el resultado al mismo tiempo por que sino, por ejemplo:
59 - quedaría - IXL
y en realidad es LIX
por es use la pila para almacenar los resultado y luego imprimirlos de atras para adelante ( como dice la pila - Last in, First out) ya que no encontre otra mejor manera de hacer esto
aca les paso el programa haber que les parece y que me pueden decir.
Tambien me gustaría saber como harían ustedes este programa.
| Código: | /*pasa de numero decimal a romano*/
/*funciona hasta el 3999*/
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
/*se declara una pila*/
struct pila {
char cad[5];
struct pila *siguiente;
};
typedef struct pila NODO;
int main(void)
{
NODO *primero = NULL;
int num, digit, i;
char rom[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
comienzo:
i = 0;
system("cls");
printf("Introduce un numero: ");
fflush(stdout);
scanf("%d", &num);
if(num > 3999)
{
system("cls");
printf("Tipo que no se contar hasta ahi");
getch();
goto comienzo;
}
printf("En numero romano es: ");
while(num != 0)
{
/*creamos un nuevo elemento de pila*/
NODO *nuevo;
nuevo = (NODO *) malloc(sizeof(NODO));
if(primero == NULL)
{
primero = nuevo;
}
else
{
nuevo->siguiente = primero;
primero = nuevo;
}
digit = num % 10;
if(digit == 1) sprintf(nuevo->cad, "%c", rom[i]);
if(digit == 2) sprintf(nuevo->cad, "%c%c", rom[i], rom[i]);
if(digit == 3) sprintf(nuevo->cad, "%c%c%c", rom[i], rom[i], rom[i]);
if(digit == 4) sprintf(nuevo->cad, "%c%c", rom[i], rom[i+1] );
if(digit == 5) sprintf(nuevo->cad, "%c", rom[i+1]);
if(digit == 6) sprintf(nuevo->cad, "%c%c", rom[i+1], rom[i]);
if(digit == 7) sprintf(nuevo->cad, "%c%c%c", rom[i+1], rom[i], rom[i]);
if(digit == 8) sprintf(nuevo->cad, "%c%c%c%c", rom[i+1], rom[i], rom[i], rom[i]);
if(digit == 9) sprintf(nuevo->cad, "%c%c", rom[i], rom[i+2]);
if(digit == 0)sprintf(nuevo->cad, "");
i = i + 2;
num = num / 10;
}
/*se recorre, lee y elimina la pila*/
while(primero != NULL)
{
NODO *auxiliar = primero;
primero = primero->siguiente;
printf("%s", auxiliar->cad);
free(auxiliar);
}
getch();
goto comienzo;
return 0;
} |
SAludos |
| | Volver arriba | | | juanel
Registrado: 24 Ene 2005
Mensajes: 236
| | Publicado: 27/04/2005 12:04 pm | | | Título: |
| me retracto lo que dije con las pilas y las colas.
aca hice un programa que usa pilas.
Se trata de un programa que pasa de numero decimal a romano.
Este programa va analizando primero las unidades y despues la decenas, etc.
como cada vez que analizo un digito no puedo imprimir el resultado al mismo tiempo por que sino, por ejemplo:
59 - quedaría - IXL
y en realidad es LIX
por es use la pila para almacenar los resultado y luego imprimirlos de atras para adelante ( como dice la pila - Last in, First out) ya que no encontre otra mejor manera de hacer esto
aca les paso el programa haber que les parece y que me pueden decir.
Tambien me gustaría saber como harían ustedes este programa.
| Código: | /*pasa de numero decimal a romano*/
/*funciona hasta el 3999*/
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
/*se declara una pila*/
struct pila {
char cad[5];
struct pila *siguiente;
};
typedef struct pila NODO;
int main(void)
{
NODO *primero = NULL;
int num, digit, i;
char rom[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};
comienzo:
i = 0;
system("cls");
printf("Introduce un numero: ");
fflush(stdout);
scanf("%d", &num);
if(num > 3999)
{
system("cls");
printf("Tipo que no se contar hasta ahi");
getch();
goto comienzo;
}
printf("En numero romano es: ");
while(num != 0)
{
/*creamos un nuevo elemento de pila*/
NODO *nuevo;
nuevo = (NODO *) malloc(sizeof(NODO));
if(primero == NULL)
{
primero = nuevo;
}
else
{
nuevo->siguiente = primero;
primero = nuevo;
}
digit = num % 10;
if(digit == 1) sprintf(nuevo->cad, "%c", rom[i]);
if(digit == 2) sprintf(nuevo->cad, "%c%c", rom[i], rom[i]);
if(digit == 3) sprintf(nuevo->cad, "%c%c%c", rom[i], rom[i], rom[i]);
if(digit == 4) sprintf(nuevo->cad, "%c%c", rom[i], rom[i+1] );
if(digit == 5) sprintf(nuevo->cad, "%c", rom[i+1]);
if(digit == 6) sprintf(nuevo->cad, "%c%c", rom[i+1], rom[i]);
if(digit == 7) sprintf(nuevo->cad, "%c%c%c", rom[i+1], rom[i], rom[i]);
if(digit == 8) sprintf(nuevo->cad, "%c%c%c%c", rom[i+1], rom[i], rom[i], rom[i]);
if(digit == 9) sprintf(nuevo->cad, "%c%c", rom[i], rom[i+2]);
if(digit == 0)sprintf(nuevo->cad, "");
i = i + 2;
num = num / 10;
}
/*se recorre, lee y elimina la pila*/
while(primero != NULL)
{
NODO *auxiliar = primero;
primero = primero->siguiente;
printf("%s", auxiliar->cad);
free(auxiliar);
}
getch();
goto comienzo;
return 0;
} |
SAludos |
| | Volver arriba | | | | areku
Registrado: 09 Feb 2005
Mensajes: 58
Ubicación: Hermosillo Sonora México
| | Publicado: 28/04/2005 9:05 pm | | | Título: |
| Mira, aqui te pongo una PILA en la forma en que yo programo.. Si quieres utilizarla solo tienes que declarar una variable tipo LIFO en el main y empezar a utilizarla masomenos como dice ahi...
Espero le entiendas..
Luego que tenga tiempo hago el programilla que dices. Se escucha entretenido 
bye
| Código: |
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct caja{
int valor; //valor donde se agregara el numero en la caja
caja *siguiente;
};
class LIFO{
caja *principio;
int cuantos;
public:
LIFO();
~LIFO();
void agregar(int a);
void borrar();
void pintar();
};
LIFO::LIFO()
{
principio=NULL;
cuantos=0;
}
LIFO::~LIFO()
{
caja *p;
p=principio;
while(p)
{
principio=principio->siguiente;
free(p);
p=principio;
}
}
void LIFO::agregar(int a)
{
caja *p;
p=(caja *)malloc(sizeof(caja));
p->valor=a; // se le asigna el valor a agregar a Valor
if(!principio) // Si Esta vacia la LIFO
{
p->siguiente=NULL;
principio=p;
}else{
p->siguiente=principio;
principio=p;
}
cuantos++;
}
void LIFO::borrar()
{
caja *p;
p=principio;
if(principio)
{
principio=principio->siguiente;
free(p);
p=principio;
cuantos--;
}
}
void LIFO::pintar()
{
caja *p;
p=principio;
while(p)
{
printf("%d ",p->valor);
p=p->siguiente;
}
puts("");
}
main()
{
LIFO a;
a.agregar(1);
a.agregar(2);
a.agregar(3);
a.agregar(4);
a.pintar();
a.borrar();
a.pintar();
getch();
}
|
P.D. Perdon por no estar comentado... Pero creo yo que esta muy facil de entender.... |
| | Volver arriba | | | rir3760
Registrado: 01 Oct 2004
Mensajes: 3099
Ubicación: Mexico
| | Publicado: 28/04/2005 11:32 pm | | | Título: |
| | juanel escribió: | | Y como es eso de la calculadora con listas??? |
Estaba pensando en uno de los ejemplos de K&R2:
| Código: | #include <stdio.h>
#include <stdlib.h> /* for atof() */
#define MAXOP 100 /* max size of operand or operator */
#define NUMBER '0' /* signal that a number was found */
int getop(char []);
void push(double);
double pop(void);
/* reverse polish calculator */
int main(void)
{
int type;
double op2;
char s[MAXOP];
while ((type = getop(s)) != EOF) {
switch (type) {
case NUMBER:
push(atof(s));
break;
case '+':
push(pop() + pop());
break;
case '*':
push(pop() * pop());
break;
case '-':
op2 = pop();
push(pop() - op2);
break;
case '/':
op2 = pop();
if (op2 != 0.0)
push(pop() / op2);
else
printf("error: zero divisor\n");
break;
case '\n':
printf("\t%.8g\n", pop());
break;
default:
printf("error: unknown command %s\n", s);
break;
}
}
return EXIT_SUCCESS;
}
#define MAXVAL 100 /* maximum depth of val stack */
int sp = 0; /* next free stack position */
double val[MAXVAL]; /* value stack */
/* push: push f onto value stack */
void push(double f)
{
if (sp < MAXVAL)
val[sp++] = f;
else
printf("error: stack full, can't push %g\n", f);
}
/* pop: pop and return top value from stack */
double pop(void)
{
if (sp > 0)
return val[--sp];
else {
printf("error: stack empty\n");
return 0.0;
}
}
#include <ctype.h>
int getch(void);
void ungetch(int);
/* getop: get next operator or numeric operand */
int getop(char s[])
{
int i, c;
while ((s[0] = c = getch()) == ' ' || c == '\t')
;
s[1] = '\0';
if (!isdigit(c) && c != '.')
return c; /* not a number */
i = 0;
if (isdigit(c)) /* collect integer part */
while (isdigit(s[++i] = c = getch()))
;
if (c == '.') /* collect fractional part */
while (isdigit(s[++i] = c = getch()))
;
s[i] = '\0';
if (c != EOF)
ungetch(c);
return NUMBER;
}
#define BUFSIZE 100
char buf[BUFSIZE]; /* buffer for ungetch */
int bufp = 0; /* next free position in buf */
/* getch: get a (possibly pushed back) character */
int getch(void)
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
/* ungetch: push characters back into input */
void ungetch(int c)
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
} |
El programa implementa una calculadora RPN sencilla, para mantener el codigo relativamente corto este tiene limites fijos y utiliza un array para almacenar los valores a procesar. Se podria modificar para que utilizara una lista vinculada en lugar del array de forma que no hubiera un limite especifico.
Tengo que admitir que no es el mejor ejemplo sobre el uso practico de listas vinculadas. Voy a revisar los libros y tutoriales que tengo y si encuentro ejercicios interesantes los coloco en el foro.
| juanel escribió: | aca hice un programa que usa pilas. Se trata de un programa que pasa de numero decimal a romano.
... snip ...
Tambien me gustaría saber como harían ustedes este programa. |
Una discusion muy interesante sobre el tema de la conversion de decimal a romano la puedes encontrar en el sitio de Radsoft: On the Conversion between Roman Numerals and Arabic Numbers.
Un saludo
_________________
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language |
| | Volver arriba | | | juanel
Registrado: 24 Ene 2005
Mensajes: 236
| | Publicado: 29/04/2005 2:04 pm | | | Título: |
| es medio complicado para mi cerebro primitivo
Gracias, lo de los numeros romanos ya lo había leido porque pusiste ese mismo link en otro mensaje de este foro.
Areku: no entiendo mucho C++, pero igual puedeo entender un poco.
Saludos |
| | Volver arriba | | | | areku
Registrado: 09 Feb 2005
Mensajes: 58
Ubicación: Hermosillo Sonora México
| | Publicado: 29/04/2005 2:16 pm | | | Título: |
| Espero luego que tenga un poco mas de tiempo poder comentarlo y explicarlo....
Es una muy buena forma de hcer las colas, listas pilas etc etc.... |
| | Volver arriba | | | | |
| No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
|
|
| |
F.A.Q.
Conéctese para revisar sus mensajes