Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

03.11.2010, 01:16. Просмотров 1640. Ответов 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;
    }
так они просто выведутся(с конца) но в деке со[ранятся?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2010, 01:16
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация дека через список (C++):

Считывание элементов дека с файла и запись дека в файл - 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;...

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

а остальное?

Добавлено через 17 часов 8 минут
help
0
Mayonez
380 / 272 / 21
Регистрация: 26.12.2009
Сообщений: 875
03.11.2010, 19:27 #4
лично я не знал что такое дек
вики ТУТ
0
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
03.11.2010, 19:49  [ТС] #5
Цитата Сообщение от Mayonez Посмотреть сообщение
лично я не знал что такое дек
вики ТУТ
я знаю что такое дек.я реализовывал его уже но через другую структуру.
проблема в другом
0
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();
}
не работает.в чем и где ошибки?
0
accept
4825 / 3246 / 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;
}
1
Artishok
ЧакЭ одобряЭ
277 / 276 / 32
Регистрация: 27.12.2009
Сообщений: 1,767
06.11.2010, 13:54  [ТС] #8
в случае showback не выводит ничего.
подкорректировал наподобие showback showfront()-выводит адреса.
если ставить ele.val - ошибка.поэтому ставлю ele->val
0
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
06.11.2010, 15:08 #9
ele.val - это я не заметил

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

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

так что нужно переделать, на первый узел сразу устанавливай head и tail
0
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
0
accept
4825 / 3246 / 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)
1
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)
0
accept
4825 / 3246 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
07.11.2010, 03:57 #13
это у тебя идёт до head->prev

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

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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