[C ANSI] TAS (PRIORITY QUEUE)

#include <stdio.h>
#include <stdlib.h>

void swap(int *v1, int *v2){
  int v3 = *v1;
  *v1 = *v2;
  *v2 = v3;
}

int to_2_exp(int i){
  if (i==0) return 0;
  if (i==1) return 1;
  return 2 * to_2_exp( i / 2);
}

int ln2(int i){
  if (i==0) return 0;
  if (i==1) return 1;
  return 1 + to_2_exp( i / 2);
}

void spaces(int n){
  int i;
  for (i=0; i<n; i++) putchar(' ');
}

typedef int * tas;

tas new_tas(size_t s){
  return malloc(s * sizeof(int));
}

void fixup(tas t, size_t n){
  if (n == 0) return;
  else{
    int n2 = (n-1)/2;
    if (t[n] > t[n2]){
      swap(&t[n], &t[n2]);
      fixup(t, n2);
    }
  }
}

void fixdown(tas t, size_t n, size_t max){
  int n2 = n*2+1;
  if (n2 >= max) return;
  if (n2 + 1 < max && t[n2+1] > t[n2] ) n2++;
  if (t[n] < t[n2]){
    swap(&t[n], &t[n2]);
    fixdown(t, n2, max);
  }
}

void draw_tas(tas t, size_t n){
  int i;
  int k = 1;
  int k_max = to_2_exp(n);
  int v;
  for (i=0; i<n; i++){
    if (i == k - 1){
      k *= 2;
      if (i) putchar('\n');
      v = 2* (k_max * 2 / k ) - 1;
      spaces(v);
    }
    printf("%2d", t[i]);
    spaces(2 * v);

  }
  putchar('\n');
}

size_t add_tas(tas t, int value, size_t n){
  t[n] = value;
  fixup(t, n);
  return n+1;
}

size_t pop_tas(tas t, size_t n){
  t[0] = t[--n];
  fixdown(t, 0, n);
  return n;
}


int main(){
  /* exemple d'utilisation d'un tas */
  int s = 0;
  tas t = new_tas(15);

  add_tas(t, 12, s++);
  add_tas(t, 24, s++);
  add_tas(t, 48, s++);

  add_tas(t, 15, s++);
  add_tas(t, 23, s++);
  add_tas(t, 49, s++);

  add_tas(t, 19, s++);
  add_tas(t, 54, s++);
  add_tas(t, 29, s++);

  add_tas(t, 18, s++);
  add_tas(t, 53, s++);
  add_tas(t, 92, s++);

  add_tas(t, 90, s++);
  add_tas(t, 64, s++);
  add_tas(t, 22, s++);


  draw_tas(t, s);
  s = pop_tas(t, s);
  s = pop_tas(t, s);
  draw_tas(t, s);
  free(t);
  return 0;
}

07 novembre 2008 04:01:53 :

correction