iceman755
Registrado: 30 Oct 2007
Mensajes: 2
|  Publicado: 30/10/2007 10:16 pm | | | Título: [leng. C] Listas dobl. enlazadas: ordenacion y busq. binaria |
| Hola, quizas alguien pueda echarme una mano, soy muy nuevo en esto de lenguaje C y hay cosas que aun no comprendo bien (punteros). Voy a decir cual es el problema, lo que llevo hecho (funciona bien) y lo que me falta.
Problema: Crear una lista doblemente enlazada, guardar en dicha lista 1000 nodos, cada nodo tiene un campo que funciona como un indice, llenar este indice con numeros aleatorios no repetidos que oscilan entre 1 y 10000. Luego ordenar de forma ascendente dicha lista y realizar una opcion de busqueda binaria por el numero de indice.
Lo que llevo hecho: He creado la estructura, lleno la lista con los numeros aleatorios.
Me falta: ordenar la lista y la busqueda binaria. (mi problema es que en realidad no logro comprender como es que trabajan los punteros al modificarlos, otro problema es que este programa me lo han puesto Martes para entregarlo Jueves de la misma semana)
A continuacion dejo el codigo de lo que llevo hecho:
| Código: |
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>
#include<time.h>
#define orden(l) ((l)->num)
#define fnam(l) ((l)->fname)
#define lnam(l) ((l)->lname)
#define next(l) ((l)->sig)
#define before(l) ((l)->ant)
typedef struct nodod nodod, *listad;
struct nodod
{
int num;
char fname[5];
char lname[5];
listad sig;
listad ant;
};
listad crearnodod()
{
listad l;
l=(listad)malloc(sizeof(nodod));
if (l!=NULL)
{
orden(l)=NULL;
strcpy(fnam(l),"NULL");
strcpy(lnam(l),"NULL");
next(l)=NULL;
before(l)=NULL;
}
return(l);
}
void addnodod(listad *pl, listad nuevo)
{
listad k;
if (*pl==NULL)
*pl=nuevo;
else
{
for(k=*pl;next(k)!=NULL;k=next(k));
next(k)=nuevo;
before(nuevo)=k;
}
}
int contarnodod(listad pl)
{
listad k;
int c;
c=1;
for (k=pl;k!=NULL;k=next(k))
c++;
return (c);
}
int buscarnodod(listad pl, int num)
{
listad k;
if (pl==NULL)
return (0);
else
for (k=pl;k!=NULL;k=next(k))
if (orden(k)==num)
return (1);
return (0);
}
void main()
{
listad pl,nuevo,tem;
int num;
pl=nuevo=tem=NULL;
num=0;
srand(time(NULL));
clrscr();
while(contarnodod(pl) <=20)
{
num=(rand() % 100)+1;
printf("numero generado %d\n",num);
if (buscarnodod(pl,num)<1)
{
nuevo=crearnodod();
orden(nuevo)=num;
strcpy(fnam(nuevo),"hola");
strcpy(lnam(nuevo),"hola");
addnodod(&pl,nuevo);
}
}
printf("\n");
for(tem=pl;tem!=NULL;tem=next(tem))
printf("%d\n",orden(tem));
getch();
}
|
Nota: Este codigo que he colocado me funciona, lo pongo para que quien me eche una mano tenga una idea de como hago las cosas y asi tal vez pueda explicarme con una sintaxis parecida.
Se nota que sobre lo que me falta no he hecho nada, lo que pasa es que necesito una explicacion de algo que no comprendo:
Para la ordenacion utilizando el metodo de insercion:
1-creo una funcion y le paso como parametro la lista. cierto???
cuantas listas (o nodos) debo utilizar como auxiliares dentro de la funcion???
como debo utilizar esas listas (o nodos) auxiliares???
segun he leido (aqui cuando utilice la busqueda) lo que debo hacer es lo siguiente:
1-crear una nueva lista en donde guardare los nodos ordenados
2-obtener el elemento mayor de la lista original
3-colocar ese elemento mayor como primer elemento de la lista nueva
4-volver al paso 2 mientras queden elementos en la lista original
5-hacer que la lista original apunte la la lista nueva
no comprendo el paso 2, como determino cual es el mayor??? y que hago para que la lista original me quede vacia, borro los elementos o los enlazo en la lista nueva??? o es que al enlazarlos en la lista nueva los estoy borrando de la original???
GRACIAS POR ADELANTADO!!!! |
|
F.A.Q.
Conéctese para revisar sus mensajes