Pentru acest proiect am ales să îmi structurez rezolvarea cerințelor în mai multe fisiere de tip header,având nume intuitive în functie de structurile de date folosite,astfel încât orice persoană care priveste din exterior acest proiect să poată să înțeleagă conținutul acestuia.
fisiere.h-fisiere.c
Având în vedere că toate cerințele presupuneau lucrul cu fisiere,în cadrul acestui header am creat 7 functii pentru scrierea în fisiere a rezolvarilor.De asemenea aici se regăsesc si functiile pentru citirea din fisiere pentru pasii unde ni se cerea acest lucru,cu exceptia ultimului pas unde am ales să citesc muchiile în functia de reprezentare a grafului,pentru a nu mai ocupa spatiu suplimentar cu stocarea muchiilor ca mai apoi să le trimit către functia de reprezentare a grafului.Toate functiile din acest fisier primesc ca parametrii numele fisierului care trebuie manipulat și structura de date necesară pentru a scrie sau a citi din respectivul fisier.În fiecare functie se deschide fisierul necesar , se verifica deschiderea acestuia pentru a nu genera functionări neprevazute.Funcțiile de scriere în fisier respecta structura de scriere a cerințelor,iar în funcțiile de citire citirea se face pe linii , datele fiind ulterior separate cu ajutorul functiei strtok.
coada.h-coada.c
Aceasta este prima structură de date utilizată în cadrul proiectului si este utilizată la pasul 1 pentru stocarea candidaților.Pentru gestionarea acestei structuri am folosit 3 functii: createcoada care ne alocă spatiu pentru această structură,adaugaq care este folosită pentru adaugarea fiecarui participant în coadă,în cadrul functiei se alocă spatiu pentru un nou element si se fac legăturile specifice acestei structuri de date,eliberarelement este folosită la pasii următori pentru a elibera spatiul ocupat de un participant după ce a fost inserat în BST.
BST.h-BST.c
Aceasta este a doua structură de date utilizată în cadrul proiectului și este folosită la pasul 2 pentru organizarea candidaților în funcție de statutul social și experiența acestora. Pentru această structură, am implementat doi arbori binari de căutare separați:unul pentru candidații cu statut "lord" - BSTl și unul pentru candidații cu statut "aventurier/cavaler" - BSTac. Pentru gestionarea acestor arbori, am implementat următoarele funcții:
newnodel / newnodeac — Alocă memorie și creează un nod nou (pentru BSTl / BSTac). Se alocă memorie și pentru numele participantului, iar câmpurile sunt copiate în nodul nou.
insertbstl / insertbstac — Inserează un participant în arborele corespunzător, pe baza experienței,inserarea respectă proprietatea de arbore binar de căutare.
insertbst — Funcție principală de inserare. Se parcurge coada creată anterior și inserează fiecare participant în arborele potrivit (BSTl sau BSTac) în funcție de statutul său. După inserare, elementul este eliminat din coadă.
deletenodel / deletenodeac — Șterge un nod din arbore (BSTl sau BSTac) pe baza valorii de experiență. Funcția gestionează toate cele trei cazuri posibile (nod frunză, nod cu un singur copil, nod cu doi copii), utilizând funcția minval/minvalac pentru a găsi succesorul în cazul ștergerii unui nod cu doi copii.
minval / minvalac — Returnează nodul cu valoarea minimă dintr-un arbore (cel mai din stânga).
maxnodel / maxnodeac — Returnează nodul cu valoarea maximă dintr-un arbore (cel mai din dreapta).
eliberarebstl / eliberarebstac — Eliberează recursiv memoria ocupată de un arbore prin parcurgere în postordine.
HEAP.h-HEAP.c
Cea de a treia structură de date utilizată în cadrul proiectului este de tip heap si este folosită începand cu pasul 4 pentru stocarea a 4 lorzi si 4 cavaleri/aventurieri cu cea mai mare experientă alături de un traseu citit din fisier.
create: Creează un heap cu o capacitate specificată, alocând memorie pentru vectorul de elemente din heap. Dacă alocarea nu reușește, funcția returnează NULL.
copiaza_participant: Copiază datele unui participant de la sursă (src) la destinație (dest). Aceasta include alocarea memoriei pentru numele participantului și copierea tuturor câmpurilor.
insert: Inserează un element în heap. Dacă heap-ul este plin, capacitatea este dublată. Elementul este inserat în heap și, dacă este necesar, heap-ul este restructurat pentru a respecta proprietățile heap-ului.
copiaza_elementl și copiaza_elementac: Copiază datele unui participant dintr-un nod de tip nodebstl sau nodebstac într-un element din heap,funcțiile verifică dacă există erori la alocarea memoriei și asigură copierea corectă a tuturor datelor relevante.
creaza_elementheap_dintr_o_linie: Creează un element din heap dintr-o linie de text, extrăgând informațiile relevante pentru traseu și participant.
swap_elemente: Schimbă două elemente din heap pe baza experienței participanților.
eliberare_heap: Eliberează toată memoria alocată pentru heap, inclusiv memoria pentru traseu și pentru participanți.
actualizare_experienta: Actualizează experiența fiecărui participant din heap pe baza traseului asociat acestuia. După actualizarea experienței, heap-ul este restructurat pentru a respecta proprietatea heap-ului.
graf.c-graf.h
Aceasta este a 4 a structură utilizată pentru acest proiect si totodată ultima,fiind folosită pentru pasul 7.
creategrap: Creeaza graful orientat folosind liste de adiecenta pe baza muchiilor din fisier,chiar daca nu specifica in cerinta ca reprezentarea trebuie facuta cu lista de adiacenta aceasta ar fi fost si alegerea mea , matricea de adiacenta ocupand foarte mult spatiu in acest caz graful fiind orientat.
calculeazagrade: Calculeaza gradul interior respectiv exterior pentru fiecare nod din graf.
insert_sortat: Functia ma ajuta sa creez listele de adiacenta lexicografic,traseele neputand fi generate in ordine lexicografica daca nu faceam acest lucru.
dfs_generaretraseu: Functia implementeaza algoritmul de parcurgere in adancime,fiind apelata doar din nodurile cu grad de intrare 0,generand toate traseele posibile,cand este gasit un nod cu grad de iesire 0 traseul este scris in fisier.
eliberare_graf: Aici eliberam spatiul alocat de functia creategraph pentru stocarea grafului.