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.

=> Spoiler Alert: <=

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 :)

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?

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

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.

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

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)

=> Spoiler Alert: <=

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;
}

---

mislim da sam pohvatao, hvala na pomoći :D