Лучший алгоритм, чтобы протестировать, если связанный список имеет цикл
Я работаю, используя потоки и обработчик / сообщение. Шаги, следующие: Объявите прогресс Диалог
ProgressDialog loadingdialog;
Создайте функцию, чтобы закрыть диалог, когда операция завершена.
private Handler handler = new Handler() {
@Override
public void handleMessage(Message msg) {
loadingdialog.dismiss();
}
};
Скомпонуйте ваши данные об исполнении:
public void startUpload(String filepath) {
loadingdialog = ProgressDialog.show(MainActivity.this, "Uploading", "Uploading Please Wait", true);
final String _path = filepath;
new Thread() {
public void run() {
try {
UploadFile(_path, getHostName(), getPortNo());
handler.sendEmptyMessage(0);
} catch (Exception e) {
Log.e("threadmessage", e.getMessage());
}
}
}.start();
}
7 ответов
Имейте две итерации указателей через список; сделайте каждый выполняет итерации через в два раза скорость другого и сравнивает их положения на каждом шаге. Первое, что пришло на ум, что-то как:
node* tortoise(begin), * hare(begin);
while(hare = hare->next)
{
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
hare = hare->next;
if(hare == tortoise) { throw std::logic_error("There's a cycle"); }
tortoise = tortoise->next;
}
O (n), который так хорош, как можно добраться.
Что относительно того, чтобы использовать хеш-таблицу для хранения уже замеченных узлов (Вы смотрите на них в порядке от запуска списка)? В практике Вы могли достигнуть чего-то близко к O (N).
Иначе, с помощью отсортированной "кучи" вместо хеш-таблицы достиг бы O (N журнал (N)).
Интересно, существует ли какой-либо другой путь, чем просто движение многократно - заполняет массив, поскольку Вы ступаете вперед, и проверка, если текущий узел уже присутствует в массиве...
В этом коде OysterD случая будет быстрое решение (вершина, окрашивающая)
, Который действительно удивил бы меня. Мое решение делает самое большее два, проходит через список (если последний узел связан с предпоследним кладезем), и в общем падеже (никакой цикл) сделает только одну передачу. Без хеширования, никакого выделения памяти, и т.д.
Алгоритм Konrad Rudolph не будет работать, если цикл не укажет на начало. Следующий список сделает это бесконечным циклом: 1-> 2-> 3-> 2.
алгоритм DrPizza является определенно способом пойти.
В этом коде OysterD случая будет быстрое решение (вершина, окрашивающая)
, Который действительно удивил бы меня. Мое решение делает самое большее два, проходит через список (если последний узел связан с предпоследним кладезем), и в общем падеже (никакой цикл) сделает только одну передачу. Без хеширования, никакого выделения памяти, и т.д.
Да. Я заметил, что формулировка не была прекрасна и перефразировала его. Я все еще полагаю, что умное хеширование могло бы работать быстрее †“волоском. Я полагаю, что Ваш алгоритм лучшее решение, все же.
Только для подчеркивания моей мысли: окраска vertec используется для обнаружения циклов в зависимостях современными сборщиками "мусора", таким образом, существует очень реальный вариант использования для нее. Они главным образом используют битовые флаги для выполнения окраски.
Необходимо будет посетить каждый узел для определения этого. Это может быть сделано рекурсивно. Для остановки Вас уже посещающий посещенные узлы Вам нужен флаг для высказывания 'уже посещенный'. Это, конечно, не дает Вам циклы. Таким образом вместо небольшого флага, используйте число. Запустите в 1. Проверьте соединенные узлы и затем отметьте их как 2 и рекурсивно вызовите, пока сеть не покрыта. При проверке узлов при обнаружении с узлом, который составляет больше чем один меньше, чем текущий узел, то у Вас есть цикл. Длина цикла дана различием.