Co to jest struktura danych wektorowych

Question

Znam wektor w C++ i Javie, to jak dynamiczna tablica, ale nie mogę znaleźć żadnej ogólnej definicji struktury danych wektorowych. Czym więc jest Vector? Czy Vector to ogólna struktura danych (np. Arrray, stack, queue, tree, ...) czy tylko typ danych w zależności od języka?

Answer 1

Jest to tablica z dynamicznie przydzielonym miejscem, za każdym razem, gdy przekroczysz tę przestrzeń, przydzielane jest nowe miejsce w pamięci, a stara tablica jest kopiowana do nowej. Stary zostaje wtedy uwolniony.

Co więcej, wektor zazwyczaj przydziela więcej pamięci, niż musi, więc nie musi kopiować wszystkich danych po dodaniu nowego elementu.

Może się wydawać, że listy są o wiele lepsze, ale niekoniecznie tak jest. Jeśli nie zmieniasz często wektora (pod względem wielkości), to pamięć podręczna komputera działa znacznie lepiej w przypadku wektorów niż list, ponieważ są one ciągłe w przestrzeni pamięci. Wadą jest, gdy masz duży wektor, który musisz rozwinąć. Następnie musisz zgodzić się na kopiowanie dużej ilości danych do innej przestrzeni w pamięci.

Co więcej. Możesz dodać nowe dane na końcu i na początku wektora. Ponieważ wektor jest podobny do tablicy, to za każdym razem, gdy chcesz dodać element na początku wektora, cała tablica musi zostać skopiowana. Dodawanie elementów do końca wektora jest znacznie bardziej efektywne. Nie ma takiego problemu z połączonymi listami.

Wektor daje losowy dostęp do przechowywanych w nim danych, podczas gdy listy, kolejki i stosy nie.

Answer 2

Słowo "wektor" stosowane w informatyce/programowaniu jest zapożyczone z matematyki, co może sprawić, że użycie będzie mylące (nawet twoje pytanie może dotyczyć wielu tematów).

Najprostszym przykładem wektorów w matematyce jest linia liczbowa używana do nauczania matematyki elementarnej (szczególnie w celu wizualizacji liczb ujemnych, odejmowania liczb ujemnych, dodawania liczb ujemnych itp.).

Wektor jest odległością i kierunkiem od punktu. Dlatego może zmylić dyskusję, ponieważ struktura danych wektorowych może składać się z trzech punktów, X, Y, Z w strukturze wykorzystywanej w silnikach graficznych 3D lub punktu 2D (tylko X, Y). W tym kontekście odjęcie dwóch takich punktów powoduje powstanie wektora - wektor opisuje, jak daleko i w jakim kierunku przejść od jednego z argumentów źródłowych do drugiego.

Dotyczy to pamięci masowej, np. Wektorów stl lub wektorów Java, w której pamięć jest reprezentowana jako odległość od adresu (gdzie adres pamięci jest podobny do punktu w przestrzeni lub na linii numerycznej).

Pojęcie jest związane z tablicami, ponieważ tablice mogą być przestrzenią przeznaczoną dla wektora, ale twierdzę, że wektor jest większym pojęciem niż tablica. Wektor musi zawierać pojęcie odległości od punktu początkowego, a jeśli myślisz o początku tablicy jako punkcie początkowym, odległość do końca tablicy jest jej rozmiarem.

Tak więc struktura danych reprezentująca wektor musi zawierać rozmiar, podczas gdy tablica nie ma pamięci do uwzględnienia rozmiaru, zakłada się ją poprzez sposób przydzielenia. Oznacza to, że jeśli dynamicznie przydzielisz tablicę, nie ma struktury danych przechowującej rozmiar tej tablicy, programista musi założyć, że zna ten rozmiar, lub przechowywać go w pewnej liczbie całkowitej lub długiej.

Struktura danych wektorowych (powiedzmy, projekt klasy wektorowej) Trzeba przechowywać rozmiar, więc przynajmniej będzie punkt początkowy (podstawa tablicy lub jakiś adres w pamięci) i odległość od tego punktu wskazująca rozmiar.

To naprawdę "RAM" zorientowane, choć w opisie, ponieważ jest jeszcze jeden punkt, który nie został jeszcze opisany, który musi być częścią danych opisujących wektor - pojęcie wielkości elementu. Jeśli wektor reprezentuje bajty, a pamięć jest zwykle mierzona w bajtach, adres i odległość (lub rozmiar) będą reprezentowały wektor bajtów, ale nic więcej - i to jest myślenie na poziomie maszynowym. Wyższa myśl, że jakiejś struktury, ma swój własny rozmiar - powiedzmy, rozmiar float lub double, lub struktury lub klasy w C++. Bez względu na rozmiar elementu, pamięć wymagana do przechowywania N z nich wymaga, aby struktura danych wektorowych posiadała pewną wiedzę o tym, CO jest przechowywana i jak duża jest ta rzecz. Dlatego możesz myśleć w kategoriach "wektor ciągów" lub "wektor punktów". Wektor musi również przechowywać rozmiar elementu.

Więc podstawową strukturą danych wektor musi mieć:

adresu (punkt wyjścia)

rozmiaru elementu (każda rzecz przechowuje jest X bajtów)

szereg elementów przechowywane (ile elementów razy rozmiar elementu jest "minimalnym" rozmiarem pamięci).

Jednym z ważnych "założeń" dokonanych na tej prostej liście pozycji w strukturze danych wektorowych jest to, że adresowi przydzielono pamięć, która musi zostać zwolniona w pewnym momencie i ma być chroniona przed dostępem poza końcem wektor.

To oznacza, że ​​czegoś brakuje. Aby klasa wektorowa działała, istnieje zauważalna różnica między liczbą ELEMENTÓW przechowywanych w wektorze a ilością pamięci ALLOCATED dla tego magazynu. Zazwyczaj, jak można sobie wyobrazić, używając wektora z STL, może on "wiedzieć", że ma miejsce do przechowywania 10 przedmiotów, ale obecnie ma tylko 2 z nich.

Tak więc klasa wektorów roboczych również musi przechowywać ilość przydzielonej pamięci. Byłby to sposób, w jaki mógłby dynamicznie się rozszerzać - miałby teraz wystarczającą ilość informacji do automatycznego rozszerzenia pamięci.

Przemyślenie sposobu, w jaki można operować klasą wektorową, zapewnia strukturę danych wymaganych do obsługi klasy wektorowej.