Estructuras de datos y algoritmos II: 2016

lunes, 5 de diciembre de 2016

Horario

Mañana la clase de 12:00 a 13:00 Hrs en el lab-07 cualquier cambio les aviso

viernes, 18 de noviembre de 2016

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
typedef struct nodo
{
int numero;
struct nodo *derecho;
struct nodo *izquierdo;
}*ptr;

void Insertar(ptr *nodo, int dato);
void Eliminar_nodo(ptr *a, int dato);
int Buscar(ptr nodo, int dato);
int EsHoja(ptr h);
int Num_Nodos(ptr nodo, int* c);
int Altura_Arbol(ptr nodo, int *altura);
int Nivel_Nodo(ptr nodo, int dat);
void InOrden(ptr nodo, void (*func)(int*));
void PreOrden(ptr nodo, void (*func)(int*));
void PostOrden(ptr nodo, void (*func)(int*));
void Eliminar_Arbol(ptr *nodo);
void auxContador(ptr nodo, int*);
void auxAltura(ptr nodo, int, int*);
void Mostrar(int *a);
int Vacio(ptr r);
int main()
{
ptr Arbol = NULL;

int i, num, ndatos, opcion;

do
{
printf("\n");
printf("\n****** arbol ********");
printf("\n1. Insertar arbol *");
printf("\n2. Nivel nodo *");
printf("\n3. Buscar nodo *");
printf("\n4. Eliminar nodo *");
printf("\n5. Eliminar árbol *");
printf("\n6. Salir *");
printf("\n*********************");
printf("\n\n\n");
printf(" Elija opción ");
scanf("%d",&opcion);
switch (opcion)
{
case 1: system("cls");

printf("\n Indique cuantos datos desea insertar ");

scanf("%d",&ndatos);

system("cls");

printf("\n Introduzca %d datos\n\n", ndatos);

for(i=1; i<=ndatos; i++)
{
scanf("%d",&num);

Insertar(&Arbol, num);
}
system("cls");
printf("\n Numero nodos ----> %d ", Num_Nodos(Arbol, &num));

printf("\n\n Altura arbol ----> %d ", Altura_Arbol(Arbol, &num));
printf("\n\n InOrden ----> ");
InOrden(Arbol, Mostrar);
printf("\n\n PreOrden ----> ");
PreOrden(Arbol, Mostrar);
printf("\n\n PostOrden ----> ");
PostOrden(Arbol, Mostrar);
printf("\n\n\n\n\n\n\n\n");
system("pause");

system("cls");
break;
case 2: system("cls");
printf("\n\n Introduzca nodo ");
scanf("%d", &num);

system("cls");

printf("\n\n Nivel de %d ----> %d\n",num, Nivel_Nodo(Arbol, num));

printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 3: system("cls");
printf("\n Introduzca dato a buscar ");
scanf("%d", &num);
system("cls");
Buscar(Arbol, num);
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 4: system("cls");
printf("\n Introduzca dato a eliminar ");
scanf("%d", &num);
system("cls");
Eliminar_nodo(&Arbol, num);
printf("\n\n Eliminado ----> %d ",num);
printf("\n\n InOrden ----> ");
InOrden(Arbol, Mostrar);
printf("\n\n Número nodos ----> %d", Num_Nodos(Arbol, &num));
printf("\n\n Altura árbol ----> %d", Altura_Arbol(Arbol, &num));
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 5: system("cls");
Eliminar_Arbol(&Arbol);
printf("\n ARBOL ELIMINADO");
printf("\n\n\n\n\n\n\n\n");
system("PAUSE");
system("cls");
break;
case 6: break;

default: system("cls");

break;
}
} while (opcion!=6);

return 0;
}
int Vacio(ptr r)
{
return r==NULL;
}
void Insertar(ptr *a, int dato){
ptr padre = NULL;
ptr actual = *a;
while(!Vacio(actual) && dato != actual->numero) {
padre = actual;
if(dato < actual->numero)
actual = actual->izquierdo;
else if(dato > actual->numero)
actual = actual->derecho;
}
if(!Vacio(actual))
return;
if(Vacio(padre)) {
*a = (ptr)malloc(sizeof(struct nodo));
(*a)->numero = dato;
(*a)->izquierdo = (*a)->derecho = NULL;
}
else if(dato < padre->numero) {
actual = (ptr)malloc(sizeof(struct nodo));
padre->izquierdo = actual;
actual->numero = dato;
actual->izquierdo = actual->derecho = NULL;
}
else if(dato > padre->numero) {
actual = (ptr)malloc(sizeof(struct nodo));
padre->derecho = actual;
actual->numero = dato;
actual->izquierdo = NULL;
actual->derecho = NULL;
}
}
void Eliminar_nodo(ptr *a, int dato){
ptr padre = NULL;
ptr actual;
ptr nodo;
int aux;
actual = *a;
while(actual!=NULL) {
if(dato == actual->numero) {
if(EsHoja(actual)) {
if(padre)
if(padre->derecho == actual)
padre->derecho = NULL;
else if(padre->izquierdo == actual)
padre->izquierdo = NULL;
free(actual);
actual = NULL;

}else {
padre = actual;
if(actual->derecho) {
nodo = actual->derecho;
while(nodo->izquierdo) {
padre = nodo;
nodo = nodo->izquierdo;}
}else {
nodo = actual->izquierdo;
while(nodo->derecho) {
padre = nodo;
nodo = nodo->derecho;}
}
aux = actual->numero;
actual->numero = nodo->numero;
nodo->numero = aux;
actual = nodo;}
}else {
padre = actual;
if(dato > actual->numero)
actual = actual->derecho;
else if(dato < actual->numero)
actual = actual->izquierdo;}
}
}

void InOrden(ptr nodo, void (*func)(int*))
{
if(nodo->izquierdo)

InOrden(nodo->izquierdo, func);

func(&(nodo->numero));

if(nodo->derecho)

InOrden(nodo->derecho, func);
}
void PreOrden(ptr nodo, void (*func)(int*))
{
func(&nodo->numero);

if(nodo->izquierdo)

PreOrden(nodo->izquierdo, func);

if(nodo->derecho)

PreOrden(nodo->derecho, func);
}
void PostOrden(ptr nodo, void (*func)(int*))
{
if(nodo->izquierdo)

PostOrden(nodo->izquierdo, func);

if(nodo->derecho)

PostOrden(nodo->derecho, func);

func(&nodo->numero);
}

int Buscar(ptr nodo, int dato)
{
ptr actual = nodo;

while(actual!= NULL)
{
if(dato == actual->numero)
{
printf("\n %d EXISTE", dato);

return TRUE;
}
else if(dato < actual->numero)

actual = actual->izquierdo;

else if(dato > actual->numero)

actual = actual->derecho;
}
printf("\n %d NO EXISTE", dato);

return FALSE;
}

int Nivel_Nodo(ptr nodo, int dato)
{
int altura = 0;

ptr actual = nodo;

while(actual != NULL)
{
if(dato == actual->numero)

return altura;

else {
altura++;

if(dato < actual->numero)

actual = actual->izquierdo;

else if(dato > actual->numero)

actual = actual->derecho;
}
}
return -1;
}

void auxContador(ptr nodo, int *c)
{
(*c)++;

if(nodo->izquierdo)

auxContador(nodo->izquierdo, c);

if(nodo->derecho)

auxContador(nodo->derecho, c);
}

int Num_Nodos(ptr nodo, int *cont)
{
*cont = 0;

auxContador(nodo, cont);

return *cont;
}
void auxAltura(ptr nodo, int a, int *altura)
{
if(nodo->izquierdo)

auxAltura(nodo->izquierdo, a+1, altura);

if(nodo->derecho)

auxAltura(nodo->derecho, a+1, altura);

if(EsHoja(nodo) && a > *altura)

*altura = a;
}

int Altura_Arbol(ptr nodo, int *altura)
{
*altura = 0;

auxAltura(nodo, 0, altura);

return *altura;
}

void Eliminar_Arbol(ptr *nodo)
{
if(*nodo)
{
Eliminar_Arbol(&(*nodo)->izquierdo);

Eliminar_Arbol(&(*nodo)->derecho);

free(*nodo);

*nodo = NULL;
}
}

int EsHoja(ptr nodo)
{
return !nodo->derecho && !nodo->izquierdo;
}
int comparar(int a,int b)
{
if(a > b)

return 1;

if(a < b)

return -1;

return 0;
}
void Mostrar(int *a)
{
printf("%d, ", *a);
}

jueves, 3 de noviembre de 2016

Árbol Binario de Búsqueda Ejercicios

1) En base al proceso descrito con anterioridad, inserte en un ABB los números: 9, 18, 10, 2, 6, 21, 8, 1, 7.

2) Construir un ABB con las claves 50, 25, 75, 10, 40, 60, 90, 35, 45, 70, 42.

3) Construir un ABB a partir de las claves 10, 75, 34, 22, 64, 53, 41, 5, 25, 74, 20, 15, 90.

4) El recorrido en postorden de un ABB que contiene caracteres es: DMLCTAISRUNOKB Y en inorden es: DMATLCBIKUSRON

A) Dibujar el árbol binario.

B) Dar el recorrido en preorden.

martes, 1 de noviembre de 2016

Árboles Binarios de Búsqueda

Árboles binarios de búsqueda

La principal característica es que la información se almacena en los nodos cuidando de mantener cierto orden.

Formalmente se define un árbol binario de búsqueda de la siguiente manera:
Para todo nodo T del árbol se debe cumplir que todos los valores almacenados en el subárbol izquierdo de T sean menores o iguales a la información guardada en el nodo T. De forma similar, todos los valores almacenados en el subárbol derecho de T deben ser mayores a iguales a la información guardada en el nodo T.

El árbol binario de búsqueda es una estructura de datos sobre la cual se puede realizar eficientemente las operaciones de búsqueda, insercion y eliminación. Comparando esta estructura con otras, se pueden observar ciertas ventajas.
Por ejemplo, en un arreglo es posible localizar datos eficientemente si estos se encuentran ordenados, pero las operaciones de insercion y eliminación resultan costosas, porque involucran movimiento de los elementos dentro del arreglo.
En las listas, por otra parte, dichas operaciones se pueden llevar a cabo con facilidad, pero la operación de búsqueda, en este caso es una operación que demanda recursos, pudiendo incluso requerir recorrer todos los elementos de ella para llegar a uno en particular.

ESPACIO PARA IMAGEN DE UN ÁRBOL

Búsqueda
La operación de búsqueda en un árbol binario de búsqueda es mucho mas eficiente que en un árbol binario general, ya que al comparar el valor buscado con la información del nodo visitado, si no es igual, se debe continuar solo por alguno de los dos subárboles.

Inserción en un árbol binario de búsqueda es una operación que se puede realizar eficientemente en este tipo de estructura de datos. La estructura crece conforme se insertan elementos al árbol. Los pasos que se deben realizar para agregar un nuevo nodo de un árbol de búsqueda son las siguientes:

1.- Comparar la clave a insertar con la raíz del árbol. Si es mayor, se sigue con el subárbol derecho. Si es menor, se continua con el subárbol izquierdo.
2.- Repetir sucesivamente el paso 1 hasta que se cumpla algunas de las siguientes condiciones:
2.1 .- El subárbol derecho, o el subárbol izquierdo, es igual a vació, en cuyo caso procederá a insertar el elemento en el lugar que le corresponde.
2.2 La clave que se quiere insertar esta en el nodo analizado, por lo tanto no se lleva a cabo la insercion. Este caso es valido solo cuando la aplicación exige que no se repitan elementos.

ELIMINACIÓN EN UN ÁRBOL BINARIO DE BÚSQUEDA.
La operación de eliminación en un árbol binario de búsqueda es un poco mas complicada que la de inserción. Esta consiste en eliminar un nodo sin violar los principios que define un árbol binario de búsqueda. se deben distinguir los siguientes casos:
1.- Si el elemento es terminal u hoja, simplemente se suprime redefiniendo el puntero de su predecesor.
2.- Si el elemento a eliminar tiene un solo descendiente, entonces tiene que sustituirse por ese descendiente.
3.- Si el elemento a eliminar tiene los dos descendientes, entonces se tiene que sustituir por el nodo que se encuentra mas a la derecha en el subárbol izquierdo.
Cabe destacar que antes de eliminar un nodo, se debe localizar este en el árbol. Para esto se utiliza el algoritmo de búsqueda presentado anteriormente.

viernes, 21 de octubre de 2016

Código para Grafo

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct nodo{
char nombre[2];//nombre del vertice o nodo
struct nodo *sgte;
struct arista *ady;//puntero hacia la primera arista del nodo
};
struct nodo *primero=NULL, *ultimo=NULL;
struct arista{
struct nodo *destino;//puntero al nodo de llegada
struct arista *sgte;
};
void insertar_nodo();
void insertar_arista();
void vaciar_aristas();
void eliminar_nodo();
void eliminar_arista();
void mostrar_grafo();
void mostrar_aristas();
void visualizar();

main (){
int opcion;
do{

printf("\n\n\n");
printf("\n****************************************");
printf("\n*******************GRAFO****************");
printf("\n\n");
printf("\n1. Insertar un nodo");
printf("\n2. Insertar un arista");
printf("\n3. Eliminar un nodo");
printf("\n4. Eliminar una arista");
printf("\n5. Mostrar grafo");
printf("\n6. Mostrar aristas de un nodo");
printf("\n7. Salir");
printf("\n8. visualizar nodo");
printf("\n****************************************\n");
printf("Ingresar opcion");
scanf("%d", &opcion);

switch(opcion){
case 1: insertar_nodo();
break;
case 2: insertar_arista();
break;
case 3: eliminar_nodo();
break;
case 4: eliminar_arista();
break;
case 5: mostrar_grafo();
break;
case 6: mostrar_aristas();
break;
case 7: printf("Salir");
break;
case 8: visualizar ();
break;
default: system("pause");
break;

}
}
while (opcion !=8);
}
void insertar_nodo(){
struct nodo *nuevo;
nuevo=(struct nodo*)malloc(sizeof(struct nodo));
if (nuevo == NULL)
printf("\n Memoria insuficiente");
else{
printf("\nINGRESE NODO: ");
scanf("%s", nuevo->nombre);
nuevo->sgte = NULL;
nuevo->ady=NULL;}

if(primero==NULL)
{
printf("PRIMER NODO...!!!");
primero = nuevo;
ultimo = nuevo;

}
else
{
nuevo->sgte=NULL;
ultimo->sgte=nuevo;
ultimo=nuevo;
while(ultimo->sgte!=NULL)
{
ultimo = ultimo->sgte;
}

printf("NODO INGRESADO...!!!");
}

}

void visualizar(){

struct nodo *actual;
actual=primero;
if(actual==NULL){
printf("\nGrafo vacio");}
else{

while(actual!=NULL){
printf("%s\n",actual->nombre);
actual=actual->sgte;
}}
printf("\n\n\n");
system("pause");
}

/*INSERTAR ARISTA---------------------------------------------------------------------*/
void insertar_arista()
{ char ini[2], fin[2];
struct arista *nuevo, *q;
struct nodo *aux, *aux2;
nuevo=(struct arista*)malloc(sizeof(struct arista));
if(primero==NULL)
{
printf("GRAFO VACIO...!!!!");
return;
}else{

nuevo->sgte=NULL;
printf("\nINGRESE NODO DE INICIO:");
scanf("%s", &ini);
printf("\nINGRESE NODO FINAL:");
scanf("%s", &fin);
aux=primero;
aux2=primero;
}
while(aux2!=NULL){
if(strcmp(fin, aux2->nombre)==0)
{
break;
}else{
aux2=aux2->sgte;}
}
while(aux!=NULL)
{

if(strcmp(ini, aux->nombre)==0)
{
if(aux->ady==NULL)
{ aux->ady=nuevo;
nuevo->destino=aux2;
printf("PRIMERA ARISTA....!");
}
else
{
q=aux->ady;
while(q->sgte!=NULL)
q=q->sgte;
nuevo->destino=aux2;
q->sgte=nuevo;
printf("ARISTA AGREGADA...!!!!");

}
return;
}

aux = aux->sgte;
}
}

void eliminar_nodo(){
char var[2];
struct nodo *aux,*ant;
aux=primero;
printf("ELIMINAR UN NODO\n");
if(primero==NULL)
{
printf("GRAFO VACIO...!!!!");
return;
}
printf("INGRESE NOMBRE DE VARIABLE:");
scanf("%s",var);

while(aux!=NULL)
{
if(strcmp(var, aux->nombre)==0)
{
if(aux->ady!=NULL)
vaciar_aristas();

if(aux==primero)
{

primero=primero->sgte;
free(aux);
printf("NODO ELIMINADO...!!!!");
return;
}
else
{
ant->sgte = aux->sgte;
free(aux);
printf("NODO ELIMINADO...!!!!");
return;
}
}
else
{
ant=aux;
aux=aux->sgte;
}
}
}
void eliminar_arista(){
char ini[2], fin[2];
struct nodo *aux, *aux2;
struct arista *q,*r;
printf("\n ELIMINAR ARISTA\n");
printf("INGRESE NODO DE INICIO:");
scanf("%s",ini);
printf("INGRESE NODO FINAL:");
scanf("%s", fin);
aux=primero;
aux2=primero;
while(aux2!=NULL)
{
if(strcmp(fin, aux2->nombre)==0)
{
break;
}
else
aux2=aux2->sgte;
}
while(aux!=NULL)
{
if(strcmp(ini, aux->nombre)==0)
{
q=aux->ady;
while(q!=NULL)
{
if(q->destino==aux2)
{
if(q==aux->ady)
aux->ady=aux->ady->sgte;
else
r->sgte=q->sgte;
free(q);
printf("ARISTA ", aux->nombre, "----->", aux2->nombre, " ELIMINADA.....!!!!");
return;
}
}
r=q;
q=q->sgte;
}
aux = aux->sgte;
}
}
void mostrar_grafo(){
struct nodo *ap;
struct arista *ca;
ap=primero;
printf("NODO|LISTA DE ADYACENCIA\n");
while(ap!=NULL){
printf("%s| ", ap->nombre);
if(ap->ady!=NULL)
{
ca=ap->ady;
while(ca!=NULL)
{
printf("%s ",ca->destino->nombre);
ca=ca->sgte; } }
ap=ap->sgte;
printf("\n");}
}
void mostrar_aristas(){
struct nodo *aux;
struct arista *ar;
char var[2];
printf("MOSTRAR ARISTAS DE NODO\n");
printf("INGRESE NODO:");
scanf("%s",var);
aux=primero;
while(aux!=NULL)
{
if(strcmp(var, aux->nombre)==0)
{
if(aux->ady==NULL)
{ printf("EL NODO NO TIENE ARISTAS...!!!!");
return;
}
else
{
printf("NODO|LISTA DE ADYACENCIA\n");
printf("%s | ",aux->nombre);
ar=aux->ady;
while(ar!=NULL)
{
printf(ar->destino->nombre," ");
ar=ar->sgte;
}

return;
}
}
else
aux=aux->sgte;
}
}
void vaciar_aristas(){
struct arista *q,*r;
struct nodo *aux;
aux=primero;
q=aux->ady;
while(q->sgte!=NULL)
{
r=q;
q=q->sgte;
free(r);
}

jueves, 20 de octubre de 2016

Apuntes Arboles

Realizar un resumen del Capitulo 6 Arboles desde la Pág. 176 hasta la pág. 179

lunes, 17 de octubre de 2016

Algoritmo de Floyd

#include<stdio.h>
#include<conio.h>
int min(int,int);
void floyds(int p[10][10],int n)
{
int i,j,k;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
p[i][j]=0;
else
p[i][j]=min(p[i][j],p[i][k]+p[k][j]);
}
int min(int a,int b)
{
if(a<b)
return(a);
else
return(b);
}
main()
{
int p[10][10],w,n,e,u,v,i,j;;
//clrscr();
printf("\n Introduce el numero de vertices:");
scanf("%d",&n);
printf("\n Introduce el número de aristas:\n");
scanf("%d",&e);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
p[i][j]=999;
}
for(i=1;i<=e;i++)
{
printf("\n Introduzca los vértices finales de primera línea %d con suetiqueta de costo \n",i);
scanf("%d%d%d",&u,&v,&w);
p[u][v]=w;
}
printf("\n Matriz de datos de entrada:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d \t",p[i][j]);
printf("\n");
}
floyds(p,n);
printf("\nClausura transitiva:\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d \t",p[i][j]);
printf("\n");
}
printf("\nLas rutas más cortas son:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j)
printf("\n <%d,%d>=%d",i,j,p[i][j]);
}
getch();
}

viernes, 7 de octubre de 2016

Apunte de libro Estructuras de datos

Pagina 277 Gráficas desde el punto 7.2 Definicion de graficas ,7.3 Conceptos basicos (todos)
y pagina 280 desde la imagen hasta antes de gráficas dirigidas.

miércoles, 5 de octubre de 2016

Estructuras de Datos

Libro en linea
http://www.colegiodrriodelaloza.edu.mx/informatica/Manejo%20de%20memoria%20en%20la%20estructura%20de%20datos/95950672-Estructura-de-Datos-Tercera-Edicion.pdf

sábado, 1 de octubre de 2016

Código para Listas Circulares Doblemente Enlazadas

#include <stdio.h>
#include <stdlib.h>//utilizar symtem cls limpiar pantralla y system pause salir mediante tecla
#include <string.h>//comparar cadenas de caracteres
struct nodo{
char nombre[40];

struct nodo *siguiente;
struct nodo *anterior;
};
struct nodo *primero=NULL, *ultimo=NULL;

int numNodos=0;
int pos;
void insertarUltimo();
void insertarPrimero();
void insertarIntermedio ();
void visualizarInicioFinal ();
void visualizarFinalInicio ();
void visualizarPosicionFinal ();
void visualizarPosicionInicio ();
void visualizarPrimeroUltimo ();
void Buscar ();
void Eliminar ();
main(){
int opcion;
do{
system ("cls");
printf("");
printf("\n *******LISTA CIRCULAR DOBLEMENTE ENLAZADA********\n");
printf("\n ****ITIC. ANA FRANCISCA MARTINEZ BETANCOURT*****\n\n");
printf("\n 1. Insertar al Final *");
printf("\n 2. Insertar al Inicio *");
printf("\n 3. Insertar en X posicion *");
printf("\n 4. Visualizar de Inicio - Fin *");
printf("\n 5. Visualizar de Fin - Inicio *");
printf("\n 6. Visualizar Desde X Posicion al Final *");
printf("\n 7. Visualizar desde X Posicion al Inicio*");
printf("\n 8. Visualizar Primero y ultimo *");
printf("\n 9. Buscar *");
printf("\n 10.Eliminar *");
printf("\n 11.Salir *");
printf("\n");
printf("\n ************************************************");
printf("\n\n\n");
printf("\n Elija una opcion ");
scanf("%d", &opcion);

switch (opcion){

case 1: insertarUltimo ();
break;
case 2: insertarPrimero ();
break;
case 3: insertarIntermedio ();
break;
case 4: visualizarInicioFinal ();
break;
case 5: visualizarFinalInicio ();
break;
case 6: visualizarPosicionFinal ();
break;
case 7: visualizarPosicionInicio ();
break;
case 8: visualizarPrimeroUltimo ();
break;
case 9: Buscar ();
break;
case 10: Eliminar ();
break;
case 11: printf ("Salir");
break;
default: system ("cls");
break;
}
} while (opcion !=11);
}

void insertarUltimo(){
system ("cls");
struct nodo *nuevo;

nuevo=(struct nodo*)malloc(sizeof( struct nodo));
if ((nuevo==NULL))
printf ("\n MEMORIA INSUFICIENTE\n");
else{
printf ("\n Nombre: ");
fflush (stdin);
gets(nuevo->nombre);
nuevo->siguiente=primero;
if (primero==NULL)
{
primero=nuevo;
ultimo=nuevo;
nuevo->anterior=ultimo;
nuevo->siguiente=primero;

}else{
nuevo->siguiente=primero;
nuevo->anterior=ultimo;
ultimo->siguiente=nuevo;
ultimo=nuevo;
primero->anterior=ultimo;
}
}
numNodos++;
}
void insertarPrimero(){
system ("cls");
struct nodo *nuevo;
nuevo=( struct nodo*)malloc (sizeof( struct nodo));
if (nuevo==NULL)
printf("MEMORIA INSUFICIENTE\n");
else{
printf("\n Nombre: ");
fflush(stdin);
gets(nuevo->nombre);
ultimo->siguiente=nuevo;
if (ultimo==NULL)
{
primero=nuevo;
ultimo=nuevo;
nuevo->anterior=ultimo;
nuevo->siguiente=primero;

}else{
nuevo->anterior=ultimo;
nuevo->siguiente=primero;
primero->anterior=nuevo;
primero=nuevo;
numNodos++;}

}
}
void insertarIntermedio (){
system ("cls");
struct nodo *actual;
struct nodo *nuevo;
nuevo =( struct nodo*)malloc(sizeof( struct nodo));
if (nuevo==NULL)
printf("\n MEMORIA INSUFUCIENTE\n");
if (numNodos <2)
printf ("\n Número de nodos insuficiente");
else{
int pos_insertar;
printf("\n Nombre: ");
fflush(stdin);
gets(nuevo->nombre);
printf ("\n Posicion: ");
scanf ("%d", &pos_insertar);
if((pos_insertar >1) &&(pos_insertar <= numNodos)){
actual=primero;
for (pos = 2; pos <pos_insertar; ++pos)
actual= actual->siguiente;
nuevo->siguiente= actual->siguiente;
nuevo->anterior = actual;
actual->siguiente->anterior = nuevo;
actual->siguiente = nuevo;
numNodos++;
}
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarInicioFinal (){
system ("cls");
struct nodo *actual;
pos=1;
actual=primero;
while(pos<=numNodos){

printf("\n\n");
printf(" %d.- ", pos);
printf(" Nombre: %s", actual->nombre);
printf("\n");
actual= actual->siguiente;
pos++;
}
if(numNodos==0)
printf("\n LISTA VACIA");
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarFinalInicio (){
system("cls");
struct nodo *actual;
actual=ultimo;
pos= numNodos;
printf("\nITIC Ana Francisca Martínez Betancourt");
printf("\n\n");
while (pos >0){
printf(" %d.- ", pos);
printf("Nombre: %s ",actual->nombre);
printf("\n\n");
actual =actual->anterior;
pos--;
}
if(numNodos==0)
printf("\n LISTA VACIA");
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarPrimeroUltimo (){
system("cls");
if(numNodos==0)
printf("\n LISTA VACIA");
else
printf("\n PRIMERO -------> Nombre: %s ", primero->nombre);
printf("\n");
printf("\n ULTIMO ------> Nombre: %s ", ultimo->nombre);
printf("\n\n\n\n\n\n\n");
system ("pause");
}
void visualizarPosicionFinal (){
system("cls");
int p=1;
int posicion;
struct nodo *actual;
actual = primero;
printf("\n Indique posicion ");
scanf("%d", &posicion);
system("cls");
for (pos = 2; pos<=posicion; pos++){
actual = actual->siguiente;
}
while (p <= numNodos){
// printf("%d.-", posicion);
printf(" Nombre: %s\n ", actual->nombre);
actual = actual->siguiente;
p++;
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarPosicionInicio (){
system("cls");
int p=1;
int posicion;
struct nodo *actual;
actual = primero;
printf ("\n Indique posicion ");
scanf("%d",&posicion);
system ("cls");
for (pos = 2; pos <=posicion; pos++){
actual = actual->siguiente;
}
//posicion = pos;
while (p <= numNodos){
//printf("%d.-", posicion);
printf(" Nombre: %s\n ", actual->nombre);
actual = actual->anterior;
p++;
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void Buscar (){
system("cls");
struct nodo *actual;
char aux [40];
int p = 1;
int encontrado =0;
actual = primero;
system("cls");
printf("\n Indique nombre a buscar ");
fflush(stdin);
gets(aux);
system("cls");
while (p <= numNodos){
if(strcmp(aux, actual->nombre)==0){
printf("\n Contacto %s EXISTE", aux);
printf("\n *** Datos del contacto ***");
printf("\n Nombre: %s", actual->nombre);
encontrado =1;
}
p++;
actual = actual->siguiente;
}
if (encontrado==0)
printf("\n %s NO EXISTE", aux);
printf("\n\n\n\n\n\n\n");
system("pause");
}
void Eliminar (){
system("cls");
struct nodo *aux;
struct nodo *actual;
int nodo_eliminar;
int x;
printf("\n Indique la posicion del nombre a eliminar ");
scanf(" %d", &nodo_eliminar);
if (nodo_eliminar > numNodos || nodo_eliminar < 1)
printf("Elemento inexistente");
if (nodo_eliminar == 1){
aux = primero;
primero = primero->siguiente;
if (primero == NULL)
ultimo = NULL;
else
primero ->anterior == NULL;
}
else if (nodo_eliminar == numNodos){
aux = ultimo;
ultimo->anterior->siguiente = NULL;
ultimo = ultimo->anterior;
}else{
actual = primero;
for (x=1; x<nodo_eliminar; ++x)
actual = actual->siguiente;
aux = actual;
actual->anterior->siguiente = actual->siguiente;
actual->siguiente->anterior = actual->anterior;
}
free(aux);
numNodos--;
}

miércoles, 28 de septiembre de 2016

Prácticas a desarrollar de Lista Circulares Doblemente Enlazadas.

Practica 1. Mediante el uso de listas circulares doblemente enlazadas realiza un Programa que devuelva la Multiplicación de los Números introducidos en los Nodos de la Lista circular.

Practica 2. Escribir un Programa que devuelva los Números Pares e Impares que se encuentran en los Nodos de una Lista.

Practica 3. Desarrollar un Programa que dada una Lista circular doblemente Enlazada ordene los Nodos en forma Ascendente.

Recursividad

La recursion o recursividad es un concepto amplio, con muchas variantes, y difícil de precisar con pocas palabras.
Un objeto recursivo es aquel que aparece en la definición de si mismo, así como el que se llama así mismo.
La recursion se puede presentar de dos maneras diferentes:
Directa:El programa o subprograma se llaman directamente a si mismo.
Indirecta: El subprograma llama a otro programa y este, en algún momento, llama nuevamente al primero.

martes, 27 de septiembre de 2016

Listas doblemente ligadas circulares

Tomar el siguiente apunte en su cuaderno para revisión el 28 de Septiembre 2016

Listas doblemente ligadas circulares

En las listas ligadas circulares, el campo liga izquierda del primer nodo de la lista apunta al ultimo y el campo liga derecha de este apunta al primero. La siguiente figura representa una estructura de este tipo:

Espacio para figura

La principal ventaja de las listas circulares es que permite la navegación en cualquier sentido a través de la misma y, además, se puede recorrer toda la lista partiendo de cualquier nodo, siempre que tengamos un apuntador a este. Sin embargo debemos destacar que es necesario establecer condiciones adecuadas para detener el recorrido de una lista y evitar caer en ciclos infinitos. Al igual que en el caso de listas simplemente ligadas circulares, se suele utilizar un nodo de cabecera.

Este nodo tendrá las características descritas anteriormente y servirá como referencia para detectar cuando se ha recorrido totalmente la lista.

Hasta este momento se han estudiado las principales características de la estructura tipo lista, considerando todas sus variantes.

Código para listas circulares simplemente enlazadas

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct listacir{
char nombre[40];
struct listacir *siguiente;
};
struct listacir *primero=NULL, *ultimo=NULL;
int numNodos;
int pos;
void insertarUltimo ();
void insertarInicio ();
void insertarIntermedio ();
void visualizar();
void visualizarDesdePosicion();
void visualizarPrimeroUltimo();
void buscar();
void eliminar();
main(){
int opcion;
do{
  system("cls");
  printf("\n\n\n");
  printf("\n************************");
  printf("\n 1. Insertar Ultimo");
  printf("\n 2. Insertar Primero");
  printf("\n 3. Insertar en X posicion");
  printf("\n 4. Visualizar");
  printf("\n 5. Visualizar desde X posicion");
  printf("\n 6. Visualizar Primero y Ultimo");
  printf("\n 7. Buscar");
  printf("\n 8. Eliminar");
  printf("\n 9. Salir");
  printf("\n****************************");
  printf("\n\n\n");
  printf("\nElija una opcion ");
  scanf("%d", &opcion);
  switch (opcion){
   case 1: insertarUltimo();
   break;
   case 2: insertarInicio();
   break;
   case 3: insertarIntermedio();
   break;
   case 4: visualizar();
   break;
   case 5: visualizarDesdePosicion();
   break;
   case 6: visualizarPrimeroUltimo();
   break;
   case 7: buscar();
   break;
   case 8: eliminar();
   break;
   case 9: printf("SALIR, GRACIAS POR ESTAR EN EL SISTEMA");
   break;
   default: system("cls");
   break;
  }
}while (opcion!= 9);
}
void insertarUltimo(){
system("cls");
struct listacir *nuevo;
nuevo=(struct listacir*)malloc(sizeof(struct listacir));
if(nuevo==NULL)
printf("\n Memoria insuficiente\n");
else{
  printf("\n Nombre: ");
  fflush(stdin);
  gets(nuevo->nombre);
  nuevo->siguiente=primero;
  if(primero==NULL)
  {
   primero=nuevo;
   ultimo=nuevo;
  }else{
   ultimo->siguiente=nuevo;
   ultimo=nuevo;
  }
}numNodos++;

}
void insertarInicio(){
system("cls");
struct listacir *nuevo;
nuevo=(struct listacir*)malloc(sizeof(struct listacir));
if(nuevo==NULL)
printf("Memoria insuficiente\n");
else{
  printf("\n Nombre: ");
  fflush(stdin);
  gets(nuevo->nombre);
  ultimo->siguiente = nuevo;
  nuevo->siguiente= primero;
  primero= nuevo;
  numNodos++;
}
}
void insertarIntermedio(){
system("cls");
struct listacir *actual;
struct listacir *nuevo;
nuevo=(struct listacir*)malloc(sizeof(struct listacir));
if (nuevo==NULL)
printf("\nMemoria insuficiente");
if(numNodos < 2)
printf(" \n Numero de nodos insuficiente");
else{
  int pos_insertar;
  printf("\n Nombre: ");
  fflush(stdin);
  gets(nuevo->nombre);
  printf("\nPosicion: ");
  scanf("%d", &pos_insertar);
  if((pos_insertar >1)&&(pos_insertar <= numNodos)){
actual=primero;
for(pos =2; pos <pos_insertar; ++pos)
actual=actual->siguiente;
nuevo->siguiente=actual->siguiente;
actual->siguiente = nuevo;
numNodos++;
} }
system("pause");
}
void visualizar(){
system("cls");
struct listacir *aux;
pos=0;
aux=primero;
while(pos< numNodos){
  printf("%d.- ", pos+1);
  printf(" %s\n", aux->nombre);
  aux= aux->siguiente;
  pos++;
}
if(numNodos==0)
printf("\nLista vacia");
printf("\n\n\n\n\n");
system("pause");
}
void visualizarPrimeroUltimo(){
system("cls");
if(numNodos==0)
printf("\nLista vacia");
else
printf("\n Primero ------> %s", primero->nombre);
printf("\n Ultimo--------_>%s", ultimo->nombre);
printf("\n\n\n\n");
system("pause");
}
void visualizarDesdePosicion(){
system("cls");
int p=1;
int posicion;
struct listacir *actual;
actual = primero;
  printf("\n Indique posicion ");
  scanf("%d", &posicion);
  system("cls");
  for (pos = 2; pos <=posicion; pos++)
  {
   actual = actual->siguiente;
}
while (p <= numNodos)
  {
  printf("%s\n", actual->nombre);
  actual = actual->siguiente;
  p++;
  }
printf("\n\n\n\n");
system("pause");
}
void buscar() {
system("cls");
struct listacir *actual;
char aux[40];
int p =1;
int encontrado=0;
actual=primero;
system("cls");
printf("\n Indique nombre a buscar   ");
fflush(stdin);
gets(aux);system("cls");
while (p <= numNodos)
{
  if(strcmp(aux, actual->nombre)==0){
   printf("\n %s EXISTE", aux);
   encontrado =1;
   }
   p++;
   actual = actual->siguiente;
}
if (encontrado==0)
  printf("\n %s NO EXISTE", aux);
  printf("\n\n\n\n\n\n\n");
system("pause");
}

void eliminar(){
system("cls");
struct listacir *aux;
struct listacir *anterior;
pos=1;
int nodo_eliminar;
aux = primero;
printf("\n Indique la posicion del nombre a eliminar ");
scanf("%d", &nodo_eliminar);
if(nodo_eliminar>numNodos || nodo_eliminar <1)
printf("Elemento inexistente");
else{
  if(nodo_eliminar==1)
  {
   aux=primero;
   primero = primero ->siguiente;
   free(aux);
   numNodos--;
  }
  else if(nodo_eliminar == numNodos)
  {
   while(pos<numNodos){
    if(pos==numNodos-1)
    anterior=aux;
    pos++;
    aux=aux->siguiente;

   }
if(pos==0)
printf("Lista vacia\n");
anterior->siguiente=primero;
ultimo=anterior;
free(aux);
numNodos--;

  }
  else{
   while(pos<=numNodos){
   if(pos == nodo_eliminar-1)
   anterior=aux;
   if(pos == nodo_eliminar)
   free(aux);
   if(pos== nodo_eliminar + 1)
   anterior->siguiente=aux;
   pos++;
   aux = aux->siguiente;
  }
  numNodos--;
}
printf("\n\n\n\n\n");
system("pause");
}
}

viernes, 23 de septiembre de 2016

Apunte

Realice el siguiente apunte para el lunes en su cuaderno.

Listas circulares

Las listas circulares son similares a las listas simplemente ligadas. sin embargo, tienen las características de que el ultimo elemento de la lista apunta al primero, en lugar de apuntar al vacío o NIL(NULL).

Se define una lista simplemente ligada circular como una colección de elementos llamados nodos, el el cual el ultimo nodo apunta al primero.

Las operaciones en listas circulares son similares a las operaciones en listas lineales; por tanto, no se trataran nuevamente en esta sección. Sin embargo, es importante señalar que para el caso de la operación de recorrido de listas circulares se necesita considerar algún criterio para detectar cuando se han visitado todos los nodos de la lista.

Esto ultimo con el propósito de evitar caer en ciclos finitos. Una posible solución al problema planteado consiste en usar un nodo extra, llamado nodo de cabecera, para indicar el inicio de la lista. este nodo contendrá información especial, de tal manera que se distinga de los demás y así poder hacer referencia al principio de la lista.

Prácticas a realizar

Agenda: En la agenda se deberá poder insertar nombre, dirección y teléfono, así como realizar todas las operaciones vistas durante las clases del tema listas doblemente enlazadas.

De la misma manera serán las practicas siguientes.

2. Inventario: Datos a insertar nombre del producto, cantidad en existencia, precio fecha de caducidad. Se deberá poder realizar todas las operaciones vistas.
3. Registro de aspirantes: Datos a insertar nombre, apellidos, edad, carrera.Se deberá poder realizar todas las operaciones vistas.

Código para listas doblemente enlazadas

//Listas doblemente enlazadas
//ITIC. Ana Francisca Martínez Betancourt
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct lista{
char nombre[40];
struct lista *siguiente;
struct lista *anterior;
};
struct lista *primero=NULL, *ultimo=NULL;
int numNodos=0;
int posicion;
//Funciones o Prototipos
void insertarInicio();
void insertarFinal();
void buscar();
void eliminar();
void visualizarInicioFin();
void visualizarFinInicio();
void insertarIntermedio();
void visualizarXfinal();
void visualizarXinicio();
void visualizarPrimerUltimo();
main (){
int opcion;
do{
  system("cls");
  printf("\n\n\n");
  printf("\n****************************************");
  printf("\n********Lista doblemente enlazada*******");
  printf("\n\n");
  printf("\n1. Insertar Datos al Inicio");
  printf("\n2. Insertar Datos al Final");
  printf("\n3. Insertar Datos en X posición");
  printf("\n4. Visualizar Lista de Inicio-Fin");
  printf("\n5. Visualizar Lista de Fin-Inicio");
  printf("\n6. Visualizar Lista de X dato al Inicio");
  printf("\n7. Visualizar Lista de X dato al Final");
  printf("\n8. Visualizar Primer y Ultimo Dato");
  printf("\n9. Buscar en Lista");
  printf("\n10. Eliminar en lista");
  printf("\n11. Salir");
  printf("\n****************************************");
  printf("\n\n");
  printf("Ingresar opcion");
  scanf("%d", &opcion);

   switch(opcion){
    case 1: insertarInicio();
    break;
    case 2:insertarFinal();
    break;
    case 3: insertarIntermedio();
    break;
    case 4: visualizarInicioFin();
    break;
    case 5: visualizarFinInicio();
    break;
    case 6: visualizarXinicio();
    break;
    case 7: visualizarXfinal();
    break;
    case 8: visualizarPrimerUltimo();
    break;
    case 9: buscar();
    break;
    case 10: eliminar();
    break;
    case 11: printf("Salir");
    break;
    default: system("cls");
    break;

   }
  }
   while (opcion !=11);
}
void insertarFinal(){
system("cls");
struct lista *nuevo;
nuevo=(struct lista*)malloc(sizeof(struct lista));
if (nuevo == NULL)
printf("\n Memoria insuficiente");
else{
  printf("\n Nombre: ");
  fflush(stdin);
  gets(nuevo->nombre);
  nuevo->siguiente=NULL;
  if (primero==NULL){
  printf("\nNo hay primer dato");
  nuevo->anterior=NULL;
  nuevo->siguiente=NULL;
  primero=nuevo;
  ultimo=nuevo;}
  else {
   nuevo->siguiente=NULL;
   nuevo->anterior=ultimo;
   ultimo->siguiente=nuevo;
   ultimo=nuevo;
  }

}numNodos++;}
void insertarInicio(){
system("cls");
struct lista *nuevo;
nuevo=(struct lista*)malloc(sizeof(struct lista));
if (nuevo == NULL)
printf("\n Memoria insuficiente");
else{
  printf("\n Nombre: ");
  fflush(stdin);
  gets(nuevo->nombre);
  nuevo->anterior=NULL;
if(ultimo==NULL){
  nuevo->siguiente=NULL;
  nuevo->anterior=NULL;
  primero=nuevo;
  ultimo=nuevo;
  }
  else{
  nuevo->anterior=NULL;
  nuevo->siguiente=primero;
  primero->anterior=nuevo;
  primero=nuevo; }}
  numNodos++;
}

void visualizarInicioFin() {
  system("cls");
  struct lista *actual;
  posicion=1;
  actual=primero;
  while(posicion<=numNodos){
   printf(" %d.- ", posicion);
   printf("%s\n",actual->nombre);
   actual=actual->siguiente;
   posicion++;
  }
  if(numNodos==0)
  printf("\nLista vacia");
  printf("\n\n\n");
  system("pause");
  }
void insertarIntermedio (){
system ("cls");
struct lista *actual, *nuevo;
nuevo=( struct lista*)malloc(sizeof( struct lista));
if (nuevo==NULL)
printf("\n MEMORIA INSUFUCIENTE\n");
if (numNodos <2)
printf ("\n Número de nodos insuficiente");
else{
  int pos_insertar;
  printf("\n Nombre:   ");
  fflush(stdin);
  gets(nuevo->nombre);
  printf ("\n Posicion: ");
  scanf ("%d", &pos_insertar);
  if((pos_insertar >1) &&(pos_insertar <= numNodos)){
   actual=primero;
   for (posicion = 2; posicion <pos_insertar; ++posicion)
   actual= actual->siguiente;
   nuevo->siguiente= actual->siguiente;
   nuevo->anterior = actual;
   actual->siguiente->anterior = nuevo;
   actual->siguiente = nuevo;
   numNodos++;
  }
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarFinInicio(){
system("cls");
struct lista *actual;
actual=ultimo;
posicion= numNodos;
while (posicion >0){
  printf(" %d.- ", posicion);
  printf("%s\n",actual->nombre);
  actual =actual->anterior;
  posicion--;
}
if(numNodos==0)
printf("\n LISTA VACIA");
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarXfinal(){
  system("cls");
int pos;
struct lista *actual;
actual = primero;
printf("\n Indique posicion     ");
scanf("%d", &pos);
system("cls");
for (posicion = 2; posicion<=pos; posicion++){
  actual = actual->siguiente;
}
while (pos <= numNodos){
  printf("%d.-", pos);
  printf("%s\n", actual->nombre);
  actual = actual->siguiente;
  pos++;
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarXinicio(){
    system("cls");
   int pos;
   struct lista *actual;
    actual = primero;
    printf ("\n Indique posicion   ");
    scanf("%d",&pos);
   system ("cls");
   for (posicion = 2; posicion <=pos; posicion++){
    actual = actual->siguiente;
}

   posicion = pos;
while (actual!= NULL){
  printf(" %d.- ", posicion);
  printf("%s\n", actual->nombre);
  actual = actual->anterior;
  posicion--;
}
printf("\n\n\n\n\n\n\n");
system("pause");
}
void visualizarPrimerUltimo(){
  system("cls");
if(numNodos==0)
  printf("\n LISTA VACIA");
else
  printf("\n PRIMERO -------> %s", primero->nombre);
  printf("\n\n ULTIMO ------>%s", ultimo->nombre);
  printf("\n\n\n\n\n\n\n");
   system ("pause");
}
void buscar(){
  system("cls");
struct lista *actual;
char aux [40];
int p = 1;
int encontrado =0;
actual = primero;
system("cls");
printf("\n Indique nombre a buscar ");
fflush(stdin);
gets(aux);
system("cls");
while (p <= numNodos){
  if(strcmp(aux, actual->nombre)==0){
   printf("\n %s EXISTE", aux);
   encontrado =1;
   }
   p++;
   actual = actual->siguiente;
}
if (encontrado==0)
  printf("\n %s NO EXISTE", aux);
  printf("\n\n\n\n\n\n\n");
system("pause");
}
void eliminar(){
system("cls");
struct lista *aux;
struct lista *actual;
int nodo_eliminar;
int x;
printf("\n Indique la posicion del nombre a eliminar ");
scanf(" %d", &nodo_eliminar);
if (nodo_eliminar > numNodos || nodo_eliminar < 1)
printf("Elemento inexistente");
if (nodo_eliminar == 1){
  aux = primero;
  primero = primero->siguiente;
  if (primero == NULL)
  ultimo = NULL;
  else
  primero ->anterior == NULL;
   }
   else if (nodo_eliminar == numNodos){
    aux = ultimo;
    ultimo->anterior->siguiente = NULL;
    ultimo = ultimo->anterior;
   }else{
    actual = primero;
    for (x=1; x<nodo_eliminar; ++x)
    actual = actual->siguiente;
    aux = actual;
    actual->anterior->siguiente = actual->siguiente;
    actual->siguiente->anterior = actual->anterior;
   }
free(aux);
numNodos--;
}