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

Сравнение элементов стеков - C++

Восстановить пароль Регистрация
 
MaxKosh
0 / 0 / 0
Регистрация: 24.05.2014
Сообщений: 7
24.05.2014, 01:47     Сравнение элементов стеков #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
24
25
26
27
28
29
30
31
32
33
34
List* combination(List *MyList1, List *MyList2, List *MyList3,int &n1, int &n2,int &n3)
 
{
List *temp1=MyList1;
List *temp2=MyList2;
List *temp3=MyList3;
 
int x1, x2;
for(int i=0;i<n1;i++)
{
  bool flag=false;
  int a = temp1->x1;
  for(int i=0;i<n1;i++)
    {
       int b = temp2->x2;
       if (a == b)
           {
             flag=true;
           }
    }
  if (!flag)
   {
      List *temp1=new List();
      temp1->x=MyList1->x;
      temp1->Next = MyList3;
      MyList3=temp1;
      MyList1=MyList1->Next;
 
      n3+=1;
   }
 
}
return MyList3;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
newbie666
Заблокирован
24.05.2014, 03:35     Сравнение элементов стеков #2
Цитата Сообщение от MaxKosh Посмотреть сообщение
программа
га будущее - никогда не называй "вот это" - программой
А по делу - std::vector
MaxKosh
0 / 0 / 0
Регистрация: 24.05.2014
Сообщений: 7
24.05.2014, 08:49  [ТС]     Сравнение элементов стеков #3
Цитата Сообщение от newbie666 Посмотреть сообщение
га будущее - никогда не называй "вот это" - программой
А по делу - std::vector
помог бы лучше, а не умничал -_-
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
24.05.2014, 10:49     Сравнение элементов стеков #4
MaxKosh, по определению стека вы можете смотреть только на верхний элемент.Если Вам нужны действительно стеки, то нужно где-то запоминать, какие элементы мы уже заносили в стек, в какой-то отдельной структуре.

Тут можно поступить по-разному.Можно, как уже писали выше, использовать std::vector, но тогда запрос на нахождение элемента в векторе будет работать за O(N).Это плохо.

Можете сами написать какое-нибудь дерево сбалансированное: Декарта, АВЛ, Splay и другие.Или тоже самое красно-чёрное - вам будет полезно, и определить, есть ли элемент в структуре мы уже моем за О(logN).Но и добавление элемента тоже за О(logN).Это уже круче.А лучше, чтобы не париться, подключите просто set - это и есть красно-чёрное дерево с хорошей реализацией и асимптотикой.

Но есть третий вариант - использовать структуры на хешах.Они позволят нам добавлять и определять нахождение элемента за О(1), что есть очень хорошо.Правда константа там по-больше будет, да и хеши коллизии давать могут, но если данных очень много, то хеши лучше всего подходят.

Выбирайте, если данных не очень много - то и вектор сойдет.А если много- то ссмотрите в сторону деревьев или хеш-структур.
Yandex
Объявления
24.05.2014, 10:49     Сравнение элементов стеков
Ответ Создать тему
Опции темы

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