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

1. Sissejuhatus

C-keel on programmeerimiskeel, mida kasutatakse laialdaselt süsteemiprogrammeerimises ja manussüsteemide arendamisel. Nende hulgas on „loendistruktuur” väga kasulik tööriist andmete haldamiseks ja töötlemiseks. Selles artiklis selgitatakse üksikasjalikult C-keele loendistruktuuri, alustades põhimõistetest ja lõpetades konkreetsete rakendusnäidetega.

Loendistruktuuri olulisus

Loendistruktuur on andmestruktuur, mis võimaldab hallata andmeid säilitades nende järjekorra. See on eriti kasulik järgmistel juhtudel:

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

Näiteks ülesannete haldamise rakenduses lisatakse ja kustutatakse ülesandeid sageli, mistõttu on paindlik loendistruktuur sobivam kui massiiv.

Artikli eesmärk

Selles artiklis rakendame C-keeles loendistruktuuri ning tutvustame selle kasutamist koos konkreetsete koodinäidetega. Lõpptulemusena mõistab lugeja loendistruktuuri põhikontseptsiooni ja praktilist kasutust ning oskab seda oma programmides rakendada.

Õ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?

Loendistruktuur on üks andmestruktuuridest, mis võimaldab andmeid hallata kindlas järjekorras. Selles jaotises selgitame loendistruktuuri põhimõisteid ja tüüpe.

Loendistruktuuri põhimõisted

Loendistruktuur koosneb omavahel aheldatud andmeüksustest (sõlmedest). Iga sõlm sisaldab kahte tüüpi teavet:

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

Tänu sellele mehhanismile saab andmeid dünaamiliselt lisada ja kustutada, mis muudab selle mugavaks muutuvpikkusega andmete töötlemisel.

Massiivi ja loendi erinevused

Loendistruktuur ja massiiv erinevad andmete haldamise viisi poolest järgmiselt:

Nagu näha, sobib loendistruktuur olukordadesse, kus on vaja paindlikkust, samas kui massiiv sobib juhtudeks, kus on oluline kiire andmepääs.

Ühendatud loendi ülevaade ja omadused

Loendistruktuuri tuntud näide on „ühendatud loend”, millel on järgmised 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

Ühendatud loendil on kolm peamist tüüpi:

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.

Järgmises jaotises selgitame „Ühendatud loendi rakendamist C-keeles” koos konkreetsete koodinäidetega.

3. Ühendatud loendi rakendamine C-keeles

Selles jaotises selgitame, kuidas rakendada ühendatud loendit C-keeles koos konkreetsete koodinäidetega.

Ühendatud loendi põhistruktuur

Ühendatud loend koosneb järgmistest elementidest:

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

Alljärgnev on näide koodist ühendatud loendi haldamiseks.

#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

Selles jaotises tutvustame peamisi ühendatud loendi tüüpe ja nende omadusi. Selgitame iga loendi eeliseid ja puudusi, et saaksite valida sobiva struktuuri vastavalt kasutusjuhtumile.

1. Ühesuunaline loend

Ühesuunalises loendis viitab iga sõlm ainult järgmisele sõlmele.

Omadused:

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

Eelised:

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

Puudused:

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

2. Kahesuunaline loend

Kahesuunalises loendis viitab iga sõlm nii eelmisele kui ka järgmisele sõlmele.

Omadused:

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

Eelised:

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

Puudused:

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

3. Ringloend

Ringloendis viitab viimane sõlm esimesel(e), moodustades tsükli.

Omadused:

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

Eelised:

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

Puudused:

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

Võrdlustabel

Järgmisena vaatleme „Ühendatud loendi toiminguid” – sisestamine, kustutamine ja otsing koos koodinäidetega.

5. Ühendatud loendi toimingud

Selles jaotises selgitame põhitoiminguid: sisestamine, kustutamine ja otsing, koos C-koodi näidetega.

1. Elementide sisestamine

Ühendatud loendisse saab elemente lisada kolmel tüüpilisel viisil.

(1) Lisamine loendi algusesse

Lisab uue sõlme loendi etteotsa.

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

Lisab uue sõlme 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

Selgitame, kuidas eemaldada elemente loendist.

(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

Otsi loendist konkreetse väärtusega sõlme.

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

Väljasta kõik elemendid järjest.

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

Kokkuvõte

Selles jaotises rakendasime sisestamist, kustutamist ja otsingut ühendatud loendis.

• 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

Siin käsitleme ühendatud loendi rakendamisel olulist mälu haldamist: dünaamiline mälureservatsioon ja mäluleke vältimine.

1. Mis on dünaamiline mälureservatsioon?

C-keeles luuakse sõlmed sageli dünaamiliselt, et vajadusel mälu juurde võtta ja paindlikult hallata.

Koodinäide: sõlme dünaamiline loomine

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

Kuna sõlmed broneeritakse dünaamiliselt, tuleb kasutus lõpetamisel mälu korrektselt vabastada, et vältida leket.

Koodinäide: mälu vabastamine

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.

Valgrindi näide (Linux)

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

Tutvustame ühendatud loendil põhinevaid struktuure: pinu (stack) ja järk (queue), mis demonstreerivad loendi paindlikkust.

1. Pinu (LIFO) teostus

Pinu on „viimane sisse, esimene välja” andmestruktuur.

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

Järk on „esimene sisse, esimene välja” andmestruktuur.

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

Selles artiklis käsitlesime C-keele ühendatud loendeid alustades põhimõistetest ja teostusest kuni rakendusnäideteni.

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

Ühendatud loendid on baasandmestruktuur, mille rakendusala on lai. Loodetavasti andis see artikkel selge teejuhi alustest praktikani, et saaksite neid struktuure oma C-projektides enesekindlalt kasutada.