Obojsmerný lineárny zoznam

Riešenie

Úloha 15

Uvedieme len funkcie, ktorými sa realizujú niektoré operácie so zoznamom, ako aj príklady volania týchto funkcií. Všimnite si dobre najmä zvýraznené časti kódu!

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

/* definícia typu */
typedef struct uzol {
	int hodnota;
	struct uzol *nasled;
	struct uzol *predch;
} TUzol;
-------------------------------------------------------------------------------------
void pridaj_na_koniec(TUzol **z, TUzol **k)
{
	TUzol *novy;

	if (*z == NULL) {
		*z = (TUzol*)malloc(sizeof(TUzol));
		scanf("%d", &((*z)->hodnota));
		(*z)->nasled = NULL;
		(*z)->predch = NULL;
		*k = *z;
	}
	else {
		novy = (TUzol*)malloc(sizeof(TUzol));
		scanf("%d", &(novy->hodnota));
		novy->nasled = NULL;
		(*k)->nasled = novy;
		novy->predch = *k;
		*k = novy;
	}
}
-------------------------------------------------------------------------------------
void pridaj_na_zaciatok(TUzol **z, TUzol **k)
{
	TUzol *novy;

	if (*z == NULL) {
		*z = (TUzol*)malloc(sizeof(TUzol));
		scanf("%d", &((*z)->hodnota));
		(*z)->nasled = NULL;
		(*z)->predch = NULL;
			*k = *z;
	}
	else {
		novy = (TUzol*)malloc(sizeof(TUzol));
		scanf("%d", &(novy->hodnota));
		novy->nasled = *z;
		novy->predch = NULL;
		*z = novy;
	}
}
-------------------------------------------------------------------------------------
void vloz_za(TUzol **z, TUzol **k, TUzol *za)
{
	TUzol *novy;

	/* pointer za ukazuje na prvok ZA ktorý vložíme nový */

	if (za == *k) pridaj_na_koniec(z, k);
	else {
		novy = (TUzol*)malloc(sizeof(TUzol));
		scanf("%d", &(novy->hodnota));

		novy->nasled = za->nasled;
		novy->nasled->predch = novy;
		za->nasled = novy;
		novy->predch = za;
	}
}
-------------------------------------------------------------------------------------
void odstran(TUzol **z, TUzol **k, TUzol *ten)
{
	if (ten == NULL) {
		printf("Error!");
		exit(1);
	}

	if (ten == *z) {
		*z = (*z)->nasled;    /* nový začiatok */
		(*z)->predch = NULL;
	}
	else
		if (ten == *k) {
			*k = (*k)->predch;   /* nový koniec */
			(*k)->nasled = NULL;
		}
		else {
			ten->predch->nasled = ten->nasled;
			ten->nasled->predch = ten->predch;
		}
	free((void*)ten);
}
-------------------------------------------------------------------------------------
void vypis_od_zac(TUzol *z)
{
	while (z != NULL) {
		printf("%d  ", z->hodnota);
		z = z->nasled;
	}
}
-------------------------------------------------------------------------------------
void vypis_od_kon(TUzol *k)
{
	while (k != NULL) {
		printf("%d  ", k->hodnota);
		k = k->predch;
	}
}
-------------------------------------------------------------------------------------
void main(void)
{
	TUzol *zac, *kon;

	zac = kon = NULL;    /* vytvorenie prázdneho zoznamu */

	/* vytvorenie 10-prvkového zoznamu */
	int i;
	for (i = 1; i <= 10; i++) pridaj_na_koniec(&zac, &kon);

	/* výpis prvkov */
	printf("Od zaciatku: ");
	vypis_od_zac(zac);
	printf("\nOd konca: ");
	vypis_od_kon(kon);

	/* odstránenie tretieho prvku zo zoznamu */
	odstran(&zac, &kon, zac->nasled->nasled);

	/* za predposledný prvok vložíme nový */
	vloz_za(&zac, &kon, kon->predch);
	…
}

Pri tvorbe programu zo zadania úlohy nezabudnite na funkciu, ktorá bude v zozname vyhľadávať prvok, ktorý spĺňa nejakú podmienku – jej návratovou hodnotou bude pointer na nájdený prvok. Ten môžeme potom využiť ako parameter vo funkciách odstran, vloz_za.