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

@outoftime · Регистрация: 25.07.2009

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

Я никак не могу реализировать полноценный стек не используя масив, у меня есть

такой код

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

, но он не пашет, что и не странно, так как о ссылках у нас была лекция только по паскалю, а как это реализуруется на си/си++ не знаю..
Если кто может дать ссылку на сответсвтующие материалы и растолковать буду весьма благодарен..

@Vladimir. · 11.12.2009, 10:18

рабочий код.

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 · 12.12.2009, 00:21 **[ТС]**

Можете еще по деревьям помочь? У мене

сорс на Паскале

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. · 12.12.2009, 00:57

но я не могу понять как реализировать равномерное распределение елементов по дереву

Вам при построении дерева нужно использовать один из алгоритмов построения балансированых (уравновешанных) деревьев. Классическим примером такого алгоритма будут красно-чёрные деревья.
зы: по коду - (imho) рисуйте, рисуйте как можно больше.... не пишите, пока не представляете, что хотите иметь в итоге...
зызы: по статистике средняя ресурсоемкость приложения:
Планирование 40%
кодинг 20%
отладка 40%
Ваш ресурс время..

@outoftime · 12.12.2009, 01:10 **[ТС]**

спасибо за пример со стеком, я понял как списки реализировать на си++)) (без использования масивов)

@pazlle · 15.12.2009, 01:21

Помогите плиз стек без массива реализовать на си ++ ) с его основными функциями!!))Оч нужно!

@outoftime · 15.12.2009, 07:57 **[ТС]**

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 · 21.09.2010, 11:28

outoftime Скажите,пожалуйста,на базе чего реализован данный стек?На базе массива или связного списка?

@outoftime · 21.09.2010, 18:32 **[ТС]**

Не по теме:

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

@Demonhunterus · 21.09.2010, 21:44

outoftime, знал бы - не спрашивал

Наполнение mstack.hpp мне пока ни о чем не говорит.Да и вопрос я задал очень легкий,ответ - одно слово:"Массива" или "Списка"...Ответь,пожалуйста.Я "Спасибку" тыкну ^_^

@ForEveR · 21.09.2010, 22:02

Demonhunterus, head/node вам ни о чем не говорит? на базе списка конечно.

@Demonhunterus · 21.09.2010, 22:27

На базе связного списка.Ясно ^_^

@Demonhunterus · 25.09.2010, 15:24

Амммм...

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 · 25.09.2010, 23:30

Demonhunterus,

~mstack(){} - деструктор. Читайте книжки.
clear соответственно для удаления стека поэлементно (по узлу)

@не_гений · 04.04.2011, 19:34

thanks))

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,360 Записей в блоге: 5
	12.12.2009, 01:10 [ТС]
	спасибо за пример со стеком, я понял как списки реализировать на си++)) (без использования масивов) 0

@pazlle 27 / 17 / 8 Регистрация: 02.11.2009 Сообщений: 176
	15.12.2009, 01:21
	Помогите плиз стек без массива реализовать на си ++ ) с его основными функциями!!))Оч нужно! 0

@Demonhunterus 1 / 1 / 0 Регистрация: 20.09.2010 Сообщений: 36
	21.09.2010, 11:28
	outoftime Скажите,пожалуйста,на базе чего реализован данный стек?На базе массива или связного списка? 0

@outoftime
	21.09.2010, 18:32 [ТС]
	Не по теме: Demonhunterus, а самому посмотреть? 0

@Demonhunterus 1 / 1 / 0 Регистрация: 20.09.2010 Сообщений: 36
	21.09.2010, 21:44
	outoftime, знал бы - не спрашивал Наполнение mstack.hpp мне пока ни о чем не говорит.Да и вопрос я задал очень легкий,ответ - одно слово:"Массива" или "Списка"...Ответь,пожалуйста.Я "Спасибку" тыкну ^_^ 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	21.09.2010, 22:02
	Demonhunterus, head/node вам ни о чем не говорит? на базе списка конечно. 1

@Demonhunterus 1 / 1 / 0 Регистрация: 20.09.2010 Сообщений: 36
	21.09.2010, 22:27
	На базе связного списка.Ясно ^_^ 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	25.09.2010, 23:30
	Demonhunterus, ~mstack(){} - деструктор. Читайте книжки. clear соответственно для удаления стека поэлементно (по узлу) 0

@не_гений 0 / 0 / 0 Регистрация: 13.12.2010 Сообщений: 2
	04.04.2011, 19:34
	thanks)) 0