проверить подмножество между двумя связанными списками в java

Question

Я пытаюсь написать логический метод isSubset (возвращает логическое значение, если каждый элемент в наборе A находится в наборе B и false в противном случае), где вызов метода может быть записан следующим образом: setA.subsetOf(setB). Моя мысль состоит в том, чтобы извлечь каждый элемент setA и сравнить его с setB. Если первый элемент setA сопоставляется с любым в setB, переходим к следующему элементу в setA для проверки. Если все элементы в setA сопоставляются с любым элементом из setB, метод возвращает true, else (не все элементы из setA находятся в setB) возвращает false. Я уже писал метод для проверки удержания элемента в виде связанного списка, как следует:

public boolean contain (Object target) { 
     boolean status = false; 
     Node cursor; 
     for (cursor = head; cursor.getNext() != null; cursor = cursor.getNext()) { 
      if (target.equals(cursor.getElement())) 
       status = true; 
     } 
     return status; 
    } 

Поскольку им до сих пор путают о синтаксисе сцепленных операции списка, мой вопрос заключается в том, чтобы извлечь каждый элемент и сделать все остальное , Любая помощь будет оценена по достоинству. Узел объявляется

public Node(Object o, Node n) { 
    element = o; 
    next = n; 
    } 

SLinkedList

public SLinkedList() { 
    head = new Node(null, null); // create a dummy head 
    size = 0; 
    } 

Answer 1

Во-первых, ваш метод содержит небольшую ошибку. Условие cursor.getNext() != null; должно быть cursor != null;. Это предотвращает поиск пустых наборов (что приведет к сбою вашего кода), а также позволяет искать последний Node в списке. Ваш код будет работать быстрее, если вы сделали return status; после status=true;

Структура для isSubset была бы очень похожа на созданную вами петлю; цикл будет выглядеть следующим образом:

for(cursor = head; cursor!=null; cursor.getNext()){ 
    if(setB.contain(cursor.getElement()) == false){ 
    return false; 
    } 
} 

Answer 2

Ваша логика для проверки, является ли множество А является подмножеством множества В является правильным. Вы спросили «как извлечь каждый элемент», но ваш код для contain показывает, что вы уже знаете, как пройти через связанный список. Таким образом, просто перейдите в набор A так же и вызовите setB.contain(cursor) для каждого элемента, с которым вы проходите. Если это возвращает false для любого элемента, немедленно верните false.

Проблема с выполнением этого способа заключается в том, что он будет очень медленный, если списки большие. Я предполагаю, что вы новичок в программировании и, возможно, никогда не слышали о «большой O» нотации. Это способ описания изменения производительности вашего алгоритма при изменении размера входных данных. Ваш метод subsetOf будет O (n^2). Если setB хранился в хеш-наборе, а не в связанном списке, то это было бы O (n), которое было бы намного лучше.

Вы можете узнать больше об этой теме по адресу: http://en.wikipedia.org/wiki/Time_complexity.