Note de curs, probleme algoritmică, clasa IX/X, 16 ianuarie 2015
From Algopedia
Jump to navigationJump to search
Î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; }