Clasa a IX-a lecția 26 - 24 mai 2020
Clasament teme lecțiile 1 - 25
Pe categorii
Divizori / Primalitate / Ciur
Sortări
Matrici
Căutare binară
Stivă
Recursivitate
Parcurgeri matrice
Divide et Impera
Programare dinamică
Backtracking
Generale
Concursuri
Lecție
Liste înlănțuite
Definiție
O listă înlănțuită este o structură de date care reprezintă o înlănțuire secvențială de noduri. Fiecare nod este format dintr-un element (care conține date, poate fi un număr natural, un caracter, etc.) și o referință către următorul nod din listă. Lista înlănțuită permite inserarea și ștergerea eficientă a elementelor de pe orice poziție.
Implementare
Sunt mai multe moduri de a implementa o listă. Să luăm ca exemplu o listă care este formată din elemente numere întregi. Vom citi elementele într-un vector V. Inițial, lista conține toate elementele, iar după fiecare element V[i] în listă, urmează elementul V[i + 1]. Deci, ne putem declara un vector auxiliar NEXT, unde NEXT[i] = j reprezintă că elementul V[j] este următorul dupa V[i] în listă. Evident, ultimul element din listă nu are un succesor, deci îi putem da o valoare terminală/invalidă (-1 de exemplu).
Crearea listei din citirea unui vector
scanf("%d", &n);
for (i = 0; i < n; ++i) {
scanf("%d", &v[i]);
next[i] = i + 1;
}
next[n - 1] = -1; // marcam ca este ultimul element din lista
Citim un vector și creăm o structură de tip listă care ține valorile din vectorul citit.
Afișarea listei
i = 0;
while (i != -1) { // cat timp nu am ajuns la o pozitie terminala
printf("%d ", v[i]); // afisam elementul
i = next[i]; // mutam cursorul la urmatorul element
}
Afișăm elementele din listă. Se observă că în vectorul next reținem pozițiile din vector care fac parte din listă, vectorul v conținând valorile efective.
Ștergere element din listă după poziție
Vrem să ștergem din listă elementul care se află după elementul de la poziția i.
if (next[i] != -1) // daca avem ceva dupa elementul i
next[i] = next[next[i]]; // luam ce avem in dreapta acelui element
Afișarea elementului de pe pozitia k
Spre deosebire de un vector, unde avem acces direct la poziția k prin V[k], într-o listă suntem nevoiți să parcurgem elementele.
i = 0; // Setam pozitia de start ca fiind primul element din lista
for (j = 1; j < k; ++j) // Avansam de k-1 ori
i = next[i];
printf("%d", v[i]);
Atenție În codul de mai sus, nu am verificat dacă nu cumva lista noastră are mai puțin de k elemente. Puteam verifica acest lucru asigurându-ne că nu ajungem niciodată cu valoarea lui i pe nodul terminal, -1. Acest lucru este însă ineficient, pentru că adăugăm o operație în plus, o întrebare la fiecare pas din parcurgere. Este mai eficient să reținem numărul de elemente din listă și să ne asigurăm că îl actualizăm de fiecare dată când este cazul. Vom compara k cu acel număr o singură dată, fiind astfel eficienți.
Aplicație
Enunț
Sursă IQAcademy
n copii numerotați de la 1 la n și așezați în cerc numără la v-ați ascunselea, din k în k, începând cu copilul 1. Date n și k să se afișeze ordinea în care ies copiii din cerc.
Rezolvare
Problema are multe modalități de abordare. Folosind vectori simpli, putem să ne jucăm cu diverse parcurgeri/eliminări ale elementelor și vom ajunge în majoritatea cazurilor la o complexitate O(N2). Soluțiile sunt prezentate foarte fain aici. Voi prezenta soluția care folosește liste. Aceasta este, întâmplător și cea mai eficientă, având o complexitate egală cu O(N * K).
Ideea este simplă: la fiecare pas, luăm cel de-al k-lea element, îl ștergem din listă și repetăm procedeul.
#include <stdio.h>
int v[100], next[100];
int main() {
int n, k, i, j, pos;
scanf("%d%d", &n, &k);
// initializam lista
for (i = 0; i < n; ++i) {
v[i] = i + 1;
next[i] = (i + 1) % n; // copiii sunt asezati in cerc, copilul din dreapta ultimului este primul
}
pos = n - 1; // pos e pozitia copilului din-nainte de copilul de eliminat
for (i = 0; i < n; ++i) {
// avanseaza k - 1 elemente deoarece eliminarea conteaza ca un element
for (j = 1; j < k; ++j)
pos = next[pos];
printf("%d ", v[next[pos]]);
next[pos] = next[next[pos]];
}
printf("\n");
return 0;
}
Union-find
Enunț
Avem N valori distincte de la 0 la N - 1, fiecare valoare făcând parte din "submulțimea ei". Se dau două tipuri de operații:
- Unifică submulțimile valorilor i și j. (union)
- Fac valorile i și j parte din aceeași submulțime? (find)
Rezolvare
Ideea #1
Vom reține un vector m[i] = indicatorul unic al mulțimii din care face parte valoarea i. Avem astfel:
Operația find
int find(int i) {
return m[i];
}
Funcția find ne întoarce chiar indicatorul mulțimii. Avem complexitate O(1).
Operația union
void union(int i, int j) {
int mj = m[j]; // retinem multimea din care face parte j
for (int k = 0; k < N; ++k) // parcurgem toate valorile
if (m[k] == mj) // daca dam de un element care face parte din multimea lui j
m[k] = m[i]; // il setam sa faca parte din multimea lui i
}
Avem complexitate O(N).
Ideea #2 - Optimizare union
Vom reține pentru fiecare valoare i, care este șeful suprem acesteia (sau dacă preferați termeni de corporație, managerul). Inițial, fiecare valoare i se are pe ea însăși pe post de manager. În momentul în care vrem să facem union între două valori, vom găsi șefii acestora, și vom seta șeful unuia dintre ei ca fiind celălalt. Implementarea arată cam așa:
Operația find
int find(int i) {
if (sef[i] == i) // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
return i; // il returnam
return find(sef[i]); // altfel returnam seful sefului meu
}
Se observă că de data aceasta, pe cel mai rău caz, funcția find poate face N operații, deci are complexitate O(N)
Operația union
void union(int i, int j) {
int sefi, sefj;
sefi = find(i); // seful suprem al lui i
sefj = find(j); // seful suprem al lui j
sef[sefj] = sefi; // seful suprem al lui sefj devine sefi
}
Funcția union apelează de două ori find și mai face încă o operație. Chiar dacă find este o funcție lentă, putem considera că union este optimizată, pentru că am scăpat de acea parcurgere de complexitate N.
Ideea #3 - Optimizare find
O optimizare foarte importantă pentru funcția find pleacă de la observația că atunci când vrem să găsim șeful suprem al valorii i, noi trecem prin mai mulți șefi, șefi ai cărui șef suprem este egal cu cel al valorii i. Astfel, putem să actualizăm șefii acestor șefi în timpul parcurgerii recursive:
int find(int i) {
if (sef[i] == i) // daca seful meu sunt eu, inseamna ca eu sunt seful suprem
return i; // il returnam
return sef[i] = find(sef[i]); // altfel legam i la seful suprem, pe care il si returnam
}
Astfel ajungem la o complexitate de O(logN) atât pe find, cât și pe union, unde logN este adâncimea arborelui de manageri.
(Opțional) Ideea #4 - Optimizare union #2
Putem optimiza și mai mult algoritmul, având grijă ca în momentul în care vrem să unim două mulțimi să alegem corespunzător care șef devine subordonat celuilalt. Altfel spus, trebuie să alegem cum trebuie dacă șeful lui i devine seful șefului lui j sau viceversa. Pentru aceasta, trebuie să reținem pentru fiecare mulțime numărul elementelor ale acesteia, iar atunci când împreunăm două mulțimi, vom atașa mulțimea mică la mulțimea mare.
Temă
zigzag - varena Aplicație la liste
lacoada - varena Aplicație la liste