Поиск коррупции в связанном списке

Сегодня у меня было интервью для позиции разработчика, и мне был задан интересный технический вопрос, на который я не знал ответа. Я спрошу его здесь, чтобы узнать, может ли кто-нибудь предоставить мне решение для моего любопытства. Это многочастный вопрос:

1) Вам предоставляется одноуровневый список со 100 элементами (целое число и указатель на следующий node), найти способ обнаружить, есть ли перерыв или повреждение на полпути через связанный список? Вы можете сделать что-либо со связанным списком. Обратите внимание, что вы должны сделать это в списке, поскольку он выполняет итерацию, и это проверка, прежде чем вы поймете, что в списке есть какие-либо проблемы с ним.

Предполагая, что разрыв в связанном списке находится в 50-м элементе, целое число или даже указатель на следующий node (51-й элемент) может указывать на значение мусора, которое не обязательно является недопустимым адресом.

2) Обратите внимание, что если в связанном списке есть повреждение, как бы вы минимизировали потерю данных?

Ответ 1

Чтобы проверить "поврежденное" целое число, вам нужно знать, что такое диапазон допустимых значений. В противном случае невозможно определить, что значение в любом заданном (подписанном) значении недействительно. Итак, предположим, что у вас есть тест валидности для int, вы всегда проверяете это значение перед повторением к следующему элементу.

Тестирование поврежденного указателя более сложное - для начала вам нужно проверить значение указателя на следующий элемент, прежде чем пытаться снять ссылку с него, и убедиться, что он является допустимым адресом кучи. Это позволит избежать ошибки сегментации. Следующее - проверить, что то, на что указывает указатель, на самом деле является действительным связанным списком node - немного сложнее? Возможно, отмените ссылку на указатель на класс/структуру элемента списка и проверьте достоверность указателя int и "next", если они также хороши, тогда можно быть уверенным, что предыдущий node тоже хорош.

В 2), обнаружив поврежденный node, [если следующий указатель поврежден], то вам следует немедленно установить "следующий указатель" предыдущего node в "NULL", отметив его как конец списка и запишите свою ошибку и т.д., если повреждение было равно целочисленному значению, но не указателю на "следующий" элемент, тогда вы должны удалить этот элемент из списка и связать предыдущий и следующий узлы вместе - так как в этом случае не нужно бросать остальную часть списка!

Ответ 2

Если вы во время разработки знаете, что коррупция может стать критической проблемой, вы можете добавить "магическое значение" в качестве поля в структуру данных node, которая позволит вам определить, могут ли некоторые данные быть node или нет. Или даже для выполнения поиска в памяти по узлам.

Или удвойте некоторую информацию о ссылках, т.е. сохраните адрес node после следующего node в каждом node, чтобы вы могли восстановить, если одна ссылка сломана.

Единственная проблема, которую я вижу, заключается в том, что вам нужно избегать ошибок сегментации.

Ответ 3

Для первой части - Перегрузка нового оператора. Когда когда-либо выделяется новый node, выделите некоторое дополнительное пространство до и после node и разместите там некоторые известные значения. При обходе каждый node может быть проверен, если он находится между известными значениями.

Ответ 4

Если вы можете сделать что-либо в связанном списке, то вы можете вычислить контрольную сумму каждого элемента и сохранить его на самом элементе. Таким образом, вы сможете обнаружить повреждение, даже если это один бит ошибки в элементе.

Чтобы свести к минимуму потерю данных, возможно, вы можете рассмотреть возможность сохранения nextPtr в предыдущем элементе, таким образом, если ваш текущий элемент поврежден, вы всегда можете найти местоположение следующего элемента из предыдущего.

Ответ 5

Это простой вопрос, и есть несколько возможных ответов. Каждый из них эффективно справляется с надежностью. Поскольку повышенная надежность является предпосылкой задаваемого вопроса, есть доступные решения, которые приносят в жертву как время (скорость перемещения по списку, так и скорость вставки и скорость удаления узлов) или поочередно пространство (дополнительная информация, хранящаяся с каждым node). Теперь выяснилось, что это фиксированный список длины 100, и в этом случае структура данных связанного списка является наиболее неуместной. Почему бы не сделать головоломку немного более сложной и сказать, что размер списка неизвестен априори?

Ответ 6

Поскольку число элементов (100) известно, 100-й node должен содержать нулевой указатель. Если это так, список с хорошей вероятностью действителен (это не может быть гарантировано, если, например, 99-й node поврежден и указывает на некоторое место в памяти со всеми нулями). В противном случае возникает некоторая проблема (это может быть возвращено как факт).

upd. Кроме того, на каждом этапе можно было бы посмотреть на некоторые структуры, которые delete будет использовать, если задан указатель, но так как использование delete само небезопасно в любом смысл, это будет специфичным для реализации.