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

SFY

Дата 5.1.2007, 01:14 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Обычный дек я сделал, но его нужно доделать до треххвостового. По идее, на пересецении "трубок" в нем появляется центральный элемент, который должен хранить указатели на предыдущие элементы, т.е. 3 указателя. И еще один нюанс: например, мы удаляем из одной "трубки" все элементы. Что делать? Очевидно, нам нужен переключатель в центральном элементе, который переключал бы дек на другие "трубки", что бы и в них можно было удалить элементы. Или наоборот - добавить.

Легко в теории, но не столь просто на практике. Как именно это реализовать в коде? Даже и не знаю, с чего начать... Долго лазил по поисковикам, по n-хвостовым декам информации 0 (

Буду рад, если кто-нибудь поможет smile

P.S. Код обычного дека (который нужно доделать) прилагаю в файле, а заодно продублирую здесь.

Код


#include "stdafx.h"
#include <iostream>
using namespace std;
struct node
{
  int elem;
  node *sled;
  node *pred;
};

class Spisok
{
  private:
    node *nd;//Указатель на начало дека.
    node *kd;//Указатель на конец  дека.
    int klad;//Информационное поле удаленного элемента
  public:
    void BuiltDeck ();
    void VyvodDeck ();
    void InsLeft (int);
    void InsRight (int);
    void DelLeft ();
    void DelRight ();
    int Get_Klad () {return klad;}
    void Ochistka();
    void Menu();
};

void main ()
{
  Spisok A;
  int el;
  int term = 10;

  A.Menu ();
  A.BuiltDeck ();
  A.VyvodDeck ();

  while (term !=0)
  {
      cin >> term;
  if (term == 1)
  {  
      cout<<"Enter an element of the part, which must be inserted on the right: ";
      cin>>el; 
      A.InsRight (el); 
      A.VyvodDeck ();
  }
  else if (term == 2)
  {
      cout<<"Enter an element of the part, which must be inserted on the left: ";
      cin>>el; 
      A.InsLeft (el); 
      A.VyvodDeck ();
  }
  else if (term == 3)
  {
      A.DelRight (); 
      A.VyvodDeck ();
      cout<<"Was deleted element: "<<A.Get_Klad()<<endl;
  }
  else if (term == 4)
  {
      A.DelLeft (); 
      A.VyvodDeck ();
      cout<<"Was deleted element: "<<A.Get_Klad()<<endl;
  }
  else if (term == 0)
  {
      break;
  }
  else 
  {
      cout<<"Unknown command"<<endl;
  }
  }
 A.Ochistka();
}

void Spisok::BuiltDeck ()
// Построение дека на базе двунаправленного
// списка с заглавным звеном.
// nd - указатель на начало дека,
// *kd - указатель на конец дека.
{
  node *q;
  node *z;
  int  el;

  nd = new(node);
  z = nd;
  (*nd).pred = (*nd).sled = NULL;
  cout<<"Enter sequence: \n";
  cin>>el;
  while  (el!=0)
  { (*z).sled = new (node);
    (*((*z).sled)).pred = z;
    z = (*z).sled; (*z).sled = NULL;
    (*z).elem = el; cin>>el;}
    if  ((*nd).sled!=NULL)
      { q = nd; nd = (*nd).sled; (*nd).pred = NULL;
        kd = z; delete q; }
    else 
      { delete nd; nd = kd = NULL; }
}

void Spisok::VyvodDeck ()
// Вывод содержимого дека.
// nd - указатель на начало дека.
{
  node *z;

  z = nd; cout<<"Contents of a deque: ";
  if  (z!=NULL)
    while  (z!=NULL)
     { cout<<(*z).elem<<" "; z = (*z).sled; }
  else  cout<<"it empty!\n";
  cout<<endl;
}
void Spisok::InsLeft (int el)
// Добавление звена, содержащего элемент el, в дек слева.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  q = new(node);
  (*q).elem = el;
  if  (nd==NULL)
    { nd = q; (*q).sled = (*q).pred = NULL; kd = q; }
  else
    { (*q).sled = nd; (*q).pred = NULL;
      (*nd).pred = q; nd = q; }
}

void Spisok::InsRight (int el)
// Добавление звена, содержащего элемент el, в дек справа.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  q = new(node);
  (*q).elem = el;
  if  (kd==NULL)
    { nd = q; (*q).sled = (*q).pred = NULL; kd = q; }
  else
    { (*q).sled = NULL; (*q).pred = kd;
      (*kd).sled = q; kd = q; }
}

void Spisok::DelLeft ()
// Удаление звена из дека слева с помещением
// элемента удаляемого звена в переменную klad.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  if  ((*nd).sled!=NULL)
    { q = nd; klad =(*q).elem;
      nd = (*nd).sled; (*nd).pred = NULL; delete q;}
  else
    { // В деке находится один элемент.
      q = nd; klad =(*q).elem;
      nd = kd = NULL; delete q;cout<<"Deque is empty!\n"; }
}

void Spisok::DelRight ()
// Удаление звена из дека справа с помещением
// элемента удаляемого звена в переменную klad.
// nd - указатель на начало дека,
// kd - указатель на конец дека.
{
  node *q;

  if  ((*kd).pred!=NULL)
    { q = kd; klad =(*q).elem;
      kd = (*kd).pred; (*kd).sled = NULL; delete q; }
  else
    {// В деке находится один элемент.
     q = kd; klad =(*q).elem;
     nd = kd = NULL; delete q; cout<<"Deque is empty!\n"; }
}

void Spisok::Ochistka()
{
  node *q,*q1;

  q = nd;
  q1 = (*q).sled;
  while (q1!=NULL)
    { delete q; q = q1; q1 = (*q).sled;}
  delete q;
  nd = kd = NULL;
}

void Spisok::Menu()
//Построение меню
{
  cout << "--------------------------------------"<<endl;
  cout << "Deque Builder v0.1 beta "<<endl;
  cout << "  "<<endl;
  cout << "1. Insert element to the right: "<<endl;
  cout << "2. Insert element to the left: "<<endl;
  cout << "3. Delete last element from the right: "<<endl;
  cout << "4. Delete last element from the left: "<<endl;
  cout << "0. Exit. "<<endl;
  cout << "  "<<endl;
  cout << "--------------------------------------"<<endl;
}

Это сообщение отредактировал(а) SFY - 5.1.2007, 01:14

Присоединённый файл ( Кол-во скачиваний: 6 )

deq.cpp 4,64 Kb

achepkunov

Дата 6.1.2007, 04:53 (ссылка)

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

Загрузка ...

Новичок

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

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

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

Например:

Код


class Dek3
{
   class Spisok deks[3];

public:
   Dek3();
   void Ins(int truba, int element);
   int Del(int truba);
}

Соединяешь все трубки левыми концами. Тогда

Код


void Dek3::Ins(int truba, int element)
{
   deks[truba].InsRight(element);
}

Не буду лишать удовольствия написать Del smile

Только обрати внимание: DelLeft и DelRight должны возвращать информацию о том, получилось ли удалить (а не только печатать). Ну и Del заодно тоже пусть возвращает,только уже номер трубы из которой удалили, или -1 если ничего не удалили: в процессе отладки заметишь, что сообщение про отсутствие элементов может вывестись 3 раза и захочешь вывод этого сообщения перенести в main.

Ну и совсем не по теме: поскольку меню твой Spisok сам не обрабатывает, то нелогично заводить функцию menu в этот класс, лучше уж пусть будет прямо в main.

SFY

Дата 19.1.2007, 04:25 (ссылка)

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

Загрузка ...

Новичок

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

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

Что-то все равно лыжи не едут. Не понял smile

Можно чуть поподробнее расписать?
smile

achepkunov

Дата 25.1.2007, 22:46 (ссылка)

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

Загрузка ...

Новичок

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

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

Если еще актуально - давай попробуем. Напиши тогда, до какого места понял, пойдем дальше потихоньку.

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