Једноструко спрегнуте листе

Један облик организације динамичког чувања података је једноструко повезана листа. Листа преставља скуп чворова (елемената) повезаних показивачима у једном смеру. Сваки чвор је структурна променљива која има најмање два поља: једно за чување података, или информација о чувању података, друго за чување показивача на следећи чвор листе.

Дефиниција структуре за представљање елемента

typedef struct elem
{ 
	int broj;
	struct elem *sled;
} Elem; /* овде је дефинисан један елеменат листе, односно чвор */
Elem *pocetak_liste; /* показивач на почетак листе, односно на први елеменат у листи */

lista1

На почетак листе показује показивачка променљива pocetak_liste. Крајњи чвор листе у елементу за везу (sled) садржи вредност NULL. Ако је листа празна pocetak_liste такође има вредност NULL.

Формирање једноструке листе

Да би формирали листу, прво иницијализујемо празну листу доделом

pocetak_liste=NULL;

Како би се креирао први динамички објекат (чвор листе), неопходно је да се додели меморијски простор,

Elem *novi = malloc (sizeof(Elem)); /* novi je показивач на структуру Elem, односно на чвор листе  */

lista2

Динамичком објекту novi, могу се доделити вредности

novi->broj= 5;
novi->sled=NULL;

lista3

Да би променљива pocetak_liste показивала на почетак, треба јој доделити вредност променљиве novi,

pocetak_liste=novi;

lista4

За додавање новог чвора у листу најпре се мора одвојити простор за нови чвор:

novi=(Elem*)malloc (sizeof(Elem)); /* није неопходно, али се препоручује дефинисање типа вредности функције malloc да буде показивач на структуру Elem */

lista5

Након

novi->broj=10;
novi->sled=pocetak_liste;

информациони део чвора добија вредност 10, укључује се у листу и то на њен почетак

lista6

Да би променљива pocetak_liste показивала на почетак, понавља се додела

pocetak_liste=novi;

lista7

За рад са једноструко спрегнутим листама може се дефинисати већи број функција које се смештају у посебан модул, а затим се, по потреби, позивају из програма који раде са једноструко спрегнутом листом. Наводимо неке од функција за рад са једноструко спрегнутом листом. У овим функцијама показивач на почетак листе означили смо са lst, а tek можемо замислити као индекс код низова. То је показивач који показује на тренутно „активан“ чвор листе. Вредност овог показивача, приликом обиласка елемената листе, креће се од tek=lst – почетак листе, до tek=NULL (вредност поља sled у последњем чвору листе). Ажурирање овог „бројача“ обавља се тако што се прочита поље sled из тренутно „активног“ чвора и упише као вредност показивача tek: tek=tek->sled

Обилазак елемената листе

for(tek=lst; tek; tek=tek->sled)
{
…
/*ovde idu naredbe koje treba izvrsiti sa SVIM elementima liste – ispisivanje, postavljanje na odredjenu vrednost, racunanje zbira...
}

Број елемената листе

int duz(Elem *lst)
{
	Elem *tek; int n = 0;
	for(tek=lst; tek; tek=tek->sled)   n++; /* da bismo odredili broj elemenata liste, prolazimo kroz celu listu i posle svakog elementa povecavamo vrednost brojaca n – broj elemenata liste */
	return n;
}

Исписивање садржаја листе

void pisi (Elem *lst)
{
	Elem *tek;
	for(tek=lst; tek; tek=tek->sled)    printf(“%d\n“,tek->broj); /* ispisivanje SVIH elemenata liste */
}

Додавање нових елемената листи – на почетак листе

Elem *na_pocetak (Elem *lst, int b)
{
	Elem *novi = malloc (sizeof(Elem));
	novi->broj = b;novi->sled = lst;lst= novi; /* ova funkcija je opisana u samom tekstu – dodeljivanje prostora za novi elemenat, upisivanje vrednosti u njega i azuriranje pokazivaca */
	return lst;
}

Додавање нових елемената листи – на крај листе

Elem *na_kraj (Elem *lst,int b)
{
	Elem *tek, *novi = malloc (sizeof(Elem));
	novi->broj = b;novi->sled = NULL; /* novi elemenat upisujemo kao poslednji cvor liste */
	if  (!lst)    lst = novi; /* ako je to PRVI elemenat u listi, samo azuriramo pokazivac na pocetak liste */
	else
	{
		for(tek=lst; tek->sled; tek=tek->sled);
		tek->sled = novi; /* ako lista ima vise od jednog elementa, potrebno je azurirati polje sled u trenutno poslednjem elementu liste da pokazuje na novi elemenat u listi */
	}
	return lst;
}

Додавање елемента у уређену листу

Elem *umetni(Elem *lst, int b)
{
	Elem *tek = lst, *pret = NULL, *novi;
	while (tek && tek->broj < b){pret = tek;tek = tek->sled;} /* prolazimo kroz listu do mesta gde bi trebalo smestiti novi elemenat */
	novi = malloc (sizeof(Elem));
	novi->broj = b; novi->sled = tek; /* ubacimo novi elemenat, a zatim azuriramo pokazivace njegovog prethodnika i sledbenika */
	if (!pret)       lst = novi;
	else     pret->sled = novi;
	return lst;
}

Уређивање листе

void uredi (Elem *lst)
{
	Elem *i, *j; int p;
	for(i=lst; i; i=i->sled)
	for(j=i->sled; j; j=j->sled)
	if(j->broj < i->broj)    {p = i->broj;i->broj = j->broj;j->broj = p;} /* sortiramo tako sto krecemo sa oba kraja i vrsimo zamenu mesta elementima ako nisu u odgovarajucem redosledu */
}

Брисање листе

void brisi (Elem *lst)
{
	Elem *stari;
	while (lst)  {stari = lst;lst = lst->sled;free (stari);} /* brisemo jedan po jedan elemenat – azuriramo pokazivace, a zatim oslobadjamo dodeljenu memoriju @obrisanom@ clanu */
}

Изостављање одабраних елемената листе

Elem *izostavi (Elem *lst, int b) 
{
	Elem *tek = lst, *pret = NULL, *stari;
	while(tek)
		if (tek->broj != b)  {pret = tek; tek = tek->sled;} /* prolazimo kroz listu do mesta gde se nalazi broj koji treba da obrisemo. Nakon toga se taj elemenat obrise i azuriraju pokazivaci i oslobodi memorija koja mu je bila dodeljena */
		else
		{
			stari = tek;tek = tek->sled;
			if (!pret)     lst = tek;
			else    pret->sled = tek;
			free(stari);
		}
	return lst;
}

Оставите одговор

Попуните детаље испод или притисните на иконицу да бисте се пријавили:

WordPress.com лого

Коментаришет користећи свој WordPress.com налог. Одјавите се /  Промени )

Google+ photo

Коментаришет користећи свој Google+ налог. Одјавите се /  Промени )

Слика на Твитеру

Коментаришет користећи свој Twitter налог. Одјавите се /  Промени )

Фејсбукова фотографија

Коментаришет користећи свој Facebook налог. Одјавите се /  Промени )

Повезивање са %s