Clasele 9-10 lecția 4 - 23 oct 2015
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: