Vissza

Labor 9

A  Kupac -Heap adatstruktúra


1. Készítsünk egy kupac programmodult. A modul tesztelésére egy állományban levő valós számokkal töltsünk fel egy kupacot, majd írjuk ki csökkenő sorrendbe egy másik állományba a számokat. Használjuk az alábbi típus és függvény definiciókat.

Kupac animáció
teljes feladat

#ifndef _HEAP_H
#define _HEAP_H

#define SWAP( T, a, b ){ T c = a; a = b; b = c; } // ket kupacbeli elem kicserelesere

typedef void * TYPE;
struct Heap{
    TYPE * x;
    int max; //a kupac kapacitasa
    int n; //a kupac aktualis elem szama
};
typedef struct Heap * HEAPPTR;

HEAPPTR create( int max ); //memoriahely foglalas
void destroy( HEAPPTR ); //memoriahely felszabaditas
void insert( HEAPPTR, TYPE ); //uj elemet szur be a kupacba
TYPE getmin( HEAPPTR ); // kiveszi a kupacbol a legkisebb elemet es visszateriti
void down( HEAPPTR ); //kivetel utan visszaalitja a kupac tulajdonsagot
void up( HEAPPTR );  //beszuras utan visszaalitja a kupac tulajdonsagot

#endif
   
Megjegyzés: az alábbi forráskód 10 darab egész számmal tölt fel egy kupacot és kiírja növekvő sorrendbe a képernyőre a számokat:

#include "Heap.h"
#include <stdio.h>

main(){
   int a[]={9, 45, 1, 6, -9, 19, -1, 21, 8, 3};
   int i;
   int m = sizeof( a )/sizeof( a[0] );
   HEAPPTR h = create( m );
   for( i=0; i<m; i++ )
       insert( h, &a[i] );
   for( i=0; i<m; i++ )
       printf("%d\t", *(int *)getmin(h));
   destroy( h );
   printf("\n");
   return 0;
}