Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

C-Kurs/BubbleSortDebug/Musterlösung: Unterschied zwischen den Versionen

(Die Seite wurde neu angelegt: „Der erste Bug verursacht einen Segmentation fault oder eine falsche Ausgabe. Er befindet sich in Zeile 23. Die Abbruchbedingung ist j < 5, dass heisst j geht bis ...“)
 
 
(2 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 8: Zeile 8:
 
Korrigierter Code:
 
Korrigierter Code:
 
<pre>
 
<pre>
  1 #include <stdio.h>
+
  #include <stdio.h>
2
+
 
  3 typedef struct
+
  typedef struct
  4 {
+
  {
5    char *data;
+
    char *data;
6    int key;
+
    int key;
  7 } item;
+
  } item;
8
+
 
  9 item array[] =
+
  item array[] =
10 {
+
{
11    {"bill", 3},
+
    {"bill", 3},
12    {"neil", 4},
+
    {"neil", 4},
13    {"john", 2},
+
    {"john", 2},
14    {"rick", 5},
+
    {"rick", 5},
15    {"alex", 1},
+
    {"alex", 1},
16 };
+
};
17
+
18 void sort(item *paItems, unsigned cItems)
+
void sort(item *paItems, unsigned cItems)
19 {
+
{
20    int i = 0, j = 0;
+
    int i = 0, j = 0;
21    int s = 1;
+
    int s = 1;
22    int cLeft = cItems - 1;
+
    int cLeft = cItems - 1;
23    for (i = 0; i < cItems && s != 0; i++)
+
    for (i = 0; i < cItems && s != 0; i++)
24    {
+
    {
25        s = 0;
+
        s = 0;
26        for (j = 0; j < cLeft; j++)
+
        for (j = 0; j < cLeft; j++)
27        {
+
        {
28            if (paItems[j].key > paItems[j+1].key)
+
            if (paItems[j].key > paItems[j+1].key)
29            {
+
            {
30                item Temp = paItems[j];
+
                item Temp = paItems[j];
31                paItems[j] = paItems[j+1];
+
                paItems[j] = paItems[j+1];
32                paItems[j+1] = Temp;
+
                paItems[j+1] = Temp;
33                s++;
+
                s++;
34            }
+
            }
35        }
+
        }
36        cLeft--;
+
        cLeft--;
37    }
+
    }
38 }
+
}
39
+
 
40 int main(void)
+
int main(void)
41 {
+
{
42    int i = 0;
+
    int i = 0;
43
+
 
44    sort(array, 5);
+
    sort(array, 5);
45    for (i = 0; i < 5; i++)
+
    for (i = 0; i < 5; i++)
46    {
+
    {
47        printf("array[%d] == {%s, %d}\n",
+
        printf("array[%d] == {%s, %d}\n",
48                i, array[i].data, array[i].key);
+
                i, array[i].data, array[i].key);
49    }
+
    }
50 }
+
}
 
</pre>
 
</pre>

Aktuelle Version vom 5. März 2013, 17:37 Uhr

Der erste Bug verursacht einen Segmentation fault oder eine falsche Ausgabe. Er befindet sich in Zeile 23. Die Abbruchbedingung ist j < 5, dass heisst j geht bis 4. Der darauffolgende Test greift durch j+1 auf das 6. Element in dem Array gibt, obwohl es nur 5 gibt. cItems gibt muss auf (cItems-1) geändert werden, damit es funktioniert.

Der zweite Bug verursacht einen vorzeitigen Abbruch der äußeren for-Schleife (Zeile 23), wodurch das array nicht komplett sortiert wird. in Zeile 36 wird citems dekrementiert. Dadurch wird auch die Abbruchbedingung verändert. Es gibt zwei Methoden diesen Bug zu beheben: 1. Einfach: Zeile 36 entfernen. Allerdings ist Bubblesort jetzt noch ineffizienter 2. cItems in Zeile 26 und 36 durch ein neue ersetzen, welche verhindert das cItems konstant bleibt.

Korrigierter Code:

 #include <stdio.h>

 typedef struct
 {
    char *data;
    int key;
 } item;

 item array[] =
 {
     {"bill", 3},
     {"neil", 4},
     {"john", 2},
     {"rick", 5},
     {"alex", 1},
 };
 
 void sort(item *paItems, unsigned cItems)
 {
     int i = 0, j = 0;
     int s = 1;
     int cLeft = cItems - 1;
     for (i = 0; i < cItems && s != 0; i++)
     {
         s = 0;
         for (j = 0; j < cLeft; j++)
         {
             if (paItems[j].key > paItems[j+1].key)
             {
                 item Temp = paItems[j];
                 paItems[j] = paItems[j+1];
                 paItems[j+1] = Temp;
                 s++;
             }
         }
         cLeft--;
     }
 }

 int main(void)
 {
     int i = 0;

     sort(array, 5);
     for (i = 0; i < 5; i++)
     {
         printf("array[%d] == {%s, %d}\n",
                i, array[i].data, array[i].key);
     }
 }