Повезане листе

Повезана листа је структура података чији су елементи уређени линеарно. Али, за разлику од низа, чије линеарно уређење је одређено низом индекса, код повезане листе је уређење одређено показивачем у сваком од објеката.
Листе су врло распрострањене у програмирању – листа догађаја, листа порука, представљање полинома,…
Листа може бити једноструко, двоструко повезана. Може бити сортирана или не, може бити кружна или не.

Једноструко повезана листа

Основна динамичка структура података је листа. На следећој слици дат је графички приказ једноструко повазане листе. Код једноструко повезане листе суседни елементи листе повезани су једном везом. Сваки елемент листе садржи неки податак и референцу (показивач) на следећи елемент листе. Посебан значај има показивач на први елемент листе, који се често зове и глава листе. Код последњег елемента листе вредност показавича на следећи елемент је NULL.

lista-1

Једноструко повезана листа целих бројева у C имплементира се преко структуре на следећи начин:

typedef struct Element {
	int podatak;
	struct Element *sledeci;
}Element;

Променљива типа листе представља се као показивач на први елемент листе:

Element *glava= NULL;

Овом наредбом креира се празна листа, тако што наведемо да је глава листе NULL показивач. Појединачни елементи листе често се називају чворови и структура за креирање листе може да има и другачије називе, уместо Element може се користити назив Cvor или Node. Такође, податак у структури може бити различитог типа, а елементи листе могу да садрже и више података различитог типа. На пример можемо направити листу која садржи податке о студентима и има име, презиме и број поена студента. Оваква листа имплементирала би се следећом структуром:

typedef struct ElementStudent{
	char *ime;
	char *prezime;
	float *brojPoena;
	struct ElementStudent *sledeci;
} ElementStudent;

Оно што је заједничко за све једноструко повезане листе је да елементи морају имати показивач на следећи елемент листе. Над описаним структурама могу се имплементирати многе операције над листом, као што су додавање елемента у листу, избацивање елемента из листе и обилазак листе ради исписа елемената листе, пребројавања елемената или проналаска одређеног елемента у листи.

Функције за рад са листама које мењају садржај листе (на пример додавање новог елемента) имају као улазни податак листу, која је представљена као показивач на први елемент листе, а као резултат враћају показивач на први елемент измењене листе. Други начин за имплементацију функције са листама је да се листа проследи као показивач на показивач на први елемент листе, тада се листа уствари прослеђује по референци, а не по вредности и немамо повратну вредност из функције.

Функција за додавања елемента у листу се може посматрати за више случајева, када се елемент додаје на почетак листе, на крај листе или на одређено место уколико су елементи листе сортирани и тада говоримо у уређеној листи. Код функције за додавање елемента један аргумент је листа, а други елемент који се додаје који може бити већ креиран и алоциран елемент (чвор) листе или само податак. Ако прослеђујемо само податак потребно је у функцији алоцирати меморију за нови елемент листе. Функција за додавање елемента на почетак листе целих бројева приказана је на следећем листингу.

Element* dodajNaPocetak(Element *glava, int broj){
    Element *novi = (Element*)malloc(sizeof(Element));
    novi->podatak = broj;
    novi->sledeci = glava;
    glava = novi;
    return glava;
}

Пошто се у овој функцији прослеђује само податак, приликом додавања новог елемента у функцији потребно је алоцирати меморијски простор за нови елемент, у овом примеру користи се функција malloc. Затим се том елементу додељују вредности, прослеђени параметар као податак, а показивач на следећи елемент је у ствари показивач на почетак листе. Остаје још да се показивач на главу листе пребаци на нови елемент (јер додајемо на почетак) и да се тако добијена нова листа врати као резултат функције. Штампање листе подразумева обилазак сваког елемента листе и испис податка за сваки елемент.

void stampaj(Element *glava){
    Element *tekuci = glava;
    while(tekuci!=NULL){
        printf("%d, ", tekuci->podatak);
        tekuci = tekuci->sledeci;
    }
}

Већина операција са листама се може имплементирати и рекурзивно. Код рекурзивних решења тривијални случај за излазак из рекурзије је празна листа, а корак ка тривијалном случају је прелазак на следећи елемент листе. На пример операција за штампање листе се рекурзивно може имплементирати на следећи начин:

void stampajRek(Element *glava){
    if(glava==NULL)
        return;
    else{
        printf("%d ", glava->podatak);
        stampajRek(glava->sledeci);
    }
}
Advertisements

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

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

WordPress.com лого

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

Google+ photo

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

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

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

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

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

w

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