Wprowadzenie do tablic w strukturze danych
Macierz jest rodzajem struktury danych służącym do przechowywania jednorodnych danych w ciągłych lokalizacjach pamięci. To wdraża pomysł przechowywania różnych przedmiotów, aby można je było odzyskać lub uzyskać do nich dostęp za jednym razem.
Tutaj indeks odnosi się do położenia elementu w tablicy. Wyobraźmy sobie, że P (L) to nazwa tablicy, gdzie „P” to nazwa zmiennej, a „L” to długość tablicy, tj. Liczba elementów obecnych w tablicy. Następnie P (i) reprezentuje element w tym 'i + 1' pozycji w tablicy.
Na przykład:
P (6) = 72 oznacza element w 6 + 1 miejscu tablicy.
Need of Array: Pomaga reprezentować dużą liczbę elementów za pomocą jednej zmiennej. Ułatwia także dostęp do elementu w celu łatwiejszego przechowywania w miejscu pamięci za pomocą indeksu tablicy, który reprezentuje lokalizację elementu w tablicy.
Jak działają tablice w strukturze danych?
Tablica przechowuje zmienne w ciągłych lokalizacjach i nadaje im określony indeks. Gdy ktoś chce pobrać dane, osoba korzysta z tego indeksu. W podanej powyżej tablicy „P” powiedz adres bazowy dla tablicy = 100, a następnie elementy są przechowywane jak poniżej:
Pamięć przydzielona do tablicy może być obliczona jako:
- Tablica jednowymiarowa: całkowita pamięć przypisana do tablicy = liczba elementów * rozmiar jednego elementu, na przykład: w powyższym przypadku pamięć = 7 * (rozmiar int)
- Rząd Major Order: Całkowita pamięć przydzielona do tablicy 2D = liczba elementów * rozmiar jednego elementu
= Liczba rzędów * liczba kolumn * rozmiar jednego elementu - Kolumna Główne zamówienie: Całkowita pamięć przydzielona na tablicę 2D = liczba elementów * rozmiar jednego elementu
= Liczba rzędów * liczba kolumn * rozmiar jednego elementu
Jak zdefiniować tablice?
Zatem tablicę można zdefiniować jako pochodną strukturę danych do przechowywania jednorodnych danych pierwotnego typu danych w ciągłych lokalizacjach pamięci. Poniżej znajdują się operacje, które można wykonać na tablicach:
1. Wstawienie: Odnosi się do wstawiania elementu do tablicy o określonym indeksie. Można to wykonać przy złożoności O (n).
2. Usuwanie: Odnosi się to do usunięcia elementu z określonego indeksu. Ta operacja wymaga przesunięcia elementów po usunięciu, dlatego przyjmuje złożoność O (n).
3. Wyszukiwanie: Odnosi się do uzyskiwania dostępu do elementu pod określonym indeksem tablicy.
4. Przechodzenie: Odnosi się do drukowania wszystkich elementów tablicy jeden po drugim.
Właściwości tablic w strukturze danych
Poniżej znajdują się właściwości tablic w strukturze danych:
- Jest to typ danych pochodnych, składający się z kolekcji różnych pierwotnych typów danych, takich jak int, char, float itp.
- Elementy tablicy są przechowywane w ciągłych blokach w pamięci podstawowej.
- Nazwa tablicy przechowuje adres bazowy tablicy. Działa jako wskaźnik do bloku pamięci, w którym został zapisany pierwszy element.
- Indeksy tablic zaczynają się od 0 do N-1 w przypadku tablicy jednowymiarowej, gdzie n oznacza liczbę elementów w tablicy.
- Elementy tablicy mogą składać się tylko ze stałych i wartości literalnych.
Jak tworzyć tablice?
Możemy tworzyć tablice przy użyciu poniższej składni:
1. Tablica wymiarowa: var = (c1, c2, c3, …… .cn)
Tutaj var odnosi się do zmiennej do tablicy, która przechowuje podstawową lokalizację tablicy. I c1, c2… są elementami tablicy.
Przykład: int a = (4, 6, 7, 8, 9)
Długość tablicy = n
2. Tablica wielowymiarowa : var = ((r 01, … r 0n ), (r 10, … ..r 1n )… .. (r m0 … .r mn ))
Tutaj var odnosi się do nazwy tablicy m wierszy i n kolumn.
Jak uzyskać dostęp do elementu tablic?
Indeksy tablicy zaczynają się od 0 do -1.0, co oznacza pierwszy element tablicy, a -1 oznacza ostatni element tablicy. Podobnie -2 wskazuje na przedostatni element tablicy. Załóżmy, że istnieje tablica „A” zawierająca 10 elementów. Następnie tutaj Zmienna przechowuje odwołanie do pierwszej zmiennej tablicy, która nazywa się „Adresem podstawowym” tablicy. Następnie, jeśli ktoś chce uzyskać dostęp do elementu tablicy, adres tego elementu jest obliczany przy użyciu poniższego wzoru.
Adres i-tego elementu = adres podstawowy + i * rozmiar każdego elementu
Tutaj rozmiar każdego elementu odnosi się do pamięci zajmowanej przez różne pierwotne typy danych, które przechowuje tablica. Na przykład int zajmuje 2 bajty miejsca, a float zajmuje 4 bajty miejsca w C.
Dostęp do tablicy wielowymiarowej
Powiedzmy, że A (r l, …… .., r u ) (c u, ……, c l ) jest tablicą wielowymiarową, a rl, ru, cu, c l są dolnymi i górnymi granicami wierszy i kolumn. Niż Liczba wierszy w A, powiedzmy NR = r u - r l +1 i Liczba kolumn w A, powiedzmy NC = c l - c u +1.
Teraz, aby znaleźć adres elementu w tablicy, istnieją 2 metody:
- Wiersz główny: tam, gdzie przechodzimy rząd po rzędzie.
Adres A (i) (j) = Adres bazowy + ((i - r l ) * NC + (j- c l )) * rozmiar każdego elementu.
- Główna kolumna: Gdzie przechodzimy kolumna po kolumnie.
Adres A (i) (j) = Adres bazowy + ((i - r l ) + (j- c l ) * NR) * rozmiar każdego elementu.
Złożoność: Dostęp do dowolnego elementu w tablicy jest znacznie łatwiejszy i można to zrobić w złożoności O (1).
Wniosek
Tablice są bardzo unikalnym sposobem strukturyzowania przechowywanych danych, dzięki czemu można do nich łatwo uzyskać dostęp i można je uzyskać w celu pobrania wartości o określonej liczbie za pomocą wartości indeksu. Mimo że wstawienie elementu do tablicy zajmuje dużo czasu, ponieważ wymaga całkowitego przestawienia i przesunięcia istniejących elementów tablicy. Nadal służy do implementacji różnych innych złożonych struktur danych, takich jak drzewo, kolejka lub stos, a także jest wykorzystywany w różnych algorytmach.
Polecany artykuł
Jest to przewodnik po tablicach w strukturze danych. Tutaj omawiamy sposób tworzenia i uzyskiwania dostępu do elementów macierzy w strukturze danych wraz z właściwościami. Możesz również przejrzeć nasze inne powiązane artykuły, aby dowiedzieć się więcej -
- Jak tworzyć tablice w PHP?
- Tablice w Javie Programowanie Zalety i wady
- Tablice w programowaniu C (przykłady)
- 10 najważniejszych pytań do wywiadu dotyczącego struktury danych