VPF::[C++]Дек - Форум программистов

al_lex_ey

Дата 1.3.2008, 23:36 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 8.12.2007

Репутация: нет
Всего: нет

Помогите, пожалуйста, сделать дек для целых чисел.

Stark

Дата 2.3.2008, 09:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 18.2.2008

Репутация: 1
Всего: 1

Прости за нескромный вопрос. Что такое дек?

al_lex_ey

Дата 2.3.2008, 10:26 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 8.12.2007

Репутация: нет
Всего: нет

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.
Но если честно я и сам не очень понимаю, что такое дек, поэтому и прошу помочь.

kevor13

Дата 6.3.2008, 20:51 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 10
Регистрация: 19.2.2008

Репутация: нет
Всего: нет

Вот наметки :
Там еще должны быть две функции push_back и pop_front а пока это просто очередь ...
Еслисам не допишешешь, обращайся..

Код


#include <windows.h>
#include <stdio.h>


const int MSize = 100; 

class Deque
      {     
      private:
            int* mas_; // массив 
            int head_; // "Указатель" на начало
            int tail_; // "Указатель" на конец
             
             
            void _nullmas ()// системная функия : зануляет массив 
                 {
                   for (int i = 0; i < MSize; i++)
                    {
                    mas_ [i] = 0; 
                    }
                 } 
      public:
            Deque (); // Конструктор
            ~Deque ();// Деструктор
            void _DUMP_ (); // Распечатка для диагностики 
      
            void push_front (int what); // кладет в голову
            
            int  pop_back  (); // вытаскивает с хвоста            
      };

// Конструктор 
Deque :: Deque ():
      mas_ (new int [MSize]), 
      head_ (1),
      tail_   (head_-1)      
      {_nullmas ();}

// Деструктор 
Deque :: ~Deque ()
      {
      delete [] mas_;
      }

// Распечатка для диагностики
void Deque :: _DUMP_ () 
     {
     printf ("head_ = %d, tail_ = %d \n", head_, tail_  ); 
     for (int i = 0; i < MSize; i++)
         {
         printf ("mas_ [%d] = %d\n", i , mas_ [i]); 
         }
     }

// кладет в начала массива
void Deque :: push_front (int what)
     {
     mas_ [head_- 1] = what;
     head_ ++;
     if (head_ == MSize && tail_ != 0) head_ = 0;
     if (head_ == MSize && tail_ == 0) printf ("Massiv is full");
     }

// вытаскивает с хвоста       
int  Deque :: pop_back ()
     {
     int result = mas_ [tail_];
     mas_ [tail_] = 0;
     tail_ ++;
     return result;      
     }
  

int main () 
{
Deque test;
test.push_front (15);  //
test.push_front (145); //
test.push_front (45);  //   В этих строчках кладуться эллементы в голову  
test.push_front (23);  //
test.push_front (23);  //

test._DUMP_ ();

printf ("result = %d", test.pop_back () ); // Здесь вытасткиваеться с хвоста 

test._DUMP_ ();
system ("PAUSE");
return 0;
}

Это сообщение отредактировал(а) kevor13 - 6.3.2008, 20:53

Domain

Дата 20.10.2010, 01:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

такой вопрос.. есть дек... как реализовать удаление элемента из конца и начала?

дек

Код


struct dek_node
{
        char city[120];
        char date[12];
        int timespeak;
        double tariff;
        dek_node *prev;
        dek_node *next;
};

Пример вставки

Код


dek_node *PutBegin(dek_node *dek)
{
 dek_node *dekNode = new dek_node;
 dek_node *dt = new dek_node;
 cout<<"Enter city: ";cin>>dt->city;
 cout<<"Enter date: ";cin>>dt->date;
 cout<<"Enter timespeak: ";cin>>dt->timespeak;
 cout<<"Enter tariff: ";cin>>dt->tariff;
 cout<<"\n";
        while (dek->prev != 0) dek = dek->prev;
         strcpy(dekNode->city,dt->city);
         strcpy(dekNode->date,dt->date);
         dekNode->timespeak=dt->timespeak;
         dekNode->tariff=dt->tariff;
         dekNode->prev = NULL;
         dekNode->next = dek;
         dek->prev = dekNode;
 return dekNode;
}

Crafty

Дата 20.10.2010, 02:56 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: нет
Всего: 14

Domain, если я ничего не напутал.

Код


void delNode(dek_node *dek)
{
    if ((dek->prev == NULL) && (dek->next == NULL)) // если всего один эл-т
    {
        delete dek;
        return;
    }

    if (dek->prev == NULL) // если эл-т в начале
    {
        dek->next->prev = NULL;
        delete dek;
        return;
    }

    if (dek->next == NULL) // если эл-т в конце
    {
        dek->prev->next = NULL;
        delete dek;
        return;
    }

    // если эл-т в середине
    dek->prev->next = dek->next;
    dek->next->prev = dek->prev;
    delete dek;
}

Это сообщение отредактировал(а) Crafty - 20.10.2010, 03:02

Domain

Дата 20.10.2010, 08:32 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

Crafty спасибо, попробую. Отпишусь как что...

Domain

Дата 20.10.2010, 22:35 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

вообщем юзаю твой метод так

Код


/**************************************************************************/
void DeleteBegin(dek_node *dek)
{
while (dek->prev != 0) dek = dek->prev;
  delNode(dek);
 return;
}
/**************************************************************************/
void DeleteEnd(dek_node *dek)
{
  while (dek->next != 0) dek = dek->next;
   delNode(dek);
      return;
}
/**************************************************************************/

с лева не удаляет строку, а только char city[120]; т.е. как так получается...

Добавлено @ 22:48
а понял. дело в том как я читаю дек из файла в Dek. что-то каряво работает однозначно. вот код как я читаю из файла

Код


dek_node *OpenDec(dek_node *dek)
 {   
 bool st=false;
 fout.close();
 fin.clear();
 fin.open(file_name,ios::in|ios::binary);
 dek_node *dt = new dek_node;
          if (fin.is_open())
          {
          while (fin.read((char*) dt,sizeof *dt))
            {
            if(st==false){
               strcpy(dek->city,dt->city);
               strcpy(dek->date,dt->date);
               dek->timespeak=dt->timespeak;
               dek->tariff=dt->tariff;
               dek->prev = NULL;
               dek->next = NULL;
               st=true;      
               }            
            else
            Opens(dek,dt);//ниже метод описан
             }
          }
          cout<<"BASE '"<<file_name<<"' OPEN\n";
      fin.clear();
      fin.close();
   return dek;
 }

Opens

Код


dek_node *Opens(dek_node *dek,dek_node *dt)
{
    dek_node *dekNode = new dek_node;
     while (dek->next != 0) dek = dek->next;
         strcpy(dekNode->city,dt->city);
         strcpy(dekNode->date,dt->date);
         dekNode->timespeak=dt->timespeak;
         dekNode->tariff=dt->tariff;
         dekNode->prev = dek;
         dekNode->next = NULL;
         dek->next = dekNode;
    return dekNode;
}

может как-то по другому надо?

Это сообщение отредактировал(а) Domain - 20.10.2010, 22:51

Crafty

Дата 20.10.2010, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: нет
Всего: 14

Попробуй в ф-ции добавить ссылку void delNode(dek_node* &dek)
Если не получиться то выложи весь код.

Domain

Дата 21.10.2010, 09:06 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

неее. все дело в том что читаю вроде из файла инфу в дек неверно. если к примеру дек только создан, то твой метод работает нормально, но если дек загружен из файла то уже все криво идет.. знаешь как правильно такие списки правильно нужно из файла тащить?

Crafty

Дата 21.10.2010, 09:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: нет
Всего: 14

Покажи как заполняешь список из файла.

Crafty

Дата 21.10.2010, 10:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: нет
Всего: 14

Вроде всё верно. Может ошибка в записи в файл.
Попробуй вывести на экран содежимое файла без записи в список.

Domain

Дата 21.10.2010, 18:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

вот как сохраняю

Код


void SaveDek(dek_node *dek)
{
  fin.close();
  fout.clear();
  fout.close();
  fout.open(file_name);
if (fout.is_open()){
  while (dek->prev != 0) dek = dek->prev;
  do
  {
    fout.write((char *) dek,sizeof *dek);
    dek = dek->next;
  } while (dek != NULL);
}
   else cout<<"File not exisit";
fout.close();
}

Crafty

Дата 21.10.2010, 20:25 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 319
Регистрация: 3.11.2008

Репутация: нет
Всего: 14

Тут тоже верно. Только открытие файла поправь

Код


fout.open(file_name, ios::binary);

Domain

Дата 21.10.2010, 21:37 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 170
Регистрация: 11.3.2010

Репутация: нет
Всего: нет

блин так в чем касяк? ничего не пойму. по любому любо с загрузкой, либо с сохранением...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »