C-keeles ühendatud loendid: täielik juhend rakendamisest ja kasutamisest

1. Sissejuhatus

Loendistruktuuri olulisus

• Järjestatud andmete haldamine
• Kui on vaja andmeid dünaamiliselt lisada või kustutada
• Mälu tõhus kasutamine

Artikli eesmärk

Õpieesmärgid

1. Mõista loendistruktuuri aluseid.
2. Õppida ühendatud loendi rakendamist C-keeles.
3. Omandada rakendusoskus praktiliste koodinäidete abil.

2. Mis on loendistruktuur?

Loendistruktuuri põhimõisted

1. Andmeosa: tegelik väärtus, mida hoitakse.
2. Lingi osa: viit (pointer) järgmisele sõlmele.

Massiivi ja loendi erinevused

Ühendatud loendi ülevaade ja omadused

1. Dünaamiline suuruse muutmine Sõlmi saab lisada ja kustutada vastavalt vajadusele, mis võimaldab tõhusat mäluhaldust.
2. Lihtne sõlmede lisamine / kustutamine Viitade ümberseadistamisega saab elemente hõlpsalt hallata ka loendi keskel või lõpus.
3. Otsing on aeglasem Andmetele pääseb ligi järjestikku algusest, mistõttu konkreetse elemendi leidmine võtab rohkem aega.

Ühendatud loendi tüübid

1. Ühesuunaline loend Iga sõlm viitab ainult järgmisele sõlmele.

• Lihtne struktuur ja väike mälukasutus.
• Liikumine võimalik ainult ühes suunas, tagasi liikumine pole võimalik.

1. Kahesuunaline loend Iga sõlm viitab nii järgmisele kui ka eelmisele sõlmele.

• Võimaldab liikuda edasi-tagasi, pakkudes paindlikke toiminguid.
• Kasutab rohkem mälu kui ühesuunaline loend.

1. Ringloend Viimane sõlm viitab esimesele sõlmele.

• Loendi lõppu jõudes saab uuesti algusesse liikuda, sobib tsükliliste protsesside jaoks.
• Kasulik spetsiaalsetes rakendustes.

3. Ühendatud loendi rakendamine C-keeles

Ühendatud loendi põhistruktuur

1. Sõlme definitsioon

• Iga sõlm sisaldab andmeid ja viita järgmisele sõlmele.

1. Peesõlm (head pointer)

• Viitab loendi esimesele elemendile ja haldab kogu loendit.

Koodinäide: Ühendatud loendi põhiteostus

#include <stdio.h>
#include <stdlib.h>

// Sõlme definitsioon
typedef struct Node {
    int data;                 // Andmeosa
    struct Node* next;        // Viit järgmisele sõlmele
} Node;

// Uue sõlme loomine
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Mälureservatsioon
    if (newNode == NULL) {
        printf("Mälu broneerimine ebaõnnestus.\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL; // Algseisus ei viita järgmisele sõlmele
    return newNode;
}

// Sõlme lisamine (loendi algusesse)
void insertAtHead(Node** head, int data) {
    Node* newNode = createNode(data); // Uue sõlme loomine
    newNode->next = *head;            // Uus sõlm viitab praegusele esimesele sõlmele
    *head = newNode;                  // Peaviit uuendatakse uuele sõlmele
}

// Loendi väljastamine
void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Mälu vabastamine
void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp); // Mälu vabastamine
    }
}

int main() {
    Node* head = NULL; // Algväärtus: tühi loend

    // Andmete lisamine loendisse
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);

    // Loendi väljastamine
    printList(head);

    // Mälu vabastamine
    freeList(head);

    return 0;
}

Koodi selgitus

1. Sõlme loomine

• Uus sõlm luuakse dünaamilise mälureservatsiooni abil.

1. Sõlme lisamine

• Andmeid saab lisada loendi algusesse või lõppu, et seda laiendada.

1. Sõlme kustutamine

• Kustutab sõlme, millel on konkreetne väärtus, või esimese sõlme.

1. Mälu haldamine

• Kasutamata mälu vabastatakse, et vältida mäluleke.

4. Ühendatud loendi tüübid

1. Ühesuunaline loend

• Elemendid liiguvad ainult ühes suunas.
• Väike mälukasutus ja lihtne teostus.

• Dünaamiline suurus – paindlik kohanemine.
• Elementide lisamine ja eemaldamine on efektiivne.

• Tagasiliikumine pole võimalik, mistõttu vastupidine otsing on ebaefektiivne.

2. Kahesuunaline loend

• Kahe viida (prev/next) olemasolu.
• Liikumine mõlemas suunas.

• Lihtsam kustutada või sisestada sõlmi suvalises kohas.
• Tagurpidi läbimine on mugav.

• Suurem mälukulu kui ühesuunalisel loendil.
• Keerukam teostus (viitade hoolikas uuendamine).

3. Ringloend

• Pole otsest lõppu – läbimine võib jätkuda lõpmatuseni.
• Võib olla ühesuunaline või kahesuunaline.

• Lihtne liikuda pea ja saba vahel – sobib tsükliliste protsesside jaoks.
• Hea järjekordade ja puhvrite rakendustes.

• Lõpu puudumine nõuab ettevaatlikkust otsingu ja kustutamise teostamisel.

Võrdlustabel

5. Ühendatud loendi toimingud

1. Elementide sisestamine

(1) Lisamine loendi algusesse

void insertAtHead(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head; // Uus sõlm viitab praegusele peale
    *head = newNode;       // Uus sõlm saab peaks
}

(2) Lisamine loendi lõppu

void insertAtTail(Node** head, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if (*head == NULL) { // Tühi loend
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) { // Liigu viimase sõlmeni
        temp = temp->next;
    }
    temp->next = newNode; // Lisa lõppu
}

2. Elementide kustutamine

(1) Eelemendi (pea) kustutamine

void deleteAtHead(Node** head) {
    if (*head == NULL) {
        printf("Loend on tühi.\n");
        return;
    }
    Node* temp = *head;
    *head = (*head)->next; // Nihuta peaviit järgmisele
    free(temp); // Vabasta mälu
}

(2) Konkreetses väärtuses sõlme kustutamine

void deleteNode(Node** head, int key) {
    Node* temp = *head;
    Node* prev = NULL;

    // Kui esimene sõlm on sihtmärk
    if (temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    // Otsi kustutatav sõlm
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) {
        printf("Väärtust ei leitud.\n");
        return;
    }

    prev->next = temp->next;
    free(temp);
}

3. Elementide otsing

int search(Node* head, int key) {
    Node* temp = head;
    int position = 0;

    while (temp != NULL) {
        if (temp->data == key) {
            return position; // Tagasta leitud asukoht
        }
        temp = temp->next;
        position++;
    }
    return -1; // Mitte leitud
}

4. Loendi kuvamine

void printList(Node* head) {
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

Kokkuvõte

• Sisestamine: tugi pea-, saba- ja (laiendatuna) suvalise positsiooni lisamiseks.
• Kustutamine: pea või kindla väärtusega sõlme eemaldamine.
• Otsing: tagastab leitud elemendi positsiooni või -1.

6. Mälu haldamise tähelepanekud

1. Mis on dünaamiline mälureservatsioon?

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Broneeri mälu
    if (newNode == NULL) { // Kontrolli ebaõnnestumist
        printf("Mälu broneerimine ebaõnnestus.\n");
        exit(1); // Lõpeta programm
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

2. Mälukasutuse vabastamise olulisus

void freeList(Node* head) {
    Node* temp;
    while (head != NULL) {
        temp = head;         // Hoia hetkesõlme
        head = head->next;   // Liigu järgmisele
        free(temp);          // Vabasta mälu
    }
}

3. Parimad tavad mäluleke vältimiseks

1. Vabasta mälu järjekindlalt

• Vabasta alati mälu kohe, kui seda enam ei vajata.

1. Kasuta silurivahendeid

• Valgrind ja AddressSanitizer aitavad lekkeid tuvastada.

valgrind --leak-check=full ./a.out

3. Halda viitasid selgelt

• Määra omandiõigus ja väldi sama viida manipuleerimist mitmes kohas.
• Pärast kasutust sea viit NULL-iks, et vältida topeltkasutust.

7. Rakendusnäited ja praktika

1. Pinu (LIFO) teostus

Koodinäide: pinu ühendatud loendiga

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { printf("Mälu broneerimine ebaõnnestus.\n"); exit(1); }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

void push(Node** top, int data) {
    Node* newNode = createNode(data);
    newNode->next = *top;
    *top = newNode;
}

int pop(Node** top) {
    if (*top == NULL) {
        printf("Pinu on tühi.\n");
        exit(1);
    }
    Node* temp = *top;
    int poppedData = temp->data;
    *top = (*top)->next;
    free(temp);
    return poppedData;
}

void printStack(Node* top) {
    while (top != NULL) {
        printf("%d -> ", top->data);
        top = top->next;
    }
    printf("NULL\n");
}

int main() {
    Node* stack = NULL;

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("Pinu sisu: ");
    printStack(stack);

    printf("Võetud väärtus: %d\n", pop(&stack));
    printf("Võetud väärtus: %d\n", pop(&stack));

    printf("Pinu sisu: ");
    printStack(stack);

    return 0;
}

2. Järgu (FIFO) teostus

Koodinäide: järk ühendatud loendiga

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    if (!q) { printf("Mälu broneerimine ebaõnnestus.\n"); exit(1); }
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) { printf("Mälu broneerimine ebaõnnestus.\n"); exit(1); }
    newNode->data = data;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("Järk on tühi.\n");
        exit(1);
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return data;
}

void printQueue(Queue* q) {
    Node* temp = q->front;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main() {
    Queue* q = createQueue();

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);

    printf("Järgu sisu: ");
    printQueue(q);

    printf("Väljavõetud väärtus: %d\n", dequeue(q));
    printf("Väljavõetud väärtus: %d\n", dequeue(q));

    printf("Järgu sisu: ");
    printQueue(q);

    return 0;
}

Kokkuvõte

• Pinu (LIFO) sobib rekursiooni haldamiseks ja avaldiste hindamiseks.
• Järk (FIFO) sobib puhverdamiseks ja tööde järjekordadele.

8. Kokkuvõte

1. Olulised punktid

Alused

• Ühendatud loend on dünaamilise suurusega ja väga paindlik.
• Erinevalt massiivist on lisamine/kustutamine lihtne, kuid otsing on järjestikuline.

Teostus ja toimingud

• Näitasime sõlme loomist, sisestamist, kustutamist ja otsingut koodinäidetega.
• Korralik mäluhaldus tagab stabiilsuse ja jõudluse.

Tüübid ja kasutus

• Ühesuunaline – lihtne ja kerge.
• Kahesuunaline – mugav edasitagasi liikumiseks.
• Ringloend – sobib tsükliliste protsesside jaoks.

Rakendused

• Pinu ja järk ühendatud loendiga – kasulikud paljudes süsteemi- ja algoritmitöödes.

2. Omandatud oskused

• Andmestruktuuride mõistmine
• Praktiline C-programmeerimine
• Probleemilahendus oskus

3. Mida edasi õppida

1. Andmestruktuuride laiendused

• Puu-struktuurid (binaarpuu, AVL)
• Graafialgoritmid (BFS, DFS)

1. Täiustatud andmehaldus

• Hash-tabelid ja map-struktuurid
• Dünaamiliste massiivide ja loendite hübriidid

1. Algoritmide optimeerimine

• Sortimise ja otsingu optimeerimine
• Aja- ja ruumikompleksuse analüüs

4. Praktilised projektid

• Ülesannete haldus (to-do rakendus loenditega)
• Simulatsioonid (sündmuste töötlus järkudega)
• Andmeanalüütika tööriistad (puhvrid ja vootöötlus)

5. Lõpetuseks