Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

Odkaz na výstup diff

Obě strany předchozí revize Předchozí verze
Následující verze
Předchozí verze
public:memdebug2 [2015/02/05 23:53]
Jiří Weiser odstraněno
public:memdebug2 [2018/02/24 19:10] (aktuální)
Řádek 1: Řádek 1:
-====== Ladění nefunkčního programu - list ====== +<code c list.c>
- +
-Níže uvedený program implementuje často používanou strukturu [[http://​en.wikipedia.org/​wiki/​Doubly_linked_list | Oboustranně spojený seznam]]. Přestože jej lze zkompilovat,​ tak tento program obsahuje celou řadu záměrně vložených chyb. Vašim úkolem je jeho oprava tak, aby: +
-  - nepadal se SIGSEGV (nekorektní zápis do paměti) +
-  - korektně implementoval strukturu Seznam +
-  - vypisoval všechny vložené položky +
-  - neměl žádné memory leaks  +
- +
-Tento nekorektní program vznikl drobnými úpravami korektního kódu. Program tedy celý nepřepisujte,​ pouze se snažte nalézt chyby a opravte je. Není nutné přidávat žádné dodatečné funkce, pouze upravujte existující. K řešení využijte debugger, dodatečné ladící výstupy a tužku a papír. +
- +
-Očekávaný výstup programu je: +
- +
-    Seznam tam +
-    Slovo: 21 +
-    Nic: 7 +
-    Zdar: 115 +
-    Ahoj: 3 +
-     +
-    Seznam zpet +
-    Ahoj: 3 +
-    Zdar: 115 +
-    Nic: 7 +
-    Slovo: 21 +
-     +
-    Seznam tam +
-    Nic: 7 +
-    Zdar: 115 +
-    Ahoj: 3 +
-     +
-    Seznam zpet +
-    Ahoj: 3 +
-    Zdar: 115 +
-    Nic: 7 +
-     +
-<code c list_problems.c> +
 #include <​stdio.h>​ #include <​stdio.h>​
 #include <​stdlib.h>​ #include <​stdlib.h>​
 #include <​string.h>​ #include <​string.h>​
  
-typedef struct ​_PRVEK ​+typedef struct ​t_item
-    ​char *slovo;​ +  int value
-    ​int pocet+  struct ​t_item ​*next; 
-    struct ​_PRVEK *next+}t_item;
-    struct _PRVEK *prev+
-PRVEK;+
  
-typedef struct _LIST { +void enqueue(t_itemlist, int value)
-    PRVEK *prvni; // ukazatel na prvni prvek v seznamu +int dequeue(t_itemlist);
-    ​PRVEK ​*posledni; ​    // ukazatel na posledni prvek v seznamu +
-} LIST;+
  
- +int main()
-/** +
-    Prida dalsi prvek +
-    @param list struktura list +
-    @param slovo retezec k pridani +
-    @param hodnota k pridani +
-*/ +
-void pridej_prvek(LIST* list, char *slovo, ​int pocet)+
 { {
-    // 1. Vytvorime novou polozku +  int value
-    PRVEK *n = (PRVEK *) malloc (sizeof(PRVEK))+  ​t_item ​*list;
-    ​n->​slovo = (char*) malloc(strlen(slovo));​ +
-    // 2. Nastavime data polozky dle parametru funkce +
-    strcpy(n->​slovo,​ slovo); +
-    n->pocet = pocet;+
  
-    // 3. Inicializujeme pozici v seznamu ​vsuneme na uplne prvni misto +  printf("​Zadejte hodnoty (zaporna-konec):"​);​ 
-    ​n->next = list->​prvni; // dalsi prvek je ten, co byl predtim prvni +  do 
-    ​if (n->next != NULL{ +  { 
-        // u puvodniho prvniho prvku musime aktualizovat ukazatel na predesly prvek +    ​scanf("​%d",&​value)
-        // n->next je ekvivalentni k list->​prvni. U nej nastavime polozku ->prev na nove vytvorenou polozku +    ​enqueue(list,value); 
-        n->​next->​prev = n; +  ​}while(value>0);
-    }+
  
-    ​list->prvni = n; // Novou polozku nastavime jako uplne prvni prvek do list->prvni+  printf("​Hodnoty v seznamu:​\n"​);​ 
 +  while((value=dequeue(list))>0) 
 +  { 
 +    printf("​%d ",​value);​ 
 +  } 
 +  printf("​\n"); 
 +  free(list);
 } }
  
- +void enqueue(t_item* list, int value)
-/** +
-    Vypise obsah spojovaneho seznamu pruchodem od zacatek po konec +
-    @param list struktura list +
-*/ +
-void vypis_tam(LIST* list)+
 { {
-    printf("​\nSeznam tam\n"); +  t_item *item = malloc(sizeof(t_item)); 
-    ​PRVEK ​*= list->prvni+  ​item->​value=value;​ 
-    // Projdeme cely seznam od prvniho po posledni prvek +  t_item ​*last = list; 
-    ​while (!= NULL) +  while( ​last != NULL ) 
-    +  
-        ​printf("​%s:​ %i\n", p->slovo, p->​pocet); // Vypiseme jeho obsah +    ​last=last->next
-        p = p->next; +  } 
-    }+  last->next=item;
 } }
  
-/** +int dequeue(t_item* list)
-    Vypise obsah spojovaneho seznamu pruchodem od konce po zacatek +
-    @param list struktura list +
-*/ +
-void vypis_zpet(LIST* list)+
 { {
-    printf("​\nSeznam zpet\n"​);​ +   int value = list->value
-    PRVEK *p = list->posledni+   ​list = list->​next;​ 
-    ​while(p != NULL) +   ​return ​value;
-    { +
-        printf("​%s:​ %i\n", p->​slovo,​ p->​pocet);​ +
-        p = p->​prev;​ +
-    } +
-+
- +
-/** +
-    Projde seznam a hleda prvek zadany argumentem slovo +
-    @param ​list struktura list +
-    @param slovo hledane slovo v seznamu +
-    @return ukazatel na prvek s hodnotou <​i>​slovo</​i>​. Pokud neni nalezen, tak NULL . +
-*/ +
-PRVEK *najdi(LIST* list, char *slovo) +
-+
- +
-    PRVEK *p = list->​prvni;​ +
-    while(p != NULL) +
-    { +
-        if (!strcmp(slovo,​p->​slovo)) return p; // Otestujeme, zda jsme nasli hledany prvek +
-        p = p->​next;​ +
-    } +
- +
-    // Pokud jsme dosli sem, tak prvek nebyl nalezen +
-    return NULL; +
-+
- +
-/** +
-    Spoji ukazatele u sousedu kolem odebiraneho prvku, smaze prvek zadany ukazatelem a uvolni pamet. +
-    @param list struktura list +
-    @param p prvek ke smazani +
-    @return nic +
-*/ +
-void smaz(LIST* list, PRVEK *p) +
-+
-    // 1. Spoji ("​premosti"​) ukazatele u sousedu kolem odebiraneho prvku +
-    if (p->next != NULL) { +
-        p->​next->​prev = p->​prev;​ +
-    } +
-    if (p->prev != NULL) { +
-        p->​prev->​next = p->​next;​ +
-    } +
- +
-    // 2. Aktualizuj prvni a posledni ptvek, pokud je to treba +
-    if (list->​posledni == p) list->​posledni = p->​prev;​ +
-    if (list->​prvni==p) list->​prvni = p->​next;​ +
- +
-    // 3. Uvolni pamet +
-    free(p); +
-+
- +
-/** +
-    Uvolni prvky struktury list +
-    @param list struktura list +
-*/ +
-void uvolni(LIST* list) +
-+
-    PRVEK *p = list->​prvni;​ +
-    // Projdeme cely seznam od prvniho po posledni prvek +
-    while (p != NULL) +
-    { +
-        smaz(list, p); +
-        p = p->​next;​ +
-    } +
-+
- +
-int main(void) +
-+
-    LIST list; +
-    pridej_prvek(&​list,​ "​Ahoj",​ 3); +
-    pridej_prvek(&​list,​ "​Zdar",​ 115); +
-    pridej_prvek(&​list,​ "​Nic",​ 7); +
-    pridej_prvek(&​list,​ "​Slovo",​ 21); +
-    vypis_tam(&​list);​ +
-    vypis_zpet(&​list);​ +
-    PRVEK *h = najdi(&​list,​ "​Slovo"​);​ +
-    smaz(&​list,​ h); +
-    vypis_tam(&​list);​ +
-    vypis_zpet(&​list);​ +
-    getchar();​ +
-    uvolni(&​list);​ +
- +
-    ​return ​0;+
 } }
 </​code>​ </​code>​
- 
QR Code
QR Code public:memdebug2 (generated for current page)