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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.91
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
#1

Реализация дека через список - C++

03.11.2010, 01:16. Просмотров 1572. Ответов 14
Метки нет (Все метки)

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

а)как проверить является ли пустой голова/хвост?
делал так
C++
1
2
3
4
 
list *head;
......
if (head==null)
ругается на null

б)добавлять элементы надо так?
в голову
C++
1
2
3
4
5
list *spis=new list;
        spis->next=head;
        spis->prev=null;
        spis->val=x;
        head=spis;
C++
1
2
3
4
spis->next=null; 
    spis->val=x;
        spis->prev=ends; 
    ends=spis;
в)как извлекать(т.е. вывести и удалить)?

C++
1
2
3
4
5
while(ele->prev!=null)
    {
        cout<<ele->val<<" ";
        ele=ele->prev;
    }
так они просто выведутся(с конца) но в деке со[ранятся?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2010, 01:16     Реализация дека через список
Посмотрите здесь:

Считывание элементов дека с файла и запись дека в файл - C++
Доброго времени суток. Я написал код программы про дек с ограниченным входом слева (то есть с него можно удалять элементы как с начала,...

реализация стека через односвязный список - C++
вот что я накалякал... должно по идее выводить первый элемент стека (ну лн в принципе пока тут и единственный), но вылетает либо 0 либо...

Реализация класса множество через двусвязный список. - C++
дали задание реализовать класс множество через двусвязный список. Сам класс список мне реализовать вроде удалось, но стоит загвоздка в...

Организация дека через New и Delete - C++
Уважаемы форумчане, помогите с написанием программы. Необходимо написать программу которая организует работу с деком (добавление...

Преимущества и недостатки при реализации стека, очереди и дека через дин. массива - C++
Доброго времени суток! 1) Назовите преимущества и недостатки реализации очереди с помощью динамического массива. 2) Назовите...

Функции посчитывающие количество вхождений подстроки в строку, реализация через char* и через шаблон - C++
Необходимо реализовать две функции: 1) int SubStrCount(const char *str, const char *subStr); 2) template&lt;typename T&gt;...

Односвязный список, реализация - C++
Добрый вечер! :) Пытаюсь разобраться как работают списки. Делаю последовательный односвязный список, в который можно добавить элемент,...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
В астрале
Эксперт С++
7970 / 4732 / 320
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
03.11.2010, 01:34     Реализация дека через список #2
Artishok, NULL пишется. + В С++ лучше использовать просто 0.
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
03.11.2010, 19:17  [ТС]     Реализация дека через список #3
хм.ясн

а остальное?

Добавлено через 17 часов 8 минут
help
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
03.11.2010, 19:27     Реализация дека через список #4
лично я не знал что такое дек
вики ТУТ
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
03.11.2010, 19:49  [ТС]     Реализация дека через список #5
Цитата Сообщение от Mayonez Посмотреть сообщение
лично я не знал что такое дек
вики ТУТ
я знаю что такое дек.я реализовывал его уже но через другую структуру.
проблема в другом
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
05.11.2010, 20:26  [ТС]     Реализация дека через список #6
ну вот что получилось у меня
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
typedef struct list
{
    int val;
    list *next; //ГіГЄГ*Г§Г*òåëü Г*Г* ñëåäóþùèé ýëåìåГ*ГІ
    list *prev; //ГіГЄГ*Г§Г*òåëü Г*Г* ïðåäûäóùèé ýëåìåГ*ГІ
};
 
list *head=0,*tail=0; //ãëîáГ*ëüГ*ûå ïåðåìåГ*Г*ûå ãîëîâû ГЁ õâîñòГ* Г±ГЇГЁГ±ГЄГ*
 
void insertfront(int x)
{
    list *spis=new list;
    spis->prev=0;//ïðè äîáГ*âëåГ*ГЁГЁ Гў Г*Г*Г·Г*ëî ïðåäûäóùåãî ýëåìåГ*ГІГ* Г*ГҐ Г±ГіГ№ГҐГ±ГІГўГіГҐГІ
    spis->val==x;
    if (head==0)
     spis->next=tail;
     else
     spis->next=head;
     head=spis;
}
 
void insertback(int x)
{
    list *spis=new list;
    spis->next=0;
    spis->val=x;
    if (tail==0)
      spis->prev=head;
      else
      spis->prev=tail;
      tail=spis;
}
 
void showfront()
{
  list *ele=new list;
  ele=head;
  while(ele!=0)
  {
   cout<<ele.val<<" ";
   ele=ele->next;
  }
}
 
void showback()
{
    list *ele=new list;
    ele=tail;
    while(ele!=0)
    {
    cout<<ele.val<<" ";
    ele=ele->next; 
    }
}
 
int main()
{
    for(int i=0;i<10;i++)
    insertfront(i);
    showfront();
}
не работает.в чем и где ошибки?
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 05:02     Реализация дека через список #7
C++
1
2
3
4
5
6
7
8
9
10
11
void showback()
{
        //list *ele=new list; // не надо выделять память
 
        list *ele = tail;
        while(ele != 0) {
            cout << ele.val << " ";
            //ele=ele->next; // почему next ?
            ele=ele->prev;
        }
}
C++
1
2
3
4
5
6
void showback()
{
    for (list *ele = tail; ele; ele = ele->prev)
        cout << ele.val << " ";
    cout << endl;
}
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
06.11.2010, 13:54  [ТС]     Реализация дека через список #8
в случае showback не выводит ничего.
подкорректировал наподобие showback showfront()-выводит адреса.
если ставить ele.val - ошибка.поэтому ставлю ele->val
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 15:08     Реализация дека через список #9
ele.val - это я не заметил

C++
1
spis->val==x;
=

у тебя как получается, если добавить несколько элементов справа, то ты не можешь применить showfront()
если добавить несколько элементов слева, то ты не можешь применить showback()

так что нужно переделать, на первый узел сразу устанавливай head и tail
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
06.11.2010, 15:27  [ТС]     Реализация дека через список #10
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream.h>
 
//äåê ðåГ*ëèçîâûâГ*ГҐГІГ±Гї Гў Г¤Г*Г*Г*îì ñëó÷Г*ГҐ ÷åðåç äâóГ*Г*ГЇГ°Г*âëåГ*Г*ûé ñïèñîê
 
typedef struct deque
{
    int val;
    deque *prev;
    deque *next;
};
 
deque *head=0,*tail=0;
 
void insertnach(int x)
{ 
  deque *tmp=new deque;
  tmp->val=x;
  if (head==0)
  {
    head=tmp;
    tail=tmp;
  }
  else
  {
    head->prev=tmp;//ýëåìåГ*ГІ ïåðåä ãîëîâîé Г*îâûé
    tmp->next=head;//ýëåìåГ*ГІ Г*îâûé èäåò ïåðåä Г±ГІГ*ðûì
    head=tmp;//Г*îâГ*Гї ãîëîâГ* Г*îâûé ýëåìåГ*ГІ
  }
}
 
void insertlast(int x)
{
    deque *tmp=new deque;//ñîçäГ*ГҐГ¬ ýëåìåГ*ГІ
    tmp->val=x;
    if (head==0)//åñëè ïóñòîé äåê
    {
        head=tmp;
        tail=tmp;
        
    }
    else
    {
        tail->next=tmp;//
        tmp->prev=tail;
        tail=tmp;
    }
}
 
void showfront()
{
    deque *el;
    el=head;
    while(el!=0)
    {
        cout<<el->val<<" ";
        el=el->next;
    }
}
 
void showback()
{
    deque *el;
    el=tail;
    while(el!=0)
    {
        cout<<el->val<<endl;
        el=el->prev;
    }
}
    
    
int main()
{
    for(int i=0;i<10;i++)
    insertnach(i);
    showfront();
}
тут не работает showback и криво insertnach
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 15:37     Реализация дека через список #11
C++
1
2
3
4
5
6
typedef struct deque
{
        int val;
        deque *prev;
        deque *next;
};
это что

C++
1
2
3
4
5
struct deque
{
    int val;
    deque *prev, *next;
};
в insertlast нужно if (tail == 0)
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
06.11.2010, 17:30  [ТС]     Реализация дека через список #12
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream.h>
 
//äåê ðåГ*ëèçîâûâГ*ГҐГІГ±Гї Гў Г¤Г*Г*Г*îì ñëó÷Г*ГҐ ÷åðåç äâóГ*Г*ГЇГ°Г*âëåГ*Г*ûé ñïèñîê
 
typedef struct deque
{
    int val;
    deque *prev,*next;
};
 
deque *head=0,*tail=0;
 
void insertnach(int x)
{ 
  deque *tmp1=new deque;//ñîçäГ*ГҐГ¬ Г*îâûé ýëåìåГ*ГІ
  tmp1->val=x;//Гў ïîëå Г¤Г*Г*Г*ûõ âïèñûâГ*ГҐГ¬ Г§Г*Г*Г·ГҐГ*ГЁГҐ
  if (head==0)
  {
    head=tmp1;//åäèГ*Г±ГІГўГҐГ*Г*ûé ýëåìåГ*ГІ ïîêГ* ГЁ Г*Г*Г·Г*ëî
    tail=tmp1;//ГЁ õâîñò
  }
  else
  {
    head->prev=tmp1;//ýëåìåГ*ГІ ïåðåä ãîëîâîé Г*îâûé
    tmp1->next=head;//ýëåìåГ*ГІ Г*îâûé èäåò ïåðåä Г±ГІГ*ðûì
    head=tmp1;//Г*îâГ*Гї ãîëîâГ* Г*îâûé ýëåìåГ*ГІ
    head->prev=0;
  }
}
 
void insertlast(int x)
{
    deque *tmp=new deque;//ñîçäГ*ГҐГ¬ ýëåìåГ*ГІ
    tmp->val=x;
    if (tail==0)//åñëè ïóñòîé äåê
    {
        head=tmp;
        tail=tmp;
        
    }
    else
    {
        tail->next=tmp;//ñëåäóþùèé ýëåìåГ*ГІ Г§Г*  ГµГўГ®Г±ГІГ®Г¬ Г*îâûé
        tmp->prev=tail;//äëÿ Г*îâîãî ýëåìåГ*ГІГ* ïðåäûäóùèé - õâîñò
        tail=tmp;//õâîñò Г*îâûé ýëåìåГ*ГІ
        tail->next=0;
    }
}
 
void showfront()
{
    deque *el;
    el=head;
    while(el!=tail->next)
    {
        cout<<el->val<<" ";
        el=el->next;
    }
}
 
void showback()
{
    deque *el1;
    el1=tail;
    while(el1!=head->prev)
    {
        cout<<el1->val<<" ";
        el1=el1->prev;
    }
}
 
void clean()
{
    deque *del;
    while(head!=0)
    {
      del=head;
      head=head->next;
      delete del;
    }
}
    
    
int main()
{
    for(int i=0;i<10;i++)
    insertnach(i);
    showfront();
}
Теперь похоже работает

Добавлено через 10 минут
правда я так и не понял почему цикл идет до head->prev(или tail->next)
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
07.11.2010, 03:57     Реализация дека через список #13
это у тебя идёт до head->prev

я тебе функцию писал, там только el.val неправильно
Реализация дека через список

хотя у тебя тоже сработает, останавливаться будет на head->prev
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
07.11.2010, 14:32  [ТС]     Реализация дека через список #14
Теоретически записи эквивалентны т.к head->prev==0 и tail->next==0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2010, 14:52     Реализация дека через список
Еще ссылки по теме:

Реализация класса «двусвязный список» - C++
потребовалось выполнить такое задание, вот только не могу сообразить с чего начать и как собственно будет выглядеть код (в связи с тем, что...

Односвязный список (реализация без классов) - C++
Задача проста: создать список из слов, вводимых с клавиатуры, и вывести его на консоль. Всё вводит и выводит. Только откуда-то взялась &quot;Д&quot;...

Реализация методов для добавления объектов в список - C++
Народ помогите пожалуйста с реализация методов для добавления объектов в список и просмотра списка. По заданию надо: 1. Определить...

Создание дека - C++
Здравствуйте. Изучаю STL и считаю, что в изучении программирования нет ничего лучше, чем создание велосипедов. От чего вы**ал свой...

Переполнение дека - C++
Здравствуйте. Не могу понять где переполняется чертов дек.Суть программы заключается в том, что при нажатии определенных кнопок выполняется...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
accept
4821 / 3241 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
07.11.2010, 14:52     Реализация дека через список #15
юзай свой вариант, так как у тебя как раз обнуление и нужно, чтобы по нему определять концы
код пояснее получается
Yandex
Объявления
07.11.2010, 14:52     Реализация дека через список
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru