VPF::Поиск элемента в стеке. - Форум программистов

avlzll

Дата 20.3.2008, 23:12 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

День добрый. Есть шаблонный стек, рабочий. В нем необходимо реализовать поиск элемента по ключу и найденный элемент вывести на экран. Немного не понимаю, как это сделать, ведь работать в стеке, по сути, можно только с верхним элементом.

Вот шаблон класса:

Код


#ifndef STACK_H
#define STACK_H

#include <cassert>

template <typename Type>
class Stack 
{
    struct StackNode
    {
        Type data;
        StackNode *next;
        StackNode(const Type &data, StackNode *next);        
    } *stackTop;
    
    //friend ostream& operator<<(ostream& out, const Stack& _stack);

    public:
        Stack() { stackTop = 0; }
        void push(const Type &element);
        Type &top();
        void pop();
        bool empty() { return (stackTop == 0); }
        ~Stack();
};

template <typename Type> 
Stack<Type>::StackNode::StackNode(const Type &data, StackNode *next)
{
    this->data = data;
    this->next = next;
}

template <typename Type>
void Stack<Type>::push(const Type &element) 
{
    StackNode *newNode = new StackNode(element, stackTop);
    assert( newNode != 0 );
    stackTop = newNode;
}

template <typename Type>
Type& Stack<Type>::top()
{
    assert( stackTop != 0 );
    return stackTop->data;
}


template <typename Type>
void Stack<Type>::pop()
{
    StackNode *top = stackTop;
    assert( top != 0 );
    stackTop = stackTop->next;
    delete top;
}

template <typename Type>
Stack<Type>::~Stack() 
{
    while ( !empty() ) pop();
}

#endif

archimed7592

Дата 20.3.2008, 23:27 (ссылка)

(нет голосов)

Загрузка ...

Архимед

Профиль
Группа: Завсегдатай
Сообщений: 2531
Регистрация: 12.6.2004
Где: Moscow

Репутация: 6
Всего: 93

Цитата(avlzll @ 20.3.2008, 23:12

)

ведь работать в стеке, по сути, можно только с верхним элементом.

Возможно, преподаватель это и хочет от тебя услышать smile

.

С другой стороны, поиск в стеке не нарушает его концепции, если добавление/извлечение элементов будет в традиционной форме FILO.

По теме: работать только с верхним элементом можно только извне стека. Изнутри(с точки зрения реализации классы) ты можешь работать с ним задом наперед, хоть "на первый-второй рассчитайсь!".

--------------------

If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas.
© George Bernard Shaw

avlzll

Дата 21.3.2008, 00:19 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

Цитата(archimed7592 @ 20.3.2008, 23:27

)

Возможно, преподаватель это и хочет от тебя услышать

Если бы.

Цитата(archimed7592 @ 20.3.2008, 23:27

)

По теме: работать только с верхним элементом можно только извне стека. Изнутри(с точки зрения реализации классы) ты можешь работать с ним задом наперед, хоть "на первый-второй рассчитайсь!".

Хм-м. Верно, верно... )) Что-то я туплю...

Тогда нечто вроде этого будет, наверно...

Код


Type& Stack<Type>::find()
StackNode *key = stackTop;
while (key) {
  if(key->data == data) break;
  key = key -> next;
 }
return key;
}

bsa

Дата 21.3.2008, 00:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

avlzll, вас код форматировать не учили?

Код

Type& Stack<Type>::find(const Type& data)
{
    StackNode *key = stackTop;
    while(key) {
        if (key->data == data)
            break;
        key = key->next;
    }
    return key;
}

Согласись, так выглядит симпатичней. smile

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

avlzll

Дата 21.3.2008, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 43
Регистрация: 30.11.2007

Репутация: нет
Всего: нет

Цитата(bsa @ 21.3.2008, 00:22

)

Согласись, так выглядит симпатичней.

Безусловно :) Просто писал сразу на форум , без компилятора, поэтому так и вышло. :)

В общем, задача решена.. )

bsa

Дата 21.3.2008, 13:40 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Цитата(avlzll @ 21.3.2008, 11:47)

Безусловно smile

Просто писал сразу на форум , без компилятора, поэтому так и вышло. smile

А причем тут компилятор? smile

Я тоже писал "сразу на форум" и у меня же получилось отформатировать

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Guitar_Player

Дата 22.3.2008, 12:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 86
Регистрация: 2.1.2007
Где: г.Новосибирск

Репутация: нет
Всего: нет

bsa +1) мне тоже так нравиться. А если не отформатированный, то как то страшно выглядит, даже смотреть не хочется!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »