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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.94
Koketka
5 / 5 / 0
Регистрация: 27.11.2009
Сообщений: 232
#1

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

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

Привет
Мне нужно разработать функции занесения и извлечения данных стека на основе связанного списка!на основе массива уже написала, а это не пойму как сделать нужно...
Плиз помогите, кто знает...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.11.2009, 16:36     Стек на основе связанного списка C++
Посмотрите здесь:
Реализация очереди на основе связанного списка C++
C++ Стек на основе односвязного списка (доработать код)
Напишите класс «Стек» для целочисленных данных на основе односвязного списка C++
Окончание связанного списка C++
Удаление элемента из связанного списка C++
C++ Проблемы с удалением связанного списка(С++)
Реализация связанного списка - нужны пояснения C++
Перегрузка оператора индексации для связанного списка C++
Пример использование стека на основе массива и на основе двунаправленного списка C++
C++ Как наиболее быстро определить зацикливание связанного списка? (a => b => c => d => e => a)
C++ Как сделать ввод данных в файл с использованием связанного списка
C++ Стек на основе массива

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
27.11.2009, 17:33     Стек на основе связанного списка C++ #2
брр..... видимо к вечеру плохо с мозгом - никак не могу понять что именно Вам нужно.
Можно ли перефразировать ваше задание следующим образом:
Реализовать стек на основе связанных (двунаправленных) списков ? Или вам нужно что-то другое?
Koketka
5 / 5 / 0
Регистрация: 27.11.2009
Сообщений: 232
27.11.2009, 18:48  [ТС]     Стек на основе связанного списка C++ #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 минут
Вот что нашла в нете по своему вопросу:

Вы можете управлять двумя стеками в одном массиве, размещая один в начале
массива, а другой - в конце. Сохраните отдельные счетчики вершин для каждого
стека, и сделайте так, чтобы стеки росли друг к другу. Этот
метод позволяет двум стекам увеличиваться, занимая один и тот же массив памя-
ти до тех пор, пока они не столкнутся друг с другом в тот момент, когда массив
полностью заполнится.
К сожалению, менять размер подобных стеков непросто. Вы должны выделить
массив под новый стек и скопировать все элементы старого массива в новый. Из-
менение размера больших стеков может занимать очень много времени. Данный
способ совсем не подходит для управления несколькими стеками.
Связанные списки предоставляют более гибкий метод формирования несколь-
ких стеков. Чтобы протолкнуть элемент в стек, надо вставить его в начало связан-
ного списка. Чтобы вытолкнуть элемент из стека, следует удалить первый элемент
связанного списка. Поскольку все элементы добавляются и удаляются только в на-
чале списка, для реализации стеков такого типа не нужны метки или двусвязные
списки. Стеки, строящиеся на связанных списках, не требуют сложных схем пере-
распределения памяти, применяющихся в стеках на основе массивов.
Vladimir.
155 / 155 / 10
Регистрация: 24.11.2009
Сообщений: 375
27.11.2009, 21:36     Стек на основе связанного списка C++ #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; 
}
Koketka
5 / 5 / 0
Регистрация: 27.11.2009
Сообщений: 232
27.11.2009, 21:51  [ТС]     Стек на основе связанного списка C++ #5
Спасибо огромнейшее
щас буду разбираться...
Yandex
Объявления
27.11.2009, 21:51     Стек на основе связанного списка C++
Ответ Создать тему
Опции темы

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