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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 313, средняя оценка - 4.62
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
#1

Списки, стеки, очереди - C++

19.10.2010, 12:11. Просмотров 42832. Ответов 53
Метки нет (Все метки)

В процессе разбора этой темы появились программки на список. Сделанные через класс, не идеал конечно, но вроде бы и не самый плохой вариант. Выложу, вдруг кому пригодится. Конструктивная критика приветствуется.
Двунаправленный список и очередь будет чуть позже. С двунаправленным возникли некоторые трудности.

Однонаправленный список
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#ifndef _LISTNODE_H_
#define _LISTNODE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class List
{
public:
    List():head(0), tail(0)
    {
    }
    
    ~List()
    {
        delete head;
        delete tail;
    }
 
    void push_back(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void print()
    {
        if(head==0)
        {
            throw std::string("List is empty!");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
 
    void push_front(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        Temp->next=head;
        head=Temp;
    }
 
    void erase()
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        Node* delptr=head->next;
        head=head->next;
        delete delptr;
    }
    
    void erase(T val)
    {
        Node* ptrPrev;
        ptrPrev=new Node;
        if(head==0)
        {
            throw std::string("List is empty\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem==val)
            {
                ptrPrev->next=ptr->next;
                delete ptr;
                break;
            }
            ptrPrev=ptr;
        }
        if(ptrPrev->next==0)
            std::cout<<"There are no elements in list equal to "<< val <<'\n';
    }
 
    void clear()
    {
        while(head!=0)
            erase();
    }
 
    void find(T val)
    {
        if(head==0)
        {
            throw std::string("List is empty!\n");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
        {
            if(ptr->elem=val)
                std::cout<<"Element "<< val <<" is finded\n";
            return;
        }
        std::cout<<"Element "<< val <<" is not finded\n";
    }
    
    void insert(T val)
    {
        if(head==0)
        {
            push_front(val);
            return;
        }
        Node* Temp=new Node;
        Temp->elem=val;
        Node* founded=head;
        for(founded; founded!=0; founded=founded->next)
        {
            if(founded->elem<val)
                break;
        }
        if(founded==0)
        {
            push_front(val);
            return;
        }
        Temp->next=founded->next;
        founded->next=Temp;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
 
    Node* head;
    Node* tail;
};
 
#endif
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
#include "ListNode.h"
 
int main()
{
    List<int> Lst;
    Lst.push_back(5);
    Lst.push_back(10);
    Lst.push_back(15);
    Lst.push_front(1);
    Lst.push_front(25);
    Lst.push_back(4);
    Lst.insert(9);
    Lst.insert(6);
    Lst.insert(4);
    Lst.insert(5);
    Lst.insert(55);
    Lst.insert(40);
    Lst.insert(0);
    Lst.insert(70);
    Lst.insert(56);
    Lst.erase(5);
    try
    {
        Lst.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    return 0;
}

Стек
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
#ifndef _STACKNODE_H_
#define _STACKNODE_H_
 
#include <string>
 
template<class T>
class Stack
{
public:
    Stack():tail(0), head(0)
    {
    }
    
    ~Stack()
    {
        delete tail;
        delete head;
    }
 
    void push(T val)
    {
        Node* Temp;
        Temp=new Node;
        Temp->elem=val;
        if(tail==0)
        {
            tail=Temp;
        }
        else
        {
            Temp->next=tail;
            tail=Temp;
        }
    }
 
    T top()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        return tail->elem;
    }
 
    void pop()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        Node* delptr=tail;
        tail=tail->next;
        delete delptr;
    }
 
    void print()
    {
        if(tail==0)
        {
            throw std::string("Stack is empty!");
        }
        for(Node* ptr=tail; ptr!=0; ptr=ptr->next)
        {
            std::cout<<ptr->elem<<' ';
        }
        std::cout<<'\n';
    }
private:
    struct Node
    {
        Node():elem(0), next(0)
        {
        }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif
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
#include <iostream>
 
#include "StackNode.h"
 
int main()
{
    Stack<char> St;
    St.push('a');
    St.push('b');
    St.push('d');
    St.push('c');
    try
    {
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
        std::cout<<St.top()<<'\n';
        St.pop();
        St.print();
    }
    catch(const std::string& e)
    {
        std::cout<<e<<'\n';
    }
    return 0;
}


Добавлено через 48 минут
Очередь
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
#ifndef _QUEUE_H_
#define _QUEUE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class NodeQueue
{
public:
    NodeQueue():head(0), tail(0)
    {
    }
 
    ~NodeQueue()
    {
        delete head;
        delete tail;
    }
 
    void enqueue(T val)
    {
        Node* Temp=new Node;
        Temp->elem=val;
        if(head==0)
        {
            head=Temp;
            tail=Temp;
            return;
        }
        tail->next=Temp;
        tail=Temp;
    }
 
    void dequeue()
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        Node* delPtr=head;
        std::cout<<"Element "<< head->elem <<" is deleted from the queue\n";
        head=head->next;
        delete delPtr;
    }
 
    const T& front() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        return head->elem;
    }
 
    void print() const
    {
        if (empty())
        {
            throw std::string("Queue is empty");
        }
        for(Node* ptr=head; ptr!=0; ptr=ptr->next)
            std::cout<<ptr->elem<<' ';
        std::cout<<'\n';
    }
 
    bool empty() const
    {
        return head==0;
    }
private:
    struct Node
    {
                Node():next(0), elem(0)
                {
                }
        Node* next;
        T elem;
    };
    Node* head;
    Node* tail;
};
 
#endif
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
#include "Queue.h"
 
int main()
{
        try
        {
    NodeQueue<int> Queue;
    Queue.enqueue(10);
    Queue.enqueue(20);
    Queue.enqueue(30);
    std::cout<<"Top is: "<<Queue.front()<<'\n';
    Queue.dequeue();
    Queue.print();
        }
        catch(const std::string& e)
        {
             std::cout<<e<<'\n';
        }
}
12
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2010, 12:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Списки, стеки, очереди (C++):

Списки. Стеки. Очереди - C++
Квадрат разбит на {4}^{k} равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина...

Задача на тему Стеки, очереди, деки, списки, кольца - C++
Программа на вход получает список школьников следующего вида: 9 Иванов 10 Петров 11 Сидоров 9 Григорьев ...

Списки, Стеки,Очереди (На сколько кусков распадется оставшаяся часть листа? ) - C++
Доброго всем времени суток!! Помогите написать программу: Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На...

C++ Стеки, Очереди - C++
Дан целочисленный массив размера N. Преобразовать его, прибавив к нечетным числам последний элемент. Последний элемент массива не изменять....

Стеки и очереди - C++
Ребят, помогите справится с заданием. Задача 6. Система состоит из процессора P, трёх очередей F0, F1, F2 и стека S. В систему...

Очереди и стеки - C++
#include &quot;stdafx.h&quot; #include &quot;iostream&quot; using namespace std; struct stack { int x; stack *Next,*Head; ...

53
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
19.10.2010, 12:20 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Lavroff, первое, что увидел:
C++
1
2
3
4
5
        ~List()
        {
                delete head;
                delete tail;
        }
А те, узлы, которые между head и tail, Страуструп удалять будет?
5
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
19.10.2010, 12:21 #3
Двунаправленный список с перегрузкой копирования(честно лень вырезать было).
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
#include<iostream>
using namespace std;
struct dates
{
    int num;
    int count;
    dates *back;
    dates *forward;
};
class list_dates
{
private:
    dates *current;
    dates *first;
public:
    list_dates()
    {
        current=NULL;
        first=NULL;
    }
    void input()
    {
        dates *nows=new dates;
        if(current==NULL)first=nows;
        cout << "Введите номер: ";
        cin >> nows->num;
        cout << "Введите количество: ";
        cin >> nows->count;
        nows->back=current;
        nows->forward=NULL;
        if(current!=NULL)current->forward=nows;
        current=nows;
    }
    void print()
    {
        dates *tmp=first;
        while(tmp!=NULL)
        {
            cout << "Номер: " << tmp->num;
            cout << "\t\tКоличество: " << tmp->count << endl;
            tmp=tmp->forward;
        }
    }
    list_dates& operator=(list_dates ld2)
    {
        cout << "RUN SCRIPT";
        dates *tmp2=ld2.current;
        while(tmp2!=NULL)
        {
            dates *tmp=new dates;
            tmp->num=tmp2->num;
            tmp->count=tmp2->count;
            tmp2=tmp2->back;
            if(first!=NULL)
            {
                tmp->forward=first;
                first->back=tmp;
            }
            if(current==NULL)
            {
                current=tmp;
                tmp->forward=NULL;
                first=current;
            }
            else first=tmp;
        }
        return *this;
    }
    void sfirst()
    {
        cout << first << endl;
    }
};
int main()
{
    setlocale(LC_ALL,"Russian");
    list_dates ld;
    ld.input();
    ld.input();
    ld.print();
    list_dates ld2;
    ld2=ld;
    ld2.print();
    ld.sfirst();
    ld2.sfirst();
    return EXIT_SUCCESS;
}
Мдя... и деструктор не написал\ Вот твк всегда\
1
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
19.10.2010, 12:43  [ТС] #4
easybudda, М... А вроде все корректно чистится... Я так понимаю, нужен деструктор в Node?

Добавлено через 14 минут
Деструктор как я понял должен выглядить примерно так?

C++
1
2
3
4
5
6
7
8
9
~List()
{
    while(head!=0)
    {
    Node* ptr=head;
    head=head->next;
    delete ptr;
    }
}
0
RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
19.10.2010, 12:46 #5
Двусвязный список:
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include "LIST.H"
 
//
// Implementation of some methods of class List
//
// You may listen and writing lections and reading
// your abstracts and thinking and this implementation
// becomes clearly!
//
 
 
Item::Item() : next( NULL), prev( NULL ), owner( NULL ) {
};
 
Item::~Item(){
    if( owner != NULL )
        owner->Remove( this );
};         
 
Item * Item::Next(void) const{
    return next;
};
 
 
 
List::List(void) : head(0), tail(0), count(0)
{
}
 
List::~List(){
    Clear();
}
 
Item * List::First(void) const
{
  return head;
}
 
void List::Add(Item * p)
{
  if (!p || p->owner) // necessary!
    return;
 
  p->prev = tail;  // it's as usual -
  p->next = 0;     // compare it with lab #2 example
  if (tail)
    tail->next = p;
  else
    head = p;
  tail = p;
 
  p->owner = this; // necessary! - and for Insert() also,
                   // moreover Remove(Item*p) must do "p->owner=0"
  count++;         // necessary! (see below)
}
 
void List::Delete(int n)
{
  Item * p = Remove(n); // then Remove(int) calls Remove(Item*) :)
  if (p)
    delete p;
}
 
int List::Count(void) const
{
  return count;  // don't spend time for watch in list -        :)
}                // Add() & Insert() do "count++" (see above)
                 // and Remove(Item*) do "count--"
 
Item * List::GetItem(int n) const{
    Item *cur;
    int i;
    if(n<0) 
       return NULL;
    //Перебираем цикл, пока не найдем n-ый элемент
    for( i = 0, cur = head; i < n && (cur != NULL); i++, cur = cur->Next() ); 
    return cur;
};
 
Item * List::Remove(int n){
    //Находим нужный элемент и удаляем его по ссылке
    Item *cur = GetItem( n );
    return Remove( cur );
};
 
Item * List::Remove(Item * p){
    //Если элемент - NULL то выходим
    if( p == NULL ) return p;
    //Если это была "голова" то перемещаем голову на следующий элемент
    /*if( p == head ) 
        head = p->next;*/
    //Если был хвос - то перемещаем его на предыдущий элемент
    if( p == tail ) 
        tail = p->prev;
    //Стандартные перемещения ссылок
    if( p->prev != NULL )
        p->prev->next = p->next;
    else
        head = p->next;
    if( p->next != NULL )
        p->next->prev = p->prev;
    //Обнуляем владельца
    p->owner = NULL;
    //Уменьшаем количество
    count--;
    return p;
};
 
int List::GetIndex(const Item * p) const
{   //проверяем корректность
    if (!p || !(p->owner)) return -1;
    //if( p == NULL ) return -1;
    Item *cur;
    int i;
    //В цикле - перебираем от головы до хвоста пока не найдем элемент который равен указателю
    for( i = 0, cur = head; (cur != NULL ) && (cur != p); i++, cur = cur->Next() ); 
    if( cur == NULL ) return -1;
    return i;
};
 
void List::Clear(void){
    //Пока количество не станет равно 0, удаляем первый элемент
    while( count > 0 ){
        Delete( 0 );
    }
};
 
void List::Insert(Item * p, int n){
    if( n >= count ) 
        Add( p );
    if (!p || p->owner) // necessary!
        return;
 
    Item * cur = GetItem( n );
    if(cur == NULL)
        return;
 
    p->prev = cur->prev;  
    p->next = cur;
 
    if( cur->prev )
        cur->prev->next = p;
    else
        head = p;
    cur->prev = p;
 
    /*if (head==cur)
        head = p;*/
 
    p->owner = this; 
    count++;         
};
LIST.H
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
#ifndef _LIST_H_
#define _LIST_H_
  // this directives requires for prevent of
  // repeated include this header in some module
 
class Item
{
  friend class List;
 
private:
  // Base set
  Item * prev;
  Item * next;
 
  // Additional
  List * owner;    // for remove self from list and
                   // for check when item in list
public:
  Item(void);
  ~Item();         // for correct object destruction
                   // with removing it from list
  // Additional
  Item * Next(void) const;  // special for implementation
                            // of iterations algorithms,
                            // returns "next" field
};
 
class List
{
private:
  // Base set
  Item * head;
  Item * tail;
 
  // Additional
  int count;     // for quickly count items in list
 
public:
  List(void);
  ~List();       // kills all of items inself
 
  // Base set
  void Add(Item * p);
  Item * GetItem(int n) const;
  Item * Remove(int n);
  int Count(void) const;
 
  // Additional
  void Insert(Item * p, int n); // insert item by pointer "p"
                                // at position "n" in list or
                                // (VERY IMPORTANT!) at end of list
  int GetIndex(const Item * p) const;
  void Delete(int n);        // found and destroy
  void Clear(void);
  Item * Remove(Item * p);   
 
  Item * First(void) const;   
 
#endif    // finish #ifndef at top
Добавлено через 2 минуты
Может у кого есть код для бинарного дерева?
1
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
19.10.2010, 13:02 #6
Цитата Сообщение от Lavroff Посмотреть сообщение
Деструктор как я понял должен выглядить примерно так?
я бы так сделал
C++
1
2
3
4
5
6
7
~List(){
    while ( head ){
        tail = head->next;
        delete head;
        head = tail;
    }
}
зачем зря переменные плодить?
2
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
19.10.2010, 13:11  [ТС] #7
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Исправленное.

Список
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#ifndef _LISTNODE_H_
#define _LISTNODE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class List
{
public:
        List():head(0), tail(0)
        {
        }
        
        ~List()
        {
                while(head)
                {
                    tail=head->next;
                    delete head;
                    head=tail;
                }
        }
 
        void push_back(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                if(head==0)
                {
                        head=Temp;
                        tail=Temp;
                        return;
                }
                tail->next=Temp;
                tail=Temp;
        }
 
        void print()
        {
                if(head==0)
                {
                        throw std::string("List is empty!");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        std::cout<<ptr->elem<<' ';
                }
                std::cout<<'\n';
        }
 
        void push_front(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                Temp->next=head;
                head=Temp;
        }
 
        void erase()
        {
                if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
                Node* delptr=head->next;
                head=head->next;
                delete delptr;
        }
        
        void erase(T val)
        {
                Node* ptrPrev;
                ptrPrev=new Node;
                if(head==0)
                {
                        throw std::string("List is empty\n");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        if(ptr->elem==val)
                        {
                                ptrPrev->next=ptr->next;
                                delete ptr;
                                break;
                        }
                        ptrPrev=ptr;
                }
                if(ptrPrev->next==0)
                        std::cout<<"There are no elements in list equal to "<< val <<'\n';
        }
 
        void clear()
        {
                while(head!=0)
                        erase();
        }
 
        void find(T val)
        {
                if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                {
                        if(ptr->elem=val)
                                std::cout<<"Element "<< val <<" is finded\n";
                        return;
                }
                std::cout<<"Element "<< val <<" is not finded\n";
        }
        
        void insert(T val)
        {
                if(head==0)
                {
                        push_front(val);
                        return;
                }
                Node* Temp=new Node;
                Temp->elem=val;
                Node* founded=head;
                for(founded; founded!=0; founded=founded->next)
                {
                        if(founded->elem<val)
                                break;
                }
                if(founded==0)
                {
                        push_front(val);
                        return;
                }
                Temp->next=founded->next;
                founded->next=Temp;
        }
private:
        struct Node
        {
                Node():next(0), elem(0)
                {
                }
                Node* next;
                T elem;
        };
 
        Node* head;
        Node* tail;
};
 
#endif
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
#include "ListNode.h"
 
int main()
{
        List<int> Lst;
        Lst.push_back(5);
        Lst.push_back(10);
        Lst.push_back(15);
        Lst.push_front(1);
        Lst.push_front(25);
        Lst.push_back(4);
        Lst.insert(9);
        Lst.insert(6);
        Lst.insert(4);
        Lst.insert(5);
        Lst.insert(55);
        Lst.insert(40);
        Lst.insert(0);
        Lst.insert(70);
        Lst.insert(56);
        Lst.erase(5);
        try
        {
                Lst.print();
        }
        catch(const std::string& e)
        {
                std::cout<<e<<'\n';
        }
        return 0;
}


Стек
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
#ifndef _STACKNODE_H_
#define _STACKNODE_H_
 
#include <string>
 
template<class T>
class Stack
{
public:
        Stack():tail(0), head(0)
        {
        }
        
        ~Stack()
        {
              while(head)
              {
                  tail=head->next;
                  delete head;
                  head=tail;
              }
        }
 
        void push(T val)
        {
                Node* Temp;
                Temp=new Node;
                Temp->elem=val;
                if(tail==0)
                {
                        tail=Temp;
                }
                else
                {
                        Temp->next=tail;
                        tail=Temp;
                }
        }
 
        T top()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                return tail->elem;
        }
 
        void pop()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                Node* delptr=tail;
                tail=tail->next;
                delete delptr;
        }
 
        void print()
        {
                if(tail==0)
                {
                        throw std::string("Stack is empty!");
                }
                for(Node* ptr=tail; ptr!=0; ptr=ptr->next)
                {
                        std::cout<<ptr->elem<<' ';
                }
                std::cout<<'\n';
        }
private:
        struct Node
        {
                Node():elem(0), next(0)
                {
                }
                Node* next;
                T elem;
        };
        Node* head;
        Node* tail;
};
 
#endif
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
#include <iostream>
 
#include "StackNode.h"
 
int main()
{
        Stack<char> St;
        St.push('a');
        St.push('b');
        St.push('d');
        St.push('c');
        try
        {
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
                std::cout<<St.top()<<'\n';
                St.pop();
                St.print();
        }
        catch(const std::string& e)
        {
                std::cout<<e<<'\n';
        }
        return 0;
}


Очередь
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
#ifndef _QUEUE_H_
#define _QUEUE_H_
 
#include <iostream>
#include <string>
 
template<class T>
class NodeQueue
{
public:
        NodeQueue():head(0), tail(0)
        {
        }
 
        ~NodeQueue()
        {
             while(head)
             {
                 tail=head->next;
                 delete head;
                 head=tail;
             }
        }
 
        void enqueue(T val)
        {
                Node* Temp=new Node;
                Temp->elem=val;
                if(head==0)
                {
                        head=Temp;
                        tail=Temp;
                        return;
                }
                tail->next=Temp;
                tail=Temp;
        }
 
        void dequeue()
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                Node* delPtr=head;
                std::cout<<"Element "<< head->elem <<" is deleted from the queue\n";
                head=head->next;
                delete delPtr;
        }
 
        const T& front() const
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                return head->elem;
        }
 
        void print() const
        {
                if (empty())
                {
                        throw std::string("Queue is empty");
                }
                for(Node* ptr=head; ptr!=0; ptr=ptr->next)
                        std::cout<<ptr->elem<<' ';
                std::cout<<'\n';
        }
 
        bool empty() const
        {
                return head==0;
        }
private:
        struct Node
        {
                Node():next(0), elem(0)
                {
                }
                Node* next;
                T elem;
        };
        Node* head;
        Node* tail;
};
 
#endif
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
 
#include "Queue.h"
 
int main()
{
        try
        {
        NodeQueue<int> Queue;
        Queue.enqueue(10);
        Queue.enqueue(20);
        Queue.enqueue(30);
        std::cout<<"Top is: "<<Queue.front()<<'\n';
        Queue.dequeue();
        Queue.print();
        }
        catch(const std::string& e)
        {
             std::cout<<e<<'\n';
        }
}
9
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
19.10.2010, 13:21 #8
Хотел бы не много добавить, так как очевидную ошибку уже исправили.


Мое мнение таково, я не кому его не навязываю, надо придерживаться
идиомы не платить за то что не используешь.

Поэтому проверки всякого рода надо делать в debug версии программы.
C++
1
2
3
4
5
6
7
#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif
2
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
19.10.2010, 13:31 #9
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Хотел бы не много добавить, так как очевидную ошибку уже исправили.


Мое мнение таково, я не кому его не навязываю, надо придерживаться
идиомы не платить за то что не используешь.

Поэтому проверки всякого рода надо делать в debug версии программы.
C++
1
2
3
4
5
6
7
#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif
Это значит - проверка не будет работать в скомпилированной версии?
0
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
19.10.2010, 14:16 #10
LineStown
Это значит что проверка будет компилироваться в DEBUG версии программы.
В RELEASE версии это участок кода компилироваться не будет.

_DEBUG - это макрос есть в Microsoft Visual Studio,
Не знаю, есть ли в других средах разработки этот макрос, но наверняка, что нибудь подобное есть.
1
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
19.10.2010, 14:32 #11
Классы привязаны к консольному выводу. Воспользоваться ними например в Win32/MFC программе будет затруднительно. Как я узнаю результат метода Find, если у меня нет консоли ?
Как мне воспользоваться очередью, что бы не мусорить в выводе ? Должен ли пользователь видеть все сообщения, связанные с внутренней работой программы ?

Что, если я пользуюсь CString. Или String в Samsung Bada ? Как мне конвертнуть из одного в другое ? А если я хочу логгировать все исключения, как запишеться \n в линуховой системе ?

Что должен делать метод erase(), изходя только из прототипа функции ?
1
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
19.10.2010, 15:26 #12
Andrew_Lvov:

Воспользоваться ними например в Win32/MFC
Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC.
Вывод на экран согласен не работает, но операции с файлами, можно делать даже в MFC и в Win32.


Классы привязаны к консольному выводу.
Мое решение данной проблемы:
print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект,
который будет делать вывод каким надо.

Добавлено через 7 минут
Andrew_Lvov
И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков.

Добавлено через 21 минуту
И автор не говорил, что все списки мега, супер.
1
Andrew_Lvov
Эксперт С++
259 / 189 / 5
Регистрация: 19.08.2010
Сообщений: 760
Записей в блоге: 1
19.10.2010, 15:31 #13
Цитата Сообщение от Genius Ignat Посмотреть сообщение
print не трудно переделать в абстрактную архитектуру, передавая в print функциональный объект,
который будет делать вывод каким надо.
И назвать его operator << ?
Цитата Сообщение от Genius Ignat Посмотреть сообщение
И вообще в заголовке темы, я не видел, что бы автор говорил, про универсальность списков.
Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Например, файловый вывод/ввод (ofstream/ifstream) может использоваться и в MFC и в Win32/MFC.
Где здесь я говорил про файловый вывод ?
1
LineStown
66 / 66 / 3
Регистрация: 04.08.2010
Сообщений: 420
Завершенные тесты: 1
19.10.2010, 15:32 #14
Тому кто только пытается понять списки - это полезно!, тому кто разбирается уже и сам допишет/дорисует что ему надо. Тема +
1
Genius Ignat
1236 / 774 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
19.10.2010, 15:40 #15
Где здесь я говорил про файловый вывод ?
Я говорил, что не все так плохо, хоть с файлами можно работать единообразно.

И назвать его operator << ?
Не понял ход этих мыслей.

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?
Тогда юзай STL, все равно со списками из STL придется плясать.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2010, 15:40
Привет! Вот еще темы с ответами:

Стеки, очереди, массивы - C++
Помогите реализовать стек с помощью двух очередей, используя массивы (операции удаления, добавления).

Бинарные деревья, очереди, стеки - C++
#include &lt;iostream&gt; // подключение библиотеки ввода-вывода #include &lt;conio.h&gt; // подключение библиотеки функций работы с консолью ...

4 задания по С++ (Бинарные деревья. Стеки,очереди) - C++
1. В текстовом файле записана без ошибок формула вида: цифра или М(формула, формула), или m(формула, формула), где M обозначает функцию...

Указатели,стеки списки. - C++
Здравствуйте помогите решить две задачи на Си++,заранее спасибо! Указатели, работа с динамическими структурами данных. Динамическое...


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

Или воспользуйтесь поиском по форуму:
15
Yandex
Объявления
19.10.2010, 15:40
Ответ Создать тему
Опции темы

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