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

Односвязные списки: реализация стека - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 42, средняя оценка - 4.76
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.12.2009, 23:39     Односвязные списки: реализация стека #1
Я никак не могу реализировать полноценный стек не используя масив, у меня есть
такой код
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
#include <iostream>
 
using namespace std;
 
struct node
{
    int inf;
    struct node *next;    
};
 
struct node *head, *s;
 
void push(int val)
{
    s = malloc(10*sizeof(int));
    s->inf = val;
    s->next = head;
    head = s;
}
 
void pop(int &val)
{
    s = head->next;
    val = head->inf;
    head = s;
    free(s);
}
 
int main()
{
    char key;
    
    do
    {
        cout << "    STACK\n1 - push elements;\n2 - pop and write elements;\n3 - exit program\nPress key 1..3 ";
        key = getchar();
        cout << key << endl;
        switch (key)
        {
            case '1':
                int n, a;
                cout << "\nenter number of elements ";
                cin >> n;
                for (int i = 0; i < n; ++i)  {
                    cin >> a;
                    push(a);
                }
                break;
            case '2':
                while (head != NULL)
                {
                    int a;
                    pop(a);
                    cout << a;
                }
        }
    }
    while (key != '3');
    
    getchar();    
    return 0;
}
, но он не пашет, что и не странно, так как о ссылках у нас была лекция только по паскалю, а как это реализуруется на си/си++ не знаю..
Если кто может дать ссылку на сответсвтующие материалы и растолковать буду весьма благодарен..
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2009, 23:39     Односвязные списки: реализация стека
Посмотрите здесь:

C++ Односвязные списки, стек
односвязные списки C++
C++ Односвязные списки
C++ Односвязные линейные списки
Односвязные списки C++
Односвязные списки C++
C++ Односвязные списки С++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
11.12.2009, 10:18     Односвязные списки: реализация стека #2
рабочий код.
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
/*
Я никак не могу реализировать полноценный стек не используя масив,
у меня есть такой код , но он не пашет, что и не странно, 
так как о ссылках у нас была лекция только по паскалю, 
а как это реализуруется на си/си++ не знаю..
Если кто может дать ссылку на сответсвтующие материалы 
и растолковать буду весьма благодарен..
*/
#include<iostream>
#define UT unsigned short int
struct nodes
{
    UT data;
    nodes* prior;
};
 
class stacks
{
    public:
        stacks(){top = NULL;}
        ~stacks(){}
        void push(UT data)
        {
            nodes* tmp = new nodes;
            tmp->prior = top;
            tmp->data = data;
            top = tmp;
        }
        
        void pop(UT *p)
        {
            *p = top->data;
            nodes* tmp;
            tmp = top;
            top = top->prior;
            delete tmp;         
        }
        
        void clear()
            {
                if (top==NULL) return;
                nodes* tmp = top;
                while (true)
                {
                    if(top->prior!=NULL) 
                        {
                            tmp = top;
                            top = top->prior;
                            delete tmp; 
                        }
                    else {  delete top;  break; }
                }
            }
        
        bool empty(){return (top==NULL);} 
    private:
        nodes* top;
};
 
stacks a;
 
int main()
{
    using namespace std;
    char key;
while(true)
{
    system("cls");
    cout<<"STACK:\n 1 - push;\n 2 - pop & write;\n 3 - exit.\n";
    cin>>key;
    switch(key)
    {
        case '1':
            {
                cout<<"\n pushing:\n input element:   ";
                UT d;
                cin>>d;
                a.push(d);
                cout<<"\t OK!!\n";
                break;
            }
        case '2':
            {
                cout<<"\n poping:\n";
                UT tmp;
                if(a.empty()) cout<<"\n is empty";
                while(!a.empty()) {a.pop(&tmp);cout<<tmp<<endl;}
                cout<<"\t\t\t\t OK!!\n";
                system("pause");
                break;
            }
        case '3':{cout<<"\n exiting: "; goto end;}
        default: {cout<<"\n input 1, 2 or 3, please...\n";system("pause");}
    }
}
 
end:        
    a.clear();
    cout<<"\texit is correct."<<endl;
    system("pause");
    return 0;
}
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.12.2009, 00:21  [ТС]     Односвязные списки: реализация стека #3
Можете еще по деревьям помочь? У мене
сорс на Паскале
Pascal
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
Program bin_tree;
Uses Crt;
Type ptr = ^node;
     node = record
          inf : integer;
          left, right : ptr;
     end;
Var n, res : integer;
    root : ptr;
 
Function Tree(anode : integer) : ptr;
         var newnode : ptr;
             lnodes, rnodes, data : integer;
         begin
              if anode = 0 then
                 tree := nil
              else
                  begin
                       lnodes := anode div 2;
                       rnodes := anode - lnodes - 1;
                       write('Enter node data: ');
                       readln(data);
                       new(newnode);
                       with newnode^ do
                            begin
                                 inf := data;
                                 left := Tree(lnodes);
                                 right := Tree(rnodes);
                            end;
                       Tree := newnode;
                  end;
         end;
 
Procedure PrintTree(RootTree : ptr; L : integer);
          var i : integer;
          begin
               if RootTree <> nil then
                  with RootTree^ do
                       begin
                            PrintTree(left, L+1);
                            for i := 1 to L do write('  ');
                            writeln(inf);
                            PrintTree(right, L+1);
                       end;
          end;
 
Procedure PrefixOrder(RootTree : ptr);
         begin
              if (RootTree^.left = nil) and (RootTree^.right = nil) then
                 res := res + 1
              else
                  begin
                       if RootTree^.left <> nil then PrefixOrder(RootTree^.left);
                       if RootTree^.right <> nil then  PrefixOrder(RootTree^.right);
                  end;
         end;
 
Begin
     ClrScr;
     writeln(' -= Create and display tree =-');
     write('Enter number of tree''s nodes: ');
     readln(n);
     root := Tree(n);
     writeln('Created tree: ');
     PrintTree(root, 0);
     writeln;
     res := 0;
     PrefixOrder(root);
     writeln('Number of leafs: ',res);
     writeln('Press any key...');
     ReadKey;
End.
есть, по вашему примеру немного разобрался, но я не могу понять как реализировать равномерное распределение елементов по дереву (сначала все левые дети а потом правые определенной глубины, после чего углубление и продолжение добавления).
Да и еще, этот код выдает результат: количество лепистков дерева (бинарного).

Добавлено через 57 минут
Наброски кода
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
#include <iostream>
#include <string>
 
using namespace std;
 
struct node
{
    int inf;
    node* L, R;
};
 
class BinTree
{
public:
    BinTree(){root = NULL;}
    ~BinTree(){}
    node* push(int n)
    {
        if (n)
            return NULL;
        int l = n/2,
            r = n - l - 1,
            data;
        cin >> data;
        node* newroot = new node;
        newroot->L = push(l);
        newroot->inf = data;
        newroot->R = push(r);
        return newroot;
    }
private:
    node* root;
};
 
BinTree T;
 
int main()
{
    int n;
    cin >> n;
    T.push(n);
    return 0;
}
, вот только нерабочего.. newroot->R = push(r); - здесь что-то нето..
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
12.12.2009, 00:57     Односвязные списки: реализация стека #4
но я не могу понять как реализировать равномерное распределение елементов по дереву
Вам при построении дерева нужно использовать один из алгоритмов построения балансированых (уравновешанных) деревьев. Классическим примером такого алгоритма будут красно-чёрные деревья.
зы: по коду - (imho) рисуйте, рисуйте как можно больше.... не пишите, пока не представляете, что хотите иметь в итоге...
зызы: по статистике средняя ресурсоемкость приложения:
Планирование 40%
кодинг 20%
отладка 40%
Ваш ресурс время..
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
12.12.2009, 01:10  [ТС]     Односвязные списки: реализация стека #5
спасибо за пример со стеком, я понял как списки реализировать на си++)) (без использования масивов)
pazlle
 Аватар для pazlle
27 / 17 / 3
Регистрация: 02.11.2009
Сообщений: 176
15.12.2009, 01:21     Односвязные списки: реализация стека #6
Помогите плиз стек без массива реализовать на си ++ ) с его основными функциями!!))Оч нужно!
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
15.12.2009, 07:57  [ТС]     Односвязные списки: реализация стека #7
mstack.hpp:
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
template <typename T>
struct node
{
    T inf;
    node<T>* next;
};
 
template <typename T>
class mstack
{
private:
    node<T>* head;
public:
    mstack(){head = NULL;}
    ~mstack(){}
    
    void push(T &val)
    {
        node<T>* tmp = new node<T>;
        tmp->inf = val;
        tmp->next = head;
        head = tmp;
    }
    
    void clear()
    {
        while (head->next != NULL)
        {
            node<T>* tmp = head;
            head = head->next;
            delete tmp;
        }
        head = NULL;
    }
    
    bool empty(){return (head == NULL);}
    
    T pop()
    {
        T res = head->inf;
        node<T>* tmp = head;
        head = head->next;
        delete tmp;
        return res;
    }
};
&
mstack.cpp
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
#include <iostream>
#include <string>
#include "mstack.hpp"
 
using namespace std;
 
int main()
{
    mstack <string> s;
    int key;
    string val;
    do
    {
        system("cls");
        cout << "\tStack\t\t\t\tmade by TFTM\n\n";
        cout << "1 - push\n";
        cout << "2 - pop & write\n";
        cout << "3 - exit\n\n";
        cout << "press key: ";
        cin >> key;
        switch (key)
        {
            case 1:
                {
                    cout << "\nenter element: ";
                    cin >> val;
                    s.push(val);
                    break;    
                }
            case 2:
                {
                    if (s.empty()) cout << "stack is empty..";
                    else
                    {
                        cout << "poping:\n";
                        while (!s.empty())
                            cout << s.pop() << endl;
                    }
                    system("pause");
                    break;    
                }
            default:
                {
                    if (key == 3) cout << "exiting succesfully..\n";
                    else cout << "press only 1, 2 or 3\n";
                    system("pause");
            }                
        }
    }
    while (key != 3);
    
    return 0;
}
Demonhunterus
1 / 1 / 0
Регистрация: 20.09.2010
Сообщений: 36
21.09.2010, 11:28     Односвязные списки: реализация стека #8
outoftime Скажите,пожалуйста,на базе чего реализован данный стек?На базе массива или связного списка?
outoftime
21.09.2010, 18:32  [ТС]
  #9

Не по теме:

Demonhunterus, а самому посмотреть?

Demonhunterus
1 / 1 / 0
Регистрация: 20.09.2010
Сообщений: 36
21.09.2010, 21:44     Односвязные списки: реализация стека #10
outoftime, знал бы - не спрашивал Наполнение mstack.hpp мне пока ни о чем не говорит.Да и вопрос я задал очень легкий,ответ - одно слово:"Массива" или "Списка"...Ответь,пожалуйста.Я "Спасибку" тыкну ^_^
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7954 / 4716 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
21.09.2010, 22:02     Односвязные списки: реализация стека #11
Demonhunterus, head/node вам ни о чем не говорит? на базе списка конечно.
Demonhunterus
1 / 1 / 0
Регистрация: 20.09.2010
Сообщений: 36
21.09.2010, 22:27     Односвязные списки: реализация стека #12
На базе связного списка.Ясно ^_^
Demonhunterus
1 / 1 / 0
Регистрация: 20.09.2010
Сообщений: 36
25.09.2010, 15:24     Односвязные списки: реализация стека #13
Амммм...
C++
1
~mstack(){}
--- а что это и зачем оно надо?Без этой строки всё вроде бы тоже работает...
И
C++
1
2
3
4
5
6
7
8
9
10
  void clear()
    {
        while (head->next != NULL)
        {
            node<T>* tmp = head;
            head = head->next;
            delete tmp;
        }
        head = NULL;
    }
--- вроде бы как не используется нигде...

Добавлено через 27 минут
Вобщем,пытаюсь переписать mstack.hpp в вид типа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 template <class Item>
class STACK
{
private:
struct node
{ Item item; node* next;
node (Item x, node* t) { item=x; next=t;}
};
typedef node*link;
link head;
public:
STACK(int) {head = 0;}
int empty() const {return head == 0;}
void push(Item x) {head=new node(x,head);}
Item pop()
{ Item v=head->item; link t=head->next;
delete head; head=t; return v;}
};
,только вот у меня ничего не получается...Помогите,если кто может,пожалуйста

Добавлено через 1 час 56 минут
Вот,что получилось.
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>
#include <string>
 
using namespace std;
 
template <class T>
 
class STACK
{
private:
        struct node
{
    T inf;
    node* next;
    node (T val,node* t) {inf = val; next = t;}
};
    typedef node *link;
    link head;
    
public:
    STACK(){head = 0;}
    ~STACK(){}
    
    void push(T val)
    {
        head=new node(val,head);
    }
    
    
    bool empty(){return (head == 0);}
    
    T pop()
    {
        T res = head->inf;
        link t = head->next;
        delete head;
        head = t;
        return res;
    }
};  
 
int main()
{
    STACK <string> s;
    int key;
    string val;
    do
    {
        system("cls");
        cout << "\tStack\t\t\t\n\n";
        cout << "1 - push\n";
        cout << "2 - pop & write\n";
        cout << "3 - exit\n\n";
        cout << "press key: ";
        cin >> key;
        switch (key)
        {
            case 1:
                {
                    cout << "\nenter element: ";
                    cin >> val;
                    s.push(val);
                    break;    
                }
            case 2:
                {
                    if (s.empty()) cout << "stack is empty..";
                    else
                    {
                        cout << "poping:\n";
                            cout << s.pop() << endl;
                    }
                    system("pause");
                    break;    
                }
            default:
                {
                    if (key == 3) cout << "exiting succesfully..\n";
                    else cout << "press only 1, 2 or 3\n";
                    system("pause");
            }                
        }
    }
    while (key != 3);
    
    return 0;
}
Пожалуйста,проверьте правильность,на всякий случай...А то может,оно работает,но не так,как надо
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7954 / 4716 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
25.09.2010, 23:30     Односвязные списки: реализация стека #14
Demonhunterus,

~mstack(){} - деструктор. Читайте книжки.
clear соответственно для удаления стека поэлементно (по узлу)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.04.2011, 19:34     Односвязные списки: реализация стека
Еще ссылки по теме:

Односвязные списки C++
C++ Односвязные списки (очередь)
односвязные списки С++ C++
C++ Односвязные списки
Односвязные списки C++

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

Или воспользуйтесь поиском по форуму:
не_гений
0 / 0 / 0
Регистрация: 13.12.2010
Сообщений: 2
04.04.2011, 19:34     Односвязные списки: реализация стека #15
thanks))
Yandex
Объявления
04.04.2011, 19:34     Односвязные списки: реализация стека
Ответ Создать тему
Опции темы

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