13 ciekawych pomysłów na projekt struktury danych i tematów dla początkujących [2022]

W świecie informatyki struktura danych odnosi się do formatu, który zawiera zbiór wartości danych, ich relacji i funkcji, które można zastosować do danych. Struktury danych porządkują dane tak, aby można było do nich uzyskać dostęp i pracować nad nimi efektywniej za pomocą określonych algorytmów. W tym artykule wymienimy kilka przydatnych projektów struktury danych, które pomogą Ci uczyć się, tworzyć i wprowadzać innowacje!

Podstawy struktury danych

Struktury danych można podzielić na następujące podstawowe typy:

• Tablice
• Połączone listy
• Półki na książki
• Kolejki
• Drzewa
• Tabele haszujące
• Wykresy

Wybór odpowiedniego ustawienia dla Twoich danych jest integralną częścią procesu programowania i rozwiązywania problemów. I można zauważyć, że struktury danych organizują abstrakcyjne typy danych w konkretnych implementacjach. Aby osiągnąć ten wynik, wykorzystują różne algorytmy, takie jak sortowanie, wyszukiwanie itp. Uczenie się struktur danych jest jedną z ważnych części kursów z zakresu data science.

Wraz z rozwojem big data i analiz, poznanie tych podstaw stało się niemal niezbędne dla naukowców zajmujących się danymi. Szkolenie zazwyczaj obejmuje różne projekty struktury danych, aby umożliwić syntezę wiedzy z rzeczywistych doświadczeń. Oto lista tematów, od których możesz zacząć!

Pomysły na projekty struktur danych

1. Niejasne drzewa wyszukiwania binarnego

Elementy, takie jak nazwy, liczby itp., mogą być przechowywane w pamięci w uporządkowanej kolejności zwanej drzewami wyszukiwania binarnego lub BST. Niektóre z tych struktur danych mogą automatycznie równoważyć swoją wysokość, gdy dowolne elementy są wstawiane lub usuwane. Dlatego są one znane jako samobalansujące BST. Ponadto mogą istnieć różne implementacje tego typu, takie jak drzewa BTrees, drzewa AVL i drzewa czerwono-czarne. Ale istnieje wiele innych mniej znanych egzekucji, o których możesz się dowiedzieć. Niektóre przykłady obejmują drzewa AA, 2-3 drzewa, drzewa splay, drzewa kozłów ofiarnych i drzewa.

Możesz oprzeć swój projekt na tych alternatywach i zbadać, w jaki sposób mogą one przewyższyć inne powszechnie używane BST w różnych scenariuszach. Na przykład w warunkach poważnej lokalizacji czasowej drzewa rozłożyste mogą okazać się szybsze niż drzewa czerwono-czarne.

2. BST zgodne z algorytmem zapamiętywania

Zapamiętywanie związane z programowaniem dynamicznym. W zestawach BST z zapamiętywaniem redukcji każdy węzeł może zapamiętywać funkcję swoich poddrzew. Rozważmy przykład BST osób uporządkowanych według ich wieku. Teraz niech węzły potomne przechowują maksymalny dochód każdej osoby. Dzięki tej strukturze możesz odpowiedzieć na pytania typu „Jaki jest maksymalny dochód osób w wieku od 18,3 do 25,3?” Może również obsługiwać aktualizacje w czasie logarytmicznym.

Co więcej, takie struktury danych są łatwe do wykonania w języku C. Możesz także spróbować powiązać go z Ruby i wygodnym API. Wybierz interfejs, który pozwala określić „lambda” jako funkcję zamawiania i funkcję zapamiętywania poddrzewa. Podsumowując, można oczekiwać, że BST z zapamiętywaniem redukcji będą samobilansującymi się BST z odrobiną dodatkowej księgowości.

Zamówienie: rodzaje drzewa binarnego

3. Czas wkładania sterty

Szukając projektów struktury danych , chcesz napotkać różne problemy, które można rozwiązywać za pomocą kreatywnego podejścia. Jedno z takich unikalnych pytań badawczych dotyczy średniego czasu wstawiania przypadku dla struktur danych binarnych sterty. Według niektórych źródeł internetowych jest to czas stały, podczas gdy inne sugerują, że jest to czas log(n).

Ale Bollobas i Simon udzielają odpowiedzi popartej liczbowo w swoim artykule zatytułowanym „Powtarzane losowe wstawianie do kolejki priorytetowej”. Po pierwsze, zakładają scenariusz, w którym chcesz wstawić n elementów do pustej sterty. Może być „n!” możliwe zamówienia na to samo. Następnie przyjmują podejście średniego kosztu, aby udowodnić, że czas wstawiania jest ograniczony przez stałą 1,7645.

4. Optymalne przydziały z parametrami zmieniającymi priorytet

Treaps to połączenie BST i hałd. Te randomizowane struktury danych obejmują przypisywanie węzłom określonych priorytetów. Możesz wybrać projekt, który optymalizuje zestaw parametrów w różnych ustawieniach. Na przykład możesz ustawić wyższe preferencje dla węzłów, do których uzyskuje się dostęp częściej niż inne. Tutaj każdy dostęp rozpocznie dwojaki proces:

• Wybór losowej liczby
• Zastąpienie priorytetu węzła tym numerem, jeśli okaże się, że jest wyższy niż poprzedni priorytet

W wyniku tej modyfikacji drzewo straci swój losowy kształt. Jest prawdopodobne, że często dostępne węzły znajdowałyby się teraz blisko korzenia drzewa, co zapewniałoby szybsze wyszukiwanie. Poeksperymentuj więc z tą strukturą danych i spróbuj oprzeć swój argument na dowodach.

Pod koniec projektu możesz albo dokonać oryginalnego odkrycia, albo nawet stwierdzić, że zmiana priorytetu węzła nie zapewnia dużej szybkości. Niemniej jednak będzie to istotne i przydatne ćwiczenie.

5. Projekt badawczy na drzewach kd

Drzewa K-wymiarowe lub drzewa kd organizują i reprezentują dane przestrzenne. Te struktury danych mają kilka zastosowań, szczególnie w wielowymiarowych wyszukiwaniach kluczy, takich jak wyszukiwanie najbliższego sąsiada i wyszukiwanie zakresu. Oto jak działają drzewa kd:

• Każdy węzeł liścia drzewa binarnego jest punktem k-wymiarowym
• Każdy węzeł niebędący liściem dzieli hiperpłaszczyznę (która jest prostopadła do tego wymiaru) na dwie półprzestrzenie
• Lewe poddrzewo danego węzła reprezentuje punkty na lewo od hiperpłaszczyzny. Podobnie, prawe poddrzewo tego węzła oznacza punkty w prawej połowie.

Możesz zbadać krok dalej i zbudować samozrównoważone drzewo kd, w którym każdy węzeł liścia będzie miał taką samą odległość od korzenia. Możesz również przetestować go, aby sprawdzić, czy tak zrównoważone drzewa okażą się optymalne dla określonego rodzaju aplikacji.

W ten sposób omówiliśmy pięć interesujących pomysłów, które możesz studiować, badać i wypróbować. Przyjrzyjmy się teraz kilku projektom dotyczącym struktur danych i algorytmów.

Przeczytaj: Wynagrodzenie analityka danych w Indiach

6. Rycerskie zmagania

W tym projekcie zrozumiemy w działaniu dwa algorytmy – BFS i DFS. BFS oznacza Breadth-First Search i wykorzystuje strukturę danych kolejki, aby znaleźć najkrótszą ścieżkę. Natomiast DFS odnosi się do wyszukiwania na podstawie głębokości i przemierza struktury danych stosu.

Na początek będziesz potrzebować struktury danych podobnej do drzew binarnych. Załóżmy teraz, że masz standardową szachownicę 8 x 8 i chcesz pokazać ruchy skoczka w grze. Jak być może wiesz, podstawowe posunięcie skoczka w szachach to dwa kroki do przodu i jeden krok w bok. Zwrócony w dowolnym kierunku i mając wystarczającą liczbę tur, może przemieścić się z dowolnego pola na planszy na dowolne inne pole.

Jeśli chcesz poznać najprostszy sposób, w jaki twój rycerz może przejść z jednego pola (lub węzła) do drugiego w układzie dwuwymiarowym, musisz najpierw zbudować funkcję taką jak ta poniżej.

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

Ponadto projekt ten wymagałby następujących zadań:

• Tworzenie scenariusza do gry planszowej i wieczoru
• Traktowanie wszystkich możliwych ruchów rycerza jak dzieci w strukturze drzewa
• Zapewnienie, że żaden ruch nie zejdzie z planszy
• Wybór algorytmu wyszukiwania w celu znalezienia najkrótszej ścieżki w tym przypadku
• Zastosowanie odpowiedniego algorytmu wyszukiwania, aby znaleźć najlepszy możliwy ruch z pola początkowego do pola końcowego.

7. Szybkie struktury danych w językach systemów innych niż C

Programiści zwykle szybko budują programy przy użyciu języków wysokiego poziomu, takich jak Ruby lub Python, ale implementują struktury danych w C/C++. I tworzą kod wiążący, aby połączyć elementy. Uważa się jednak, że język C jest podatny na błędy, co może również powodować problemy z bezpieczeństwem. W tym tkwi ekscytujący pomysł na projekt.

Możesz zaimplementować strukturę danych w nowoczesnym języku niskiego poziomu, takim jak Rust lub Go, a następnie powiązać swój kod z językiem wysokiego poziomu. Dzięki temu projektowi możesz spróbować czegoś nowego, a także dowiedzieć się, jak działają wiązania. Jeśli Twój wysiłek się powiedzie, możesz nawet zainspirować innych do wykonania podobnego ćwiczenia w przyszłości i lepiej ukierunkować struktury danych na wydajność.

Przeczytaj także: Pomysły na projekty Data Science dla początkujących

8. Wyszukiwarka struktur danych

Oprogramowanie ma na celu zautomatyzowanie i przyspieszenie wyboru struktur danych dla danego API. Projekt ten nie tylko demonstruje nowe sposoby reprezentowania różnych struktur danych, ale także optymalizuje zestaw funkcji, aby wyposażyć w nie wnioskowanie. Poniżej zestawiliśmy jego podsumowanie.

• Projekt wyszukiwarki struktur danych wymaga wiedzy na temat struktur danych i relacji między różnymi metodami.
• Oblicza czas potrzebny na każdą możliwą złożoną strukturę danych dla wszystkich metod.
• Na koniec wybiera najlepsze struktury danych dla konkretnego przypadku.

Przeczytaj: Pomysły na projekty eksploracji danych

9. Aplikacja książki telefonicznej przy użyciu podwójnie połączonych list

Ten projekt może zademonstrować działanie aplikacji książki kontaktów, a także nauczyć Cię struktur danych, takich jak tablice, listy połączone, stosy i kolejki. Zazwyczaj zarządzanie książką telefoniczną obejmuje operacje wyszukiwania, sortowania i usuwania. Charakterystyczną cechą zapytań wyszukiwania jest to, że użytkownik widzi sugestie z listy kontaktów po wpisaniu każdego znaku. Możesz czytać kod źródłowy swobodnie dostępnych projektów i powielać je, aby rozwijać swoje umiejętności.

10. Indeksowanie przestrzenne z drzewami czwórkowymi

Struktura danych quadtree jest specjalnym rodzajem struktury drzewa, która może rekurencyjnie dzielić płaską przestrzeń 2D na cztery ćwiartki. Każdy węzeł hierarchiczny w tej strukturze drzewa ma zero lub czworo dzieci. Może być używany do różnych celów, takich jak przechowywanie rzadkich danych, przetwarzanie obrazu i indeksowanie przestrzenne.

Indeksowanie przestrzenne polega na wydajnym wykonywaniu wybranych zapytań geometrycznych, stanowiących istotną część projektowania aplikacji geoprzestrzennych. Na przykład aplikacje do wspólnego przejazdu, takie jak Ola i Uber, przetwarzają zapytania geograficzne w celu śledzenia lokalizacji taksówek i dostarczania aktualizacji użytkownikom. Funkcja znajomych w pobliżu Facebooka również ma podobną funkcjonalność. Tutaj powiązane metadane są przechowywane w postaci tabel, a indeks przestrzenny jest tworzony oddzielnie ze współrzędnymi obiektu. Celem problemu jest znalezienie najbliższego punktu do danego.

Możesz realizować projekty struktury danych w postaci czterodrzewa w wielu różnych dziedzinach, od mapowania, planowania urbanistycznego i planowania transportu po zarządzanie i łagodzenie skutków katastrof. Przedstawiliśmy krótki opis, który pomoże Ci w rozwiązywaniu problemów i umiejętnościach analitycznych.

Cel: Stworzenie struktury danych umożliwiającej następujące operacje

• Wstaw lokalizację lub przestrzeń geometryczną
• Wyszukaj współrzędne określonej lokalizacji
• Policz liczbę lokalizacji w strukturze danych w określonym ciągłym obszarze

11. Projekty oparte na grafach na strukturach danych

Możesz zająć się projektem dotyczącym topologicznego sortowania grafu. W tym celu będziesz potrzebować wcześniejszej znajomości algorytmu DFS. Oto podstawowa różnica między tymi dwoma podejściami:

• Wypisujemy wierzchołek, a następnie rekurencyjnie wywołujemy algorytm dla sąsiednich wierzchołków w DFS.
• W sortowaniu topologicznym najpierw rekurencyjnie wywołujemy algorytm dla sąsiednich wierzchołków. A następnie umieszczamy zawartość w stosie w celu wydrukowania.

Dlatego algorytm sortowania topologicznego pobiera skierowany graf acykliczny lub DAG, aby zwrócić tablicę węzłów.

Rozważmy prosty przykład zamówienia przepisu na naleśniki. Aby zrobić naleśniki, potrzebujesz określonego zestawu składników, takich jak jajka, mleko, mąka lub mieszanka naleśnikowa, olej, syrop itp. Te informacje, wraz z ilością i porcjami, można łatwo przedstawić na wykresie.

Ale równie ważne jest poznanie dokładnej kolejności stosowania tych składników. Tutaj możesz zaimplementować uporządkowanie topologiczne. Inne przykłady obejmują tworzenie wykresów pierwszeństwa w celu optymalizacji zapytań do bazy danych i harmonogramów dla projektów oprogramowania. Oto przegląd procesu w celach informacyjnych:

• Wywołaj algorytm DFS dla struktury danych wykresu, aby obliczyć czasy zakończenia dla wierzchołków
• Przechowuj wierzchołki na liście z malejącą kolejnością czasu zakończenia
• Wykonaj sortowanie topologiczne, aby zwrócić uporządkowaną listę

12. Reprezentacje numeryczne z losowymi listami dostępu

W reprezentacjach, które widzieliśmy w przeszłości, elementy liczbowe są na ogół utrzymywane w stosach dwumianowych. Ale te wzorce można również zaimplementować w innych strukturach danych. Okasaki wymyślił technikę reprezentacji numerycznej przy użyciu binarnych list losowego dostępu. Listy te mają wiele zalet:

• Umożliwiają wkładanie i wyjmowanie od początku
• Umożliwiają dostęp i aktualizację w określonym indeksie

Dowiedz się więcej: Sześć najczęściej używanych struktur danych w R

13. Edytor tekstu oparty na stosie

Twój zwykły edytor tekstu umożliwia edycję i przechowywanie tekstu podczas jego pisania lub edytowania. Tak więc istnieje wiele zmian w pozycji kursora. Aby osiągnąć wysoką wydajność, potrzebujemy szybkiej struktury danych do wstawiania i modyfikacji. A zwykłe tablice znaków wymagają czasu na przechowywanie ciągów.

Aby rozwiązać te problemy, możesz eksperymentować z innymi strukturami danych, takimi jak bufory przerw i liny. Twoim celem końcowym będzie osiągnięcie szybszej konkatenacji niż zwykłe ciągi poprzez zajmowanie mniejszej ciągłej przestrzeni pamięci.

Wniosek

Umiejętności tworzenia struktury danych stanowią podstawę tworzenia oprogramowania, zwłaszcza jeśli chodzi o zarządzanie dużymi zestawami danych w dzisiejszym ekosystemie cyfrowym. Wiodące firmy, takie jak Adobe, Amazon i Google, zatrudniają na różne lukratywne stanowiska w dziedzinie struktury danych i algorytmów. A na rozmowach kwalifikacyjnych rekruterzy sprawdzają nie tylko Twoją wiedzę teoretyczną, ale także umiejętności praktyczne. Więc przećwicz powyższe projekty struktury danych, aby wstawić stopę do drzwi!

Jeśli jesteś zainteresowany nauką o danych, sprawdź program IIIT-B i upGrad Executive PG w dziedzinie Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami z branży, 1 -on-1 z mentorami branżowymi, ponad 400 godzin nauki i pomocy w pracy z najlepszymi firmami.