Форум программистов, компьютерный форум CyberForum.ru

объединение множеств - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
21.10.2012, 01:55     объединение множеств #1
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class ValType, class FwdIt>
  FwdIt copy ( FwdIt first, FwdIt last, FwdIt result )
{
  while (first!=last) *result++ = *first++;
  return result;
}
 
template <class ValType, class FwdIt>
FwdIt set_union(FwdIt first1, FwdIt last1, 
                FwdIt first2, FwdIt last2, FwdIt result)
{
    merge_sort<ValType, FwdIt>(first1, last1);
    merge_sort<ValType, FwdIt>(first2, last2);
    while (true)
    {
        if (first1==last1) return copy<ValType, FwdIt>(first2,last2,result);
        if (first2==last2) return copy<ValType, FwdIt>(first1,last1,result);
 
        if (*first1<*first2) *result++ = *first1++;
        else if (*first2<*first1) *result++ = *first2++;
        else { *result++ = *first1++; first2++; }
    }
}
функция должна объединить два множества в одно.

проверка:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{   
    char s[7] = {'A','B','F','D','A','F','F'}; // check set_union
    char q[6] = {'E','A', 'B','H','F','C'};
    char result[10];
    set_union<char>(s,s + 6, q, q + 5, result);
    int size_r = strlen(result);
    for(int i = 0; i < size_r; i++)
        cout << result[i] << ' ';
    cout << endl;
 
 
    return 0;
}
выводится вот такая несуразная строка, подскажите пожалуйста, где процесс идет не так?
у меня лишь догадки, что когда я передаю начало строки и конец ее, вот в этой передаче и кроется беда, но что именно не так идет, никак не пойму
A A B D E F F H ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ A B E F H C ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ ╠ A A B D
F F F ╠ ╠ ╠ ╠ ╠ ← # !
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.10.2012, 01:55     объединение множеств
Посмотрите здесь:

Объединение множеств C++
Пересечение множеств C++
C++ Найти пересечение, объединение, разность, симметрическую разность множеств
C++ Объединение, пересечение, разность, симметрическая разность множеств
Описать класс "множество", позволяющий выполнять основные операции - добавления и удаление элемента, пересечение, множеств, объединение и разность мно C++
C++ Объединение и упорядочивание двух множеств
C++ Осуществить все операции над элементами множеств: пересечение, объединение, ...
C++ Объединение множеств. Некорректная обработка
C++ Объединение множеств(массивов)
Объединение, пересечение и разность множеств с помощью оператора SWITCH C++
C++ Объединение, пересечение, разность множеств
C++ Найти объединение двух множеств

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
21.10.2012, 02:04     объединение множеств #2
http://www.cplusplus.com/reference/algorithm/merge/
Посмотрите реализацию этой функции.
Но даже сейчас могу сказать следующее:
C++
1
set_union<char>(s,s + 7, q, q + 6, result);
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
21.10.2012, 02:10  [ТС]     объединение множеств #3
спасибо, недоглядел) сейчас set_union объединяет правильно, но все равно в конце начинается такая же белиберда. сортировка и объединение писались как раз по этим реализациям

Добавлено через 33 секунды
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
template <class ValType, class FwdIt> void merge(FwdIt first, FwdIt middle, FwdIt last, ValType *arr)
{
 
    int cursor = 0;
 
    FwdIt f = first, center = middle;
 
    while(first != middle && center != last)
        if(*first < *center)
            arr[cursor++] = *(first++);
        else
            arr[cursor++] = *(center++);
        
    
    while(first != middle)
        arr[cursor++] = *(first++);       
  
    while(center != last)
        arr[cursor++] = *(center++);    
    
 
    for(int i = 0; i < cursor; i++, f++)
        *f = arr[i];
}
template <class ValType, class FwdIt> void merge_sort(FwdIt first, FwdIt last)
{
    int n = last - first;
    ValType *arr = new ValType[n];
 
 
    if(n > 1){
        FwdIt mid = first + (n / 2);
        merge_sort<ValType, FwdIt>(first, mid);
        merge_sort<ValType, FwdIt>(mid, last);
        merge<ValType, FwdIt>(first, mid, last, arr);
    }
    delete[] arr;
}
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
21.10.2012, 02:48     объединение множеств #4
вы не возвращаете никакой информации о том, где должен кончаться массив result.
вы надеетесь, что strlen сделает это за вас. однако strlen вернет вам позицию нулевого символа в строке. Который вы, впрочем тоже не ставите
xexew
0 / 0 / 0
Регистрация: 22.02.2011
Сообщений: 76
21.10.2012, 03:56  [ТС]     объединение множеств #5
спасибо)
даже если выставить в конце '\0' не получается, и функция то шаблонная, а с таким же успехом должна работать и с простыми числами.

Добавлено через 16 минут
вообщем это никак не решить, иначе не будет работать для остальных. поэтому просто в проверке вместо size_r, ставлю размер по факту(10)
спасибо за помощь
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
21.10.2012, 05:20     объединение множеств #6
xexew, ну почему же никак. Возвращайте указатель на конец созданного массива. Т.е. копируйте поведение std::set_union полностью
Yandex
Объявления
21.10.2012, 05:20     объединение множеств
Ответ Создать тему
Опции темы

Текущее время: 13:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru