SDA Lucrarea 3
În acest laborator se vor implementa secvențe cu vectori și liste simplu și dublu înlănțuite.
Secvența (lista abstractă - Sequence)
Secvența este o structură de date abstractă care stochează datele sub forma unui șir de elemente de același fel.
Secvența are următoarele proprietăți:
- Datele sunt stocate într-o anumită ordine (se poate spune că un element este plasat înaintea sau după un alt element în structură).
- Numărul de elemente ce poate fi stocat de structură este nelimitat (a nu se confunda cu infinit, există întotdeauna limita dată de memoria disponibilă).
- Elementele stocate în secvență sunt de același fel.
Secvența suportă următoarele operații de bază:
- Interogarea numărului de elemente din secvență.
- Inserția unui element pe o anumită poziție în secvență.
- Ștergerea unui element de pe o anumită poziție din secvență.
- Căutarea unui element în secvență (căutare care va întoarce primul index pe care apare elementul în structură).
- Accesarea unui element de pe o anumită poziție.
- Dacă există o relație de ordine pe mulțimea din care fac parte elementele, se poate defini operația de sortare a secevenței care implică mutarea elementelor pe alte poziții, astfel încât un element considerat mai mic după relația de ordine folosită să fie plasat înaintea oricărui element considerat mai mare.
Implementarea secvenței cu vectori
În cazul implementării cu vectori, elementele sunt plasate într-un vector de dimensiune fixă și cunoscută. Din cauza faptului că secvența are dimensiune nelimitată, se cere ca vectorii să suporte redimensionarea dinamică pentru a acomoda elemente suplimentare în momentul când se umplu. Astfel, suntem obligați ca pentru implementarea secvențelor să folosim alocare dinamică de memorie, iar tipul de date care poate fi folosit pentru stocarea adreselor alocate este pointerul. Totuși cunoaștem din lecțiile anterioare faptul că o variabilă de tip pointer nu memorează decât o adresă de start a zonei de memorie alocată, nu și dimensiunea ei. Prin urmare vom defini o clasa numită sda::vector
care va stoca adresa de start dar și dimensiunea zonei alocate. Mai jos este un exemplu de secvență de elemente de tip arbitrar T:
namespace sda {
template <class T>
class vector {
/** Pointer la zona de memorie alocata. */
T * array;
/** Dimensiunea zonei alocate. */
uint32_t capacity;
};
}
În plus față de câmpurile de mai sus, structura sda::vector
trebuie să memoreze și numărul de elemente valide din secvență. Motivul fiind acela că inițial, chiar dacă vectorul este alocat și are o capacitate ne-nulă, el nu conține de fapt nici un element. Astfel introducem un nou câmp: count
, care reprezintă numărul de elemente din secvență, și care este inițial 0:
namespace sda {
template <class T>
class vector {
/** Pointer la zona de memorie alocata. */
T * array;
/** Dimensiunea zonei alocate. */
uint32_t capacity;
/** Numarul de elemente valide din secventa (initial 0). */
uint32_t count;
};
}
Crearea unui sda::vector
Pentru crearea unei secvențe noi, se definesc doi constructori:
/**
* Constructorul aloca memorie si creeaza un nou vector cu o capacitate initiala de 10 elemente.
*/
vector();
/**
* Constructorul aloca memorie si creeaza un nou vector cu o capacitate initiala.
* @param initialCapacity capacitatea initiala a secventei.
*/
vector(uint32_t initialCapacity);
Implementarea acestor constructori se face folosind următorul algoritm:
- Se inițializează
capacity
cu valoarea dininitialCapacity
(sau 10, în funcție de constructor). - Se inițializează
count
cu 0. - Se alocă memorie pentru un vector de
initialCapacity
elemente iar adresa alocată se memorează înarray
.
Analiza complexității: Singura operație care depinde de valoarea capacitatea vectorului este alocarea de memorie. Această alocare durează la fel de mult, indiferent de cantitatea de memorie alocată. Prin urmare, complexitatea în timp a operației de creare a unui vector este O(1). Cantitatea de memorie ocupată inițial de vector este direct proporțională cu capacitatea inițială, deci complexitatea în spațiu a operației de creare a unui vector este O(initialCapacity).
Interogarea dimensiunii
Pentru interogarea dimensiunii, se definește următoarea metodă:
/**
* Metoda intoarce numarul de elemente valide din lista specificata.
* @return numarul de elemente valide din lista list.
*/
uint32_t size();
Implementarea acestei funcții se face întorcând direct valoarea câmpului count din clasă. În mod evident, atât complexitatea în timp cât și cea în spațiu pentru această operație este de O(1).
Inserția
Pentru inserția unui element value pe o anumită poziție index se definește următoarea funcție:
/**
* Metoda insereaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta
* se face realocare. Se afiseaza un mesaj de eroare daca indexul este mai mare decat size.
* @param index indexul pe care se va face insertia
* @param value valoarea ce trebuie inserata
*/
void insert(uint32_t index, T value);
Inserția unui element value pe o anumită poziție index într-o secvență implementată cu vectori, se face urmând următorul algoritm:
- Dacă index este mai mare strict decat count, se afișează un mesaj de eroare și funcția se încheie.
- Dacă count este egal cu capacity, se face realocare de memorie alocând un vector nou de 2 * capacity elemente, copiind elementele din array-ul vechi în cel nou (se poate utilizeaza funcția memcpy) și eliberând memoria veche.
- Se folosește funcția memmove pentru a muta toate elementele de la poziția index la size - 1 cu un element mai la dreapta.
- Se atribuie elementului de pe poziția index din vector valoarea value.
- count se incrementează cu 1.
Analiza complexității: În cel mai favorabil caz, când există memorie pentru inserție fără a fi nevoie de realocare, și dacă index-ul pentru inserție este egal cu count, adică inserția se face la sfârșit, nu este necesară nicio copiere sau mutare de date, deci complexitatea în timp este O(1). În cazul cel mai nefavorabil, este necesară o realocare de memorie pentru dublarea capacității, cât și o copiere a tuturor elementelor la dreapta cu o poziție, deci complexitatea în timp devine O(count). În cazul general, se observă că se fac mult mai puține realocări decât inserții și pe măsură ce count crește, numărul de realocări scade. Astfel, complexitatea în timp este O(1) amortizat, adică, deși unele operații pot dura mult (proporțional cu count), în medie durata nu depinde de count.
Ștergerea
Pentru ștergerea unui element de pe o anumită poziție index se definește următoarea funcție:
/**
* Functia sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare
* daca indexul este mai mare decat (size - 1).
* @param list lista din care se face stergerea.
* @param index indexul de la care se va face stergerea
*/
void arrayListDelete(struct ArrayList * list, unsigned index);
Ștergerea unui element de pe o anumită poziție index dintr-o secvență implementată cu vectori, se face urmând următorul algoritm:
- Dacă index este mai mare decat size - 1, se afișează un mesaj de eroare și funcția se încheie.
- Se folosește funcția memmove pentru a muta elementele de la poziția index + 1 la size - 1 cu un element mai la stânga.
- size se decrementează cu 1.
Căutarea
Pentru căutarea unui element value într-o secvență neordonată se definește următoarea funcție:
/**
* Functia cauta elementul value in vector si intoarce prima pozitie pe care apare.
* Se intoarce -1 daca valoarea nu exista in vector.
* @param list lista in care se face cautarea.
* @param value valoarea care se cauta.
* @return indexul la care apare valoarea sau -1 daca nu exista in vector.
*/
int arrayListSearch(struct ArrayList * list, short value);
Căutarea unui element value într-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:
- Se iterează cu o variabilă i de la 0 la size - 1.
- Dacă elementul de pe poziția i din vector este egal cu value, se întoarce valoarea lui i.
- Se întoarce valoarea -1.
Accesarea elementului de pe o anumită poziție
Pentru accesarea unui element de pe poziția index dintr-o secvență se definește următoarea funcție:
/**
* Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza
* un mesaj de eroare (si se întoarce 0).
* @param list lista in care se face accesul.
* @param index pozitia de la care se doreste citirea elementului.
* @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1)
*/
short arrayListGet(struct ArrayList * list, unsigned index);
Accesarea unui element de pe poziția index dintr-o secvență neordonată implementată cu vectori, se face urmând următorul algoritm:
- Dacă index este mai mare decât (size - 1) se afișează un mesaj de eroare și se întoarce 0.
- Se întoarce valoarea de la indexul index din vector.
Sortarea unei secvențe implementate cu vectori - Bubble Sort
Pentru sortarea unei secvențe se definește următoarea funcție:
/**
* Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.
* @param list lista care se doreste sortata.
*/
void arrayListBubbleSort(struct ArrayList * list);
Sortarea unei secvențe implementată cu vectori se face urmând următorul algoritm:
- Se declară o variabilă done.
- Se atribuie lui done valoarea 1.
- Se iterează cu un contor i de la 0 la (size - 2)
- Dacă elementul de pe poziția i din vector este mai mare decât elementul de pe poziția (i + 1), acestea se interschimbă și lui done i se atribuie valoarea 0.
- După terminarea iterării peste vector, dacă done e 0, se sare la pasul 2 (se folosește o buclă do-while).
Căutarea într-o secvență sortată implementată cu vectori - Binary Search
Căutarea într-o secvență ordonată se poate realiza mai eficient decât iterând peste toate elementele cu o buclă în O(n), deoarece avem informații suplimentare legate de poziția cea mai probabilă a elementului căutat.
Algoritmul numit Binary Search, care face parte din clasa Divide-et-impera, funcționează căutând elementul la mijlocul intervalului în care se realizează căutare, și în funcție de rezultat întorcând poziția sau eliminând în întregime jumătate din interval.
Pentru căutarea unei valori value într-o secvență sortată implementată cu vectori, se definește următoarea funcție:
/**
* Functia cauta elementul value in secventa list sortata crescator.
* Daca secventa nu este sortata, comportamentul nu este definit.
* @param list lista in care se cauta.
* @param value valoarea cautata in secventa.
* @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista.
*/
int arrayListBinarySearch(struct ArrayList * list, short value);
Căutarea unei valori value într-o secvență sortată implementată cu vectori se face urmând următorul algoritm:
- Se inițializează o variabilă start cu valoarea 0 și o varibilă end cu valoarea (size - 1).
- Cât timp start este mai mic sau egal decât end se realizează următoarele operații:
- Se declară o variabilă middle și i se atribuie valoarea (start + end ) / 2.
- Dacă elementul din vector de pe poziția middle este egal cu value, se întoarce valoarea middle.
- Dacă elementul din vector de pe poziția middle este mai mare decât value, end va lua valoarea middle - 1 altfel,
- Dacă elementul din vector de pe poziția middle este mai mic decât value, start va lua valoarea middle + 1.
- Se sare la punctul 3.
- Aici se ajunge dacă start devine mai mare decât end, în care situație se întoarce -1.
Ștergerea unui ArrayList
Pentru ștergerea unui ArrayList
se definește următoarea funcție.
/**
* Functia dezalocă memoria folosită de lista specificată.
* @param list lista care trebuie ștearsă.
*/
void deleteArrayList(struct ArrayList * list);
Ștergerea unui ArrayList
se realizează în doi pași:
- Se dezalocă memoria alocată pentru vector.
- Se dezalocă memoria alocată pentru structura de tip
struct ArrayList
.
Implementarea secvenței cu liste simplu și dublu înlănțuite
În cazul implementării cu liste simplu și dublu înlănțuite, elementele sunt plasate în zone de memorie separate, numite noduri, iar fiecare nod conține pe lângă valoarea efectivă și adresa următorului nod (în cazul listelor simplu înlănțuite), sau adresa nodului următor și a nodului anterior (în cazul listelor dublu înlănțuite). Acest tip de structurare a secvențelor respectă în mod natural contractul stabilit de lista abstractă (dimensiune nelimitată, secvențierea elementelor, etc.). Prin urmare vom defini o structură numită LinkedList
care va stoca adresa primului și ultimului nod, dar și numărul de elemente din secvență, pentru optimizarea operației de interogare a dimensiunii. Pentru a defini un nod, ne trebuie o a doua structură numită ListNode
. Mai jos este un exemplu de listă simplu înlănțuită de valori în virgulă mobilă cu dublă precizie:
struct ListNode {
double value;
struct ListNode * next;
};
struct LinkedList {
struct ListNode * firstNode;
struct ListNode * lastNode;
unsigned size;
};
Crearea unui LinkedList
Pentru crearea unei liste noi, se definește următoarea funcție (observați lipsa parametrului capacity):
/**
* Functia aloca memorie si creeaza un nou LinkedList.
* @return pointer la o structura de tip LinkedList.
*/
struct LinkedList * createLinkedList();
Implementarea acestei funcții se face folosind următorul algoritm:
- Se alocă memorie pentru o variabilă de tip
struct LinkedList
. - Se inițializează
firstNode
șilastNode
cu valoarea NULL. - Se inițializează
size
cu 0. - Se întoarce adresa variabilei de tip
struct LinkedList
.
Interogarea dimensiunii
Pentru interogarea dimensiunii, se definește următoarea funcție:
/**
* Functia intoarce numarul de elemente valide din lista specificata.
* @param list lista pentru care se cere dimensinea.
* @return numarul de elemente valide din lista list.
*/
unsigned linkedListSize(struct LinkedList * list);
Implementarea acestei funcții se face întorcând direct valoarea câmpului size
din structură.
Inserția
Pentru inserția unui element value pe o anumită poziție index se definește următoarea funcție:
/**
* Functia inseareaza elementul value pe pozitia index in lista.
* @param list lista in care se face insertia.
* @param index indexul pe care se va face insertia
* @param value valoarea ce trebuie inserata
*/
void linkedListInsert(struct LinkedList * list, unsigned index, double value);
Inserția unui element value pe o anumită poziție index într-o secvență implementată cu liste înlănțuite, se face urmând următorul algoritm:
- Dacă
index
este mai mare decatsize
, se afișează un mesaj de eroare și funcția se încheie. - Se alocă memorie pentru un nod
newNode
, unde câmpulnewNode->next
este NULL șinewNode->value
estevalue
. - Dacă
index
este egal cu 0,newNode->next
va devenifirstNode
șifirstNode
va deveninewNode
. - Dacă
size
nu este egal cu 0, se folosește un pointer temporartmpNode
cu care se avansează până la nodul de pe pozițiaindex-1
. Se inserează nodulnewNode
întretmpNode
șitmpNode->next
:newNode->next
devinetmpNode->next
șitmpNode->next
devinenewNode
.
- Dacă
index
este egal cusize
,lastNode
devinenewNode
size
se incrementează cu 1.
Ștergerea
Pentru ștergerea unui element de pe o anumită poziție index se definește următoarea funcție:
/**
* Functia sterge elementul de pe pozitia index din lista. Se afiseaza un mesaj de eroare
* daca indexul este mai mare sau egal decat size.
* @param list lista din care se face stergerea.
* @param index indexul de la care se va face stergerea
*/
void linkedListDelete(struct LinkedList * list, unsigned index);
Ștergerea unui element de pe o anumită poziție index dintr-o secvență implementată cu liste, se face urmând următorul algoritm:
- Dacă
index
este mai mare sau egal decâtsize
, se afișează un mesaj de eroare și funcția se încheie. - Dacă
size
e 1, se eiberează memoria pentrufirstNode
,firstNode
șilastNode
devin NULL,size
devine 0 și funcția se încheie. - Se definește un pointer temporar la un nod numit
oldNode
. - Dacă index este 0,
oldNode
devinefirstNode
șifirstNode
devineoldNode->next
- Dacă index NU este 0, se folosește un pointer suplimentar numit
tmpNode
pentru a avansa în listă până pe pozițiaindex - 1
.oldNode
devinetmpNode->next
șitmpNode->next
devineoldNode->next
. - Dacă
index
este egal cusize - 1
,lastNode
devinetmpNode
- Se eliberează memoria pentru
oldNode
size
se decrementează cu 1.
Căutarea
Pentru căutarea unui element value într-o secvență neordonată se definește următoarea funcție:
/**
* Functia cauta elementul value in lista si intoarce prima pozitie pe care apare.
* Se intoarce -1 daca valoarea nu exista in lista.
* @param list lista in care se face cautarea.
* @param value valoarea care se cauta.
* @return indexul la care apare valoarea sau -1 daca nu exista in lista.
*/
int linkedListSearch(struct LinkedList * list, double value);
Căutarea unui element value într-o secvență neordonată implementată cu liste, se face urmând următorul algoritm:
- Se folosește un pointer suplimentar
tmpNode
cu care se iterează peste elementele din listă până când acesta devine NULL. - Dacă elementul din nodul
tmpNode
din listă este egal cuvalue
, se întoarce valoarea din nod. - Se întoarce valoarea -1.
Accesarea elementului de pe o anumită poziție
Pentru accesarea unui element de pe poziția index dintr-o secvență se definește următoarea funcție:
/**
* Functia intoarce elementul din lista de pe poziția index. Daca index este mai mare sau egal decat size
* se afiseaza un mesaj de eroare (si se întoarce 0).
* @param list lista in care se face accesul.
* @param index pozitia de la care se doreste citirea elementului.
* @return valoarea de la pozitia index sau 0 daca index este mai mare sau egal decat size
*/
short linkedListGet(struct LinkedList * list, unsigned index);
Accesarea unui element de pe poziția index dintr-o secvență neordonată implementată cu liste, se face urmând următorul algoritm:
- Dacă
index
este mai mare sau egal decâtsize
se afișează un mesaj de eroare și se întoarce 0. - Se folosește un pointer la nod temporar numit
tmpNode
și folosind o buclă se avansează în listă până la pozițiaindex
. - Se întoarce valoarea din nodul
tmpNode
.
Sortarea unei secvențe implementate cu liste - Bubble Sort
Pentru sortarea unei secvențe se definește următoarea funcție:
/**
* Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort.
* @param list lista care se doreste sortata.
*/
void linkedListBubbleSort(struct LinkedList * list);
Sortarea unei secvențe implementată cu vectori se face urmând următorul algoritm:
- Se declară o variabilă
done
. - Se atribuie lui
done
valoarea 1. - Se folosește un pointer temporar la un nod
tmpNode
și se parcurge lista de lafirstNode
la nodul anterior luilastNode
- Dacă elementul din nodul
tmpNode
din listă este mai mare decât elementul din nodultmpNode->next
, acestea se interschimbă și lui done i se atribuie valoarea 0. - După terminarea iterării peste listă, dacă
done
e 0, se sare la pasul 2 (se folosește o buclă do-while).
Căutarea într-o secvență sortată implementată cu liste
Deoarece listele simplu și dublu înlănțuite nu suportă acces aleator, PE ACESTEA NU SE POATE IMPLEMENTA CĂUTAREA BINARĂ..
Ștergerea unui LinkedList
Pentru ștergerea unui LinkedList
se definește următoarea funcție.
/**
* Functia dezalocă memoria folosită de lista specificată.
* @param list lista care trebuie ștearsă.
*/
void deleteLinkedList(struct LinkedList * list);
Ștergerea unui LinkedList
se realizează în doi pași:
- Se dezalocă nodurile din listă.
- Se dezalocă memoria alocată pentru structura de tip
struct LinkedList
.
Exerciții
Săptămâna 1
-
Se dă următorul header file
arrayList.h
:#ifndef ARRAY_LIST_H #define ARRAY_LIST_H struct ArrayList { short * array; // pointer la zona de memorie alocată unsigned capacity; // dimensiunea zonei alocate unsigned size; // numarul de elemente valide din secventa }; /** * Functia aloca memorie si creeaza un nou ArrayList cu o capacitate initiala. * @param initialCapacity capacitatea initiala a secventei. * @return pointer la o structura de tip ArrayList. */ struct ArrayList * createArrayList(unsigned initialCapacity); /** * Functia intoarce numarul de elemente valide din lista specificata. * @param list lista pentru care se cere dimensinea. * @return numarul de elemente valide din lista list. */ unsigned arrayListSize(struct ArrayList * list); /** * Functia inseareaza elementul value pe pozitia index in vector. Daca capacitatea este insuficienta * se face realocare. Se afiseaza un mesaj de eroare daca indexul este mai mare decat size. * @param list lista in care se face insertia. * @param index indexul pe care se va face insertia * @param value valoarea ce trebuie inserata */ void arrayListInsert(struct ArrayList * list, unsigned index, short value); /** * Functia sterge elementul pe pozitia index in vector. Se afiseaza un mesaj de eroare * daca indexul este mai mare decat (size - 1). * @param list lista din care se face stergerea. * @param index indexul de la care se va face stergerea */ void arrayListDelete(struct ArrayList * list, unsigned index); /** * Functia cauta elementul value in vector si intoarce prima pozitie pe care apare. * Se intoarce -1 daca valoarea nu exista in vector. * @param list lista in care se face cautarea. * @param value valoarea care se cauta. * @return indexul la care apare valoarea sau -1 daca nu exista in vector. */ int arrayListSearch(struct ArrayList * list, short value); /** * Functia intoarce elementul din vector de pe poziția index. Daca index este mai mare decat (size - 1) se afiseaza * un mesaj de eroare (si se întoarce 0). * @param list lista in care se face accesul. * @param index pozitia de la care se doreste citirea elementului. * @return valoarea de la pozitia index sau 0 daca index este mai mare decat (size - 1) */ short arrayListGet(struct ArrayList * list, unsigned index); /** * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort. * @param list lista care se doreste sortata. */ void arrayListBubbleSort(struct ArrayList * list); /** * Functia cauta elementul value in secventa list sortata crescator. * Daca secventa nu este sortata, comportamentul nu este definit. * @param list lista in care se cauta. * @param value valoarea cautata in secventa. * @return indexul unde s-a găsit valoarea value sau -1 daca valoarea nu exista. */ int arrayListBinarySearch(struct ArrayList * list, short value); /** * Functia dezalocă memoria folosită de lista specificată. * @param list lista care trebuie ștearsă. */ void deleteArrayList(struct ArrayList * list); #endif
Implementați într-un fișier sursă C funcțiile definite în header.
- Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
- definiți un
ArrayList
de capacitatea initiala 3. - adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați arrayListInsert cu indexul 0 de fiecare dată).
- căutați valoarea 4 și afișați indexul pe care apare.
- inserați valoarea 9 la indexul 5.
- afișați valoarea de la indexul 5.
- sortați vectorul.
- căutați valoarea 16 și afișați indexul la care apare.
- afișați conținutul secvenței.
- ștergeți secvența.
- definiți un
Săptămâna 2
-
Se dă următorul header file
linkedList.h
:#ifndef LINKED_LIST_H #define LINKED_LIST_H struct ListNode { double value; struct ListNode * next; }; struct LinkedList { struct ListNode * firstNode; struct ListNode * lastNode; unsigned size; }; /** * Functia aloca memorie si creeaza un nou LinkedList. * @return pointer la o structura de tip LinkedList. */ struct LinkedList * createLinkedList(); /** * Functia intoarce numarul de elemente valide din lista specificata. * @param list lista pentru care se cere dimensinea. * @return numarul de elemente valide din lista list. */ unsigned linkedListSize(struct LinkedList * list); /** * Functia insereaza elementul value pe pozitia index in lista. Se afiseaza un * mesaj de eroare daca indexul este mai mare decat size. * @param list lista in care se face insertia. * @param index indexul pe care se va face insertia * @param value valoarea ce trebuie inserata */ void linkedListInsert(struct LinkedList * list, unsigned index, double value); /** * Functia sterge elementul de pe pozitia index din lista. Se afiseaza un mesaj de eroare * daca indexul este mai mare sau egal decat size. * @param list lista din care se face stergerea. * @param index indexul de la care se va face stergerea */ void linkedListDelete(struct LinkedList * list, unsigned index); /** * Functia cauta elementul value in lista si intoarce prima pozitie pe care apare. * Se intoarce -1 daca valoarea nu exista in lista. * @param list lista in care se face cautarea. * @param value valoarea care se cauta. * @return indexul la care apare valoarea sau -1 daca nu exista in lista. */ int linkedListSearch(struct LinkedList * list, double value); /** * Functia intoarce elementul din lista de pe poziția index. Daca index este mai * mare sau egal decat size se afiseaza un mesaj de eroare (si se întoarce 0). * @param list lista in care se face accesul. * @param index pozitia de la care se doreste citirea elementului. * @return valoarea de la pozitia index sau 0 daca index este mai mare sau egal decat size */ double linkedListGet(struct LinkedList * list, unsigned index); /** * Functia sorteaza crescator elementele din secventa list folosind algoritmul Bubble Sort. * @param list lista care se doreste sortata. */ void linkedListBubbleSort(struct LinkedList * list); /** * Functia dezalocă memoria folosită de lista specificată. * @param list lista care trebuie ștearsă. */ void deleteLinkedList(struct LinkedList * list); #endif
Implementați într-un fișier sursă C funcțiile definite în header.
- Folosind structura și funcțiile definite în header, scrieți un program simplu care să efectueze următoarele operații:
- definiți un
LinkedList
. - adăugați 7 elemente: 6, 10, 0, -5, 4, 16, 20 (utilizați linkedListInsert cu indexul 0 de fiecare dată).
- căutați valoarea 4 și afișați indexul pe care apare.
- inserați valoarea 9 la indexul 5.
- afișați valoarea de la indexul 5.
- sortați vectorul.
- căutați valoarea 16 și afișați indexul la care apare.
- afișați conținutul secvenței.
- ștergeți secvența.
- definiți un