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

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

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

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

19.10.2010, 12:11. Просмотров 40031. Ответов 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';
        }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
19.10.2010, 12:20     Списки, стеки, очереди #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Lavroff, первое, что увидел:
C++
1
2
3
4
5
        ~List()
        {
                delete head;
                delete tail;
        }
А те, узлы, которые между head и tail, Страуструп удалять будет?
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;
}
Мдя... и деструктор не написал\ Вот твк всегда\
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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;
    }
}
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 минуты
Может у кого есть код для бинарного дерева?
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
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;
    }
}
зачем зря переменные плодить?
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 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';
        }
}
Genius Ignat
1234 / 772 / 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
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
Это значит - проверка не будет работать в скомпилированной версии?
Genius Ignat
1234 / 772 / 44
Регистрация: 16.09.2009
Сообщений: 2,014
19.10.2010, 14:16     Списки, стеки, очереди #10
LineStown
Это значит что проверка будет компилироваться в DEBUG версии программы.
В RELEASE версии это участок кода компилироваться не будет.

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

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

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

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

Какой смысл писать список, к-рый можно использовать в ограниченном числе случаев ?
Тогда юзай STL, все равно со списками из STL придется плясать.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
19.10.2010, 17:34  [ТС]     Списки, стеки, очереди #16
Естественно списки только тестовые. Собственно, про вывод я и не задумывался когда писал. Была задача изучить и понять. Скинул сюда - вдруг кому поможет. Обычно на форуме часто спрашивают как написать список/стек/очередь для пользовательского типа допустим. Эти шаблонные классы вполне для этого подходят.


Andrew_Lvov, Ценю ваше мнение. Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
19.10.2010, 18:12     Списки, стеки, очереди #17
Цитата Сообщение от LineStown Посмотреть сообщение
Тема +
Так никто и не спорит. В отличие от бесконечных "памагите срочна надо" человек пытается сам что-то сделать, это только приветствуется.

Цитата Сообщение от Lavroff Посмотреть сообщение
Но про универсальность я действительно ничего не говорил. Это же не попытка сделать по типу СТЛ. Только для того, чтобы понять и помочь, тем кому это нужно.
Ну это понятно. По сравнению с первыми Вашими постами большой шаг вперёд. Но критика действительно разумная. Классы нужно максимально абстрагировать от всяких там cin/cout. Если нужна работа с потоками определённого типа - лучше функции-друзья определять. Про тонкости этого подхода, если не ошибаюсь, у Дейтлов подробно расписано.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
19.10.2010, 20:23  [ТС]     Списки, стеки, очереди #18
easybudda, Спасибо. Да. Про ввод-вывод действительно несколько косяк. Но тогда вся система исключений несколько летит. Или стринг впринципе универсален? Про син/каут конечно согласен. Попробую сделать как-нибудь универсально.
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
20.10.2010, 09:01     Списки, стеки, очереди #19
Цитата Сообщение от Lavroff Посмотреть сообщение
Но тогда вся система исключений несколько летит. Или стринг впринципе универсален?
Да ничего никуда не летит! Функция-член класса выбрасывает исключение, а вызывающая программа его ловит и либо на консоль в cerr сообщение выдаёт, или в MessageBox с ругательными флагами вроде MB_ICONERROR... А может и не ловить, а тупо грохнуться, но это плохой стиль...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.05.2011, 19:32     Списки, стеки, очереди
Еще ссылки по теме:

Очереди и стеки C++
Задача на тему Стеки, очереди, деки, списки, кольца C++
C++ Задания на стеки/очереди (без шаблонных классов stack, queue)
Стеки и очереди C++

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

Или воспользуйтесь поиском по форуму:
lemegeton
2915 / 1344 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
26.05.2011, 19:32     Списки, стеки, очереди #20
Сообщение было отмечено автором темы, экспертом или модератором как ответ

Не по теме:

[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;
}
Yandex
Объявления
26.05.2011, 19:32     Списки, стеки, очереди
Ответ Создать тему
Опции темы

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