A csatolt lista egy olyan adatszerkezet, amelyben a csomópontok egymásra mutatnak, nézzük hogyan lehet új csomópontokat hozzáadni, és hogyan lehet megtalálni és törölni a csomópontokat:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
void insert(int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = head;
head = new_node;
}
void delete(int key) {
struct Node* temp = head;
struct Node* prev = NULL;
if (temp != NULL && temp->data == key) {
head = temp->next;
free(temp);
return;
}
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
return;
}
prev->next = temp->next;
free(temp);
}
void search(int key) {
struct Node* current = head;
int pos = 1;
while (current != NULL) {
if (current->data == key) {
printf("%d found at position %d\n", key, pos);
return;
}
current = current->next;
pos++;
}
printf("%d not found in the list\n", key);
}
int main() {
insert(3);
insert(5);
insert(7);
insert(9);
printf("List before deletion: ");
search(5);
delete(5);
printf("List after deletion: ");
search(5);
return 0;
}
---------------
Az összes csomópont kiírásához a következő kódot használhatod:
void printList() {
struct Node* ptr = head;
printf("\n[ ");
while (ptr != NULL) {
printf("(%d) ", ptr->data);
ptr = ptr->next;
}
printf("]\n");
}
A fenti kód egy új függvényt definiál, amely végigiterál a csatolt listán, és kiírja az összes csomópont értékét. A printList() függvényt bármikor hívhatod a program futása közben, hogy megjelenítse a lista aktuális állapotát.
A csatolt lista rendezése C-ben többféleképpen is megoldható. Az egyik lehetséges megoldás a buborékrendezés algoritmusának alkalmazása. A buborékrendezés során a lista elemeit páronként összehasonlítjuk, és ha az előző elem nagyobb, mint a következő, akkor felcseréljük őket. Ezt addig ismételjük, amíg a lista rendezett lesz.
A következő kódban láthatod, hogyan lehet implementálni a buborékrendezést egy csatolt listában:
void bubbleSort() {
int swapped;
struct Node* ptr1;
struct Node* lptr = NULL;
if (head == NULL) {
return;
}
do {
swapped = 0;
ptr1 = head;
while (ptr1->next != lptr) {
if (ptr1->data > ptr1->next->data) {
int temp = ptr1->data;
ptr1->data = ptr1->next->data;
ptr1->next->data = temp;
swapped = 1;
}
ptr1 = ptr1->next;
}
lptr = ptr1;
} while (swapped);
}
A fenti kód egy egyszerű példa arra, hogyan lehet rendezni egy csatolt listát a buborékrendezés algoritmusával. A bubbleSort() függvényt bármikor hívhatod a program futása közben, hogy rendezze a lista elemeit.
A csatolt lista rendezése C-ben többféleképpen is megoldható. Az egyik lehetséges megoldás a buborékrendezés algoritmusának alkalmazása. A buborékrendezés során a lista elemeit páronként összehasonlítjuk, és ha az előző elem nagyobb, mint a következő, akkor felcseréljük őket. Ezt addig ismételjük, amíg a lista rendezett lesz.
Azonban a buborékrendezés nem hatékony algoritmus, mivel a legrosszabb esetben a futási ideje O(n^2). Ezért a nagyobb listák rendezéséhez hatékonyabb algoritmusokat kell használni, például:
Gyorsrendezés: A gyorsrendezés egy rekurzív algoritmus, amely a lista elemeit két részre osztja, és minden részt külön-külön rendez. A gyorsrendezés átlagos esetben nagyon hatékony, mivel a futási ideje O(n log n). Azonban a legrosszabb esetben a futási ideje O(n^2) lehet.
Beszúró rendezés: A beszúró rendezés egy egyszerű algoritmus, amely a lista elemeit egyesével veszi ki, és beszúrja őket a megfelelő helyre a rendezett részben. A beszúró rendezés átlagos esetben hatékony, mivel a futási ideje O(n^2), de a legjobb esetben csak O(n).
Kupacrendezés: A kupacrendezés egy hatékony rendezési algoritmus, amely a kupac adatszerkezetét használja. A kupacrendezés átlagos esetben nagyon hatékony, mivel a futási ideje O(n log n). Azonban a kupacrendezés nem stabil rendezés, és a legrosszabb esetben a futási ideje O(n log n) lehet.
--------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _pbook {
char nev[51];
char cim[51];
char tel[13];
struct _pbook* next;
struct _pbook* prev;
} pbook;
void write_list(pbook* first) {
pbook* p = first;
while ((p != NULL)) {
printf("%s %s %s\n", p->nev, p->cim, p->tel);
p = p->next;
}
}
pbook* read_file(char fnev[50]) {
FILE* fp;
pbook* kov = NULL;
pbook* first = NULL;
fp = fopen(fnev, "r");
char nev2[51];
char cim2[51];
char tel2[13];
if (fscanf(fp, "%s %s %s]", nev2, cim2, tel2) == 3) {
first = (pbook*) malloc(sizeof(pbook));
strcpy(first->nev, nev2);
strcpy(first->cim, cim2);
strcpy(first->tel, tel2);
}
---------------
if(akt == first)
{
first = first->next;
return first;
}
else
{
elozo->next = akt->next;
return first->next; // inkább return first
+ törlésnél memória-felszabadítás
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _pbook {
char nev[51];
char cim[51];
char tel[13];
struct _pbook* next;
struct _pbook* prev;
} pbook;
void write_list(pbook* first) {
pbook* p = first;
while ((p != NULL)) {
printf("%s %s %s\n", p->nev, p->cim, p->tel);
p = p->next;
}
}
pbook* read_file(char fnev[50]) {
FILE* fp;
pbook* kov = NULL;
pbook* first = NULL;
fp = fopen(fnev, "r");
char nev2[51];
char cim2[51];
char tel2[13];
if (fscanf(fp, "%s %s %s]", nev2, cim2, tel2) == 3) {
first = (pbook*) malloc(sizeof(pbook));
strcpy(first->nev, nev2);
strcpy(first->cim, cim2);
strcpy(first->tel, tel2);
}
----------------
Egy egyszerű példa egy olyan csatolt listára, ahol a csomópontok egymásra mutatnak
class CsomoPont:
def __init__(self, adat):
self.adat = adat
self.kovetkezo = None
# Csatolt lista kialakítása
fej = CsomoPont(1)
fej.kovetkezo = CsomoPont(2)
fej.kovetkezo.kovetkezo = CsomoPont(3)
fej.kovetkezo.kovetkezo.kovetkezo = CsomoPont(4)
# Csomópontok kiírása
jelenlegi = fej
while jelenlegi:
print(jelenlegi.adat, end=' ')
jelenlegi = jelenlegi.kovetkezo
print()
a CsomoPont osztályt használjuk egy csomópont létrehozásához. A csomópontok az "adat" attribútumon keresztül tárolják az értékeiket, és a "kovetkezo" attribútumon keresztül mutatnak a következő csomópontra.
A következő példában láthatjuk, hogyan lehet új csomópontokat hozzáadni a csatolt listához:
# Új csomópont hozzáadása
uj_csomo = CsomoPont(5)
fej.kovetkezo.kovetkezo.kovetkezo.kovetkezo = uj_csomo
Nézzük hogyan lehet megtalálni és törölni egy csomópontot. Vegyük például azt, hogy szeretnénk megtalálni és törölni a 3-as értékű csomópontot:
# Csomópont megtalálása és törlése
jelenlegi = fej
elozo = None
while jelenlegi:
if jelenlegi.adat == 3:
if elozo:
elozo.kovetkezo = jelenlegi.kovetkezo
else:
fej = jelenlegi.kovetkezo
break
elozo = jelenlegi
jelenlegi = jelenlegi.kovetkezo
A while ciklus segítségével végigiterálunk a csatolt listán, és megtaláljuk a keresett csomópontot. Ha megtaláljuk, akkor töröljük azt a break kulcsszóval, és frissítjük a kapcsolatokat a kovetkezo attribútumokon keresztül.
Nincsenek megjegyzések:
Megjegyzés küldése