13 idei și subiecte interesante de proiecte cu structură de date pentru începători [2022]

În lumea informatică, structura datelor se referă la formatul care conține o colecție de valori de date, relațiile acestora și funcțiile care pot fi aplicate datelor. Structurile de date aranjează datele astfel încât să poată fi accesate și lucrate cu algoritmi specifici mai eficient. În acest articol, vom enumera câteva proiecte utile de structură de date pentru a vă ajuta să învățați, să creați și să inovezi!

Bazele structurii datelor

Structurile de date pot fi clasificate în următoarele tipuri de bază:

• Matrice
• Liste legate
• Stive
• Cozile
• Copaci
• Tabele de hash
• Grafice

Selectarea setării adecvate pentru datele dvs. este o parte integrantă a procesului de programare și de rezolvare a problemelor. Și puteți observa că structurile de date organizează tipuri de date abstracte în implementări concrete. Pentru a obține acest rezultat, ei folosesc diverși algoritmi, cum ar fi sortarea, căutarea etc. Învățarea structurilor de date este una dintre părțile importante ale cursurilor de știință a datelor.

Odată cu creșterea datelor mari și a analizei, cunoașterea acestor elemente fundamentale a devenit aproape esențială pentru oamenii de știință ai datelor. Instruirea încorporează de obicei diverse proiecte de structură de date pentru a permite sinteza cunoștințelor din experiențele din viața reală. Iată o listă de subiecte pentru a începe!

Idei de proiecte de structuri de date

1. Arbori de căutare binari obscuri

Elementele, cum ar fi nume, numere etc. pot fi stocate în memorie într-o ordine sortată numită arbori de căutare binare sau BST. Și unele dintre aceste structuri de date își pot echilibra automat înălțimea atunci când elementele arbitrare sunt inserate sau șterse. Prin urmare, ele sunt cunoscute ca BST-uri cu auto-echilibrare. În plus, pot exista diferite implementări de acest tip, cum ar fi arborii BTrees, arborii AVL și arborii roșu-negru. Dar există multe alte execuții mai puțin cunoscute despre care puteți afla. Câteva exemple includ copaci AA, 2-3 copaci, copaci întinși, copaci de țap ispășitor și copaci.

Vă puteți baza proiectul pe aceste alternative și puteți explora modul în care acestea pot depăși alte BST-uri utilizate pe scară largă în diferite scenarii. De exemplu, copacii împrăștiați se pot dovedi mai rapid decât copacii roșu-negri în condițiile unei localități temporale serioase.

2. BST-uri care urmează algoritmul de memorare

Memorarea legată de programarea dinamică. În BST-urile de reducere-memoizing, fiecare nod poate memoriza o funcție a subarborilor săi. Luați în considerare exemplul unui BST de persoane ordonate după vârsta lor. Acum, lăsați nodurile copil să stocheze venitul maxim al fiecărui individ. Cu această structură, puteți răspunde la întrebări precum „Care este venitul maxim al persoanelor cu vârsta cuprinsă între 18,3 și 25,3 ani?” De asemenea, poate gestiona actualizări în timp logaritmic.

Mai mult, astfel de structuri de date sunt ușor de realizat în limbajul C. De asemenea, puteți încerca să-l legați cu Ruby și un API convenabil. Alegeți o interfață care vă permite să specificați „lambda” ca funcție de comandă și funcția de memorare a subarborelui. Per total, vă puteți aștepta ca BST-uri care memorează reducerea să fie BST-uri auto-echilibrare, cu o strop de contabilitate suplimentară.

Checkout: Tipuri de arbore binar

3. Timpul de inserare a grămezii

Când căutați proiecte de structură de date , doriți să întâlniți probleme distincte care sunt rezolvate cu abordări creative. O astfel de întrebare unică de cercetare se referă la timpul mediu de inserare a cazurilor pentru structurile de date heap binare. Potrivit unor surse online, este timpul constant, în timp ce altele sugerează că este timp log(n).

Dar Bollobas și Simon oferă un răspuns susținut numeric în lucrarea lor intitulată „Inserare aleatorie repetată într-o coadă prioritară”. În primul rând, ei presupun un scenariu în care doriți să inserați n elemente într-un heap gol. Poate fi „n!” posibile comenzi pentru același lucru. Apoi, adoptă abordarea costului mediu pentru a demonstra că timpul de inserție este limitat de o constantă de 1,7645.

4. Treaps optime cu parametrii care schimbă prioritățile

Treaps sunt o combinație de BST și grămezi. Aceste structuri de date randomizate implică atribuirea unor priorități specifice nodurilor. Puteți alege un proiect care optimizează un set de parametri în diferite setări. De exemplu, puteți seta preferințe mai mari pentru nodurile care sunt accesate mai des decât altele. Aici, fiecare acces va declanșa un proces dublu:

• Alegerea unui număr aleatoriu
• Înlocuirea priorității nodului cu acel număr dacă se constată că este mai mare decât prioritatea anterioară

Ca urmare a acestei modificări, copacul își va pierde forma aleatorie. Este posibil ca nodurile accesate frecvent să fie acum aproape de rădăcina arborelui, oferind astfel căutări mai rapide. Deci, experimentați cu această structură de date și încercați să vă bazați argumentul pe dovezi.

La sfârșitul proiectului, puteți fie să faceți o descoperire originală, fie chiar să concluzionați că schimbarea priorității nodului nu oferă multă viteză. Va fi totuși un exercițiu relevant și util.

5. Proiect de cercetare pe arbori kd

Arborii K-dimensionali sau arborii kd organizează și reprezintă date spațiale. Aceste structuri de date au mai multe aplicații, în special în căutările de chei multidimensionale, cum ar fi căutările de vecin cel mai apropiat și de interval. Iată cum funcționează arborii kd:

• Fiecare nod frunză al arborelui binar este un punct k-dimensional
• Fiecare nod fără frunze împarte hiperplanul (care este perpendicular pe acea dimensiune) în două semi-spații
• Subarborele din stânga unui anumit nod reprezintă punctele din stânga hiperplanului. În mod similar, subarborele din dreapta acelui nod indică punctele din jumătatea dreaptă.

Puteți verifica un pas mai departe și puteți construi un arbore kd auto-echilibrat în care fiecare nod frunză ar avea aceeași distanță de la rădăcină. De asemenea, îl puteți testa pentru a afla dacă astfel de arbori echilibrați s-ar dovedi optimi pentru un anumit tip de aplicație.

Cu aceasta, am acoperit cinci idei interesante pe care le puteți studia, investiga și încerca. Acum, să ne uităm la câteva proiecte despre structurile de date și algoritmi.

Citiți: Salariul Data Scientist în India

6. Necazurile cavalerilor

În acest proiect, vom înțelege doi algoritmi în acțiune – BFS și DFS. BFS înseamnă Breadth-First Search și utilizează structura de date Queue pentru a găsi calea cea mai scurtă. În timp ce, DFS se referă la Depth-First Search și traversează structurile de date Stack.

Pentru început, veți avea nevoie de o structură de date similară cu arborii binari. Acum, să presupunem că ai o tablă de șah standard 8 X 8 și vrei să arăți mișcările cavalerului într-un joc. După cum probabil știți, mișcarea de bază a unui cavaler în șah este doi pași înainte și un pas în lateral. Cu fața în orice direcție și având suficiente ture, se poate muta din orice pătrat de pe tablă în orice alt pătrat.

Dacă vrei să știi cel mai simplu mod în care cavalerul tău se poate muta de la un pătrat (sau nod) la altul într-o configurație bidimensională, mai întâi va trebui să construiești o funcție ca cea de mai jos.

• Knight_plays([0,0], [1,2]) == [[0,0], [1,2]]
• Knight_plays([0,0], [3,3]) == [[0,0], [1,2], [3,3]]
• Knight_plays([3,3], [0,0]) == [[3,3], [1,2], [0,0]]

În plus, acest proiect ar necesita următoarele sarcini:

• Crearea unui scenariu pentru un joc de societate și o noapte
• Tratează toate mișcările posibile ale cavalerului ca pe niște copii în structura arborelui
• Asigurându-vă că orice mișcare nu iese de pe tablă
• Alegerea unui algoritm de căutare pentru a găsi calea cea mai scurtă în acest caz
• Aplicarea algoritmului de căutare adecvat pentru a găsi cea mai bună mișcare posibilă de la pătratul de început la pătratul final.

7. Structuri rapide de date în limbaje de sistem non-C

De obicei, programatorii construiesc rapid programe folosind limbaje de nivel înalt precum Ruby sau Python, dar implementează structuri de date în C/C++. Și creează un cod obligatoriu pentru a conecta elementele. Cu toate acestea, se crede că limbajul C este predispus la erori, ceea ce poate cauza și probleme de securitate. Aici se află o idee de proiect interesantă.

Puteți implementa o structură de date într-un limbaj modern de nivel scăzut, cum ar fi Rust sau Go, și apoi să vă legați codul la limbajul de nivel înalt. Cu acest proiect, puteți încerca ceva nou și, de asemenea, vă puteți da seama cum funcționează legăturile. Dacă efortul tău este de succes, îi poți inspira chiar și pe alții să facă un exercițiu similar în viitor și să conducă o mai bună orientare spre performanță a structurilor de date.

Citește și: Idei de proiecte Data Science pentru începători

8. Motor de căutare pentru structuri de date

Software-ul își propune să automatizeze și să accelereze alegerea structurilor de date pentru un anumit API. Acest proiect nu numai că demonstrează modalități noi de reprezentare a diferitelor structuri de date, ci și optimizează un set de funcții pentru a dota inferența asupra acestora. Am compilat mai jos rezumatul acestuia.

• Proiectul motorului de căutare a structurii datelor necesită cunoștințe despre structurile de date și relațiile dintre diferitele metode.
• Acesta calculează timpul necesar fiecărei structuri de date compuse posibile pentru toate metodele.
• În cele din urmă, selectează cele mai bune structuri de date pentru un anumit caz.

Citiți: Idei de proiecte de exploatare a datelor

9. Aplicație de agendă telefonică folosind liste dublu legate

Acest proiect poate demonstra funcționarea aplicațiilor de agenda de contacte și, de asemenea, vă poate învăța despre structurile de date, cum ar fi matrice, liste legate, stive și cozi. De obicei, gestionarea agendei telefonice include operațiuni de căutare, sortare și ștergere. O caracteristică distinctivă a interogărilor de căutare aici este că utilizatorul vede sugestii din lista de contacte după introducerea fiecărui caracter. Puteți citi codul sursă al proiectelor disponibile gratuit și îl puteți replica pentru a vă dezvolta abilitățile.

10. Indexare spațială cu quadtrees

Structura de date quadtree este un tip special de structură arborescentă, care poate împărți recursiv un spațiu plat 2-D în patru cadrane. Fiecare nod ierarhic din această structură arborescentă are fie zero, fie patru copii. Poate fi folosit în diverse scopuri, cum ar fi stocarea rară a datelor, procesarea imaginilor și indexarea spațială.

Indexarea spațială se referă la executarea eficientă a unor interogări geometrice selectate, formând o parte esențială a proiectării aplicațiilor geo-spațiale. De exemplu, aplicațiile de partajare a călătoriei precum Ola și Uber procesează interogări geografice pentru a urmări locația cabinelor și pentru a oferi actualizări utilizatorilor. Funcția Facebook Nearby Friends are și o funcționalitate similară. Aici, metadatele asociate sunt stocate sub formă de tabele, iar un index spațial este creat separat cu coordonatele obiectului. Obiectivul problemei este găsirea celui mai apropiat punct de unul dat.

Puteți urmări proiecte de structură de date cu patru arbori într-o gamă largă de domenii, de la cartografiere, planificare urbană și planificare a transportului până la managementul și atenuarea dezastrelor. Am oferit o scurtă schiță pentru a vă alimenta abilitățile de rezolvare a problemelor și de analiză.

Obiectiv: Crearea unei structuri de date care să permită următoarele operații

• Introduceți o locație sau un spațiu geometric
• Căutați coordonatele unei anumite locații
• Numărați numărul de locații din structura de date într-o anumită zonă adiacentă

11. Proiecte bazate pe grafice pe structuri de date

Puteți începe un proiect privind sortarea topologică a unui grafic. Pentru aceasta, veți avea nevoie de cunoștințe prealabile ale algoritmului DFS. Iată diferența principală dintre cele două abordări:

• Printăm un vârf și apoi apelăm recursiv algoritmul pentru vârfurile adiacente în DFS.
• În sortarea topologică, apelăm mai întâi recursiv algoritmul pentru vârfurile adiacente. Și apoi, împingem conținutul într-o stivă pentru imprimare.

Prin urmare, algoritmul de sortare topologic ia un grafic aciclic direcționat sau DAG pentru a returna o matrice de noduri.

Să luăm în considerare exemplul simplu de a comanda o rețetă de clătite. Pentru a face clătite, aveți nevoie de un set specific de ingrediente, precum ouă, lapte, făină sau amestec de clătite, ulei, sirop etc. Aceste informații, împreună cu cantitatea și porțiile, pot fi ușor reprezentate într-un grafic.

Dar este la fel de important să cunoaștem ordinea precisă de utilizare a acestor ingrediente. Aici puteți implementa ordonarea topologică. Alte exemple includ realizarea de diagrame de prioritate pentru optimizarea interogărilor bazei de date și a programelor pentru proiectele software. Iată o prezentare generală a procesului pentru referință:

• Apelați algoritmul DFS pentru structura de date a graficului pentru a calcula timpii de sfârșit pentru vârfuri
• Stocați vârfurile într-o listă cu o ordine descrescătoare a timpului de sfârșit
• Executați sortarea topologică pentru a returna lista ordonată

12. Reprezentări numerice cu liste de acces aleatoriu

În reprezentările pe care le-am văzut în trecut, elementele numerice sunt în general ținute în grămezi binomiale. Dar aceste modele pot fi implementate și în alte structuri de date. Okasaki a venit cu o tehnică de reprezentare numerică folosind liste binare de acces aleator. Aceste liste au multe avantaje:

• Acestea permit introducerea și îndepărtarea de la început
• Acestea permit accesul și actualizarea la un anumit index

Aflați mai multe: Cele șase structuri de date cele mai frecvent utilizate în R

13. Editor de text bazat pe stivă

Editorul dvs. de text obișnuit are funcționalitatea de a edita și stoca text în timp ce acesta este scris sau editat. Deci, există mai multe modificări în poziția cursorului. Pentru a obține o eficiență ridicată, avem nevoie de o structură de date rapidă pentru inserare și modificare. Și matricele obișnuite de caractere necesită timp pentru stocarea șirurilor.

Puteți experimenta cu alte structuri de date, cum ar fi spații tampon și frânghii, pentru a rezolva aceste probleme. Obiectivul tău final va fi să obții o concatenare mai rapidă decât șirurile obișnuite prin ocuparea unui spațiu de memorie contigu mai mic.

Concluzie

Abilitățile de structurare a datelor formează baza dezvoltării software, în special atunci când vine vorba de gestionarea unor seturi mari de date în ecosistemul digital de astăzi. Companii de top precum Adobe, Amazon și Google angajează pentru diverse posturi profitabile în domeniul structurii de date și al algoritmului. Și în interviuri, recrutorii vă testează nu numai cunoștințele teoretice, ci și abilitățile practice. Așadar, exersați proiectele de structură de date de mai sus pentru a pune piciorul în ușă!

Dacă sunteți curios să aflați despre știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie, 1 -on-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.