C-Programmierung
Liste Durchsuchen
← Knoten in Liste Einfügen | ● | Knoten aus Liste Löschen →
Listen bieten keinen wahlfreien Zugriff auf einzelne Elemente!
Der passende Knoten zu einem bestimmten Element muss gesucht werden!
Zum Durchsuchen einer verketteten Liste nach einem bestimmten Element bedient man sich eines Suchzeigers:
- Der Suchzeiger zeigt anfangs auf den Wurzelknoten
- Solange der Suchzeiger nicht NULL ist:
- Suchzeiger dereferenzieren und damit den referenzierten Knoten aufsuchen
- Aus dem referenzierten Knoten das Nachfolger-Element auslesen
- Suchzeiger auf den Nachfolger des aktuellen Knotens setzen
node_ptr root;
node_ptr search_list(const T &element)
{
for (node_ptr ptr=root; ptr!=NULL; ptr=ptr->next)
if (ptr->item == element)
return(ptr);
return(NULL);
}
node_ptr search_list(const T &element)
{
for (node_ptr ptr=root; ptr!=NULL; ptr=ptr->next)
if (ptr->item == element)
return(ptr);
return(NULL);
}
Zum Vergleich dazu die Suche in einem Array:
T array[n];
int search_array(const T &element)
{
for (int index=0; index<n; index++)
if (array[index] == element)
return(index);
return(-1);
}
int search_array(const T &element)
{
for (int index=0; index<n; index++)
if (array[index] == element)
return(index);
return(-1);
}
Die durchschnittliche Suchzeit beträgt $\frac{k}{2}$ Schritte.
← Knoten in Liste Einfügen | ● | Knoten aus Liste Löschen →