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

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

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

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

03.11.2010, 01:16. Просмотров 1477. Ответов 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++
Реализация класса «двусвязный список» C++
Реализация класса множество через двусвязный список. C++
Односвязный список, реализация C++
C++ Односвязный список (реализация без классов)
C++ Функции посчитывающие количество вхождений подстроки в строку, реализация через char* и через шаблон
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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
4819 / 3239 / 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
4819 / 3239 / 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
4819 / 3239 / 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
4819 / 3239 / 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++
Организация дека через New и Delete C++
C++ Создание дека
Переполнение дека C++
C++ Реализация методов для добавления объектов в список

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

Или воспользуйтесь поиском по форуму:
accept
4819 / 3239 / 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