|
Das Sortieren von Listenstrukturen ist nicht so einfach wie das Sortieren eines Arrays, für das z.B. schnelle Quicksort-Algorithmen existieren, die teilweise auch Bestandteil der C++ Bibliotheken sind. Verkettete Listen müssen hingegen mit speziellen Sortieralgorithmen bearbeitet werden. Hierfür wird nachfolgend eine Template-Klasse vorgestellt, die zunächst auf CObList basiert. Diese grundlegende Klasse wird erst einmal um die Fähigkeit des Sortierens erweitert.
class CSortableObList : public CObList
{
public:
CSortableObList(int nBlockSize = 10) : CObList(nBlockSize) {}
void Sort(int (*CompareFunc)(CObject* pFirstObj,
CObject* pSecondObj));
void Sort(POSITION posStart,
int iElements,
int (*CompareFunc)(CObject* pFirstObj,
CObject* pSecondObj));
};
Die Vergleichsfunktion CompareFunc() hat den C-Gepflogenheiten entsprechend einen positiven Integer zu returnieren, wenn Objekt pFirstObj größer als Objekt pSecondObj ist, einen negativen Integer für den umgekehrten Fall, sowie Null bei Gleichheit.
Als Sortieralgorithmus kommt Sortieren durch Einfügen zum Einsatz. Dieser Algorithmus schiebt Einträge nach hinten, um vorne Platz für das Einfügen eines „kleineren“ Elements zu schaffen. Dies kommt der Struktur einer Liste entgegen.
Im ersten Schritt prüft die Methode Sort, ob die Liste überhaupt ein Element enthält.
void CSortableObList::Sort(int (*CompareFunc)(CObject* pFirstObj,
CObject* pSecondObj))
{
ASSERT_VALID(this);
if (m_pNodeHead == NULL)
return;
Für das Sortieren wird die Liste durchlaufen, wobei der erste Schritt immer darin besteht, den alten Zeiger zu sichern.
CObject *pOtemp;
CObList::CNode *pNi,*pNj;
for (pNi = m_pNodeHead->pNext; pNi != NULL; pNi = pNi->pNext)
{
pOtemp = pNi->data;
Die Liste wird rückwärts ab pNi bis zum Anfang durchlaufen oder bis die Vergleichsfunktion meldet, daß ein Eintrag an seiner richtigen Position ist. Dabei werden alle Einträge aufwärts geshiftet.
for (pNj = pNi;
pNj->pPrev != NULL &&
CompareFunc(pNj->pPrev->data,pOtemp) > 0;
pNj = pNj->pPrev)
pNj->data = pNj->pPrev->data;
Anschließend wird der Datenzeiger an der richtigen Position eingefügt.
pNj->data = pOtemp;
}
}
Die zweite Variante der Sortiermethode erlaubt, nur einen Teil der Liste zu sortieren. IElements kann größer als die Anzahl der verbleibenden Elemente sein oder auch -1, was immer dazu führt, daß an das Ende der Liste sortiert wird.
void CSortableObList::Sort(
POSITION posStart,
int iElements,
int (*CompareFunc)(CObject* pFirstObj,
CObject* pSecondObj))
{
ASSERT_VALID(this);
Es ist sicherzustellen, daß posStart ein Positionswert ist, der von den Membern GetHeadPosition() oder Find() geliefert wurde, da ansonsten keine sinnvolle Möglichkeit besteht, die Adresse zu verifizieren.
ASSERT( AfxIsValidAddress((CObList::CNode*)posStart,
sizeof(CObList::CNode)) );
Ist die Liste leer, gibt es nichts zu tun.
if (m_pNodeHead == NULL)
return;
Anschließend wird die Liste durchlaufen und wiederum im ersten Schritt jeweils der alte Zeiger gesichert.
CObject *pOtemp;
CObList::CNode *pNi,*pNj;
for (pNi = (CObList::CNode*)posStart;
pNi != NULL && iElements != 0;
pNi = pNi->pNext, iElements--)
{
pOtemp = pNi->data;
Die Liste wird rückwärts ab pNi bis zum Anfang durchlaufen oder bis die Vergleichsfunktion meldet, daß ein Eintrag an seiner richtigen Position ist. Dabei werden alle Einträge aufwärts geshiftet.
for (pNj = pNi;
pNj->pPrev != NULL &&
pNj->pPrev != ((CObList::CNode*)posStart)->pPrev &&
CompareFunc(pNj->pPrev->data,pOtemp) > 0;
pNj = pNj->pPrev)
pNj->data = pNj->pPrev->data;
Anschließend wird der Datenzeiger an der richtigen Position eingefügt.
pNj->data = pOtemp;
}
}
Template-Klasse CTypedSortableObList
Die Template-Klasse kann nun anhand der Implementation der Klasse CSortableObList abgeleitet werden.
template
class CTypedSortableObList: public CSortableObList
{
public:
CTypedSortableObList(int nBlockSize = 10)
: CSortableObList(nBlockSize) { }
Die Methoden GetHead() und GetTail() liefern einen Zeiger auf das erste bzw. letzte Element der Liste.
TYPE& GetHead()
{ return (TYPE&)CSortableObList::GetHead(); }
TYPE GetHead() const
{ return (TYPE)CSortableObList::GetHead(); }
TYPE& GetTail()
{ return (TYPE&)CSortableObList::GetTail(); }
TYPE GetTail() const
{ return (TYPE)CSortableObList::GetTail(); }
Die Methoden RemoveHead() und RemoveTail() entfernen das erste bzw. letzte Element der Liste.
TYPE RemoveHead()
{ return (TYPE)CSortableObList::RemoveHead(); }
TYPE RemoveTail()
{ return (TYPE)CSortableObList::RemoveTail(); }
AddHead() und AddTail() fügen ein Element vor dem ersten oder nach dem letzten Element der Liste ein.
POSITION AddHead(TYPE newElement)
{ return CSortableObList::AddHead(newElement); }
POSITION AddTail(TYPE newElement)
{ return CSortableObList::AddTail(newElement); }
Alternativ kann auch eine ganze Liste von Elementen vor dem ersten bzw. nach dem letzten Listenelement eingefügt werden.
void AddHead(CTypedSortableObList* pNewList)
{ CSortableObList::AddHead(pNewList); }
void AddTail(CTypedSortableObList* pNewList)
{ CSortableObList::AddTail(pNewList); }
Iterationen liefern den jeweiligen Nachfolger bzw. Vorgänger zur Position rPosition.
TYPE& GetNext(POSITION& rPosition)
{ return (TYPE&)CSortableObList::GetNext(rPosition); }
TYPE GetNext(POSITION& rPosition) const
{ return (TYPE)CSortableObList::GetNext(rPosition); }
TYPE& GetPrev(POSITION& rPosition)
{ return (TYPE&)CSortableObList::GetPrev(rPosition); }
TYPE GetPrev(POSITION& rPosition) const
{ return (TYPE)CSortableObList::GetPrev(rPosition); }
Die Methode GetAt() returniert das Element an der Position position:
TYPE& GetAt(POSITION position)
{ return (TYPE&)CSortableObList::GetAt(position); }
TYPE GetAt(POSITION position) const
{ return (TYPE)CSortableObList::GetAt(position); }
Zum Setzen des Elements newElement an Position pos steht die Methode SetAt() zur Verfügung.
void SetAt(POSITION pos, TYPE newElement)
{ CSortableObList::SetAt(pos, newElement); }
Die beiden Sortierfunktionen komplettieren die Template-Klasse.
void Sort( int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort((int(*)(CObject*,CObject*))CompareFunc);}
void Sort( POSITION posStart, int iElements,
int(*CompareFunc)(TYPE pFirstObj, TYPE pSecondObj) )
{ CSortableObList::Sort(posStart, iElements,
(int(*)(CObject*,CObject*))CompareFunc); }
};
Einsatz der Klasse
Das nachfolgende Beispiel zeigt den Einsatz der Template-Klasse anhand einer von CObject abgeleiteten Klasse.
class CMyObject : public CObject
{
public:
CString name;
static int CompBackward(CMyObject* pFirstObj,
CMyObject* pSecondObj)
{
return -lstrcmp((LPCTSTR)pFirstObj->name,
(LPCTSTR)pSecondObj->name);
}
};
Es wird sodann ein Listenobjekt erzeugt und mit Elementen gefüllt.
CTypedSortableObList list;
for (int i=0; i name.Format("Object #%d",i);
list.AddTail(pObj);
}
Das Sortieren der Liste erfolgt dann anschließend über den Aufruf
list.Sort(CMyObject::CompBackward);
Anzeigen läßt ich der Inhalt der sortierten Liste wie folgt:
for (POSITION pos = list.GetHeadPosition(); pos != NULL; )
{
CMyObject* pObj = list.GetNext(pos);
TRACE1("%s\n",pObj->name);
}
| 