11. labor: Láncolt listák

A lenti feladatok első része egyszeresen láncolt, strázsa nélküli listára vonatkozik. Meg kell valósítani az összes alapvető műveletet: bejárás, beszúrás, felszabadítás. Javasolt az összes függvény kidolgozása előtt rajzot készíteni: melyik pointer hova mutat a művelet előtt, és hogyan módosulnak azok a művelet hatására! Így sokkal könnyebb megírni a függvényeket is.

Adott a lenti programkód. Ez létrehoz egy dinamikusan foglalt, egyszeresen láncolt, strázsa nélküli listát, amelynek az elejére a lis pointer mutat. Így néz ki:

#include <stdlib.h>

typedef struct Lista {
   int adat;
   struct Lista *kov;
} Lista;


/* létrehoz egy listát, benne egy csomó számmal */
Lista *lista_letrehoz(void) {
    int szamok[] = { 8, 14, 13, 17, 1, 19, 16, 5, 3, 11, 2,
                     15, 9, 10, 6, 22, 4, 7, 18, 20, -1 };
    Lista *l = NULL;
    int i;
    
    for (i = 0; szamok[i] != -1; ++i) {
        Lista *u = (Lista*)malloc(sizeof(Lista));
        u->kov = l;
        u->adat = szamok[i];
        l = u;
    }
    return l;
}


int main() {
   Lista *lis=lista_letrehoz();
   
   ....
   
   return 0;   
}

Másold be egy új projektbe a kódot! Írj ciklust, amely kiírja a képernyőre a listában tárolt számokat! A képernyőn ezt kell kapjad:

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

A fenti program memóriaszivárgást tartalmaz. Írj egy ciklust, amely felszabadítja a listát! (Ne használj rekurziót!) Tedd be ezt a ciklust és az előzőt egy-egy függvénybe, amelyek paraméterként veszik át a listát!

Írj függvényt, amely paraméterként átvesz egy listát és egy egész számot. Szúrja be a függvény a számot a lista legelejére! Térjen vissza az így megváltozott lista eleje mutatóval!

Ettől a lista eleje mutató megváltozik. Vagyis azt a függvény visszatérési értékként meg kell adja (esetleg cím szerint kell átvegye). Most válaszd az előbbit:

lis = lista_elejere_beszur(lis, 21);

Szúrj be számokat a lista elejére, és írd ki a lista tartalmát! A beszúrt számok természetesen fordítva kell megjelenjenek. Ha működik ez a függvény, akkor a kapott létrehozó függvényt (lista_letrehoz()) már kitörölheted, hiszen van saját listaépítőd.

Írj függvényt, amely egy paraméterként kapott lista végéhez láncol egy új elemet, amely az ugyancsak paraméterként kapott számot tartalmazza! Figyelj arra, hogy üres lista esetén (vagyis ha NULL pointert kap) is helyesen működjön a függvény! Ebben az esetben megváltozik a lista elejét mutató pointer, ezért a fentihez hasonlóan kell kezelni azt.

Írj függvényt, amely paraméterként egy listát vesz át, és visszatér annak hosszával! Ennek működését könnyen ellenőrizni tudod, ha az eredményt összehasonlítod a képernyőre kiírt lista elemszámával.

Szaporodnak a listát kezelő függvények, ezért bontsd szét a programodat több forrásmodulba:

1. lista.h – a lista típus definíciója és a függvények deklarációi (include őrszemmel együtt!)
2. lista.c – a listát kezelő függvények definíciói
3. foprogram.c – a listakezelő függvényeket hívó, vagyis a listát használó programrészek.

A továbbiakban így dolgozz!

Írj függvényt, amely paraméterként egy listát és egy számot vesz át. Visszatérési értékként pedig egy pointert ad a lista első olyan elemére, amely a számot tartalmazza. Ha nincs ilyen, akkor pedig NULL pointert.

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

int main() {
   Lista *lis=NULL, *tal;
   
   /* lis = lista_letrehoz(lis); */
   lis = lista_vegere_beszur(lis, 66);
   lis = lista_elejere_beszur(lis, 55);
   lis = lista_vegere_beszur(lis, 77);
   lis = lista_elejere_beszur(lis, 44);
   lis = lista_elejere_beszur(lis, 33);
   lis = lista_elejere_beszur(lis, 22);
   lis = lista_elejere_beszur(lis, 11);
   lista_kiir(lis);
   printf("\n\nHossz: %d\n", lista_hossz(lis));
   
   tal = lista_keres(lis, 44);
   if (tal!=NULL)
      printf("%d\n", tal->adat);
   else
      printf("nincs ilyen\n");

   lista_free(lis);
   
   return 0;   
}

#ifndef LISTA_H
#define LISTA_H

/* Lista adatszerkezet */
typedef struct Lista {
   int adat; /* Maga az adat */
   struct Lista *kov; /* Pointer a következő elemre */
} Lista;
 
/* Lista létrehozása */
Lista *lista_letrehoz(void);

/* Lista kiírása */
void lista_kiir(Lista *l);

/* Lista felszabadítása */
void lista_free(Lista *l);

/* Adat beszúrása a lista elejére */
Lista *lista_elejere_beszur(Lista *l, int mit);

/* Adat beszúrása a lista végére */
Lista *lista_vegere_beszur(Lista *l, int mit);

/* Lista hosszának kiszámolása */
int lista_hossz(Lista *l);

/* Keresés a listában */
Lista *lista_keres(Lista *l, int mit);

#endif

#include "lista.h"
#include <stdlib.h>
#include <stdio.h>
 
/* Lista létrehozása */
Lista *lista_letrehoz(void) {
    int szamok[] = { 8, 14, 13, 17, 1, 19, 16, 5, 3, 11, 2,
                     15, 9, 10, 6, 22, 4, 7, 18, 20, -1 };
    Lista *l = NULL;
    int i;
    
    for (i = 0; szamok[i] != -1; ++i) {
        Lista *u = (Lista*)malloc(sizeof(Lista));
        u->kov = l;
        u->adat = szamok[i];
        l = u;
    }
    return l;
}


/* Lista kiírása */
void lista_kiir(Lista *l) { 
	Lista *p;
	
    /* Végigmegyünk a listán és kiírjuk az adatokat */
	for(p=l;p!=NULL;p=p->kov) printf("%d ",p->adat);
}

/* Lista felszabadítása */
void lista_free(Lista *l) {
	Lista *p=l; /* Végigmegyünk a listán */

	while (p!=NULL) {
		/* Ha csak simán azt mondanánk hogy free(p); akkor elveszne a következő */
		/* elemre a pointer, nem mondhatnánk azt hogy: p=p->kov;  */
		Lista *tmp = p->kov; /* Ezért eltároljuk a következő elem címét */
		free(p); /* Mostmár törölhetjük az adott elemet */
		p=tmp; /* Folytassuk a következőtől */
	}
}

/* Adat beszúrása a lista elejére */
Lista *lista_elejere_beszur(Lista *l,int mit) {
	Lista *uj = (Lista *) malloc(sizeof(Lista)); /* Új elem */
	
	uj->adat = mit; /* Adat bemásolása */
	uj->kov = l; /* Az új elem után jön az eddigi lista (akkor is jó, ha üres volt eredetileg) */
    
    return uj; /* A lista eleje ez az elem lesz */
}

/* Adat beszúrása a lista végére */
Lista *lista_vegere_beszur(Lista *l, int mit) {
	Lista *uj = (Lista *)malloc(sizeof(Lista)); /* Új elem */

	uj->adat = mit; /* Adat bemásolása */
	uj->kov=NULL; /* Ez lesz a lista vége, ezért NULL a következő elem */
	if (l==NULL)
       return uj; /* Ha üres a lista, akkor ez lesz az eleje */
	else {
		Lista *p=l; /* Elmegyünk az utolsó elemig (aminek a pointere NULL pointer) */
		while (p->kov!=NULL) p=p->kov;
		p->kov=uj; /* És hozzáfűzzük */
        return l;
	}
}

/* Lista hosszának kiszámolása */
int lista_hossz(Lista *l) {
	Lista *p=l;
	int hossz=0;
    
	/* Végigmegyünk a listán és számoljuk az elemeket */
	while (p!=NULL) {
		p=p->kov;
		hossz++;
	}
	return hossz;
}

/* Keresés a listában */
Lista *lista_keres(Lista *l,int mit) {
	Lista *p;
	for (p=l; p!=NULL; p=p->kov)
        if (p->adat==mit)
            return p;
	return NULL;
}

Írj függvényt, amelyik a paraméterként adott sorszámú listaelem után (az 1-es jelenti az első elemet) beszúr egy új listaelemet! A beszúrás működjön akkor is, ha a lista üres! Figyelj az indexre is: ha 0, akkor kerüljön a legelejére az elem, ha túl nagy a sorszám, akkor pedig a legvégére.

Írj olyan függvényt is, amely egy adott sorszámú elemet töröl a listából. Jelentse itt is az 1-es az első elemet. Ha nem létezik az adott sorszámú elem, akkor ez ne csináljon semmit!

Figyelj arra, hogy mindkét esetben a szóban forgó listaelem előtt álló listaelem pointerét kell módosítani!

Írj függvényt, amely egy paraméterként kapott nevű szöveges fájlba kiírja egy lista tartalmát; minden számot egy külön sorba.

Írj egy másik függvényt, amely egy paraméterként kapott nevű fájlból új listát épít, és az elejére mutató pointert egy cím szerint átvett üres listába teszi. Ha a fájl nem olvasható, térjen vissza NULL pointerrel, azaz üres listával. (Figyelj arra, hogy a lista a kiírás és beolvasás hatására ne forduljon meg!)

• Írj függvényt, amely lemásol egy listát! Készítsen az a listáról mély másolatot, vagyis ne csak egy új pointer keletkezzen, amely az eredeti listára mutat, hanem egy teljesen új lista, amely az eredetitől mindenben független!
• Írj függvényt, amely lemásol egy listát, de úgy, hogy a másolat az eredeti fordítottja legyen! Ötlet: ehhez használható az előző feladat megoldása, és a gyakorlati órák utolsó feladatának ötlete.
• Írj függvényt, amely úgy módosít egy paraméterként kapott listát, hogy abban minden elem csak egyszer szerepeljen! Térjen vissza a függvény az esetleg megváltozott lista eleje pointerrel! (Pl. ha a bemeneti lista 1,5,7,4,4,1,5,6, a megváltozott lista tartalma legyen 1,5,7,4,6).
• Írj függvényt, amely létrehoz egy listát olyan módon, hogy az a paraméterként kapott lista minden elemét csak egyszer tartalmazza. (Vagyis a feladat ugyanaz, mint az előbb, csak nem módosítani kell a listát, hanem létrehozni egy újat.)
• Írd át a függvényeket úgy, hogy maximum 50 betűs szavakat tartalmazó listákon működjenek! Mely függvényeket, hogyan kell ehhez módosítani?