Note de curs, probleme algoritmică, clasa IX/X, 16 ianuarie 2015

În acest curs am implementat operațiile clasice pe trei dintre structurile de date elementare: stiva, coada și heap-ul folosind paradigma programării funcționale.

Stiva

Să se implementeze o stivă, cu operațiile emptyStack, isEmpty, push, peek, pop și reverse.

#include <cstdio>
#include <cstdlib>
#include <cassert>

class Stack {
public:
  const int data;
  const Stack* previous;

  Stack(const int data, const Stack* previous) :
    data(data),
    previous(previous) {
  }
};

const Stack* const emptyStack() {
  return NULL;
}

bool isEmpty(const Stack* const stack) {
  return stack == emptyStack();
}

const Stack* const push(const Stack* const stack, int val) {
  return new Stack(val, stack); // ok
}

int peek(const Stack* const stack) {
  return stack->data;
}

const Stack* const pop(const Stack* const stack) {
  return stack->previous;
}

const Stack* const reverse(const Stack* const stack,
      const Stack* const answer = emptyStack()) {
  if (isEmpty(stack))
    return answer;
  else
    return reverse(stack->previous, push(answer, stack->data));
}

Coada

Să se implementeze o coadă, cu operațiile emptyQueue, isEmpty, push, pop și peek.

class Queue {
public:
  const Stack* const first;
  const Stack* const second;

  Queue(const Stack* const first, const Stack* const second) :
    first(first),
    second(second) {
    ;
  }
};

const Queue* const emptyQueue() {
  return new Queue(emptyStack(), emptyStack());
}

bool isEmpty(const Queue* const queue) {
  return queue == emptyQueue();
}

const Queue* const push(const Queue* const queue, int val) {
  return new Queue(push(queue->first,val), queue->second);
}

const Queue* const pop(const Queue* const queue) {
  if (isEmpty(queue->second))
    return new Queue(emptyStack(), pop(reverse(queue->first)));
  else
    return new Queue(queue->first, pop(queue->second));
}

int peek(const Queue* const queue) {
  if (isEmpty(queue->second))
    return peek(reverse(queue->first));
  else
    return queue->second->data;
}

Heap-ul

Să se implementeze operațiile: emptyHeap, isEmpty, push, peek și pop într-un Min Heap.

class Heap {
public:
  int data;
  const Heap* const left;
  const Heap* const right;

  Heap(int data, const Heap* const left, const Heap* const right) :
    data(data),
    left(left),
    right(right) {
    ;
  }
};

const Heap* const emptyHeap() {
  return NULL;
}

bool isEmpty(const Heap* const heap) {
  return heap == emptyHeap();
}

const Heap* const push(const Heap* const heap, int val) {
  if (isEmpty(heap)) {
    return new Heap(val, emptyHeap(), emptyHeap());
  } else if (heap->data < val) {
    if (rand() % 2 == 0)
      return new Heap(heap->data, heap->left, push(heap->right, val));
    else
      return new Heap(heap->data, push(heap->left, val), heap->right);
  } else { // val < heap->data
    if (rand() % 2 == 0)
      return new Heap(val, heap->left, push(heap->right, heap->data));
    else
      return new Heap(val, push(heap->left, heap->data), heap->right);
  }
}

int peek(const Heap* const heap) {
  return heap->data;
}

const Heap* const pop(const Heap* const heap) {
  assert(!isEmpty(heap));
  if (isEmpty(heap->left) && isEmpty(heap->right))
    return emptyHeap();
  else if (isEmpty(heap->right))
    return heap->left;
  else if (isEmpty(heap->left))
    return heap->right;
  else if (heap->left->data < heap->right->data)
    return new Heap(heap->left->data, pop(heap->left), heap->right);
  else // heap->right->data < heap->left->data
    return new Heap(heap->right->data, heap->left, pop(heap->right));
}

Testarea implementării

Să se testeze structurile de date implementate anterior.

int main() {
  printf("Stack: ");
  const Stack* const s1 = emptyStack();
  const Stack* const s2 = push(s1, 1);
  printf("%d ", peek(s2));
  const Stack* const s3 = push(s2, 2);
  printf("%d ", peek(s3));
  const Stack* const s4 = push(s3, 3);
  printf("%d ", peek(s4));
  const Stack* const s5 = pop(s4);
  printf("%d ", peek(s5));
  const Stack* const s6 = pop(s5);
  printf("%d ", peek(s6));
  const Stack* const s7 = push(s6, 4);
  printf("%d ", peek(s7));
  const Stack* const s8 = push(s7, 5);
  printf("%d ", peek(s8));
  const Stack* const s9 = pop(s8);
  printf("%d ", peek(s9));
  const Stack* const s10 = pop(s9);
  printf("%d\n", peek(s10));

  printf("Queue: ");
  const Queue* const q1 = emptyQueue();
  const Queue* const q2 = push(q1, 1);
  printf("%d ", peek(q2));
  const Queue* const q3 = push(q2, 2);
  printf("%d ", peek(q3));
  const Queue* const q4 = push(q3, 3);
  printf("%d ", peek(q4));
  const Queue* const q5 = pop(q4);
  printf("%d ", peek(q5));
  const Queue* const q6 = pop(q5);
  printf("%d ", peek(q6));
  const Queue* const q7 = push(q6, 4);
  printf("%d ", peek(q7));
  const Queue* const q8 = push(q7, 5);
  printf("%d ", peek(q8));
  const Queue* const q9 = pop(q8);
  printf("%d ", peek(q9));
  const Queue* const q10 = pop(q9);
  printf("%d\n", peek(q10));

  printf("Heap: ");
  const Heap* const h1 = emptyHeap();
  const Heap* const h2 = push(h1, 6);
  printf("%d ", peek(h2));
  const Heap* const h3 = push(h2, 4);
  printf("%d ", peek(h3));
  const Heap* const h4 = push(h3, 8);
  printf("%d ", peek(h4));
  const Heap* const h5 = pop(h4);
  printf("%d ", peek(h5));
  const Heap* const h6 = pop(h5);
  printf("%d ", peek(h6));
  const Heap* const h7 = push(h6, 7);
  printf("%d ", peek(h7));
  const Heap* const h8 = push(h7, 5);
  printf("%d ", peek(h8));
  const Heap* const h9 = pop(h8);
  printf("%d ", peek(h9));
  const Heap* const h10 = pop(h9);
  printf("%d\n", peek(h10));
  return 0;
}