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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.92
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
#1

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

26.09.2009, 13:53. Просмотров 4593. Ответов 10
Метки нет (Все метки)

Всем привет.
Помогите пожалуйста !
Надо написать стек на базе массива, и на базе связного списка.
И еще очередь на базе связного списка.
Скиньте пожалуйста информацию как это сделать и реализовать!!!
Заранее спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.09.2009, 13:53
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Написать стек на базе массива, и на базе связного списка (C++):

Динамическое программирование, стек на базе списка... - C++
Доброе время суток... :) Имеется такой код (рабочий), реализация стека на базе списка: struct stack { int data; stack...

Стек на базе массива - C++
Есть код #include <iostream> #include <string> using namespace std; template <class T> class STACK ...

Стек на базе статического массива - C++
Здравствуйте помогите, верней напишите за меня пожалуйста стек на базе статического массива. требования для массива: 1)тип элементов -...

Создать базовый класс список. Реализовать на базе списка стек и очередь с виртуальными функциями вставки и вытаскивания - C++
Здравствуйте, помогите пожалуйста разобраться что как работает в программе (напишите комментарии). Задание: Создать базовый класс...

Класс стек, наследованный от связного списка - C++
Как я понял из текста, что для методов isEmpty и print класса List нужен какой-то аргумент. Объясните пожалуйста, что такое -fpermissive....

Написать функцию полного удаления списка на основе связного хранения - C++
Помогите составить такую функцию! Добавлено через 14 минут *связного

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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();
}
0
R0mm
Псевдо программист
192 / 113 / 15
Регистрация: 19.09.2009
Сообщений: 303
26.09.2009, 14:47 #3
Попробуйте использовать опцию поиска по этому сайту.
0
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
26.09.2009, 19:55  [ТС] #4
Реализацию в классе нашел уже.
Подскажите сто надо писать в ф-ии main , мне надо заполнить стек и вывести его на экран.
Подскажите пожалуйста , целый день ищу не могу найти.
0
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 выводит инфу в скобках"-" на экран. Вот только затрудняюсь ответить,что именно надо писать в этих скобках...
0
kravam
быдлокодер
1695 / 882 / 45
Регистрация: 04.06.2008
Сообщений: 5,459
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;
}
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() , как создать этот стек и вывести на печать???
0
Sekt
156 / 155 / 10
Регистрация: 29.04.2009
Сообщений: 637
27.09.2009, 22:07 #8
В
C++
1
2
main():
STACK<int>Stackobj.
0
as
36 / 22 / 3
Регистрация: 14.02.2009
Сообщений: 355
30.09.2009, 10:47  [ТС] #9
А как заполнить стек числами и вывести на печать???
0
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);
0
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]
помогите пожалуйста разобраться!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.09.2009, 18:08
Привет! Вот еще темы с ответами:

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

Реализовать очередь на базе односвязного списка - C++
собственно, весь вопрос содержится в теме. Помогите, пожалуйста, а то я совсем не понимаю как это сделать...

Реализация двусвязного списка на базе вектора - C++
Дано задание реализовать двусвязный список на базе вектора. Насколько я понял, сам вектор реализовывать полностью не нужно, как и...

Очередь на базе массива - C++
очередь на базе массива . код С


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
30.09.2009, 18:08
Ответ Создать тему
Опции темы

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