0
Ich habe eine Zuordnung für meine C-Programmierklasse, wo wir mit verknüpften Listen arbeiten.Suche effizient eine verknüpfte Liste
Eine Funktion verwendet den Stammzeiger und eine ID und durchsucht die Liste, um sie zu löschen. Ich habe die Linkliste bereits anhand dieser Ids sortiert.
Gibt es eine Möglichkeit, die verknüpfte Liste effizient zu durchsuchen, ohne sie linear auszuführen? Die Aufgabe deutet stark darauf hin, dass es ein besserer Weg ist, aber ich kann mir keinen Weg vorstellen, dies zu tun, ohne schrecklich ineffizient zu sein oder nur eine lineare Suche zu verwenden.
einzelne verkettete Liste oder doppelte verkettete Liste? Wenn Sie doppelt vorhanden sind, können Sie einen Binärbaum darstellen und die Suchzeit auf log (n) reduzieren (wenngleich der beste Fall für einen ausgeglichenen Baum ist). – karakfa
Die offensichtliche Möglichkeit, ein sortiertes Array zu durchsuchen, ist die binäre Suche. Sie können eine kleine Verbesserung der Leistung erzielen, indem Sie die Suche beenden, nachdem die ID des nächsten Knotens größer als der Suchschlüssel ist (oder weniger, je nachdem, wie Sie sortiert haben). Sie können dramatische Leistungszuwächse erzielen, wenn Sie eine "Sprungliste" (https://en.wikipedia.org/wiki/Skip_list) implementieren, aber das ist ein ziemlich großes Add-on. –
Wessen ist ein besserer Weg? Wie auch immer, wenn Sie eine effizientere Suche wünschen, ziehen Sie die verknüpfte Liste ab und verwenden Sie etwas anderes. Es gibt keine Möglichkeit, die verknüpfte Liste schneller als linear zu durchsuchen. Natürlich können Sie einen Baum oder ein Array oder was auch immer Sie möchten zusätzlich zu einer verknüpften Liste erstellen und durchsuchen, aber Sie werden die Liste dann nicht durchsuchen. Eigentlich ziehst du einfach immer die verknüpfte Liste ab und verwendest noch etwas anderes. Es ist fast nie das richtige Werkzeug für den Job, egal was für eine Arbeit es ist. Aber ohne deine ganze Aufgabe wörtlich zu haben ** ist das alles reine Spekulation, die Elektronen nicht wert, die man dafür ausgegeben hat –