Prikazujem rezultate 1 do 7 od 7

Tema: manipulacija vezanim listama-need help

  1. #1
    Senior Member Respawned sorcerer mronki's Avatar
    Datum registracije
    Mar 2008
    Lokacija
    tu i tamo
    Postova
    1.463

    manipulacija vezanim listama-need help

    Ovako, imam zadatak na vježbama na faxu koji glasi:
    "korisnik unosi N prirodnih brojeva, N <= 40. Brojeve je potrebno sortirati uzlazno.
    Rješenje je potrebno izvesti pomoću vezane liste. Nakon sortiranje potrebno je
    provjeriti dali postoje brojevi koji se nalaze u rasponu ASCII kodova slova i ako da
    ispisati kodove kao i sama slova. Isto tako potrebno je razdvojiti velika i mala
    slova u posebna polja te polja sortirati silazno koristeći sortiranje zamjenom te
    mjehurićasto sortiranje tim redoslijedom. Algoritam realizirati pomoću funkcija."

    radili smo do sada samo jednostruke vezane liste i nismo došli dalje od rekurzija... vidio sam Lukin post o vezanim listama, ali on je koristio klase i razne "naprednije" stvari koje još nismo radili pa se u njegovom kodu baš i ne snalazim, a ne znam ni jel smijemo još koristiti klase itd. Ugl. ne tražim da mi netko riješi zadatak, ali da mi barem malo više pojasni kako se manipulira vezanim listama, i koja je njihova svrha ovdje (ovaj zadatak bi bez beda napravio sa poljima :S). Ugl. sve što sam uspio napraviti je kod za vezanu listu, ali ne kužim kako i što dalje (ne kužim baš ni kako da to strpam u posebnu funkciju.


    Code:
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    struct element {int vrijednost; element *sljedeci;}; //slog vezane liste, sastoji se od vrijednosti i pokazivaca na adresu sljedeceg sloga
    typedef element *lista; //definira se tip element koji je pokzaivac lista
    
    int main (){
        lista l=NULL; //deklarira se l tipa lista i inicijalizira joj se NULL (prazna adresa)
        int n,a;
        cin>>n;
        element *el; //deklariranje pokazivaca *el tipa element
        for (int i=0;i<n;i++) {
            cin>>a;
            el=new element; //svaki put se alocira memorija za novu varijablu
            (*el).vrijednost=a; //u element.vrijednost se sprema vrijednost varijable a
            (*el).sljedeci=l; //u element.sljedeci se prebacuje vrijednost od l, koja je u prvom krugu null, a kasnije adresa prethodnog elementa
            l=el;}//u l se prebacuje vrijednost el, tj. adresa novog sloga element      
        
        system ("pause");
        return 0;
    }

    S

    P.S. uz kod sam si ostavljao reference da bolje skužim listu, ako sam nešto krivo shvatio, bio bih zahvalan da mi pripomenete

  2. #2
    Senior Member You have been warned cham3leon's Avatar
    Datum registracije
    Oct 2007
    Lokacija
    Rijeka
    Postova
    18.414

    Re: manipulacija vezanim listama-need help

    Dvostruko vezana lista je lista koja ima dva "redoslijeda". Primjerice, to može biti lista u kojoj su čvorovi popunjeni podacima kao što su imena i prezimena, pa je preko dva pointera u svakom čvoru zapravo istovremeno povezana tako da je sortirana i po imenu i po prezimenu, ali to tebi ne treba sada.

    Dakle, zadatak bi bio dobiti neku gotovu listu i sortirati je, koliko sam razumio. Ako ste radili bilo kakvo sortiranje sa običnim poljima, tu bi se trebali koristiti isti algoritmi, samo bi dio koda koji zamjenjuje 2 elementa trebao promijeniti adrese u pointerima, odnosno kamo pokazuju.

    EDIT: Ne ček, ne kužim zadatak, prvo bi polje trebalo bit sortirano, pa onda prebačeno u listu?

  3. #3
    Senior Member Respawned sorcerer mronki's Avatar
    Datum registracije
    Mar 2008
    Lokacija
    tu i tamo
    Postova
    1.463

    Re: manipulacija vezanim listama-need help

    mislim da bi trebalo napraviti listu, sortirati, a onda prebaciti u polje za ostale dijelove zadatka
    problem je u tome što se ja baš sa tim pokazivačima ne snalazim 100%, pa mi sortiranje liste uz pomoć algoritama za sortiranje polja baš i ne ide :S

  4. #4
    Senior Member You have been warned cham3leon's Avatar
    Datum registracije
    Oct 2007
    Lokacija
    Rijeka
    Postova
    18.414

    Re: manipulacija vezanim listama-need help

    Gle, pokazivač je samo tip varijable koji sadrži adresu na neku drugu varijablu. U slučaju liste, svaki čvor (ili slog kako ti zoveš ovdje) ima u sebi jedan pointer koji sadrži adresu idućeg čvora, odnosno pokazuje na njega.

    Kad sortiraš bilo što, prvo ti treba algoritam koji će programu govoriti kada da zamijeni, i koje elemente. Kad imaš polje, onda ta zamjena jednostavno ide po principu zamijeni vrijednosti na indeksima polje[1]Si polje[2]. Pošto lista nema indeksiranja nego je organizirana uz pomoć pointera, kod liste se ta zamjena napravi tako da preusmjeriš kamo pointeri pokazuju.

    Nama nisu nikad davali ovakve zadatke, ali čisto ovako iz glave bih rekao da kad naiđeš na dva čvora A, B koja treba zamijeniti, onda bi ta zamjena trebala ići ovako: Morao bi prethodnom čvoru od A namjestiti pointer da pokazuje na B, a na B namjestiti pointer da pokazuje na A.
    Možeš koristit bubble sort potpuno isto ko i na nizovima, samo što ćeš umjesto for petlje koja vrti indekse unaprijed imati jedan pokazivač koji šeće naprijed po čvorovima, i to na taj način da na svakom koraku gleda i provjerava 2 sljedeća čvora i uspoređuje njihove vrijednosti. Tek onda može na čvoru na kojeg zapravo i pokazuje promijeniti sadržaj njegovog pokazivača na drugi čvor, a njegov stari sadržaj (koji pokazuje na prvi čvor) ide u pokazivač na drugom čvoru.

    Sad više ni ja ne znam šta sam napisao.

  5. #5
    Senior Member Respawned sorcerer mronki's Avatar
    Datum registracije
    Mar 2008
    Lokacija
    tu i tamo
    Postova
    1.463

    Re: manipulacija vezanim listama-need help

    kužim ja kako bi to trebalo ići, ali ja ne znam kako se preusmjerava pointer... koliko sam skužio (*el).sljedeci pokazuje na adresu sljedeceg sloga... i kako da ja preusmjerim da on pokazuje na jedan ili više čvora unazad ili unaprijed? isporbavao sam gluposti poput (*(el+1)).sljedeci, ali ne uspijeva :S

  6. #6
    Senior Member You have been warned cham3leon's Avatar
    Datum registracije
    Oct 2007
    Lokacija
    Rijeka
    Postova
    18.414

    Re: manipulacija vezanim listama-need help

    Ne, *(el+1) ne pali iz jednostavnog razloga što za razliku od niza, čvorovi od liste uopće ne moraju biti na susjednim adresama, tako da će te pomicanje pointera unaprijed dovesti u neku memorijsku vukojebinu daleko od čvora koji ti doista treba. Upravo je to snaga liste što može po memoriji biti razasuta kako god želi, a i dalje je povezana onako kako ti hoćeš s tim pointerima.

    Inače, za pristupanje elementu n strukture na koju pokazuje neki pointer p možeš koristiti ovo:

    p->n

    Mislim da bi bilo moguće odmah pristupati idućem elementu ovako:

    (p->sljedeci)->sljedeci = nešto

    Na taj način bi se trebalo promijeniti vrijednost pointera sljedeci u idućem čvoru na kojeg pokazuje pointer sljedeci u trenutnom čvoru. Bar se ja sjećam da sam to tako radio. Možda sam fulao šta. Inače, evo na brzaka par funkcija sa listama s naših vježbi:

    (jezik je C obični, to ne bi trebao biti problem)

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    
    
    struct nd {
    	int data;
    	struct nd *next;
    };
    typedef struct nd node;
    
    
    
    //list sorted in descending order
    int add(node **header, int listData) 
    {
    	node *newNode, *p, *lastP;
    
    	if ((newNode = (node *) malloc(sizeof(node))) == NULL) {
    		return 0;
    	}
    	
    	newNode->data = listData;   
    
    	//empty list or listData > first node->data
    	if (*header == NULL || listData >= (*header)->data) {
    		newNode->next = *header;
    		*header= newNode;
    	} else {
    		//find correct position
    		for(p=*header; listData < p->data && p->next; lastP=p, p=p->next);
    		//should we append to the end of a list
    		if(listData < p->data) {
    			newNode->next = p->next;
    			p->next = newNode;
    		} else {
    			newNode->next = lastP->next;
    			lastP->next = newNode;
    		}
    	}
    return 1;
    }
    
    
    //list printout
    void display (node *header)
    {
    	node *p;
    	int i;
    
    	printf("\nPrinting list\n");
    	if( !header ) {
    		printf("\tEmpty list!\n");
    	} else {
    		for (i=1, p = header; p != NULL; p = p->next, i++) {
    			printf ("Node: %d -> data = %d\n", i, p->data);
    		}
    	}
    	printf("Done\n\n");
    }
    
    
    //find and return node address
    node *find (node *header, int searchData) 
    {
    	node *p;
    
    	for (p = header; p; p = p->next) {
    		if (p->data == searchData){
    			return p;
    		}
    	}
    
    	return NULL;
    }
    
    
    //delete node
    int delete(node **header, int delData)
    {
    	node *p, *pp;
    
    	if ( !(p = find(*header, delData)) ) {
    		return 0;
    	} else {
    		if (p == *header) {
    		//delete from top of the list
    			pp = (*header)->next;
    			free (*header);
    			*header = pp;
    		} else { 
    		//delete other nodes
    			// find previous node
    			for (pp = *header; pp->next != p; pp = pp->next);
    			
    			// bridge previous and next node
    			pp->next = p->next;
    
    			free (p);
    		}
    		return 1;
    	}
    }
    
    
    
    int push(node **header, int stackData)
    {
    	node *newNode, *p;
    
    	if ((newNode = (node *) malloc(sizeof(node))) == NULL) {
    		return 0;
    	}
    	
    	newNode->data = stackData;
    
    	newNode->next = *header;
    	*header= newNode;
    
    	return 1;
    }
    
    
    
    int pop(node **header, int *data)
    {
    	node *p;
    
    	if( !(*header) ){
    	//empty stack
    		return 0;
    	} else {
    		p = *header;
    		*data = (*header)->data;
    		*header = (*header)->next;
    		free(p);
    	}
    
    	return 1;
    }
    
    
    
    int main ( void )
    {
    	node *header = NULL, *pnode;
    	int i, n, data;
    
    	//add values to list
    	printf("Koliko brojeva zelite unijeti u listu: ");
    	scanf("%d", &n);
    
    	printf("\n");
    	for(i=1; i<=n; i++) {
    		printf("Unesite %d. broj: ", i);
    		scanf("%d", &data);
    		
    		if(!add(&header, data)) {
    			printf("Nema dovoljno memorije za dodavanje novog elementa u listu!\n");
    			return -1;
    		}	
    	}
    	
    	//display list
    	display(header);
    
    
    	//search through list
    	printf("\nUnesite element koji zelite pronaci: ");
    	scanf("%d", &data);
    	pnode=find(header, data);
    	if(pnode) {
    		printf("\tTrazeni element nalazi se na adresi: %p\n", pnode);
    	} else {
    		printf("\tTrazeni element ne postoji u listi\n");
    	}
    
    
    	//delete value from a list
    	printf("\nUnesite element koji zelite izbrisati: ");
    	scanf("%d", &data);
    	i = delete(&header, data);
    	if(i) {
    		printf("\tElement je uspjesno izbrisan\n");
    		display(header);
    	} else {
    		printf("\tTrazeni element ne postoji u listi\n");
    	}
    
    	printf("\nUnesite element koji zelite dodati na stog: ");
    	scanf("%d", &data);
    	if( !push(&header, data) ) {
    		printf("Nema dovoljno memorije za dodavanje novog elementa u listu!\n");
    	}
    	//display list
    	display(header);
    
    	while( pop(&header, &data) ) {
    		printf("Operacijom POP dobivena je vrijednost: %d\n", data);
    	}
    
    	//display list
    	display(header);
    
    return 0;
    }


  7. #7
    Senior Member Respawned sorcerer mronki's Avatar
    Datum registracije
    Mar 2008
    Lokacija
    tu i tamo
    Postova
    1.463

    Re: manipulacija vezanim listama-need help

    mislim da sam pohvatao, hvala na pomoći

Pravila postanja

  • Ne možeš stvarati nove teme
  • Ne možeš odgovarati na postove
  • Ne možeš slati privitke
  • Ne možeš mijenjati svoje postove
  •