Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Волновой алгоритм.

Автор: FasTer 2.7.2006, 18:03

Здравствуйте. пишу прогу и там в алгоритме я в цикле использую свой класс типа int. потом в стандартных классах я использую очередь Queue.
далее
Int - мой класс. поле класса int theInt; конструктор только присваивает значение и есть функция присваивания.
далее

Код


Int Cur;
Cur.putInt(6);
q.put(Cur);
Cur.putInt(5);
q.put(Cur);

теперь когда я 2 раза использую get
cout<<q.get()<q.get();
мне два раза возращает 5.
Подскажите, в чем может быть дело...

Автор: Romikgy 2.7.2006, 18:14

FasTer, исходник весь в студию

Автор: FasTer 2.7.2006, 19:11

usr^) те гык% smile

файл .h с моим классом его назвать summer.h

Код


#include<sortable.h>

classType classInt = __firstUserClass;

class _CLASSTYPE Int :public Sortable
   {
    public:
           Int(int a=0)
              {
               theInt=a;
              }
           /*       Int(Object&a)
               {
            theInt=a.get();
               }
        */
           virtual int isEqual(const Object _FAR & testChar) const
              {
               return (theInt ==((Int&)testChar).theInt);
              }
           virtual int isLessThan(const Object _FAR & testChar) const
              {
               return (theInt<((Int&)testChar).theInt);
              }
           virtual classType isA() const
              {
               return classInt;
              }
           virtual char _FAR *nameOf() const
              {
               return "Integer";
              }
           virtual hashValueType hashValue() const
              {
               return theInt&&theInt;
              }
           virtual void printOn(ostream& outputStream) const
              {
               outputStream<<theInt<<"\n";
              }
           void putInt(int a)
              {
               theInt=a;
              }
           int showElem()
              {
               return theInt;
              }
   private:
           int theInt;
   };

теперь сам .сpp:

Код


#include<conio.h>
#include<string.h>
#include "summer.h"
#include<queue.h>
#include <fstream.h>
#include <iostream.h>
#include <iomanip.h>
#include <dos.h>
odin(int*a,int n)
   {
    for(int i=0;i<n;i++)
       a[i]=-1;
    return *a;
   }

main()
{
clrscr();
ifstream  file;
file.open("tree7.txt",ios::in);
int n;
file>>n;
cout<<n;

int *metka=new int[n];

*metka=odin(metka,n);
Int Cur;
Int** ver=new Int*[n];
for(int i=0;i<n;i++)
ver[i]=new Int[n];

/*for(i=0;i<n;i++)
cout<<metka[i];
otladka
*/

Queue q;
int vershina;

for(i=0;i<n;i++)
 {
  for(int j=0;j<n;j++)
    {
     file>>vershina;
     ver[i][j].putInt(vershina);
     cout<<ver[i][j].showElem();
    }
  cout<<endl;
 }
//First and last Tops of Graph:

int top1,top2;
cout<<endl<<"Enter first top: ";cin>>top1;cout<<endl;
cout<<endl<<"Enter last top: ";cin>>top2;cout<<endl;
//clrscr();

metka[top1-1]=0;
Cur.putInt(top1);
q.put(Cur);
//cout<<endl<<q.peekLeft(); otladka
int k=0,flag=1,flagk=0; //schetchik:
Int hCur;
while(!q.isEmpty())
  {
   if(flagk==0)
    {
     k++;
     flagk=1;
    }

    Cur=(Int&)q.get();
   for(int j=0;j<n;j++)
     if((ver[Cur.showElem()-1][j].showElem()==1)&& ( metka[j]==-1) )
       {
    metka[j]=k;
    hCur.putInt(j+1);
    q.put(hCur);
    if(metka[top2-1]==k) flag=0;

    flagk=0;
       }
   if(flag==0) break;
  // if(q.isEmpty()) {flag==-1; break;}
  }

for(i=0;i<n;i++)
cout<<metka[i]<<endl;
cout<<"k = "<<k<<endl;
if(flag==0)
  {
   cout<<"Way from "<<top1<<" to "<<top2<<": "<<k<<endl;
   cout<<"transport:\n";
   k=0;
   for(i=0;i<n;i++)
    {
     for(int j=0;j<n;j++)
      {
       if(metka[j]==k) cout<<j+1<<" ";
      }
    k++;
    }
  }


if(metka[top2-1]==-1)
  {
   cout<<"Way is not exist!";
  }
Cur.putInt(1);
q.put(Cur);
Cur.putInt(2);
q.put(Cur);
Cur.putInt(3);
q.put(Cur);

delete []metka;
file.close();
getch();
return 0;
}

а вот файл матрицы tree7.txt:

Код


7
0 1 0 0 0 0 0
1 0 1 1 0 0 0
0 1 0 0 0 0 0
0 1 0 1 1 1 1
0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 1 0 0 0

и вот когда указываю путь от 1 до 7 - то работает, а когда от 7 до 1 не работает, тк в очередь вносит 1 вершину. вот собстна не понимаю ,почему так.
Извиняюсь за некорректный путь, ну это и не столь важно, тк это уже не алгоритм волновой smile

Автор: FasTer 3.7.2006, 12:29

Up!

Автор: Sardar 3.7.2006, 13:07

FasTer, а ты не подумал что в очередь добавляеться обьект по ссылке? Дважды закинув один и тот же обьект ты на самом деле закинул две ссылки на один обьект.

Возьми нитку и яблоко. Одна длинная нитка это твоя очередь. Теперь привяжи к яблоку короткую нитку, другим концом к нитке-очереди. Надкуси яблоко. Привяжи ещё одну нитку к яблоку и другим концом к очереди. Глянь на это художественное произведение, поудивляйся чуду.

Автор: zss 3.7.2006, 15:16

Цитата(Sardar @ 3.7.2006, 13:07

)

FasTer, а ты не подумал что в очередь добавляеться обьект по ссылке?

это обсолютно ничего не значит (лишь только для избежания создания ненужных копий).
Внутри все-равно вызывается копирующий конструктор (тоесть будут создано 2 копии объекта)

FasTer, что есть Queue. У меня есть подозрение, что это обертка над std::queue.

Если так, то есть большое подозрение, что ты не удаляешь элемент из очереди а лишь несколько раз получаешь ссылку на первый элемент очереди

Автор: FasTer 3.7.2006, 18:35

zss, Так а что мне делать?
по правилам же я написал get, взять.
я использовал функцию printOn(cout); и выдает пустую очередь. Пытался отслеживать.

Добавлено @ 18:44
Я попробывал по-разному. и вот что получил:
когда я создаю Int q,w; Queue a;
q.puInt(1);
w.putInt(2);
a.put(q);
a.put(w);
a.printOn(cout); \\ тут получаю 1 и 2 в a
дальше изменяю w и тогда в a автоматически получается изменение smile

а как тогда мне сделать так, чтобы использовать в цикле адгоритма переменную типа Int? массив создать?

Автор: Earnest 4.7.2006, 06:40

Ты бы лучше вместо своего путанного кода показал, что такое Queve. Действительно, возникает подозрение, что объекты туда не копируются, а только их ссылки.

Автор: FasTer 4.7.2006, 18:25

Romikgy, код в студии...
Earnest. так я и спрашиваю, из-за чего в очереди хранится указатель элемента моего класса,и что можно с этим сделать... smile

Автор: Romikgy 4.7.2006, 20:42

Цитата(FasTer @ 4.7.2006, 17:25

)

Romikgy, код в студии...

это к чему?

Цитата(FasTer @ 4.7.2006, 17:25

)

из-за чего в очереди хранится указатель элемента моего класса,

а кто класс писал? ты или нет?

Автор: Earnest 4.7.2006, 20:49

Очередь откуда взялась? Что это за класс?
Что толку смотреть на твой код, если неизвестно, как очередь устроена.
Давай показывай реализацию.
Это явно не std::queve, т.е. в последней копии объектов хранятся.

Автор: FasTer 6.7.2006, 08:43

Earnest, Что толку смотреть на твой код, если неизвестно, как очередь устроена.
Давай показывай реализацию.

А что именно про куеуе?

Romikgy,

Я писал класс. у тебя какие-то сомнения? или что-то там не понятно? что сказать про класс?

Добавлено @ 08:50
Использую СLassLib, вот файл куеуе

Код


/*------------------------------------------------------------------------*/
/*                                                                        */
/*  QUEUE.H                                                               */
/*                                                                        */
/*  Copyright Borland International 1991, 1992                            */
/*  All Rights Reserved                                                   */
/*                                                                        */
/*------------------------------------------------------------------------*/

#if !defined( __QUEUE_H )
#define __QUEUE_H

#if defined( TEMPLATES )

    #if !defined( __QUEUES_H )
    #include <Queues.h>
    #endif  // __QUEUES_H

    #pragma option -Vo-
    #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
    #pragma option -po-
    #endif

    #define Queue   BI_TCQueueAsDoubleList
    #define PQueue  PBI_TCQueueAsDoubleList
    #define RQueue  RBI_TCQueueAsDoubleList
    #define RPQueue RPBI_TCQueueAsDoubleList
    #define PCQueue PCBI_TCQueueAsDoubleList
    #define RCQueue RCBI_TCQueueAsDoubleList

    _CLASSDEF( BI_TCQueueAsDoubleList )

    #define QueueIterator   BI_TCQueueAsDoubleListIterator
    #define PQueueIterator  PBI_TCQueueAsDoubleListIterator
    #define RQueueIterator  RBI_TCQueueAsDoubleListIterator
    #define RPQueueIterator RPBI_TCQueueAsDoubleListIterator
    #define PCQueueIterator PCBI_TCQueueAsDoubleListIterator
    #define RCQueueIterator RCBI_TCQueueAsDoubleListIterator

    _CLASSDEF( BI_TCQueueAsDoubleListIterator )

#else   // TEMPLATES

    #if !defined( __CLSTYPES_H )
    #include <ClsTypes.h>
    #endif  // __CLSTYPES_H

    #if !defined( __DEQUE_H )
    #include <Deque.h>
    #endif  // __DEQUE_H

    #pragma option -Vo-
    #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
    #pragma option -po-
    #endif

    _CLASSDEF(Queue)

    class _CLASSTYPE Queue : public Deque
    {

    public:

        Object _FAR & get()
            {
            return Deque::getRight();
            }

        void put( Object _FAR & o )
            {
            Deque::putLeft( o );
            }

        virtual classType isA() const
            {
            return queueClass;
            }

        virtual char _FAR *nameOf() const
            {
            return "Queue";
            }

    private:

        Object _FAR & getLeft();
        Object _FAR & getRight();

        void putLeft( Object _FAR & );
        void putRight( Object _FAR & );

    };

#endif  // TEMPLATES

#if defined( __BCOPT__ ) && !defined( _ALLOW_po )
#pragma option -po.
#endif
#pragma option -Vo.

#endif  // __QUEUE_H

вот класс декуе

Код


/*------------------------------------------------------------------------*/
/*                                                                        */
/*  DEQUE.H                                                               */
/*                                                                        */
/*  Copyright Borland International 1991, 1992                            */
/*  All Rights Reserved                                                   */
/*                                                                        */
/*------------------------------------------------------------------------*/

#if !defined( __DEQUE_H )
#define __DEQUE_H

#if defined( TEMPLATES )

    #if !defined( __DEQUES_H )
    #include <Deques.h>
    #endif  // __DEQUES_H

    #pragma option -Vo-
    #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
    #pragma option -po-
    #endif

    #define Deque   BI_TCDequeAsDoubleList
    #define PDeque  PBI_TCDequeAsDoubleList
    #define RDeque  RBI_TCDequeAsDoubleList
    #define RPDeque RPBI_TCDequeAsDoubleList
    #define PCDeque PCBI_TCDequeAsDoubleList
    #define RCDeque RCBI_TCDequeAsDoubleList

    _CLASSDEF( BI_TCDequeAsDoubleList )

    #define DequeIterator   BI_TCDequeAsDoubleListIterator
    #define PDequeIterator  PBI_TCDequeAsDoubleListIterator
    #define RDequeIterator  RBI_TCDequeAsDoubleListIterator
    #define RPDequeIterator RPBI_TCDequeAsDoubleListIterator
    #define PCDequeIterator PCBI_TCDequeAsDoubleListIterator
    #define RCDequeIterator RCBI_TCDequeAsDoubleListIterator

    _CLASSDEF( BI_TCDequeAsDoubleListIterator )

#else   // TEMPLATES

    #if !defined( __CLSTYPES_H )
    #include <ClsTypes.h>
    #endif  // __CLSTYPES_H

    #if !defined( __CONTAIN_H )
    #include <Contain.h>
    #endif  // __CONTAIN_H

    #if !defined( __DBLLIST_H )
    #include <DblList.h>
    #endif  // __DBLLIST_H

    #pragma option -Vo-
    #if defined( __BCOPT__ ) && !defined( _ALLOW_po )
    #pragma option -po-
    #endif

    _CLASSDEF(Deque)

    class _CLASSTYPE Deque : public Container
    {

    public:

        ~Deque()
            {
         //    flush();
            }

        Object& peekLeft() const
            {
            return list.peekAtHead();
            }

        Object& peekRight() const
            {
            return list.peekAtTail();
            }

        Object& getLeft();
        Object& getRight();

        void putLeft( Object& o )
            {
            list.addAtHead( o );
            itemsInContainer++;
            }

        void putRight( Object& o )
            {
            list.addAtTail( o );
            itemsInContainer++;
            }

        virtual void flush( DeleteType dt = DefDelete )
            {
            list.flush( dt );
            }

        virtual int isEmpty() const
            {
            return list.isEmpty();
            }

        virtual countType getItemsInContainer() const
            {
            return list.getItemsInContainer();
            }

        virtual void forEach( iterFuncType f, void _FAR *arg )
            {
            list.forEach( f, arg );
            }

        virtual Object _FAR & firstThat( condFuncType f, void _FAR *arg ) const
            {
            return list.firstThat( f, arg );
            }

        virtual Object _FAR & lastThat( condFuncType f, void _FAR *arg ) const
            {
            return list.lastThat( f, arg );
            }

        virtual classType isA() const
            {
            return dequeClass;
            }

        virtual char _FAR *nameOf() const
            {
            return "Deque";
            }

        virtual hashValueType hashValue() const
            {
            return list.hashValue();
            }

        virtual int isEqual( const Object& obj ) const
            {
            return list.isEqual( obj );
            }

        virtual int isSortable() const
            {
            return list.isSortable();
            }

        virtual int isAssociation() const
            {
            return list.isAssociation();
            }

        virtual void printOn( ostream& os ) const
            {
            list.printOn( os );
            }

        virtual void printHeader( ostream& os ) const
            {
            list.printHeader( os );
            }

        virtual void printSeparator( ostream& os ) const
            {
            list.printSeparator( os );
            }

        virtual void printTrailer( ostream& os ) const
            {
            list.printTrailer( os );
            }

        virtual ContainerIterator& initIterator() const;

        int ownsElements()
            {
            return list.ownsElements();
            }

        void ownsElements( int del )
            {
            list.ownsElements( del );
            }

    private:

        DoubleList list;

    };

#endif  // TEMPLATES

#if defined( __BCOPT__ ) && !defined( _ALLOW_po )
#pragma option -po.
#endif
#pragma option -Vo.

#endif  // __DEQUE_H

это все из classlib include. вот тут описаны очередь с 2-й очередью... ну это же стандартно...

Автор: Romikgy 6.7.2006, 09:01

Цитата(FasTer @ 6.7.2006, 07:43

)

Я писал класс.

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

Автор: FasTer 6.7.2006, 20:30

В каких указателях?
я создаю Cur - элемент моего класса. его поле - int. и эту величину заношу в очередь.
...
Romikgy, А у тебя код вообще работает этот, если запускал, ты настроил Вс для работы с classlib?
У меня мой алгоритм работает на циклических графах, а вот на дереве не работает, если идти из листка в корень. а если из корня в листок - то работает, тк постоянно одна вершина в очереди хранится и извелкается потом.
Если не можете помочь, то не нужно говорить, что сам написал, сам разбирайся. я бы и не постил тему если бы мог сам справиться, и не писал бы тут на 3 км.
Я наследовал все вируальные классы от сортабла. чтобы мой класс был не вируальным...

Автор: Earnest 7.7.2006, 06:53

Похоже, в очереди действительно хранятся указатели: Хотя внутренностей контейнера все равно не видно, но настораживает, что функция put принимает неконстантную ссылку... и возвращает неконстантные ссылки... Да и сам тип Object - это что? Ты бы почитал документацию, если библиотека стандартная борландовская, то должно быть где-то описано, как с ней работать.

Но я бы выкинула это безобразие с дгоисторической семантикой и использовала stl.

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