Установите пересечение и разницу со связанными списками в C

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

struct node{
    unsigned n;
    struct node *next;
};

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

int cardinality(struct node *s){
    struct node *tmp = s;
    int count = 0;

    while(tmp != NULL){
    tmp = tmp->next;
    count++;
    }

    return count;
}

int contains(struct node *s, int v){ /* returns 0 if in list, 1 if not in list */
    struct node *tmp = s;
    int contains = 1;

    while(tmp->next != NULL){
    if(tmp->n == v){
        contains = 0;
        break;
        } else{
        if(tmp == NULL) break;
        tmp = tmp->next;
    }
    }
    return contains;
}

Теперь мне нужно закодировать следующие функции, но я не знаю, как это сделать. Должен ли я перебирать один список и для каждого элемента в цикле списка проходить через второй список, чтобы проверить, содержится ли он / нет (разница) во втором? Это кажется сложным для этой задачи, должен быть более простой способ сделать это. Надеюсь, вы можете мне помочь

void intersection(struct node *s1, struct node *s2, struct node **result){

}

void difference(struct node *s1, struct node *s2, struct node **result){

}

c singly-linked-list set-difference set-intersection
person sj134    schedule 24.11.2013    source источник
comment
Почему две функции недействительны? Мне кажется более логичным использовать возвращаемое значение для сообщения результата вместо уродливого третьего аргумента.   -  person wildplasser    schedule 24.11.2013
comment
@wildplasser Действительно, для настройки списка у вас может быть функция assign, поэтому, если кто-то хочет перезаписать список результатами intersection, это может быть assign(&list, intersection(a, b)). Функции в основном выполняют две задачи: вычисляют некоторые операции над множествами и разрушающее присваивание.   -  person Kaz    schedule 24.11.2013
comment
Нет, подход не слишком сложен для задачи. Вам нужно пройти по одному списку и найти каждый элемент во втором списке. Вы можете написать общую процедуру для intersection и difference, которая принимает дополнительный логический аргумент, указывающий, следует ли сохранить соответствующий элемент или отклонить. Тогда intersection и difference просто обертки.   -  person Kaz    schedule 24.11.2013
comment
И хорошая новость: операция действительно тривиальна, если списки отсортированы. Кстати: ОП не сказал, разрешено ли изменять два исходных списка.   -  person wildplasser    schedule 24.11.2013

Ответы (2)


arrow_upward
0
arrow_downward

Реализуйте следующее:

// Copy one node s, giving the copy a NULL next pointer.
struct node *copy_one(struct node *s);

// Add the given node s to an existing list.
void add(struct node *s, struct node **existing);

Они полезны для многих целей, но здесь вы будете их составлять:

add(copy_one(s), &existing_list);

чтобы закрепить свой результат.

Теперь алгоритм пересечения такой:

set result empty
for all elements e in s1
   if e->val is contained in s2
       add a copy of e to result

Для разницы s1 - s2 это

set result empty
for all elements e in s1
   if e is _not_ contained in s2
       add a copy of e to result

Я позволю вам поработать над C. Мне неинтересно давать вам полный ответ.

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

person Gene    schedule 24.11.2013

arrow_upward
0
arrow_downward

Должен ли я перебирать один список и для каждого элемента в цикле списка проходить через второй список, чтобы проверить, содержится ли он / нет (разница) во втором?

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

Это кажется слишком сложным для этой задачи, должен быть более простой способ сделать это.

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

person Jim Lewis    schedule 24.11.2013