[es] - [Zadatak] Punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste

danijel385
Danijel Markic
PMF, Zagreb

Član broj: 57379
Poruke: 13
*.cmu.carnet.hr.

Profil

[Zadatak] Punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste

^{23.04.2006. u 15:53 - pre 219 meseci}

Za zadatak sam dobio da rjesim ovo:

Citat:

Izraditi program za punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste (liste u kojoj svaki čvor sadrži pokazivač na prethodni i sljedeći čvor). Element liste sadržava cijeli broj i niz od 15 znakova. Lista se oblikuje prema cijelom broju (to je ključ), novi element se unosi u listu tako da su cijeli brojevi sortirani uzlazno, a elementi se brišu i pretražuju po vrijednosti cijelog broja. Funkcija za ispis elemenata u listi mora ispisati obje varijable koje čine element: cijeli broj i niz znakova.

Uspio sam rjesiti zadatak pomocu jednostruko povezane liste:

Code:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define BR_B 128
#define V_IME 30
#define V_TELEF 20

/* sablon strukture */
typedef struct carton_st {
    char ime[V_IME];
    char telefon[V_TELEF];
    struct carton_st *slijedeci;
} CARTON;
CARTON p_liste, *pocetak, *tekuci;

static int dodaj_k(void);
static int pronadji_k(void);
static int listaj_k(void);
static int citaj_k(void);
static int pisi_k(void);
CARTON *umetni_cvor(CARTON *);
void greska(char *);
static void prik_zapis(char *, char *);

char odgovor[BR_B + 1];

int main (void)
{
    int pk;
    tekuci = pocetak = &p_liste;
    pocetak->slijedeci = pocetak;

    puts("Naredbe za dadoteku imenika:");
    puts(" d = dodavanje novog unosa u datoteku");
    puts(" p = pronalazenje unosa prema njegovu imenu");
    puts(" l = izlistavanje unosa");
    puts(" i = izlaz bez cuvanja izmjena\n");
    while(1)
    {
        printf("Naredba (d, p, l ili i): ");
        gets(odgovor);
        switch (odgovor[0])
        {
            case 'd':
            case 'D':dodaj_k();break;
            case 'p':
            case 'P':pronadji_k();break;
            case 'l':
            case 'L':listaj_k();break;
            case 'i':
            case 'I':return EXIT_SUCCESS;
            default:break;
        }
    }

    return EXIT_SUCCESS;
}

static int citaj_k(void)
{
    char red[BR_B+1];
    int pk = 0;
    CARTON *priv;

        priv = umetni_cvor(tekuci);
        if (priv == NULL)
            greska("Nema dovoljno memorije");
        tekuci = priv;
        strcpy(tekuci->ime, strtok(red, "\t"));
        strcpy(tekuci->telefon, strtok(NULL, "\t"));
    }

static int dodaj_k(void)
{
    int pk = 0, i, pravibroj;
    CARTON *priv;

    priv = umetni_cvor(tekuci);
    if (priv == NULL)
        {
        fprintf(stderr, "Nema dovoljno memorije");
        ++pk;
        }
    else
        {
        tekuci = priv;
        printf("Ime: ");
        gets(odgovor);
        strcpy(tekuci->ime, odgovor);
        printf("Telefon: ");
        do
            {
                  scanf("%s", odgovor);
                pravibroj = 1;
                for(i=0; i<strlen(odgovor); i++)
                    {
                        if(isalpha(odgovor[i]))
                          pravibroj = 0;
                    }
                if(pravibroj == 0)
                printf("\nNiste unijeli broj!Ponovite unos: ");
            }
        while(pravibroj == 0);
        strcpy(tekuci->telefon, odgovor);
    }

    return 0;
}
static int listaj_k(void)
{
    int i,j,pk = 0;
    CARTON *priv;

    priv = pocetak;
    if (priv->slijedeci == pocetak) {
        puts("Lista je prazna");
        ++pk;
    }
    else
        while (priv->slijedeci != pocetak) {
            priv = priv->slijedeci;
            prik_zapis(priv->telefon, priv->ime);
        }

    return pk;
}
static int pisi_k(void)
{
    int pk = 0;
    CARTON *priv;

    priv = pocetak;
    if (priv->slijedeci == pocetak) {
        puts("Lista je prazna");
        ++pk;
    }
    else
        while (priv->slijedeci != pocetak) {
            priv = priv->slijedeci;
            printf("%s\t%s\n",priv->telefon, priv->ime);
        }
    return pk;
}

static int pronadji_k(void)
{
    int pk = 0;
    int pogodaka = 0;
    int duz;
    char *pz;
    CARTON *priv;

    priv = pocetak;
    if (priv->slijedeci == pocetak) {
        puts("Lista je prazna");
        return ++pk;
    }

    printf("Telefon koji trazite: ");
    gets(odgovor);
    duz = strlen(odgovor);
    while(priv->slijedeci != pocetak) {
        priv = priv->slijedeci;
        pz = priv->telefon;
        while (*pz != '\0') {
            if (strncmp(pz, odgovor, duz) == 0) {
                prik_zapis(priv->telefon, priv->ime);
                ++pogodaka;
            }
            ++pz;
        }
    }
    if (pogodaka == 0)
        puts("Karton nije pronadjen");

    return pk;
}

static void prik_zapis (char *zn1, char *zn2)
{
    printf ("%-*s\t%-*s\n",V_TELEF, zn1, V_IME, zn2);
}

CARTON *umetni_cvor (CARTON *listp)
{
    CARTON *novi;
    novi = (CARTON *) malloc (sizeof (CARTON));
    if (novi != NULL) {
        novi->slijedeci = listp->slijedeci;
        listp->slijedeci = novi;
    }

    return novi;
}

void greska (char *poruka)
{
    fprintf (stderr, "GRESKA: %s\n", poruka);
    exit (EXIT_FAILURE);
}

Zanima moze li se ovaj program preoblikovati u ono sto je zadano zadatkom (i kako)? Ne znam raditi sa dvostruko povezanim listama pa ne znam kako ovo napraviti, i ne znam kako napraviti da se brojevi slazu uzlazno? Molio bih za bilo kakvu pomoc...

Thanks in advance

"We haven't the money, so we've got to think." — Ernest Rutherford
-----------------------------------------------------------------
-[ D ¤ E ¤ U ¤ S ]-

Odgovor na temu

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
*.powernet.bg.

ICQ: 195487525
Sajt: cpptea.com

+1 Profil

Re: [Zadatak] Punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste

^{23.04.2006. u 17:23 - pre 219 meseci}

Evo jednog malog primera za dvostruko povezane C-liste sa uzlaznim sortiranjem po indeksu. Verovatno radi kako treba.

*edit*
Ideja je da se prilikom ubacivanja novog elementa pretrazi vec postojeci niz elemenata i pritom nadje mesto za njega. Kada je nadjen elemenat koji treba da bude pre ili posle novog elementa. Elemenat koji treba da se nalazi pre njega (ako postoji) treba da bude povezan sa njim, umesto sa svojim trenutnim sledecim (ako ga ima), a on sam treba da bude povezan sa bivsim sledecim svog prethodnog. Ako nesto iz prethodnog iskaza *ne postoji*, onda pricamo o dodavanju novog "prvog" odnosno novog "poslednjeg elementa". Nije neophodno da imas oba pokazivaca na "prvi" i "poslednji" ali oni dobro dodju u dosta prilika kao sto su npr. odredjivanje opsega elemenata niza, pretrazivanje u oba smera (odlucivanje kojoj strani liste je trazeni indeks verovatno blizi) itd.

_{[Ovu poruku je menjao Mali Misha dana 23.04.2006. u 18:41 GMT+1]}

Ipak se ++uje.

Prikačeni fajlovi

list.c - 2.55k

Odgovor na temu

EArthquake

Član broj: 20684
Poruke: 884
*.smin.sezampro.yu.

+67 Profil

Re: [Zadatak] Punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste

^{23.04.2006. u 17:54 - pre 219 meseci}

malo nevazna cinjenica ali mozda dublje objasnjava stvar i objasnjava gde se to koristi

naime to me podsetilo na doug lea`s implementaciju memory alokatora ili ti linuxove malloc algoritme
naime oni imaju upravo takvu doubly linked listu u kojoj se nalaze svi slobodni chunkovi koji mogu da se alocraju

chunkovi su poredjani po velicini naravno i svaki ima forward i backward pointer , tj pokazivac za chunk ispred i chunk iza

kada se chunk alocira on se vadi iz te doubly linked liste unlink()ovanjem sto je bila tehnika za eksploatisanje heap overflowa koju je predstavio solar designer ne to je vec isuvise offtopic :)

nove verzije glibc-a imaju novi implementacije malloc() algoritama koji sprecavaju tako lako iskoriscavanje overflow-a...

ajd pozdrav i sorry na nebitnim stvarima
Aca

Odgovor na temu

danijel385
Danijel Markic
PMF, Zagreb

Član broj: 57379
Poruke: 13
*.cmu.carnet.hr.

Profil

Re: [Zadatak] Punjenje, brisanje, pretraživanje i ispis dvostruko povezane liste

^{24.04.2006. u 09:37 - pre 219 meseci}

Uspio sam nesto napraviti, no sad mi ne radi pretrazivanje i brisanje po rijeci:

Code:

#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <stdlib.h>
typedef struct node {
    int lkey;
    char name[15];
    struct node* next;
    struct node* prev;
} TNODE;

TNODE b_list, *first, *last;

int LoadNode(TNODE *p);
void FreeNode(TNODE *p);
void PrintNode(TNODE *p);

void CreateList()
{
    TNODE *p;
    int n=sizeof(TNODE);

    first=last=0;
    for(;;)
    {
        if( (p=(TNODE*)malloc(n))==0 )
        {
            printf("\nNot enough memory");
            break;
        }

        if(LoadNode(p)!=1)
        {
            FreeNode(p);
            break;
        }

        p->next=0;
        if (first==0)
            first=last=p;
        else
        {
            last->next=p;
            last=p;
        }
    }
}

int LoadNode(TNODE *p)
{
    char opt;
    printf("\nNovi unos?");
    opt=getche();
    opt=toupper(opt);
    if(opt=='Y'&&'y')
    {
        puts("\n\nMolim, unesite podatke:");
        printf("\nSifra:\t");
        if (scanf("%d",&(p->lkey))!=1) return 0;

        printf("\nIme:\t");if (scanf("%s",p->name)!=1) return 0;
        return 1;
    }
    else
        return -1;
}
void FreeNode(TNODE *p)
{
    free(p);
}

void ViewAllList()
{
    TNODE *p;
    p=first;
     if(p==0)
        {
                printf("Lista je prazna");
        }
    while(p)
    {


        PrintNode(p);
        p=p->next;
    }
    return;
}

void FindNode(int key)
{


    TNODE *p;
    int pk=0;
    p=0;
    p=first;
    if(p->next==first)
        {
        puts("Lista je prazna");
        return ++p;
        }
        printf("Unesite kljuc: ");
        scanf("%d",key);
        while (p->next!=first)
        {
              p=p->next;
              p=p->lkey;
              PrintNode(p->lkey);
              }


}

void PrintNode(TNODE *p) //function specific to the application
{
    if(p) printf("\n%d\t%s",p->lkey,p->name);
}

void RemoveFirst()
{
    TNODE *p;

    if(first==0)
        return;

    if(first==last)
    {
        FreeNode(first);
        first=last=0;
        return;
    }

    p=first;
    first=first->next;
    FreeNode(p);
}

void RemoveLast()

{
    TNODE *p, *q;

    if(first==0)
        return;

    if(first==last)
    {
        FreeNode(first);
        first=last=0;
        return;
    }

    q=0;
    p=first;
    while(p!=last)
    {
        q=p;
        p=p->next;
    }

    p=last;
    FreeNode(p);
    q->next=0;
    last=q;

}

void RemoveByKey()
{
    TNODE *p, *q;
    int key;
    if(first==0)
        return;
scanf("%d",key);
    q=0;

    p=first;

      if(key == p->lkey)
        q=p;
        p=p->next;


    if(!p)
    {
        printf("\nNe postoji takav kod");
        return;
    }

    if(first==last)
    {
        FreeNode(first);
        first=last=0;
        return;
    }

    if(p==first)
    {
        first=first->next;
        FreeNode(p);
        return;
    }

    if(p==last)
    {
        q->next=0;
        last=q;
        FreeNode(p);
        return;
    }

    q->next=p->next;
    FreeNode(p);
}

void DeleteList()
{
    TNODE *p;

    p=first;
    while(p)
    {
        first=first->next;
        FreeNode(p);
        p=first;
    }
    last=0;
}
int main (void)
{
    int pk;
    char odgovor[15];
    /* ucitavanje podataka u bafer */
    puts("Odaberite opciju:\n");
        puts("1 -> Dodati podatke u red.");
        puts("2 -> Izbrisati podatke iz reda.");
        puts("3 -> Ispisati red.");
        puts("4 -> Pretrazivanje liste.");
        puts("5 -> IZLAZ");
    while(1)
    {
        printf("\nNaredba: ");
        gets(odgovor);
        switch (odgovor[0])
        {
            case '1':CreateList();;break;
            case '2':
                 {
                     printf("Sto zelite obrisati:\n");
                     printf("a -> izbrisati prvi unos\n");
                     printf("b -> izbrisati posljednji unos\n");
                     printf("c -> izbrisati zadani unos\n");
                     printf("d -> izbrisati cijelu listu\n");
                     printf("e -> IZLAZ\n");
                     printf("\nNaredba:");
                     gets(odgovor);
                     switch (odgovor[0])
                     {
                            case 'a':
                            case 'A':RemoveFirst();break;
                            case 'b':
                            case 'B':RemoveLast();break;
                            case 'c':
                            case 'C':RemoveByKey();break;
                            case 'd':
                            case 'D':DeleteList();break;
                            case 'e':
                            case 'E':return EXIT_SUCCESS;
                            default:break;
                     }
            case '3':ViewAllList();break;
            case '4':FindNode(1);break;
            case '5':return EXIT_SUCCESS;
            default:break;
        }
    }
}
    return EXIT_SUCCESS;
}

Moze li netko pogledati u cemu je problem? Tocnije kada pokrenem program i unesem podatke te pokrenem pretrazivanje ili brisanje program mi se srusi... Kako da rijesim ovo sa sortiranjem?

Hvala unaprijed...

_{[Ovu poruku je menjao danijel385 dana 24.04.2006. u 10:38 GMT+1]}

"We haven't the money, so we've got to think." — Ernest Rutherford
-----------------------------------------------------------------
-[ D ¤ E ¤ U ¤ S ]-

Odgovor na temu