data-structures Samouczek
Pierwsze kroki ze strukturami danych

Uwagi

Wprowadzenie do struktur danych

Struktura danych to sposób organizowania i przechowywania informacji.

Niech „Witaj, świecie!” string to informacja, którą potrzebujemy uporządkować i przechowywać w pamięci bajtowej.

Każdy znak ASCII wymaga 7 bitów pamięci. Większość systemów rezerwuje 8 bitów (1 bajt) na każdą postać, więc każda postać w „Witaj, świecie!” jest przechowywany w jednej bajtowej jednostce pamięci, jedna po drugiej, kolejno.

Potrzebujemy pojedynczego odwołania do naszego ciągu, nawet jeśli obejmuje on wiele adresów pamięci, dlatego używamy adresu pierwszego znaku w ciągu, „H”. Do każdego innego znaku można uzyskać dostęp pod adresem „H” + indeks tego znaku za pomocą znaków o indeksie zerowym.

Chcemy wydrukować nasz ciąg „Witaj, świecie!” Znamy jego adres w pamięci, który podajemy do funkcji drukowania, ale skąd funkcja drukowania wie, aby przestać drukować kolejne lokalizacje pamięci? Jednym z powszechnych podejść jest dołączanie do łańcucha znaku zerowego „\ 0”. Gdy funkcja drukowania napotka znak zerowy, wie, że osiągnęła koniec łańcucha.

Zdefiniowaliśmy sposób organizowania i przechowywania naszego łańcucha, tj. Strukturę danych! Ta bardzo prosta struktura danych to tablica znaków zakończona znakiem null, która jest jednym ze sposobów porządkowania i przechowywania łańcucha.

Tablica: prosta struktura danych

Struktura danych tablicowych służy do przechowywania podobnych obiektów (lub wartości danych) w ciągłym bloku pamięci. Struktura danych macierzy ma stały rozmiar, który określa liczbę wartości danych, które można w niej zapisać.

Array: The C ++ Way

W języku programowania C ++ możemy zadeklarować tablicę statyczną w następujący sposób

int arrayName[100];

Tutaj zadeklarowaliśmy tablicę o nazwie „arrayName”, która może przechowywać do 100 wartości, z których wszystkie są tego samego typu, czyli liczb całkowitych.

Teraz omówimy niektóre zalety i wady tej struktury danych

1. Możemy uzyskać dostęp do wartości danych przechowywanych w tablicy w czasie stałym, czyli złożoność czasu wynosi O (1) . Więc jeśli chcemy uzyskać dostęp do wartości danych przechowywanych w i-tej pozycji, nie musimy zaczynać od pozycji początkowej i przechodzić do i-tej pozycji, ale możemy bezpośrednio przeskoczyć do i-tej pozycji, oszczędzając w ten sposób czas obliczeniowy.
2. Wstawienie elementu na środku tablicy nie jest wydajnym zadaniem. Załóżmy, że chcemy dodać nowy element do tablicy w i-tej pozycji, a następnie musimy najpierw przesunąć wszystkie elementy w (i-tej) i (i + 1-ej) pozycji, aby stworzyć miejsce dla nowego elementu. Przykład: 1 4 2 0 to tablica z 4 elementami, teraz chcemy wstawić 3 na 2 pozycji, następnie musimy przesunąć 4,2 i 0 o jedną pozycję dalej, aby stworzyć miejsce na 3.

  1 3 4 2 0

3. Podobnie jak wstawianie elementu, usuwanie elementu z i-tej pozycji w tablicy również nie jest skuteczne, ponieważ musimy przesunąć wszystkie elementy przed usuniętym elementem o 1 blok, aby wypełnić wolne miejsce utworzone przez usunięte element.

Są to 3 proste cechy macierzy. Tutaj możesz sądzić, że macierz nie jest wydajną strukturą danych, ale w praktyce przewaga macierzy może przewyższać jej wady. Zależy to w dużej mierze od celu, któremu chcesz służyć, być może nie chcesz wstawiać ani usuwać elementu tak często, jak chcesz uzyskać do nich dostęp, w takim przypadku tablica jest absolutnie idealną strukturą danych.

Jedynym celem wprowadzenia tej struktury danych jest upewnienie się, że po prostu nie wybierasz Struktury danych na podstawie liczby zalet i wad, ale zawsze powinieneś próbować analizować znaczenie Struktury danych, biorąc pod uwagę swój problem, na przykład: jeśli będziesz spędzać dużo czasu na uzyskiwaniu dostępu do wartości danych w porównaniu do ich wstawiania lub usuwania, w takim przypadku musimy zwiększyć wagę przewagi nad wadą.