Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

[Zadatak] Jednostruko spregnuta lista

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Jednostruko spregnuta lista

[ Pregleda: 6729 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

dolke022
Dean Dolic
Inđija - Novi Sad

Član broj: 80485
Poruke: 96
*.bxy.org.yu.

Sajt: www.3dcrystal3d.com


+1 Profil

icon [Zadatak] Jednostruko spregnuta lista09.01.2006. u 01:28 - pre 221 meseci
Napisati C program koji demonstrira realizaciju
osnovnih operacija sa dinamickom strukturom podataka
oblika jednostruko spregnute liste. Element liste se
sastoji od dva polja: podatak koji predstavlja ceo
broj i pokazivac na sledeci element liste.
Operacije koje treba realizovati sa jednostruko
spregnutom listom su:
-Unos novog broja, po izboru korisnika(na pocetak ili
kraj liste)
NAPOMENA: Zadovoljiti uslov da se u listi ne moze
nalaziti vise od 5 istih brojeva)
-Modifikacija (umesto jednog broja treba upisati drugi
broj)
-Trazenje broja u listi
-Brisanje broja iz liste (ako ima vise istih,
izbrisati ih sve)
DODATNO:
Napraviti tabelarni prikaz pojavljivanja brojeva u listi.

TheTruthIsOutThere
Nije meni krivo sto kradu moje ideje, vec ih zalim sto nemaju svoje!!! N.T.
There is appx 6.877.912.425 people in the WORLD, but sometimes all you need is
ONE - OTH

www.3dcrystal3d.com
 
Odgovor na temu

RedDrake

Član broj: 80474
Poruke: 17
*.adsl.net.t-com.hr.



Profil

icon Re: [Zadatak] Jednostruko spregnuta lista09.01.2006. u 02:52 - pre 221 meseci
Code:

//------------------------------------------------------------------------
//
// Name : Lista.cpp
//
// Desc : Glavni source fajl
//
//------------------------------------------------------------------------
// Include files
//------------------------------------------------------------------------
#include <stdio.h>
#include <malloc.h>





//------------------------------------------------------------------------
//
// Name : ListNode
//
// Desc : Element linkirane liste
//
//------------------------------------------------------------------------
typedef struct _ListNode
{
    struct _ListNode*            mNext;

    int                            mValue;
}ListNode;





//------------------------------------------------------------------------
//
// Name : main
//
// Desc : Pocetna funkcija koda
//
//------------------------------------------------------------------------
int main (void)
{
    ListNode*                    fFirst = NULL;
    ListNode*                    fLast = NULL;

    int                            fInput;
    char                           fPos;

    ListNode* fNode;
    int nRefs;

    do
    {
        printf("Unesite broj : \n");
        scanf("%d", &fInput);

        printf("Unesite poziciju broja (K)raj/(P)ocetak \n");
        scanf("%c", &fPos);
        scanf("%c", &fPos);

        fNode = fFirst;
        nRefs = 0;

        if (fFirst != NULL)
        {
            do
            {
                if (fNode->mValue == fInput)
                    nRefs++;
                
                fNode = fNode->mNext;
            }while(fNode != NULL && nRefs < 5);
        }

        if (nRefs >= 5)
        {
            printf("U listi vec postoji 5 brojeva zadane vrijednosti ! \n");
        }
        else
        {
            ListNode* fTemp = (ListNode*)malloc(sizeof(ListNode));
            fTemp->mValue = fInput;

            if (fFirst != NULL)
            {
                if (fPos == 'K')
                {
                    fLast->mNext = fTemp;
                    fLast = fTemp;
                    fLast->mNext = NULL;
                }
                else
                {
                    fTemp->mNext = fFirst;
                    fFirst = fTemp;
                }
            }
            else
            {
                fFirst = fTemp;
                fLast = fTemp;

                fFirst->mNext = NULL;
            }
        }

    }while (fInput != 0);


    fNode = fFirst->mNext;

    do
    {
        printf("%d ", fNode->mValue);
        
        free((void*)fFirst);
        fFirst = fNode;

        fNode = fNode->mNext;
    }while (fNode != NULL);

    getchar();

    return 0;
};


kod ti ne radi sve trazeno, ali sve te funkcije je lako ubaciti - sa minimalno truda ...
ovo je valja ispravno - mozda sam pogresno svatio zadatak :)
je sigurno da mora bit zadatak u c ? u c++ se ovo moze rijesit u par linija koda sa STL-om.
 
Odgovor na temu

X Files
Vladimir Stefanovic
Pozarevac

SuperModerator
Član broj: 15100
Poruke: 4901
*.dynamic.sbb.rs.

Jabber: xfiles@elitesecurity.org


+638 Profil

icon Re: [Zadatak] Jednostruko spregnuta lista20.03.2009. u 21:55 - pre 182 meseci
Code:

/*
   Napisati C program koji demonstrira realizaciju osnovnih operacija
   sa dinamickom strukturom podataka oblika jednostruko spregnute liste.

   Element liste sastoji se od dva polja: Podatak koji predstavlja ceo
   broj i pokazivaca na sledeci element liste.

   Operacije koje treba realizovati sa jednostruko spregnutom listom su:
   * Unos novog broja i to po izboru korisnika na pocetku ili kraj liste
   (NAPOMENA:Zadovoljiti uslov da se u liste ne moze nalaziti vise od pet
   istih brojeva).
   * Modifikacija (umesto jednog broja treba upisati drugi broj)
   * Trazenje broja u listi i
   * brisanje brisanje broja iz liste
   (ako ih ima vise istih izbrisati ih sve).
*/
#include <stdio.h>
#include <stdlib.h>

#define MAX_DOZVOLJENI_BROJ_POJAVA 5

/* Struktura jednostruko sregnute liste */
struct jednostruko_spregnuta_lista
{
    int broj;
    struct jednostruko_spregnuta_lista *sledeci;
};

/* promovisanje strukture u tip, da bismo kasnije lakse s njome radili */
typedef struct jednostruko_spregnuta_lista cvor;

/* inicijalizovanje liste, bitno je zbog testiranja granica (nule su granice) */
cvor *prvi = NULL;
cvor *poslednji = NULL;

/* operacije nad menijem - deklaracija */
void unos_broja_na_kraj();
void unos_broja_na_pocetak();
void zamena_jednog_broja_drugim();
void brisanje_svih_pojava_broja();
void trazenje_broja();
void ispis_brojeva();
void zavrsetak_rada();
void tabelarni_pregled();

/* operacije nad listom - deklaracija */
int brojac_pojava_broja( int );
void unos( char, int );
void ispis();
void zamena( int, int );
void pretraga( int );
void brisanje();
void brisanje_elementa( int );
void brisanje_svih_elemenata( int );
void tabela(); /* <--- NOVO */
int broj_elemenata_liste();

/* glavna funkcija */
int main( void )
{
    /* odgovor u meniju */
    char odgovor;

    /* meni: ispis i akcije */
    do
    {
        /* meni: ispis... */
        do
        {
            printf("\n\n\n");
            printf( "------------------------------------------------\n" );
            printf( "M E N I :\n" );
            printf( "------------------------------------------------\n" );
            printf( "[1] - Unos broja na kraj\n" );
            printf( "[2] - Unos broja na pocetak\n" );
            printf( "[3] - Zamena jednog broja drugim\n" );
            printf( "[4] - Brisanje svih pojava broja\n" );
            printf( "[5] - Trazenje broja\n" );
            printf( "[6] - Ispis brojeva\n" );
            printf( "[7] - Tabelarni pregled\n" );
            printf( "\n" );
            printf( "[0] - Zavrsetak rada\n" );
            printf( "------------------------------------------------\n" );
            printf( "Vas izbor?:" );
            fflush( stdin );
            scanf( "%c", &odgovor );
        /* ako nije jedna od navedenih stavki, ispisi ponovo */
        } while ( odgovor < '0' || odgovor > '7' );

        /* meni: akcije... */
        switch ( odgovor )
        {
            case '1' :  unos_broja_na_kraj();
                        break;
            case '2' :  unos_broja_na_pocetak();
                        break;
            case '3' :  zamena_jednog_broja_drugim();
                        break;
            case '4' :  brisanje_svih_pojava_broja();
                        break;
            case '5' :  trazenje_broja();
                        break;
            case '6' :  ispis_brojeva();
                        break;
            case '7' :  tabelarni_pregled();
                        break;
            /* case '0' */
            default :   zavrsetak_rada();
                        break;
        }
    /* ostani u petlji i radi sa listom dok god korisnik ne zeli da izadje iz programa*/
    } while ( odgovor != '0' );

    return 0;
}

/*
    -----------------------------------------------------------------
    IMPLEMENTACIJA MENIJA
    -----------------------------------------------------------------
*/
void unos_broja_na_kraj()
{
    int broj_za_unos;
    printf( "\n\n----- UNOS BROJA NA KRAJ -----------------------\n" );
    printf( "Unesite broj: " );
    scanf( "%d", &broj_za_unos );
    if ( brojac_pojava_broja( broj_za_unos ) < MAX_DOZVOLJENI_BROJ_POJAVA )
        unos( 'k', broj_za_unos );
    else
        printf( "\n\nNEDOZVOLJEN UNOS:\nU listi se vec nalazi maksimalan (%d) dozvoljeni broj pojava broja %d !\n\n", MAX_DOZVOLJENI_BROJ_POJAVA, broj_za_unos );
}

void unos_broja_na_pocetak()
{
    int broj_za_unos;
    printf( "\n\n----- UNOS BROJA NA POCETAK --------------------\n" );
    printf( "Unesite broj: " );
    scanf( "%d", &broj_za_unos );
    if ( brojac_pojava_broja( broj_za_unos ) < MAX_DOZVOLJENI_BROJ_POJAVA )
        unos( 'p', broj_za_unos );
    else
        printf( "\n\nNEDOZVOLJEN UNOS:\nU listi se vec nalazi maksimalan (%d) dozvoljeni broj pojava broja %d !\n\n", MAX_DOZVOLJENI_BROJ_POJAVA, broj_za_unos );
}

void zamena_jednog_broja_drugim()
{
    int broj_koji_se_trazi, broj_za_zamenu;
    int brojac_postojecih, brojac_novih;
    printf( "\n\n----- ZAMENA JEDNOG BROJA DRUGIM ---------------\n" );
    if ( prvi == NULL )
    {
        printf( "\n\nNema unetih elemenata!\n\n" );
    }
    else
    {
        printf( "Unesite broj koji se trazi: " );
        scanf( "%d", &broj_koji_se_trazi );
        printf( "Unesite broj za zamenu: " );
        scanf( "%d", &broj_za_zamenu );

        if ( broj_koji_se_trazi == broj_za_zamenu )
        {
            printf( "\n\nBrojevi moraju biti razliciti!.\n\n" );
        }
        else
        {
            brojac_postojecih = brojac_pojava_broja( broj_za_zamenu );
            brojac_novih = brojac_pojava_broja( broj_koji_se_trazi );

            if ( ( brojac_postojecih + brojac_novih ) <= MAX_DOZVOLJENI_BROJ_POJAVA )
                zamena( broj_koji_se_trazi, broj_za_zamenu );
            else
                printf( "\n\nNEDOZVOLJENA OPERACIJA:\nZamenom, u listi bi bio premasen maksimalan (%d) dozvoljeni broj pojava broja %d !\n\n", MAX_DOZVOLJENI_BROJ_POJAVA, broj_za_zamenu );
        }
    }
}

void brisanje_svih_pojava_broja()
{
    int broj_koji_se_trazi;
    printf( "\n\n----- BRISANJE SVIH POJAVA BROJA ---------------\n" );
    if ( prvi == NULL )
    {
        printf( "\n\nNema unetih elemenata!\n\n" );
    }
    else
    {
        printf( "Unesite broj koji se trazi za brisanje: " );
        scanf( "%d", &broj_koji_se_trazi );
        brisanje_svih_elemenata( broj_koji_se_trazi );
        //brisanje_elementa( broj_koji_se_trazi );
    }
}


void trazenje_broja()
{
    int broj_koji_se_trazi;
    printf( "\n\n----- TRAZENJE BROJA ---------------------------\n" );
    if ( prvi == NULL )
    {
        printf( "\n\nNema unetih elemenata!\n\n" );
    }
    else
    {
        printf( "Unesite broj koji se trazi: " );
        scanf( "%d", &broj_koji_se_trazi );
        pretraga( broj_koji_se_trazi );
    }
}

void tabelarni_pregled()
{
    printf( "\n\n----- TABELARNI PREGLED ------------------------\n" );
    tabela();
}

void ispis_brojeva()
{
    printf( "\n\n----- ISPIS BROJEVA ----------------------------\n" );
    ispis();
}


void zavrsetak_rada()
{
    printf( "\n\n----- ZAVRSETAK RADA ---------------------------\n" );
    brisanje();
    printf( "Hvala, vidimo se!\n" );
}


/*
    -----------------------------------------------------------------
    IMPLEMENTACIJA OPEACIJA SA LISTOM
    -----------------------------------------------------------------
*/

/* BROJ POJAVA TRAZENOG BROJA U LISTI */
int brojac_pojava_broja( int trazeni_broj )
{
    cvor *trenutni = prvi;
    int broj_pojava = 0;

    if ( trenutni != NULL )
    {
        do
        {
            if ( trenutni->broj == trazeni_broj )
                ++broj_pojava;
            trenutni = trenutni->sledeci;
        } while ( trenutni != NULL );
    }
    return ( broj_pojava );
}

/* DODAJE broj_za_unos NA POCETAK 'p' ILI NA KRAJ 'k' LISTE, ZAVISNO OD ARGUMENTA pozicija */
void unos( char pozicija, int broj_za_unos )
{
    cvor *pomocni = (cvor*)malloc( sizeof( cvor ) );
    pomocni->broj = broj_za_unos;

    if ( prvi != NULL)
    {
        if ( pozicija == 'k')
        {
            poslednji->sledeci = pomocni;
            poslednji = pomocni;
            poslednji->sledeci = NULL;
        }
        else
        {
            pomocni->sledeci = prvi;
            prvi = pomocni;
        }
    }
    else
    {
        prvi = pomocni;
        poslednji = pomocni;
        prvi->sledeci = NULL;
    }
}

/* ISPISUJE SVE ELEMENTE LISTE */
void ispis()
{
    if ( prvi == NULL )
    {
        printf( "\n\nNema unetih elemenata!\n\n" );
    }
    else
    {
        cvor *trenutni = prvi;
        printf( "LISTA: " );
        while ( trenutni != NULL )
        {
            printf( "%d\t", trenutni->broj );
            trenutni = trenutni->sledeci;
        }
        printf( "\n" );
    }
}


/* ISPISUJE SVE ELEMENTE LISTE */
void tabela() /* <--- NOVO, CELA FUNKCIJA */
{
    int i, vec_postoji;

    int ukupno_elemenata;
    int brojac=0;
    int *element;
    int *ponavljanja;

    ukupno_elemenata = broj_elemenata_liste();

    element = (int*)malloc( ukupno_elemenata * sizeof(int) );
    if ( element == NULL ) return;

    ponavljanja = (int*)malloc( ukupno_elemenata * sizeof(int) );
    if ( ponavljanja == NULL ) { free( element ); return; }


    if ( prvi == NULL )
    {
        printf( "\n\nNema unetih elemenata!\n\n" );
    }
    else
    {

        cvor *trenutni = prvi;
        while ( trenutni != NULL )
        {
            /* da li je tekuci element vec ubelezen u listu jedinstvenih */
            vec_postoji=0;
            for ( i=0; i<brojac; i++ )
            {
                if ( element[i] == trenutni->broj )
                {
                    vec_postoji = 1; /* element je vec u listi */
                    break;
                }
            }
            if ( vec_postoji == 0 ) /* ako broj ne postoji, treba ga uvesti u listu jedinstvenih i prebrojati pojave */
            {
               element[brojac] = trenutni->broj;
               ponavljanja[brojac] = brojac_pojava_broja( trenutni->broj );
               ++brojac;
            }

            trenutni = trenutni->sledeci;
        }

        for ( i=0; i<brojac; i++ )
            printf( "BROJ: %d\t\tPONAVLJANJA: %d\n", element[i], ponavljanja[i] );
    }

    free( element );
    free( ponavljanja );
}

/* KOLIKO LISTA IMA ELEMENATA */
int broj_elemenata_liste()
{
    int broj_elemenata = 0;

    cvor *trenutni = prvi;
    while ( trenutni != NULL )
    {
        ++broj_elemenata;
        trenutni = trenutni->sledeci;
    }

    return( broj_elemenata );
}

/* MENJA TRAZENI SA NOVIM BROJEM */
void zamena( int trazeni_broj, int novi_broj )
{
    cvor *trenutni = prvi;
    int broj_zamena = 0;

    if ( trenutni != NULL )
    {
        do
        {
            if ( trenutni->broj == trazeni_broj )
            {
                trenutni->broj = novi_broj;
                broj_zamena++;
            }
            trenutni = trenutni->sledeci;
        } while ( trenutni != NULL );

        if ( broj_zamena > 0 )
        {
            printf( "\n\nZamenjeno je %d pojava broja %d brojem %d.\n\n", broj_zamena, trazeni_broj, novi_broj );
        }
        else
        {
            printf( "\n\nNema pojava broja %d u listi.\n\n", trazeni_broj );
        }
    }
}

/* PROVERAVA DA LI ODREDJENI BROJ POSTOJI U LISTI */
void pretraga( int trazeni_broj )
{
    int pojava = brojac_pojava_broja( trazeni_broj );
    if ( pojava == 0 )
    {
        printf( "\n\nNema pojave broja %d u listi!\n\n", trazeni_broj );
    }
    else
    {
        printf( "\n\nPronadjeno je %d pojava broja %d u listi.\n\n", pojava, trazeni_broj );
    }
}

/* BRISE SVE ELEMENTE IZ LISTE (OVO SE RADI NA KRAJU, DA SE OSLOBODI MEMORIJA) */
void brisanje()
{
   cvor *trenutni = prvi;
   while ( trenutni )
   {
      trenutni = trenutni->sledeci;
      free (prvi);
      prvi = trenutni;
   }
}


/* BRISE OZNACENI ELEMENTE IZ LISTE */
void brisanje_elementa( int broj_za_brisanje )
{
    cvor* trenutni = prvi;
    cvor *novicvor, *pomocni;
    novicvor = trenutni;

    if ( trenutni->broj == broj_za_brisanje )
    {
        /* Brisanje prvog cvora */
        novicvor = trenutni;
        trenutni = trenutni->sledeci;
        free ( novicvor );
        prvi = trenutni;
        return;
    }
    else
    {
        while ( novicvor->sledeci->sledeci != NULL )
        {
            // provera uslova za brisanje svih cvorova
            // sem prvog i zadnjeg
            if ( novicvor->sledeci->broj == broj_za_brisanje )
            {
                pomocni=novicvor->sledeci;
                novicvor->sledeci=novicvor->sledeci->sledeci;
                free( pomocni );
                prvi = trenutni;
                return;
            }
            novicvor=novicvor->sledeci;
        }
        if ( novicvor->sledeci->sledeci == NULL && novicvor->sledeci->broj == broj_za_brisanje )
        {
            // Provera uslova za brisanje poslednjeg cvora
            free( novicvor->sledeci );
            novicvor->sledeci=NULL;
            prvi = trenutni;
            return;
        }
    }
    return;
}

/* BRISE SVE OZNACENE ELEMENTE IZ LISTE */
void brisanje_svih_elemenata( int broj_za_brisanje )
{
    while ( brojac_pojava_broja( broj_za_brisanje ) > 0 )
    {
        brisanje_elementa( broj_za_brisanje );
        printf("Prolaz!\n");
    }
}


Hvala Danijelu.
 
Odgovor na temu

[es] :: C/C++ programiranje :: C/C++ za početnike :: [Zadatak] Jednostruko spregnuta lista

[ Pregleda: 6729 | Odgovora: 2 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.