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

Написать стек на базе массива, и на базе связного списка - C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.92
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
26.09.2009, 13:53     Написать стек на базе массива, и на базе связного списка #1
Всем привет.
Помогите пожалуйста !
Надо написать стек на базе массива, и на базе связного списка.
И еще очередь на базе связного списка.
Скиньте пожалуйста информацию как это сделать и реализовать!!!
Заранее спасибо.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Sekt
 Аватар для Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
26.09.2009, 14:44     Написать стек на базе массива, и на базе связного списка #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
# include<iostream.h>
# include<process.h>
# include<conio.h>
# define SIZE 20
 
class stack
{
int a[SIZE];
int tos; // Top of Stack
public:
    stack();
    void push(int);
    int pop();
    int isempty();
    int isfull();
};
stack::stack()
{
tos=0; //Initialize Top of Stack
}
 
int stack::isempty()
{
return (tos==0?1:0);
}
int stack::isfull()
{
return (tos==SIZE?1:0);
}
 
void stack::push(int i)
{
if(!isfull())
{
a[tos]=i;
tos++;
}
else
{
 cerr<<"Stack overflow error !
Possible Data Loss !";
}
}
int stack::pop()
{
if(!isempty())
{
return(a[--tos]);
}
else
{
cerr<<"Stack is empty! What to pop...!";
}
return 0;
}
 
void main()
{
stack s;
int ch=1,num;
while(ch!=0)
{
    cout<<"Stack Operations Mani Menu
1.Push
2.Pop
3.IsEmpty
4.IsFull
0.Exit
 
";
    cin>>ch;
    switch(ch)
    {
    case 0:
        exit(1); //Normal Termination of Program
    case 1:
        cout<<"Enter the number to push";
        cin>>num;
        s.push(num);
        break;
    case 2:
        cout<<"Number popped from the stack is: "<<s.pop()<<endl;
        break;
    case 3:
        (s.isempty())?(cout<<"Stack is empty.
"):(cout<<"Stack is not empty.
");
        break;
    case 4:
        (s.isfull())?(cout<<"Stack is full.
"):(cout<<"Stack is not full.
");
        break;
    default:
        cout<<"Illegal Option.
Please try again
";
    }
}//end of while
getch();
}
R0mm
Псевдо программист
 Аватар для R0mm
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
26.09.2009, 14:47     Написать стек на базе массива, и на базе связного списка #3
Попробуйте использовать опцию поиска по этому сайту.
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
26.09.2009, 19:55  [ТС]     Написать стек на базе массива, и на базе связного списка #4
Реализацию в классе нашел уже.
Подскажите сто надо писать в ф-ии main , мне надо заполнить стек и вывести его на экран.
Подскажите пожалуйста , целый день ищу не могу найти.
MotherBoard
Путешественница
 Аватар для MotherBoard
1250 / 478 / 11
Регистрация: 22.02.2009
Сообщений: 2,843
26.09.2009, 22:08     Написать стек на базе массива, и на базе связного списка #5
После подключения библиотек(что в самом верху)
C++
1
2
3
4
5
6
using namespace std;
int main()
{
cout<<"---------------------------";
return 0;
}
Насколько я знаю,именно функция cout выводит инфу в скобках"-" на экран. Вот только затрудняюсь ответить,что именно надо писать в этих скобках...
kravam
быдлокодер
 Аватар для kravam
1513 / 873 / 44
Регистрация: 04.06.2008
Сообщений: 5,302
26.09.2009, 23:04     Написать стек на базе массива, и на базе связного списка #6
Друзья!
Вот эта штука реализует задачу с помощью связного списка.
За основу взял код Sekt.
Из него я убрал две функции:
int isempty();
int isfull();

И добавил одну vozvr
Остальные комментарии в тексте.
Для лёгкости тестирования SIZE== 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
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
# include<iostream>
# include<conio.h>
# define SIZE 3
using namespace std;
 
//Каждый элемент массива суть структура, состоящая из двух полей.
//Первое поле- САМО значение элемента массива
//Второе- указатель на следующую структуру
struct element {
 int el;
 element* pel;  
}; 
 
//Все функции будут работать с адресами элементов element. Это глобальная переменная,
//она содержит адрес структуры
element* adres_nulevogo_elementa;
 
 
class stack {
 
 private:
 element a [SIZE];
 //Индексы как в прошлом примере не нужны, будем обходиться  переменной pel
 
 public:
        stack();
        void push(int);
        int pop();
 
        //Эта функция возвращает значение a. И всё!.Она нужна будет тогда только, когда будем 
        //инициализировать статическую переменую adres_nulevogo_elementa и когда будем проверять
        //не пустой ли стек.
        element* vozvr () {return a;}
 
};
 
//+++++++++++++++++++++++++++++++++++++++++++++++Конструктор+++++++++++++++++++++++++++++++++++++++++
 
//Это конструктор
//При объявлении объекта типа stack все поля el переменных типа element устанавливаются в ноль
//А все поля pel переменных типа element содержат адреса СЛЕДУЮЩЕЙ ПЕРЕМЕННОЙ типа element
//На то он и связный список
//Делаем всё это дело в цикле
stack::stack(){
 
 int i= 0;
 
 for (; i< SIZE- 1; i++) {
  a[i].el= 0;
  a[i].pel= &a [i+1];
 }
 
 //Последний элемент заполняем отдельно, ибо второе его поле должно одержать нулевой указатель
 a [i].el= 0;
 a [i].pel= 0;
 
}
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 
 
 
 
 
 
 
 
void stack::push(int i){
 
 //Здесь решено отказаться от использования функции isfull. Просто смотрим, куда
 //указывает переменная adres_nulevogo_elementa 
 
 if(adres_nulevogo_elementa) {
  adres_nulevogo_elementa->el= i;
 
  //Поле adres_nulevogo_elementa-> не запоняем, ибо оно уже заполнено конструктором.
  //А вот значение переменной adres_nulevogo_elementa изменяем
  adres_nulevogo_elementa= adres_nulevogo_elementa->pel;
 }
 else {
  cout<<"Stack overflow error !  Possible Data Loss !";
 }
}
 
 
 
 
 
 
int stack::pop(){
 
 //Здесь тоже решено отказаться от исполльзования функции isempty
 //Вместо этого смотрим, не на s [0] ли указывает adres_nulevogo_elementa
 if (adres_nulevogo_elementa!= a) {
 
  //Допустим, что стек не пуст. А это значит, что он либо полон, либо нет. Если стек полон, тогда
  //вот что делаем
  if (adres_nulevogo_elementa== 0) {
   adres_nulevogo_elementa= &a[SIZE-1] ;
  }
 
  //Ну, а если не полон то вот что. А если полон, то простая деинкременация не пойдёт, т. к. 
  //adres_nulevogo_elementa будет содержать 0, потому такие заморочки (см. инструкцию выше)
  else {
   adres_nulevogo_elementa--;
  }
  getchar ();
  return adres_nulevogo_elementa->el;
 }
 
 else {
  cerr<<"Stack is empty! What to pop...!";
 }
 return 0;
}
 
 
 
int main(){
stack s;
 
//Вот перво-наперво проинициализируем эту переменную
adres_nulevogo_elementa= s.vozvr(); 
 
int ch=1,num;
while(ch!=0) {
 
        cout<<"Stack Operations Mani Menu\n1.Push\n2.Pop\n3.IsEmpty\n4.IsFull\n0.Exit\n";
        cin>>ch;
 
        switch(ch) {
 
        case 0:
                exit(1); //Normal Termination of Program
        case 1:
                cout<<"Enter the number to push"<<endl;
                cin>>num;
                s.push(num);
                break;
        case 2:
                cout<<"Number popped from the stack is: "<<s.pop()<<endl;
                break;
        case 3:
                (adres_nulevogo_elementa== s.vozvr())?(cout<<"Stack is empty."):(cout<<"Stack is not empty.");
                break;
        case 4:
                (!adres_nulevogo_elementa->pel)?(cout<<"Stack is full."):(cout<<"Stack is not full.");
                break;
        default:
                cout<<"Illegal Option.Please try again";
        }
}//end of while
getch();
 return 0;
}
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
27.09.2009, 21:47  [ТС]     Написать стек на базе массива, и на базе связного списка #7
Описание класса есть:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<class Item> class STACK
{
private:
Item *s; int N;
public:
STACK(int maxN)
{s=new Item[maxN]; N=0;}
int empty() const
{return==0;}
void push(Item item)
{s[N++]=item;}
Item pop()
{return s[--N];}
};
А что писать в main() , как создать этот стек и вывести на печать???
Sekt
 Аватар для Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
27.09.2009, 22:07     Написать стек на базе массива, и на базе связного списка #8
В
C++
1
2
main():
STACK<int>Stackobj.
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
30.09.2009, 10:47  [ТС]     Написать стек на базе массива, и на базе связного списка #9
А как заполнить стек числами и вывести на печать???
R0mm
Псевдо программист
 Аватар для R0mm
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
30.09.2009, 13:29     Написать стек на базе массива, и на базе связного списка #10
C++
1
2
3
main():
STACK<int>Stackobj.
Stackobj.push(5);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.09.2009, 18:08     Написать стек на базе массива, и на базе связного списка
Еще ссылки по теме:

Создать базовый класс список. Реализовать на базе списка стек и очередь с виртуальными функциями вставки и вытаскивания C++
Написать функцию полного удаления списка на основе связного хранения C++
C++ Класс стек, наследованный от связного списка
Реализация двусвязного списка на базе вектора C++
Реализовать пользовательские классы - дек, стек (LIFO), очередь (FIFO) на базе класса list библиотеки STL C++

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

Или воспользуйтесь поиском по форуму:
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
30.09.2009, 18:08  [ТС]     Написать стек на базе массива, и на базе связного списка #11
Это получается, я загнал цифру 5?
А потом указатель становится +1 , и также следующие числа?
А как вывести на печать???

Добавлено через 1 час 22 минуты
Записал код:
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
#include <iostream>
#include <stdlib.h>
using namespace std;
 
template <class Item>class STACK
{
    private:
    Item *s; int N;
    public:
    STACK(int maxN)
    {s=new Item[maxN]; N=0;}
    int empty() const
    {return N==0;}
    void push(Item item)
    {s[N++]=item;}
    Item pop()
    {return s[--N];}
};
 
int main ()
{
    STACK<int>Mystack;
    Mystack.push(5);
    return 0;
}
выдает сообщение:
\its0701-2\main.cpp||In function `int main()':
\its0701-2\main.cpp|22|error: no matching function for call to `STACK<int>::STACK()'
\its0701-2\main.cpp|6|note: candidates are: STACK<int>::STACK(const STACK<int>&)
\its0701-2\main.cpp|11|note: STACK<Item>::STACK(int) [with Item = int]
помогите пожалуйста разобраться!
Yandex
Объявления
30.09.2009, 18:08     Написать стек на базе массива, и на базе связного списка
Ответ Создать тему
Опции темы

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