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

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

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

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

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

источник

2012-06-01 John Baum

", который не обязательно является недопустимым адресом" Запрет небезопасного ключевого слова C# или некорректного взаимодействия (P/Invoke, JNI), как бы у вас был указатель на недопустимый адрес на C# или Java? –

Сначала вам нужно определить «коррумпированные». – SimpleVar

Действительно ли правильно отметить это с помощью C# и Java? У них нет указателей (если не написано небезопасный код C#), а ссылка не может указывать на недопустимый адрес. Вопрос имеет смысл в C или C++. –

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

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

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

источник

2012-06-01 07:01:04 Ozraptor

Как вы можете проверить, является ли адрес действительным адресом кучи. – Vijay

@peter, вы можете установить обработчик segfault и просто попытаться прочитать указатель. Если вы не получите segfault, то он, по крайней мере, указывает где-нибудь, что вы можете прочитать. –

Также важно проверить для случая «коррупции», когда список содержит цикл. Если вы абсолютно знаете размер (100), это тривиально, но я предполагаю, что этот предел будет следующим вопросом. Обнаружение петли на месте также не слишком сложно, если вы знаете трюк. – samkass

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

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

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

источник

2012-06-01 05:45:20 JohnB

" вам нужно избегать ошибок сегментации »- вам всегда нужно не только в этом конкретном случае :-) – zerkms

Да, но избежать ошибок сегментации сложнее, если вы не можете полагаться на правильность указателей. – JohnB

-3

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

обн: Кроме того, это может быть возможным, каждый шаг, посмотрим на некоторые структуры delete бы использовать, если данный указатель, но с использованием delete сама не является безопасным в каком-то смысле, это будет реализация -конкретный.

источник

2012-06-01 05:45:44

Это не так на многих уровнях. Как насчет поврежденного узла в середине? Вы просто «путешествуете» по памяти, как будто завтра нет, когда на самом деле все это мусор, и только по везению вы можете остаться в памяти, к которой вам разрешен доступ, только для того, чтобы сыграть в азартные игры, что после 100 итераций вы получите значение '0' как указатель. Это не удается. – SimpleVar

Неправильное решение, как пройти список до конца, если есть неправильные указатели посередине? – DhruvPathak

@Yorye Nathan well, в тот момент, когда вы ОСТАВЛЯете память, которой вы можете получить доступ, вы просто поймаете исключение и скажете, что «проблема ПЕРЕД». Прекрасно. То же самое, если вы обнаруживаете нулевой указатель перед 100-м элементом. –

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

источник

2012-06-01 05:46:31 Superman

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

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

источник

2012-06-01 14:45:26 tytchong

Проблема с такими ответами заключается в том, что вы пытаетесь вернуться в любое время или в области видимости или в обоих случаях, а также создать список или ограничить его содержимое, чтобы облегчить обнаружение. Есть все действительные ответы на подмножества вопроса, но ни одна из них не имеет ничего общего с проблемой, поскольку она дается. –

Это правда. Вы можете сделать это только до того, как будет создан список. – tytchong

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

источник

2013-06-28 00:34:07 JohnnyU9999

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

ответ

Смежные вопросы