Pole vs. propojený seznam – rozdíl mezi polem a propojeným seznamem

Přemýšleli jste někdy, jak jsou data uložena v paměti počítače? Nemůžete jen tak naházet data do paměti, aniž byste pro ně vytvořili vhodnou strukturu.

Pro zajištění organizované struktury pro ukládání dat uvnitř paměti počítače, abychom mohli uložená data používat a spravovat co nejefektivněji, používáme datové struktury.

Všechny programovací jazyky poskytují základní datové struktury jako int, char, float atd. pro ukládání hodnot primitivního typu. Pomocí uživatelsky definovaných datových typů však můžeme vytvářet datové struktury podle potřeby. Je to podobné, jako když si vytváříme dům z cihel, můžeme si vytvořit jakýkoli typ struktury, kterou chceme.

V tomto článku si ukážeme dva nejčastěji používané uživatelsky definované datové typy:

Pole

Nejjednodušším typem datové struktury je pole, které slouží k uložení množiny podobných dat v souvislých blocích paměti pod společnou hlavičkou nebo názvem proměnné. S jeho jednoduchostí se pojí určité překážky, jako že potřebuje souvislý blok paměti, a pokud není k dispozici volná paměť v souvislém bloku, stává se použití pole neefektivní.

Prezentace pole

Prezentace pole (zdroj)

Indexace pole začíná od 0 a ke každému prvku pole lze přistupovat pomocí jeho indexu. Operace s polem je velmi rychlá, protože ke každému prvku lze přistupovat přímo pomocí indexace pole. Jméno pole je základní adresa pole a ke všem ostatním prvkům lze přistupovat pomocí základní adresy, protože paměť přidělená poli je souvislá.

Spojený seznam

Na druhé straně jednoduchou, ale velmi užitečnou datovou strukturou, která nepotřebuje souvislé bloky paměti, je spojený seznam. Používají se v situacích, kdy je potřeba alokovat paměť dynamicky, tedy za běhu programu. Lze si jej představit jako vlak, kde máme lokomotivu (hlavu) a všechny vagóny (uzly) jsou propojeny s lokomotivou vlaku buď přímo, nebo nepřímo přes jiné vagóny.

Prezentace propojeného seznamu

Prezentace propojeného seznamu (zdroj)

Propojený seznam je uživatelsky definovaný datový typ, kde jsou všechny uzly seznamu propojeny pomocí ukazatelů. Pro přístup k libovolnému uzlu seznamu musíme seznamem lineárně procházet na rozdíl od pole, kde můžeme k prvkům přistupovat přímo.

Pole vs. propojený seznam – rozdíl mezi polem a propojeným seznamem

Parametry Pole Propojený seznam
Definice Jedná se o kolekci prvků se stejným datovým typem se společným názvem. Je to uspořádaná kolekce prvků, které jsou propojeny odkazy nebo ukazateli.
Velikost Fixní, jednou deklarovaná, nelze ji měnit. Proměnná, lze ji měnit za běhu.
Alokace paměti Vyžaduje souvislé bloky paměti. Může být alokována náhodná paměť.
Přístup Přímý nebo náhodný přístup, tj, Zadejte index pole nebo index podskupiny. Sekvenční přístup, tj, Procházet od prvního uzlu v seznamu pomocí ukazatele.
Vkládání a mazání Relativně pomalé, protože k vložení nebo smazání jakéhokoli prvku je třeba posunout jiné prvky, aby obsadily prázdné místo nebo vytvořily prostor. Rychlejší, jednodušší a efektivnější, protože stačí pouze propojit nebo odpojit uzel.
Vyhledávání Binární vyhledávání a lineární vyhledávání Lineární vyhledávání
Mimořádný prostor Mimořádný prostor není potřeba. K propojení uzlů seznamu se používají ukazatele, které vyžadují další prostor.
Využití paměti Neefektivní Efektivní
Typy Může být jednorozměrný, dvourozměrný nebo vícerozměrný. Může být jedno-, dvou- nebo kruhově propojený seznam.

Implementace pole v jazyce C++

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;
int main()
{
int arr; // deklarace celočíselného pole o velikosti 5
arr=5; // přiřazení hodnot prvkům pole
arr=4; // všimněte si, že indexování pole začíná od 0 a končí na velikosti-1
arr=3;
arr=2;
arr=1;
for(int i=0;i<5;i++)
cout<<arr<<“ „; // výpis prvků pole
return 0;
}

Výstup

5 4 3 2 1

Implementace propojeného seznamu v C++

1
2
3

.

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<iostream>
using namespace std;
/* Vytvoření uživatelsky definované struktury pro uložení dat v propojeném seznamu */
struct Node
{
int data;
struct Node *next; // ukazatel na propojené uzly seznamu
};
struct Node* head = NULL; // Zpočátku není v seznamu žádný prvek, takže head ukazuje nikam
/* funkce pro vložení a propojení uzlů do seznamu */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // dynamická alokace paměti
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
/* funkce pro zobrazení dat seznamu */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<“ „;
ptr = ptr->next;
}
}
int main()
{
insert(5); // vložení dat do seznamu
insert(1);
insert(4);
insert(6);
insert(7);
cout<<„Spojový seznam je: „
display();
return 0;
}

Výstup

Spojený seznam je: 7 6 4 1 5

Video výukový program

Leave a Reply

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna.