Неверное значение для определения длины узла в круговом связанном списке - PullRequest
0 голосов
/ 28 января 2019

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

# Defined Node class
class Node(object):
    data = 0
    def __init__(self, data=None, next_node=None):
        self.data = self.increment()
        self.next = next_node

    def increment(self):
        Node.data += 1
        return Node.data

    def setNext(self, next_node = None):
        self.next = next_node

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

def create_chain(num_of_nodes, loop_size):
    nodes = [Node() for _ in range(num_of_nodes)]
    if loop_size == 0:
        return nodes[0]
    else:
        for node, next_node in zip(nodes, nodes[1:]):
            node.next = next_node
            # cleaned_nodes.append(node)
        nodes[num_of_nodes-1].next = nodes[(num_of_nodes - loop_size)-1]
        return nodes[0]

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

def loop_size(node):

    count = 0
    if node == None:
        return 1

    if node.next == None:
        return 1


    slow = fast = node

    while(slow or fast or node.next):
        count += 1
        if fast.next == None:
            #count += 1
            break

        if slow == fast.next or slow == fast.next.next:
            count += 1
            break

        slow = slow.next
        fast = fast.next.next

    return count

Я написал несколько тестов, но это конкретное утверждение не сработало, и яМне бы хотелось понять, почему.

def test_very_long_chain(self):
    self.chain = create_chain(3904, 1087)
    self.assertEqual(loop_size(self.chain), 10, 'Loop size of 10 expected')

Я получаю эту ошибку утверждения;

AssertionError: 3264 != 10 : Loop size of 10 expected

Я бы очень признателен за некоторые рекомендации по этому вопросу.Спасибо

1 Ответ

0 голосов
/ 31 января 2019

Я вижу некоторые проблемы в create_chain, а также в loop_size.

В create_chain логика не ясна, когда loop_size == 0, цепочка не создана, но яПредположим, что цепь должна быть создана независимо от размера цикла?

Также определение размера цикла в функции create_chain не является строгим, предположим, что есть 300 узлов, возможно ли создать цикл длиной 300?Если это так, эта строка «node [num_of_nodes-1] .next = node [(num_of_nodes - loop_size) -1]» должна измениться.

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

Внутри скобки while в функции loop_size должно быть 'и' вместо 'или'.Ниже мое переписывание класса и метода.Я надеюсь, что это то, что вы хотели!

class Node(object):
  def __init__(self, data=None, next_node=None):
    self.data = data
    self.next = next_node

  def increment(self):
    self.data += 1
    return self.data

  def setNext(self, next_node=None):
    self.next = next_node




def create_chain(number, loop):
  if number <= 0 or loop > number:
    print("Error")
    return
  nodes = [Node(i) for i in range(number)]
  for i in range(number-1):
    nodes[i].setNext(nodes[i+1])
  if loop > 0:
    nodes[number-1].setNext(nodes[number-loop])
  return nodes[0]


def loop_size(node):
  def helper(node):
    #print(node.data)
    count = 1
    temp = node
    while(temp.next != node):
      temp = temp.next
      count += 1
    return count

  if not node:
    return 0
  slow = fast = node
  while(slow and fast and fast.next):
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
      return helper(slow)
  return 0


chain = create_chain(300, 300)
print(loop_size(chain))
chain = create_chain(300, 0)
print(loop_size(chain))
chain = create_chain(300, 130)
print(loop_size(chain))
...