Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.94
Koketka
5 / 5 / 1
Регистрация: 27.11.2009
Сообщений: 232
#1

Стек на основе связанного списка C++ - C++

27.11.2009, 16:36. Просмотров 6369. Ответов 4
Метки нет (Все метки)

Привет
Мне нужно разработать функции занесения и извлечения данных стека на основе связанного списка!на основе массива уже написала, а это не пойму как сделать нужно...
Плиз помогите, кто знает...
http://www.cyberforum.ru/cpp-beginners/thread1205009.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2009, 16:36
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Стек на основе связанного списка C++ (C++):

Стек на основе односвязного списка (доработать код)
Написать класс "стек" (первый пришел, последний ушел) на основе односвязного...

Напишите класс «Стек» для целочисленных данных на основе односвязного списка
Напишите класс «Стек» для целочисленных данных на основе односвязного списка....

Определить в классе статическую компоненту - указатель на начало связанного списка объектов и функцию просмотра списка
Помогите пожалуйста доделать программу. Необходимо определить в классе...

Окончание связанного списка
Скажите, пожалуйста, как в моём случае можно поступить: выйти из цикла, если...

Проблемы с удалением связанного списка(С++)
Здравствуйте! Передо мной стоит следующая задача: необходимо создать список,...

4
Vladimir.
158 / 158 / 48
Регистрация: 24.11.2009
Сообщений: 375
27.11.2009, 17:33 #2
брр..... видимо к вечеру плохо с мозгом - никак не могу понять что именно Вам нужно.
Можно ли перефразировать ваше задание следующим образом:
Реализовать стек на основе связанных (двунаправленных) списков ? Или вам нужно что-то другое?
0
Koketka
5 / 5 / 1
Регистрация: 27.11.2009
Сообщений: 232
27.11.2009, 18:48  [ТС] #3
вообще в задании написано просто связанный список, но думаю что там имеется ввиду двунапраленный...

Добавлено через 27 минут
Вот так я написала на основе массива:

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<stdio.h>
#include<iostream.h>
#include<fstream.h>
 
struct Stack {
  int left, right;
  Stack *p;
};
 
Stack *top = 0;            
Stack *push(Stack *top, const int l, const int r);
Stack *pop(Stack *top, int &l, int &r);
 
int main() {
 ...
}
 
/*стек на основе массива занесение*/
Stack *push(Stack *top, const int l, const int r) {
  Stack *pv = new Stack;
  pv->left = l;
  pv->right = r;
  pv->p = top;
}
 
/*стек на основе массива выборка*/
Stack *pop(Stack *top, int &l, int &r) {
  Stack *pv = top->p;
  l = top->left;
  r = top->right;
  delete top;
  return pv;
}
Добавлено через 36 минут
Вот что нашла в нете по своему вопросу:

Вы можете управлять двумя стеками в одном массиве, размещая один в начале
массива, а другой - в конце. Сохраните отдельные счетчики вершин для каждого
стека, и сделайте так, чтобы стеки росли друг к другу. Этот
метод позволяет двум стекам увеличиваться, занимая один и тот же массив памя-
ти до тех пор, пока они не столкнутся друг с другом в тот момент, когда массив
полностью заполнится.
К сожалению, менять размер подобных стеков непросто. Вы должны выделить
массив под новый стек и скопировать все элементы старого массива в новый. Из-
менение размера больших стеков может занимать очень много времени. Данный
способ совсем не подходит для управления несколькими стеками.
Связанные списки предоставляют более гибкий метод формирования несколь-
ких стеков. Чтобы протолкнуть элемент в стек, надо вставить его в начало связан-
ного списка. Чтобы вытолкнуть элемент из стека, следует удалить первый элемент
связанного списка. Поскольку все элементы добавляются и удаляются только в на-
чале списка, для реализации стеков такого типа не нужны метки или двусвязные
списки. Стеки, строящиеся на связанных списках, не требуют сложных схем пере-
распределения памяти, применяющихся в стеках на основе массивов.
0
Vladimir.
158 / 158 / 48
Регистрация: 24.11.2009
Сообщений: 375
27.11.2009, 21:36 #4
Цитата Сообщение от Koketka Посмотреть сообщение
вообще в задании написано просто связанный список, но думаю что там имеется ввиду двунапраленный...
Нет, это я ошибся - односвязный список вполне подходит;

Я хочу извиниться за лень - комментарии не выписывал сильно, думаю, что проблем с прочтением кода у Вас не будет.

Общий принцип: вот был у нас пустой стек, потом положили в него элемент. Элемент, помимо полезной информации хранит вспомогательную. Так же есть указатель на активный (верхний) в данный момент элемент. Пусть их положили в порядке 1, 2, 3. Тогда активным будет третий элемент, следующим (next) за ним будет второй, следующим для второго будет первый, для первого следующим будет NULL; Опять же, по причине лени проверку на пустоту стека и сборку мусора вынес в отдельную функцию. По хорошему, нужно добавить счётчик элементов, дабы стек не разползся на всю доступную память. Ну и вообще прекрасно было бы "завернуть в обёртку".... Если возникнут вопросы - ю уелкам...

спойлер
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
struct lls
{
    some_type data;
    lls* next;
};
 
lls* active_plate = NULL;   
 
void push(lls* tmp)
{
    lls* plate new lls;
    plate->data = tmp->data;
    plate->next = active_plate;
    
    active_plate = plate;
}
 
lls* pop()
{
    lls* tmp;
    tmp = active_plate;
    active_plate = active_plate->next;
    
    return tmp;
}
 
bool is_empty()
{
    return (active_plate==NULL)?true:false;
}
 
void clean(lls* tmp)
{
    delete tmp; 
}
1
Koketka
5 / 5 / 1
Регистрация: 27.11.2009
Сообщений: 232
27.11.2009, 21:51  [ТС] #5
Спасибо огромнейшее
щас буду разбираться...
0
27.11.2009, 21:51
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.11.2009, 21:51
Привет! Вот еще темы с решениями:

Создание индекса связанного списка
Доброго времени суток! Требуется создать класс (IndexedList) индекс для...

Удаление элемента из связанного списка
Нужно удалить все элементы списка кратные 3. void Del() { if (head == NULL)...

Реализация связанного списка - нужны пояснения
#include &lt;iostream&gt; using namespace std; class cool { public: ...


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

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

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