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

dLEX

Дата 11.4.2008, 12:12 (ссылка)

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

Загрузка ...

Новичок

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

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

Помогите мне сделать простейший дек. Простейший значит без классов и т. п.
За рание спасибо.

baldina

Дата 11.4.2008, 12:37 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

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

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

JackYF

Дата 11.4.2008, 14:15 (ссылка)

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

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

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

Цитата(dLEX @ 11.4.2008, 11:12

)

Простейший значит без классов и т. п.

и чем должен быть дек, если не классом? smile

--------------------

Пожаловаться на меня как модератора можно здесь.

archimed7592

Дата 11.4.2008, 14:26 (ссылка)

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

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

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

Цитата(JackYF @ 11.4.2008, 14:15

)

и чем должен быть дек, если не классом? smile

Ты не поверишь, но в С, где классов нет в принципе, тоже используют деки smile

--------------------

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

dLEX

Дата 11.4.2008, 14:40 (ссылка)

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

Загрузка ...

Новичок

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

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

Соображений в целом нет, так только немного разобрался с push

archimed7592

Дата 11.4.2008, 14:44 (ссылка)

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

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

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

Ок, для дека понадобится
1. Структура в которой будешь хранить узлы.
2. Ф-ции
  - create
  - pushBack
  - popBack
  - pushFront
  - popFront
  - destroy

С чем конкретно из этого проблемы в реализации или понимании?

--------------------

JackYF

Дата 11.4.2008, 16:41 (ссылка)

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

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

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

Цитата(archimed7592 @ 11.4.2008, 13:26

)

Ты не поверишь, но в С, где классов нет в принципе, тоже используют деки

Поверю. Но, исходя из названия темы, у нас С++ smile

--------------------

Пожаловаться на меня как модератора можно здесь.

baldina

Дата 11.4.2008, 17:00 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

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

dLEX, в качестве базовой структуры проще всего использовать список. Т.к. вставка/удаление ведется с обоих концов, то - двунаправленный.

archimed7592

Дата 11.4.2008, 17:02 (ссылка)

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

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

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

Проще всего воспользоваться std::deque... Ну это так, к слову... smile

--------------------

dLEX

Дата 12.4.2008, 10:15 (ссылка)

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

Загрузка ...

Новичок

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

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

У меня проблемы с пониманием программирования вообще, пытался по книге разобраться, но пока не очень получается, а программа нужна сейчас.

archimed7592

Дата 12.4.2008, 13:22 (ссылка)

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

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

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

Цитата(dLEX @ 12.4.2008, 10:15

)

а программа нужна сейчас

Ок, здесь помогут.

Это сообщение отредактировал(а) archimed7592 - 12.4.2008, 13:26

--------------------

baldina

Дата 12.4.2008, 15:27 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 3433
Регистрация: 5.12.2007
Где: Москва

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

это ну очень простой дек целых чисел. при попытке чтения из пустого дека возвращается 0.
попробуй разобраться.
кстати тут уже и до классов недалеко

Код


#include "iostream"

struct Node {
  Node *prev; 
  Node *next; 
  int data;   
};

struct Deque {
  Node *first; 
  Node *last;  
};

void init (Deque& deque)
{
  deque.first = deque.last = 0;
}

void destroy (Deque& deque)
{
  Node *p = deque.first; 
  while (p != 0)
  {
    Node *temp = p;
    p = p->next;
    delete temp;
  }
  init (deque);
}

void push_back (Deque& deque, int value)
{
  Node *p = new Node;
  p->data = value;
  p->prev = deque.last;
  p->next = 0;

  deque.last = p;
  if (deque.first == 0)
    deque.first = deque.last;
  else
    deque.last->prev->next = deque.last;
}

int pop_back (Deque& deque)
{
  int value = 0;
  if (deque.last != 0)
  {
    value = deque.last->data;
    Node *temp = deque.last;
    deque.last = temp->prev;
    delete temp;
    if (deque.last == 0)
      deque.first = 0;
    else
      deque.last->next = 0;
  }

  return value;
}

void push_front (Deque& deque, int value)
{
  Node *p = new Node;
  p->data = value;
  p->prev = 0;
  p->next = deque.first;

  deque.first = p;
  if (deque.last == 0)
    deque.last = deque.first;
  else
    deque.first->next->prev = deque.first;
}

int pop_front (Deque& deque)
{
  int value = 0;
  if (deque.first != 0)
  {
    value = deque.first->data;
    Node *temp = deque.first;
    deque.first = temp->next;
    delete temp;
    if (deque.first == 0)
      deque.last = 0;
    else
      deque.first->prev = 0;
  }

  return value;
}

bool is_empty (const Deque& deque)
{
  return deque.first == 0;
}

int main ()
{
  Deque d;
  init (d);
  push_front(d, 2);
  push_front(d, 1);
  push_back(d, 3);
  push_back(d, 4);

  while (!is_empty(d))
    std::cout << pop_front (d) << std::endl;


  std::cout << std::endl;

  push_front(d, 2);
  push_back(d, 3);
  push_front(d, 1);
  push_back(d, 4);

  while (!is_empty(d))
    std::cout << pop_back (d) << std::endl;

  destroy (d);

  return 0;
}

Steven

Дата 22.5.2008, 19:29 (ссылка)

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

Загрузка ...

Новичок

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

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

Цитата(baldina @ 12.4.2008, 15:27)

Код


#include "iostream"

struct Node {
  Node *prev; 
  Node *next; 
  int data;   
};

struct Deque {
  Node *first; 
  Node *last;  
};

void init (Deque& deque)
{
  deque.first = deque.last = 0;
}

void destroy (Deque& deque)
{
  Node *p = deque.first; 
  while (p != 0)
  {
    Node *temp = p;
    p = p->next;
    delete temp;
  }
  init (deque);
}

void push_back (Deque& deque, int value)
{
  Node *p = new Node;
  p->data = value;
  p->prev = deque.last;
  p->next = 0;

  deque.last = p;
  if (deque.first == 0)
    deque.first = deque.last;
  else
    deque.last->prev->next = deque.last;
}

int pop_back (Deque& deque)
{
  int value = 0;
  if (deque.last != 0)
  {
    value = deque.last->data;
    Node *temp = deque.last;
    deque.last = temp->prev;
    delete temp;
    if (deque.last == 0)
      deque.first = 0;
    else
      deque.last->next = 0;
  }

  return value;
}

void push_front (Deque& deque, int value)
{
  Node *p = new Node;
  p->data = value;
  p->prev = 0;
  p->next = deque.first;

  deque.first = p;
  if (deque.last == 0)
    deque.last = deque.first;
  else
    deque.first->next->prev = deque.first;
}

int pop_front (Deque& deque)
{
  int value = 0;
  if (deque.first != 0)
  {
    value = deque.first->data;
    Node *temp = deque.first;
    deque.first = temp->next;
    delete temp;
    if (deque.first == 0)
      deque.last = 0;
    else
      deque.first->prev = 0;
  }

  return value;
}

bool is_empty (const Deque& deque)
{
  return deque.first == 0;
}

int main ()
{
  Deque d;
  init (d);
  push_front(d, 2);
  push_front(d, 1);
  push_back(d, 3);
  push_back(d, 4);

  while (!is_empty(d))
    std::cout << pop_front (d) << std::endl;


  std::cout << std::endl;

  push_front(d, 2);
  push_back(d, 3);
  push_front(d, 1);
  push_back(d, 4);

  while (!is_empty(d))
    std::cout << pop_back (d) << std::endl;

  destroy (d);

  return 0;
}

Помогите пожалуйста изменить выше написанную программу и сделать в ней так, чтобы использовалась только одна структура:

Код


struct Node {
  Node *prev; 
  Node *next; 
  int data;   
};

struct Deque {
  Node *first; 
  Node *last;  
};

вот это заменить на одну структуру и чуть-чуть переписать программу с учетом изменений!

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