Hoe de beschadigde aanwijzer in de gekoppelde lijst op te lossen?

Als ik heb geconstateerd dat een aanwijzer (link) -veld in de gekoppelde lijst is beschadigd, hoe kan ik dit probleem dan oplossen?

Ik werd deze vraag in een interview gesteld. Ik zei nee, het is niet mogelijk om het op te lossen. Interviewer zei dat het mogelijk was. Zijn er manieren?

2
Inderdaad, hoe ben je dat te weten gekomen? In het algemene geval is het onmogelijk ...
toegevoegd de auteur fakedrake, de bron
Hoe ben je dat te weten gekomen? als u ontdekt dat u een betere logica zou hebben dan de logica van uw programma's, en als u een betere logica zou hebben, waarom zou u het dan niet in de eerste plaats gebruiken? (Dit is de conjunctie van Godel in vermomming)
toegevoegd de auteur wildplasser, de bron
Ik zie ... Huiswerk?
toegevoegd de auteur wildplasser, de bron
Ongevraagd algemeen advies op basis van interviews ... Maak geen ongegronde aannames die leiden tot onbevredigende antwoorden zoals u die hebt gegeven. Vraag om details (enkelvoudig gekoppeld, dubbel gelinkt, hoe we weten dat het is beschadigd, wat oplossen betekent, of geheugen op willekeurige adressen kan worden gelezen zonder een crash te veroorzaken, enz.). Als ze u geen details geven, overweeg dan andere gevallen van wat zou zijn als dit en dat zo en zo was, beschrijf deze gevallen en wat er mogelijk in hen kan worden gedaan.
toegevoegd de auteur Alexey Frunze, de bron
raadpleeg het antwoord voor het vinden van de beschadigde aanwijzer in de onderstaande link: stackoverflow.com/questions/4079099/…
toegevoegd de auteur vijayanand1231, de bron
@thrustmaster: Ik heb de antwoorden geüpdatet, wat logisch correct is voor alle antwoorden op mijn vraag.
toegevoegd de auteur vijayanand1231, de bron

4 antwoord

Nou, ervan uitgaande dat het een dubbel gelinkte lijst is:

Als het de "volgende" aanwijzer is die beschadigd is geraakt, kan men beginnen bij de staart en met behulp van de "vorige" aanwijzer de lijst naar het hoofd doorlopen met behoud van een verwijzing naar het laatste element dat werd doorlopen. Wanneer u het element met de slechte aanwijzer vindt, hoeft u alleen maar de "volgende" aanwijzer van dat element naar het laatste element te verplaatsen dat is doorlopen.

Als een "vorige" link is beschadigd in een dubbel gelinkte lijst, kan het proces worden omgekeerd - begin bij de kop, verplaats totdat de slechte "vorige" aanwijzer is gevonden en repareer deze met de verwijzing naar het laatste element dat werd doorlopen.

4
toegevoegd

Misschien moet je er gewoon vanaf komen? Het is echt niet mogelijk in het algemeen wanneer we een element van een lijst niet zomaar kunnen interpoleren door anderen.

1
toegevoegd
Misschien was dit beter als een opmerking :)
toegevoegd de auteur SuperSaiyan, de bron

Bij het ontwikkelen van mijn ingesloten taak gebruik ik vaak forward-linked queues. Ik houd zowel een telling als de hoofdaanwijzer bij. De wachtrijen hebben de methode check() die rond de [aantal] links loopt en roept de kritieke foutafhandeling op als de resulterende aanwijzer niet hetzelfde is als de kop. Het is niet onfeilbaar, maar het werkt voldoende goed om double-pushes en andere dergelijke veelvoorkomende wachtrijfouten te vangen.

OPMERKING: In multithread-apps moet de wachtrij worden vergrendeld om deze veilig te kunnen controleren.

0
toegevoegd

In een dubbelcirkelige gekoppelde lijst kunnen we de beschadigde aanwijzer oplossen als een van de aanwijzers (vorige of volgende aanwijzer) is beschadigd.

Als de volgende aanwijzer niet correct is, kunnen we de lijst omgekeerd doorlopen en dan kunnen we deze corrigeren, of anders als de vorige aanwijzer niet correct is, kunnen we de lijst vooruitlopen om deze te corrigeren.

Nu moeten we nadenken over het identificeren van een beschadigde link (aanwijzer) in een lijst. We gebruiken om dynamisch geheugen ( malloc of calloc ) voor elke knoop afzonderlijk toe te wijzen. Als we vaak malloc of calloc aanroepen voor klein geheugen, kan dit van invloed zijn op de prestaties van het systeem. In plaats daarvan kunnen we in het beginstadium een ​​grote rommel van heap-geheugen toewijzen en dan kunnen we onze eigen geheugentoewijzingsfunctie implementeren voor elke knooppuntcreatie. En gebruik dit ook alleen voor het maken van lijstknooppunten om beschadigde links van de lijst te identificeren.

Dit verhoogt de prestaties van het systeem en het zal ook helpen om vast te stellen of de link van een knooppunt beschadigd is of niet, door de limieten te controleren van het initiële geheugen dat is toegewezen aan de lijst.

Zodra we een pointer naar een knooppunt krijgen, moeten we eerst de onderstaande controles uitvoeren voordat we toegang krijgen tot de gegevens in dat knooppunt.

check_limit(node);
check_limit(node->next);
check_limit(node->previous);

And also we can check whether the node->previous is equal to current_node.

After this also there may be possibility of node->next might be pointing to wrong address but inside the initial memory limit. In this case we can read node->next->previous (this will not leads to crash, even if next is pointing wrong address but inside the initial memory limit) and check whether it is equal to node or not.

En ook ongebruikte begingeheugenruimte moet altijd NULL worden ingesteld (met memset ).

Op deze manieren kunnen we de 99% van de beschadigde aanwijzers in een lijst achterhalen.

0
toegevoegd
Ik zie de logica niet. als (één-> volgende == twee && twee-> vorige! = één) , hoe weet u of [a] u twee moet instellen -> prev = one; of [b] dat één-> volgende in de eerste plaats verkeerd was? Er is geen manier om het te vertellen. (er zijn eenvoudiger gevallen zoals als (twee-> vorige == drie && drie-> volgende == twee) , wat zou aangeven dat één-> volgende fout was in het eerste geval)
toegevoegd de auteur wildplasser, de bron
@wildplasser: ik heb mijn antwoord bijgewerkt. Gelieve dit na te kijken.
toegevoegd de auteur rashok, de bron