Уменьшите количество итераций при прохождении в связанном списке в C

У меня есть одноуровневый список, который имеет 100 узлов. Мне нужно проверить этот связанный список или нет?Уменьшите количество итераций при прохождении в связанном списке в C

Это может быть достигнуто путем перемещения списка и необходимо проверить поле связи последнего узла, равное головке.

struct node *temp1, *temp2; 
while(i != 100) { 
    temp2 = temp1->link; 
    if(temp2==head) { 
    printf("circular"); 
    break; 
    else 
    temp1=temp1->link; 
     i++; 
    }

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

Возможно ли это? Если да, как мы можем это сделать?

источник

2013-09-28 sujin

Проверьте «Tortoise & Hare», который должен сделать это: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare – alk

Однако, круг не necessarly необходимо включить голова. – alk

сделать 2 проверки на итерацию (ручная размотка a.k.a.) – technosaurus

Таким образом, вы можете сделать это в 50 итераций с небольшим хака. Держите другую голову (*head2), которая указывает на head->link. Это все равно займет постоянное пространство. Сравните его с текущим узлом в условии if вместе с исходной головой. Смотрите код below--

struct node *head, *head2, *temp; 
temp = head; //assuming head points to start of the list 
head2 = head->link; 
while(i != 50) { 
    temp = temp->link->link; 
    if(temp==head || temp==head2) { 
    printf("circular"); 
    break; 
    } 
    i++; 
}

источник

2013-09-29 23:34:42 hrv

для проверки кругового связанного списка, только петли связанного списка и для каждой итерации необходимо проверить следующее:

if the head == temp->next than True, it does, than it's CircularLinkedList 
else if temp->next == null than False

источник

2013-09-28 16:04:08

Мне нужно уменьшить количество проходов по времени. – sujin

@sujin, уменьшая количество перемещений, конечно, приведет к сокращению времени. –

Использования одного linklist вы должны пройти весь linklist. Это также относится к циклическому списку ссылок. Еще почему люди делают такой ADT?

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

источник

2013-09-28 16:23:43 Tonmoy

Но вам необязательно проверять каждый узел. См. Алгоритм «Черепаха и заяц». – alk

@alk; Заяц должен посещать каждый узел. Я предполагаю, что это займет всего 50 итераций, но на каждой итерации он выполняет в два раза больше работы. Если вы хотите развернуть цикл полностью, вы можете сделать это на одной итерации, но это глупый ответ. – pburka

@pburka: Суть заключается в том, что количество тестов, которые нужно выполнить, составляет всего 50% от числа узлов. – alk

Алгоритм черепахи и зайца будет работать в ваших целях.

На каждой итерации заяц будет двигаться через два узла, а черепаха - только одна. Заяц будет посещать каждый узел, а некоторые из них несколько раз, но если вы добавите общее количество посещений хоста и разделите их на два, результат не будет больше длины списка. Возможно, что черепаха также посетит каждый узел, но он не будет посещать один и тот же узел дважды.

Алгоритм O (п)

Ссылки: http://codingfreak.blogspot.com/2012/09/detecting-loop-in-singly-linked-list_22.html

источник

2013-09-29 23:17:06

Уменьшите количество итераций при прохождении в связанном списке в C

ответ

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