Trovare la corruzione in un elenco collegato

Question

Oggi ho avuto un'intervista per una posizione di sviluppatore e mi è stata presentata un'interessante domanda tecnica che non conoscevo la risposta. Lo chiederò qui per vedere se qualcuno può fornirmi una soluzione per la mia curiosità. È una domanda in più parti:

1) Viene fornita una lista concatenata con 100 elementi (intero e un puntatore al nodo successivo), trovare un modo per rilevare se c'è un'interruzione o una corruzione a metà del collegamento elenco? Puoi fare qualsiasi cosa con la lista collegata. Si noti che è necessario farlo nell'elenco mentre itera e questa è la verifica prima di rendersi conto che l'elenco ha problemi con esso.

Supponendo che l'interruzione nell'elenco collegato sia al 50 ° elemento, il numero intero o anche il puntatore al nodo successivo (51 ° elemento) potrebbe puntare a un valore di garbage che non è necessariamente un indirizzo non valido.

2) Si noti che se c'è un danneggiamento nell'elenco collegato, come ridurrai al minimo la perdita di dati?

Answer 1

Per verificare un numero intero "corrotto", è necessario conoscere l'intervallo di valori validi. Altrimenti, non c'è modo di determinare che il valore in un dato intero (firmato) non sia valido. Quindi, supponendo che tu abbia un test di validità per l'int, controllerai sempre quel valore prima di passare all'elemento successivo.

test per un puntatore danneggiato è più difficile - per cominciare, quello che dovete fare è controllare il valore del puntatore al successivo elemento prima di tentare di de-riferimento a esso, e assicurarsi che sia un indirizzo mucchio valido. Ciò eviterà un errore di segmentazione. La prossima cosa è convalidare che ciò a cui punta il puntatore è in effetti un elemento nodo di lista collegato valido - che è un po 'più complicato? Forse de-referenziare il puntatore in un elemento list class/struct e testare la validità del puntatore int e "next", se sono anche buoni, quindi può essere abbastanza sicuro che anche il nodo precedente fosse buono.

In 2), dopo aver scoperto un nodo danneggiato, [se il puntatore successivo è danneggiato] ciò che si dovrebbe fare è impostare immediatamente il "puntatore successivo" del nodo precedente su "NULL", contrassegnandolo come la fine del elenca e registra il tuo errore ecc. ecc.se il danneggiamento fosse solo al valore intero, ma non al puntatore "next" dell'elemento, allora dovresti rimuovere quell'elemento dall'elenco e collegare insieme i nodi precedenti e quelli successivi, poiché non c'è bisogno di buttare via il resto dell'elenco in quel caso!

Answer 2

Se in fase di progettazione si conosce che la corruzione può diventare un problema critico, è possibile aggiungere un "valore magico" come un campo nella struttura dati del nodo che consente di identificare se alcuni dati potrebbero essere un nodo o meno . O anche per scorrere la memoria alla ricerca di nodi.

Oppure raddoppiare alcune informazioni di collegamento, ovvero memorizzare l'indirizzo del nodo dopo il nodo successivo in ciascun nodo, in modo tale che è possibile ripristinare se un collegamento è interrotto.

L'unico problema che vedo è che devi evitare errori di segmentazione.

Answer 3

Poiché il numero di elementi (100) è noto, il centesimo nodo deve contenere un puntatore nullo. Se lo fa, la lista con una buona probabilità è valida (questo non può essere garantito se, ad esempio, il 99 ° nodo è corrotto e punta a qualche posizione di memoria con tutti gli zeri). Altrimenti, c'è qualche problema (questo può essere restituito come un fatto).

UPD: Inoltre, potrebbe essere possibile, una ogni passo, guardare alcune strutture delete userebbero se dato il puntatore, ma dal momento che utilizzando delete sé non è sicuro in qualsiasi senso, questo sta per essere implementazione -specifica.

Answer 4

Per la prima parte: sovraccaricare il nuovo operatore. Quando viene allocato un nuovo nodo, allocare uno spazio aggiuntivo prima e dopo il nodo e inserire lì alcuni valori noti. In attraversamento ogni nodo può essere controllato se si trova tra i valori noti.

Answer 5

Se si può fare qualsiasi cosa nella lista collegata, ciò che si può fare è calcolare il checksum di ciascun elemento e memorizzarlo sull'elemento stesso. In questo modo sarai in grado di rilevare il danneggiamento anche se si tratta di un errore di un singolo bit sull'elemento.

Per ridurre al minimo la perdita di dati, è possibile considerare di memorizzare la nextPtr nell'elemento precedente, in questo modo se l'elemento corrente è danneggiato, è sempre possibile trovare la posizione dell'elemento successivo rispetto al precedente.

Answer 6

Questa è una domanda facile e ci sono diverse possibili risposte. Ognuno scambia robustezza con efficienza. Poiché una maggiore robustezza è un prerequisito della domanda che viene posta, ci sono soluzioni disponibili che sacrificano sia il tempo (elencare la velocità trasversale, ma anche la velocità di inserimento e la velocità di cancellazione dei nodi) o alternativamente lo spazio (informazioni extra memorizzate con ciascun nodo). Ora il problema è stato affermato che si tratta di un elenco fisso di lunghezza 100, nel qual caso la struttura dei dati di un elenco collegato è più inappropriata. Perché non rendere l'enigma un po 'più impegnativo e dire che la dimensione della lista non è nota a priori?