C: Функция поиска в связанном списке

Question

У меня есть два связанных списка.

typedef struct node
{
   char value[256];
   struct node *next;
} Node_t;

    typedef struct node1
    {
       char value1[256];
       int count;
       struct node1 *next;
    } Node1_t;

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

Спасибо.

Answer 1

Если оба списка отсортированы, то вы можете использовать следующий алгоритм (псевдокод, сложность времени выполнения O(n+m)):

INPUT: list1, list2 (first nodes of the lists you want to compare, sorted!)

while list1 != null AND list2 != null
    if list1->value < list2->value
        list1->value = list1->next

    elseif
        list2->value < list1->value
          list2->value = list2->next

    else
        list3->appendValue(list1->value)
        list1->next

Если один из списков не отсортирован, вы должнысравнить каждый элемент из первого списка с каждым элементом во втором списке (сложность времени исполнения O(n*m)):

INPUT: list1, list2 (first nodes of the lists you want to compare)

while list1 != null
    list2temp = list2

    while list2temp != null
        if list1->value == list2temp->value
            list3->appendValue(list1->value)
        list2temp = list2temp->next
    list1 = list1->next

Часто лучше сначала отсортировать списки, а затем использовать первый метод, это приведет ксложность во время выполнения O(n log n + m log m).В обоих случаях list3 будет содержать общие элементы обоих списков.

Answer 2

list = head;
while (list) {
  list1 = head1;
  while (list1) {
    if (yourcompare(list->value, list1->value) == 0) {
      // do something with common data
      // if only possible case: then break;
    }
    list1 = list1->next;
  }
  list = list->next;
}

Вы можете добавить бухгалтерские данные, такие как «кратко обновленные», если одноразовое значение в списке list1 не должно совпадать снова. так что вам нужно 'if (! list1-> updated) {...; list1-> updated = TRUE;} 'внутри внутреннего while.