Cola de Prioridad de enteros en C

Cola de Prioridad de enteros en C

Una cola de prioridad es una estructura de datos lineal en la que los elementos se antienden en el orden indicado por una prioridad asociada a cada uno de los elementos.

Es otra de las prácticas que era necesario implementar durante la carrera para superar la asignatura de estructura de datos. Aún la conservo y he querido compartirla con vosotros. Podéis descargarla libremente desde mi repositorio en github.

Declaración de las cabeceras de las funciones y procedimentos de la estructura de datos

#ifndef CPRE_int_H
#define CPRE_int_H

#define MAXpri 5   //Tamanio max del array de prioridades

struct cprie_int_typo {   //Tipo base de la cola con prioridad
  int info;
};


typedef struct cprie_int_rep *cprie_int;

cprie_int cprie_int_nuev(void);
int cprie_int_vacia(cprie_int cprie);
void cprie_int_mete(cprie_int cprie,struct cprie_int_typo *e,int prior);
void cprie_int_saca(cprie_int cprie,struct cprie_int_typo *e);
void cprie_int_dest(cprie_int *cprie);

#endif

Implementación de cada una de las funciones y procedimientos

Continuamos el desarrollo de ésta estructura de datos con la implementación de cada una de las funciones y procedimientos.

#include <stdio.h>
#include <stdlib.h>
#include "CPRE_INT.H"


struct cprie_int_nodo {
  struct cprie_int_typo val;
  struct cprie_int_nodo *sig;
};

struct cprie_int_cab {
  struct cprie_int_nodo *p;
  struct cprie_int_nodo *u;
};

struct cprie_int_rep {
  struct cprie_int_cab arrpri[MAXpri];
};


//---------------------------- PRIMITIVAS PUBLICAS ----------------

cprie_int cprie_int_nuev(void) {

  cprie_int cprie;
  int i;

  cprie=(struct cprie_int_rep *) malloc (sizeof (struct cprie_int_rep));
  if (!cprie) {
     fprintf(stderr,"cprie_int_nuev : no hay memoria.\n");
     exit(1);
  }
  for (i=0;i<MAXpri;i++){
     cprie->arrpri[i].p=cprie->arrpri[i].u=NULL;
  }

}

//------------------------------------------------------------------

int cprie_int_vacia(cprie_int cprie) {

  int i;
  int vacia;

  if (!cprie) {
     fprintf(stderr,"cprie_int_vacia : la cola con prioridad no existe.\n");
     exit(2);
  }
  vacia=1;
  i=0;
  while ((i<MAXpri) &amp;&amp; (vacia)) {
     if (cprie->arrpri[i].p) vacia=0;
     else i++;
  }
  return(vacia);

}

//------------------------------------------------------------------

void cprie_int_mete(cprie_int cprie,struct cprie_int_typo *e,int prior) {

  struct cprie_int_nodo *nuevo;

  if (!cprie) {
     fprintf(stderr,"cprie_int_mete : la cola con prioridad no existe.\n");
     exit(2);
  }
  if ((prior<0) || (prior>=MAXpri)) {
     fprintf(stderr,"cprie_int_mete : prioridad fuera de rango.\n");
     exit(3);
  }

  nuevo=(struct cprie_int_nodo *) malloc(sizeof(struct cprie_int_nodo));
  if(!nuevo){
     fprintf(stderr,"cprie_int_mete : no hay memoria.\n");
     exit(1);
  }
  nuevo->val=*e;
  nuevo->sig=NULL;
  //Si no vacia
  if (cprie->arrpri[prior].p)
     cprie->arrpri[prior].u=cprie->arrpri[prior].u->sig=nuevo;
  else
     cprie->arrpri[prior].u=cprie->arrpri[prior].p=nuevo;

}

//------------------------------------------------------------------

void cprie_int_saca(cprie_int cprie,struct cprie_int_typo *e) {

  struct cprie_int_nodo *viejo;
  int i;
  int vacia;


  if (!cprie) {
     fprintf(stderr,"cprie_int_saca : la cola con prioridad no existe.\n");
     exit(2);
  }
  vacia=1;
  i=0;
  while ((i<MAXpri) &amp;&amp; (vacia)) {
     if (cprie->arrpri[i].p) {
        vacia=0;
        viejo=cprie->arrpri[i].p;
        *e=cprie->arrpri[i].p->val;
        //Solo hay un elemento
        if(cprie->arrpri[i].p==cprie->arrpri[i].u)
           cprie->arrpri[i].p=cprie->arrpri[i].u=NULL;
        //Hay mas de uno
        else cprie->arrpri[i].p=viejo->sig;
        free (viejo);
     }
     else i++;
  }
  if (vacia) {
     fprintf(stderr,"cprie_int_saca : la cola con prioridad esta vacia.\n");
     exit(4);
  }

}

//------------------------------------------------------------------

void cprie_int_dest(cprie_int *cprie) {

  struct cprie_int_nodo *aux,*viejo;
  int i;

  if (!cprie) {
     fprintf(stderr,"cprie_int_dest : la cola con prioridad no existe.\n");
     exit(2);
  }
  for (i=0;i<MAXpri;i++) {
     aux=(*cprie)->arrpri[i].p;
     while(aux) {
         viejo=aux;
         aux=aux->sig;
         free(viejo);
     }
  }
  free(*cprie);
  *cprie=NULL;

}

Programa de prueba

Para terminar, voy a dejaros un programa de prueba en el que verificar que cada una de las funciones y procedimientos de ésta estructura de datos.

#include "CPRE_INT.H"

int main(void) {

  cprie_int a;
  struct cprie_int_typo x;

  clrscr();

  printf("\nCreando cola con prioridad");
  a=cprie_int_nuev();
  if (cprie_int_vacia(a)) printf("\ncola VACIA");
  else printf("\ncola NO VACIA");

  x.info=2;
  cprie_int_mete(a,&amp;x,1);
  x.info=5;
  cprie_int_mete(a,&amp;x,1);
  x.info=3;
  cprie_int_mete(a,&amp;x,0);

  cprie_int_saca(a,&amp;x);
  printf("\nElemento sacado: %d",x.info);

  cprie_int_saca(a,&amp;x);
  printf("\nElemento sacado: %d",x.info);

  cprie_int_saca(a,&amp;x);
  printf("\nElemento sacado: %d",x.info);

  if (cprie_int_vacia(a)) printf("\ncola VACIA");
  else printf("\ncola NO VACIA");
  cprie_int_dest(&amp;a);

}

Conclusión

Os dejo, como siempre, la sección de comentarios abierta para que podáis dejarme vuestras aportaciones, comentarios o códigos alternativos. De esta manera podemos aprender todos.

No Comments

Post a Comment