Clasele 9-10 lecția 4 - 23 oct 2015

From Algopedia
Revision as of 14:46, 31 October 2015 by Dan (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Prima oră

Liste simplu înlănțuite

Reprezentare în memoria calculatorului

struct Node {
  int head; // valoare
  Node* tail; // urmator
};

Alocare dinamică a memoriei cu prealocare

Atunci când trebuie să alocăm dinamic memorie puțină de foarte multe ori, folosirea frecventă a instrucțiunii new duce la consum suplimentar de timp și memorie, deoarece instrucțiunea new face apel la funcțiile sistemului de operare de gestionare a memoriei.

Într-o astfel de situație, ne putem ocupa noi înșine de gestionarea memoriei astfel:

const int ALLOC_SIZE = 1 << 16;

Node* start;
int size = ALLOC_SIZE;
std::vector<Node*> addresses;

void prealloc(int noNodes) {
  start = new Node[noNodes];
  size = 0;
  addresses.push_back(start);
}

Node* newNode() {
  if (size == ALLOC_SIZE) {
    prealloc(ALLOC_SIZE);
  }
  return &start[size++];
}

void myDelete() {
  int i;
  for (i = 0; i < (int)addresses.size(); ++i)
    delete[] addresses[i];
}

Mai departe putem apela funcția newNode() în loc să folosim instrucțiunea new Node. De asemenea, va trebui să apelăm funcția myDelete() la finalul execuției programului.

Lista vidă (care nu conține niciun element)

Node* emptyList() {
  return NULL;
}

Test dacă o listă este vidă

bool isEmpty(Node* list) {
  return list == NULL;
}

Adăugarea unei valori la începutul unei liste

Node* prepend(int value, Node* list) {
  Node* tmp = newNode();
  tmp->head = value;
  tmp->tail = list;
  return tmp;
}

Afișarea unei liste pe ecran

void printList(Node* list) {
  if (!isEmpty(list)) {
    printf("%d ", list->head);
    printList(list->tail);
  }
}

Suma elementelor unei liste

Cu acumulator și cu mai puțin consum de memorie (optimizată de compilator):

// Spațiu: (2*pointeri+intreg)
int sumList1(Node* list, int sum = 0) {
  if (!isEmpty(list)) {
    return sumList1(list->tail, sum + list->head);
  } else {
    return sum;
  }
}

Fără acumulator și cu un consum mai mare de memorie (neoptimizată de compilator):

// Spațiu: 2*pointeri*dimensiuneaListei
int sumList2(Node* list) {
  if (isEmpty(list)) {
    return 0;
  } else {
    return list->head + sumList2(list->tail);
  }
}

Ștergerea unei liste

// Spațiu: 3*pointer
void eraseList(Node* list) {
  if (!isEmpty(list)) {
    Node* tail = list->tail;
    delete list;
    eraseList(tail);
  }
}

Testarea funcțiilor

int main(void) {
  int i;
  int val;
  int N;

  // citirea datelor
  Node* list = emptyList();
  scanf("%d", &N);
  for (i = 0; i < N; ++i) {
    scanf("%d", &val);
    list = prepend(val, list);
  }

  // afisarea solutiei
  printList(list);
  printf("\n");
  printf("%d\n", sumList1(list));
  printf("%d\n", sumList2(list));
  myDelete();

  return 0;
}

A doua oră

Trie

Trie-ul este o structură de date care permite stocarea și interogarea unui dicționar de cuvinte. Inițial, o structură trie nu conține nicun cuvânt. Operațiile care se pot efectua asupra unui trie sunt:

  • inserarea unui cuvânt;
  • ștergerea unui cuvânt;
  • căutarea unui cuvânt.

Reprezentarea în memorie a unui trie

Un trie va fi reprezentat în memorie sub forma unui arbore ale cărui noduri vor avea un număr finit de fii etichetați, câte unul pentru fiecare literă din alfabetul cuvintelor care se indexează.

Spunem că un cuvânt se află într-un trie dacă și numai dacă există un drum care pornește din rădăcină și merge din fiu în fiu, pe muchiile corespunzătoare literelor cuvântului.

Un nod al arborelui va fi sotcat astfel:

const int SIGMA = 3; // {a, b, c}
const char FIRST_LETTER = 'a';

class TrieNode { // nod al trie-ului
private:
  TrieNode* next[SIGMA];
  int contor;

public:
  void insert(char* word);
  int query(char* word);
  bool erase(char* word);
};

Inserarea unui cuvânt în trie

Un cuvânt nou se va insera în trie prin crearea drumului său, dacă nu există.

void TrieNode::insert(char* word) {
  if (*word == 0) {
    this->contor++;
  } else {
    if (this->next[*word - FIRST_LETTER] == NULL) {
      this->next[*word - FIRST_LETTER] = new TrieNode;
    }
    this->next[*word - FIRST_LETTER]->insert(word + 1);
  }
}

Căutarea unui cuvânt în trie

Un cuvânt va fi căutat în heap verificând dacă se poate parcurge drumul său.

int TrieNode::query(char* word) {
  if (*word == 0) {
    return this->contor;
  } else {
    if (this->next[*word - FIRST_LETTER] == NULL) {
      return 0;
    } else {
      return this->next[*word - FIRST_LETTER]->query(word + 1);
    }
  }
}

Ștergerea unui cuvânt din trie

Un cuvânt va fi șters din trie ștergând toate nodurile de pe drumul corespunzător cuvântului cu condiția ca acestea să nu fie folosite de alte drumuri, corespunzătoare altor cuvinte din trie.

bool TrieNode::erase(char* word) {
  if (*word == 0) {
    if (this->contor == 0) {
      return false;
    } else {
      this->contor--;
      return true;
    }
  } else {
    if (this->next[*word - FIRST_LETTER] == NULL) {
      return false;
    } else {
      bool answer = this->next[*word - FIRST_LETTER]->erase(word + 1);
      if (answer) {
        TrieNode* mySon = this->next[*word - FIRST_LETTER];
        bool toDelete = mySon->contor == 0;
        for (int i = 0; i < SIGMA; i++) {
          toDelete &= mySon->next[i] == NULL;
        }
        if (toDelete) {
          delete mySon;
          this->next[*word - FIRST_LETTER] = NULL;
        }
      }
    }
  }
}

Stocarea rădăcinii

Rădăcina unui trie poate fi stocată într-o altă clasă și toate operațiile pot fi apelate de acolo:

class Trie {
private:
  TrieNode* root;

public:
  Trie() {
    this->root = new TrieNode;
  }

  void insert(char* word) {
    this->root->insert(word);
  }

  int query(char* word) {
    return this->root->query(word);
  }

  bool erase(char* word) {
    return this->root->erase(word);
  }
};

Temă

Pentru data viitoare veți avea de rezolvat următoarele 3 probleme: