Matematické Fórum

ragu · 18. 10. 2009 20:05

Ahoj,
mám obousměrně zřetězený seznam, do kterého mám přidat funkce výpis, výpis pozpátku, hledání a mazání. S výpisem jsem si poradil, v hledání mám asi nějakou chybu, ale nevím si rady s mazáním. Mohl by mi někdo poradit?
děkuji

Code:

// cviceni4.cpp : Defines the entry point for the console application.
//
#include <malloc.h>
#include <stdlib.h>
#include <string.h>


#include "stdafx.h"


struct uzel 
{
        char *jmeno;
        struct uzel *prev,*next;

}*head,*tail;
void add (char *j)
{
    struct uzel *n = (struct uzel*)malloc(sizeof(struct uzel));
    if(n==NULL)
    {
        printf("Neni pamet");
        exit (1);
    }
    n->jmeno = (char*)malloc(strlen(j)+1);
    if(n->jmeno==NULL)
    {
        printf("Neni pamet");
        exit (2);
    }
    strcpy (n->jmeno, j);
    n->prev=NULL;
    n->next=head;
    head=n;
    if(n->next!=NULL)
    {
        n->next->prev=n;

    };

    if(tail==NULL)
    {
        tail=n;
    };
    

}



void vypis(void)
{
    struct uzel *uk=head;

    while (uk!=NULL)
    {
        printf("uzel %s\n", uk->jmeno);
        uk = uk->next;
    }
}

void vypispozpatku(void)
{
    struct uzel *uk=tail;

    while (uk!=NULL)
    {
        printf("uzel %s\n", uk->jmeno);
        uk = uk->prev;
    }
}
struct uzel* najdi(char*j)
{
    struct uzel *uk=head;

    while (uk!=NULL)
    {
        if(!strcmp(j,uk->jmeno))
        {
            return(uk);
        }
        uk = uk->prev;
    }
    return(NULL);
}


/*

void smaz(void)
*/
int _tmain(int argc, _TCHAR* argv[])
{
    add("jarda");
    add("karel");
    add("ana");
    vypis();
    vypispozpatku();
    najdi ();
    

    return 0;
}

Oxyd · 18. 10. 2009 20:18

↑ ragu:

V najdi máš uk = uk->prev; -- tedy procházíš uzel směrem k začátku -- ale začínáš ho prohledávat od začátku -- takže když nenajdeš v prvním uzlu, tak hned skončíš. Buď procházej ke konci nebo začínej od konce.

A odstraňování -- prostě najdeš uzel se správnou hodnotou (pomocí najdi třeba) a pak přepojíš ukazatele. Nejlíp se to vysvětluje asi obrázek:

ragu · 18. 10. 2009 20:21

↑ Oxyd:
Díky za odpověď, ale to mi moc nepomůže, protože tomu moc nerozumím zatím, teprve začínám. Mohl bys mi to prosím napsat přímo v kodu?

Oxyd · 18. 10. 2009 20:39 — Editoval Oxyd (18. 10. 2009 20:47)

Můžu:

Code:

void odstran(char const* co) {
  struct uzel* u = najdi(co);
  if (u) {
    if (u != head && u != tail) {
      /* Odstranovani ze zacatku a z konce sou zvlastni pripady -- tady osetrim odstraneni zprostredka */

      /* Ted udelam to, co je na obrazku pod cislem 2.
       * Rozmysli si, ze u->next i u->prev nejsou nullove */
      u->next->prev = u->prev;
      u->prev->next = u->next;

      /* A ted ten uzel odstranim -- na obrazku ciso 3. */
      free(u);
    } else if (u == head) {
      /* Odstranuju zacatek, takze spojak bude ted zacinat druhym uzlem -- druhy uzel tak bude
       * mit ukazatel "prev" nullovy, protoze pred nim nic nebude */
      if (u->next) {  /* Ovsem pozor na jednoprvkovy spojak */
        u->next->prev = NULL;
      }
      head = u->next;
      free(u);
    } else {  /* u == tail */
      /* Symetricke s predchozim pripadem */
      if (u->prev) {
        u->prev->next = NULL;
      }
      tail = u->prev;
      free(u);
    }
  }
}

ragu · 18. 10. 2009 20:49 — Editoval ragu (18. 10. 2009 20:49)

↑ Oxyd:
díky moc

Matematické Fórum

#1 18. 10. 2009 20:05

obousměrně zřetězený seznam v C

Code:

#2 18. 10. 2009 20:18

Re: obousměrně zřetězený seznam v C

#3 18. 10. 2009 20:21

Re: obousměrně zřetězený seznam v C

#4 18. 10. 2009 20:39 — Editoval Oxyd (18. 10. 2009 20:47)

Re: obousměrně zřetězený seznam v C

Code:

#5 18. 10. 2009 20:49 — Editoval ragu (18. 10. 2009 20:49)

Re: obousměrně zřetězený seznam v C

Zápatí