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

@ForEveR · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

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

Однонаправленный список

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';
        }
}

@easybudda · 19.10.2010, 12:20

Lavroff, первое, что увидел:

C++
1
2
3
4
5
        ~List()
        {
                delete head;
                delete tail;
        }

А те, узлы, которые между head и tail, Страуструп удалять будет?

@LineStown · 19.10.2010, 12:21

Двунаправленный список с перегрузкой копирования(честно лень вырезать было).

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;
}

Мдя... и деструктор не написал\ Вот твк всегда\

@ForEveR · 19.10.2010, 12:43 **[ТС]**

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;
    }
}

@RUSya82 · 19.10.2010, 12:46

Двусвязный список:

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 минуты
Может у кого есть код для бинарного дерева?

@easybudda · 19.10.2010, 13:02

Сообщение от Lavroff

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

я бы так сделал

C++
1
2
3
4
5
6
7
~List(){
    while ( head ){
        tail = head->next;
        delete head;
        head = tail;
    }
}

зачем зря переменные плодить?

@ForEveR · 19.10.2010, 13:11 **[ТС]**

Исправленное.

Список

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';
        }
}

@Ignat · 19.10.2010, 13:21

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

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

Поэтому проверки всякого рода надо делать в debug версии программы.

C++
1
2
3
4
5
6
7
#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif

@LineStown · 19.10.2010, 13:31

Сообщение от Genius Ignat

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

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

Поэтому проверки всякого рода надо делать в debug версии программы.

C++
1
2
3
4
5
6
7
#ifdef _DEBUG
 if(head==0)
                {
                        throw std::string("List is empty!\n");
                }
 
#endif

Это значит - проверка не будет работать в скомпилированной версии?

@Ignat · 19.10.2010, 14:16

LineStown
Это значит что проверка будет компилироваться в DEBUG версии программы.
В RELEASE версии это участок кода компилироваться не будет.

_DEBUG - это макрос есть в Microsoft Visual Studio,
Не знаю, есть ли в других средах разработки этот макрос, но наверняка, что нибудь подобное есть.

@Andrew_Lvov · 19.10.2010, 14:32

Классы привязаны к консольному выводу. Воспользоваться ними например в Win32/MFC программе будет затруднительно. Как я узнаю результат метода Find, если у меня нет консоли ?
Как мне воспользоваться очередью, что бы не мусорить в выводе ? Должен ли пользователь видеть все сообщения, связанные с внутренней работой программы ?

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

Что должен делать метод erase(), изходя только из прототипа функции ?

@Ignat · 19.10.2010, 15:26

Andrew_Lvov:

Воспользоваться ними например в Win32/MFC

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

Классы привязаны к консольному выводу.

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

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

Добавлено через 21 минуту
И автор не говорил, что все списки мега, супер.

@Andrew_Lvov · 19.10.2010, 15:31

Сообщение от Genius Ignat

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

И назвать его operator << ?

Сообщение от Genius Ignat

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

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?

Сообщение от Genius Ignat

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

Где здесь я говорил про файловый вывод ?

@LineStown · 19.10.2010, 15:32

Тому кто только пытается понять списки - это полезно!, тому кто разбирается уже и сам допишет/дорисует что ему надо. Тема +

@Ignat · 19.10.2010, 15:40

Где здесь я говорил про файловый вывод ?

Я говорил, что не все так плохо, хоть с файлами можно работать единообразно.

И назвать его operator << ?

Не понял ход этих мыслей.

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?

Тогда юзай STL, все равно со списками из STL придется плясать.

@ForEveR · 19.10.2010, 17:34 **[ТС]**

Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят.

Andrew_Lvov, Ценю ваше мнение. Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.

@easybudda · 19.10.2010, 18:12

Сообщение от LineStown

Тема +

Так никто и не спорит. В отличие от бесконечных "памагите срочна надо" человек пытается сам что-то сделать, это только приветствуется.

Сообщение от Lavroff

Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.

Ну это понятно. По сравнению с первыми Вашими постами большой шаг вперёд. Но критика действительно разумная. Классы нужно максимально абстрагировать от всяких там cin/cout. Если нужна работа с потоками определённого типа - лучше функции-друзья определять. Про тонкости этого подхода, если не ошибаюсь, у Дейтлов подробно расписано.

@ForEveR · 19.10.2010, 20:23 **[ТС]**

easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально.

@easybudda · 20.10.2010, 09:01

Сообщение от Lavroff

Но тогда вся система исключений несколько летит. Или стринг впринципе универсален?

Да ничего никуда не летит! Функция-член класса выбрасывает исключение, а вызывающая программа его ловит и либо на консоль в cerr сообщение выдаёт, или в MessageBox с ругательными флагами вроде MB_ICONERROR... А может и не ловить, а тупо грохнуться, но это плохой стиль...

@lemegeton · 26.05.2011, 19:32

Не по теме:

[UP]

Упрощенные до минимума шаблоны контейнеров с итераторами. Для примера или для "лаб" вполне сгодятся.
Длинный

двусвязный список с итератором.

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
// базовый класс элемента связного списка
// так же содержит некоторую логику
struct node_base_ {
  node_base_ *next; // указатель на следующую запись
  node_base_ *prev; // указатель на предыдущую запись
  // при создании без параметров, поля указывают сами на себя
  node_base_() : next(this), prev(this) {}
  // при задании параметров, реализует "вставку" элемента в список
  node_base_(node_base_ *next_, node_base_ *prev_)
    : next(next_), prev(prev_) {
    prev_->next = this;
    next_->prev = this;
  }
  // при удалении элемента удаляет разрыв в списке
  virtual ~node_base_() {
    prev->next = next;
    next->prev = prev;
  }
};
 
// шаблонная структура элемента связного списка
template <class Tp_>
struct node_: public node_base_ {
  Tp_ value;  // содержимое элемента
  // конструктор, вызывает базовый
  node_() : node_base_() {}
  // конструктор с параметрами, вызывает базовый
  node_(node_base_ *next_, node_base_ *prev_, const Tp_ &value_)
    : node_base_(next_, prev_), value(value_) {}
};
 
// шаблонный класс итератора двусвязного списка
template <class ValueType,
          class Pointer = ValueType*, class Reference = ValueType&>
class iterator_base_ {
 public:
  typedef ValueType  value_type;
  typedef Pointer    pointer;
  typedef Reference  reference;
  typedef node_base_ node_base;
  typedef node_<value_type> node;
  iterator_base_() : data_(0) {}
  iterator_base_(node_base *data) : data_(data) {}
  // приведение к типу node для реализации вставки элемента 
  // (допущение для упрощения)
  operator node*() { return (node*)data_; }
  iterator_base_ &operator++() {
    data_ = data_->next;
    return *this;
  }
  iterator_base_ operator++(int) {
    iterator_base_ result(data_);
    data_ = data_->next;
    return result;
  }
  iterator_base_ &operator--() {
    data_ = data_->prev;
    return *this;
  }
  iterator_base_ operator--(int) {
    iterator_base_ result(data_);
    data_ = data_->prev;
    return result;
  }
  iterator_base_ operator-(int count) {
    iterator_base_ result(data_);
    while (count--) --result;
    return result;
  }
  iterator_base_ operator+(int count) {
    iterator_base_ result(data_);
    while (count--) ++result;
    return result;
  }
  bool operator==(const iterator_base_ &other) const {
    return data_ == other.data_;
  }
  bool operator!=(const iterator_base_ &other) const {
    return data_ != other.data_;
  }
  value_type &operator*() { return   ((node*)data_)->value; }
  value_type *operator->() { return &((node*)data_)->value; }
 private:
  node_base *data_;
};
 
template <class ValueType>
class list {
 public:
  typedef ValueType value_type;
  typedef ValueType& reference;
  typedef node_<value_type> node;
  typedef node_base_ node_base;
  typedef iterator_base_<value_type> iterator;
  list() : data_(new node_base()) {}
  ~list() {
    clear();
    delete data_;
  }
  int size() const {
    int result = 0;
    for (iterator i = begin(); i != end(); ++i)
      ++result;
    return result;
  }
  bool empty() {
    return (data_->next == data_ && data_->prev == data_);
  }
  void clear() {
    while (!empty()) delete data_->next;
  }
  reference back() { return *(end() - 1); }
  reference front() { return *begin(); }
  iterator begin() const { return data_->next; }
  iterator end() const { return data_; }
  iterator insert(iterator before, const value_type &value) {
    return new node((node_base_*)before, ((node_base_*)before)->prev, value);
  }
  iterator find_first(const value_type &what) {
    iterator result = begin();
    while (result != end() && *result != what)
      ++result;
    return result;
  }
  iterator erase(iterator what) {
    iterator result = what + 1;
    delete (node*)what;
    return result;
  }
  // erases elements in range [begin, end)
  iterator erase(iterator begin, iterator end) {
    while (begin != end)
      begin = erase(begin);
    return begin;
  }
  iterator push_back(const value_type &value) {
    return insert(end(), value);
    //return new node(data_, data_->prev, value);
  }
 private:
  node_base *data_; // элемент, находящийся "перед" списком и сразу
                    // "за" списком
};

Пример:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "ilist.h"
#include <cstdio>
 
int main_(int argc, char *argv[]) {
  list<int> lst;
  for (int i = 0; i < 10; ++i)
    lst.push_back(i);
  lst.insert(lst.end() - 2, 10);
  lst.erase(lst.end() - 3);
  lst.erase(lst.find_first(4), lst.find_first(5) + 1);
  list<int>::iterator j = lst.begin();
  while (j != lst.end())
    printf("%d\n", *(j++));
  printf("Size: %d\n", lst.size());
  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
template <class ValueType>
class vector {
 public:
  typedef ValueType  value_type;
  typedef ValueType* pointer;
  typedef ValueType& reference;
  typedef pointer iterator;
  vector() : begin_(0), end_(0), end_of_storage_(0) {}
  ~vector() { delete [] begin_; }
  void clear() { end_ = begin_; }
  bool empty() const { return begin_ == end_; }
  int size() const { return end_ - begin_; }
  void reserve(int new_size) {
    if (new_size > size()) {
      pointer new_begin = new ValueType[new_size];
      pointer new_end = new_begin;
      for (iterator i = begin(); i != end(); ++i) *new_end++ = *i;
      delete [] begin_;
      begin_ = new_begin;
      end_ = new_end;
      end_of_storage_ = begin_ + new_size;
    }
  }
  iterator begin() const { return begin_; }
  iterator end() const { return end_; }
  reference front() const { return *begin_; }
  reference back() const { return *(end_ - 1); }
  iterator erase(iterator what) {
    for (iterator i = what; i != end() - 1; ++i)
      *i = *(i + 1);
    --end_;
    return what;
  }
  reference at(int position) const { return begin_[position]; }
  iterator insert(iterator before, const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    ++end_;
    for (iterator i = end() - 1; i != before; --i)
      *i = *(i - 1);
    *before = value;
    return before;
  }
  iterator push_back(const value_type &value) {
    if (end_ == end_of_storage_) reserve(size() + 5);
    *end_++ = value;
    return end_ - 1;
  }
  reference operator[](int position) const { return begin_[position]; }
 private:
  pointer begin_;
  pointer end_;
  pointer end_of_storage_;
};

Пример:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include "ivector.h"
#include <cstdio>
int main(int argc, char *argv[]) {
  vector<int> v;
  for (int i = 0; i < 10; ++i)
    v.push_back(i);
  v.erase(v.begin() + 1);
  v.insert(v.begin() + 1, 1);
  for (vector<int>::iterator i = v.begin(); i != v.end(); ++i)
    printf("%4d", *i);
  printf("\n");
  for (int i = 0; i < v.size(); ++i)
    printf("%4d", v[i]);
  printf("\n");
  return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

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

Решение

Решение

Решение

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	19.10.2010, 14:16
	LineStown Это значит что проверка будет компилироваться в DEBUG версии программы. В RELEASE версии это участок кода компилироваться не будет. _DEBUG - это макрос есть в Microsoft Visual Studio, Не знаю, есть ли в других средах разработки этот макрос, но наверняка, что нибудь подобное есть. 1

@Andrew_Lvov 261 / 191 / 10 Регистрация: 19.08.2010 Сообщений: 760 Записей в блоге: 1
	19.10.2010, 14:32
	Классы привязаны к консольному выводу. Воспользоваться ними например в Win32/MFC программе будет затруднительно. Как я узнаю результат метода Find, если у меня нет консоли ? Как мне воспользоваться очередью, что бы не мусорить в выводе ? Должен ли пользователь видеть все сообщения, связанные с внутренней работой программы ? Что, если я пользуюсь CString. Или String в Samsung Bada ? Как мне конвертнуть из одного в другое ? А если я хочу логгировать все исключения, как запишеться \n в линуховой системе ? Что должен делать метод erase(), изходя только из прототипа функции ? 1

@LineStown 72 / 71 / 8 Регистрация: 04.08.2010 Сообщений: 434
	19.10.2010, 15:32
	Тому кто только пытается понять списки - это полезно!, тому кто разбирается уже и сам допишет/дорисует что ему надо. Тема + 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	19.10.2010, 17:34 [ТС]
	Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят. Andrew_Lvov, Ценю ваше мнение. Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	19.10.2010, 20:23 [ТС]
	easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально. 0