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

Не могу понять в чем ошибка: реализация односвязного списка - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
18.08.2010, 21:12     Не могу понять в чем ошибка: реализация односвязного списка #1
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
#include <iostream>
using namespace std;
 
struct list
{
    int key;
    list *next;
};
 
void addList(list *start);
void printList(list *start);
 
int main()
{
    list *start;
    start=new list;
    cin >> start->key;
    start->next=NULL;
 
    int listSize;
    cin >> listSize;
 
    for(int i=0;i<listSize;i++)
        addList(start);
 
    printList(start);
    
    cin.get();
    cin.get();
 
    return 0;
}
 
 
void addList(list *start)
{
    list *temp;
    temp=new list;
    cin >> temp->key;
    temp->next=start;
    start=temp;
}
 
void printList(list *start)
{
    list *now=start;
 
    while(now!=NULL)
    {
        cout << now->key << " ";
        now=now->next;
    }
 
}
Пытаясь разобраться со списками, создал вот такую примитивную программку. Но почему-то она не работает и я , хоть убейте, не пойму в чем ошибка. Буду очень благодарен за любые советы и помощь.

Добавлено через 3 минуты
Программа должна выводить ключи всех элементов списка, но выводит она почему-то лишь один.
Сдается мне, что проблема в реализации функции addList.

Добавлено через 15 минут
Спасибо, проблема решилась после модификации функции addList:
C++
1
2
3
4
5
6
7
8
9
10
list *addList(list *start)
{
    list *temp;
    temp=new list;
    cin >> temp->key;
    temp->next=start;
    start=temp;
    
    return start;
}
Но возник вопрос - как сделать то же самое, используя void? Нужен указатель на указатель в параметре функции addList: void addList(list **start)? Спасибо.

Добавлено через 8 минут
Я имею в виду, чтобы не нужно было возвращать указатель на первый элемент снова.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.08.2010, 21:12     Не могу понять в чем ошибка: реализация односвязного списка
Посмотрите здесь:

не могу понять в чем ошибка. C++
C++ не могу понять в чем ошибка
Не могу понять в чем ошибка C++
C++ не могу понять в чем ошибка
C++ не могу понять в чем ошибка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
20.08.2010, 06:43     Не могу понять в чем ошибка: реализация односвязного списка #21
bobromet, а стек нужно обязательно сделать в виде структуры без методов, или можно сделать в виде (шаблонного) класса?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
20.08.2010, 23:05     Не могу понять в чем ошибка: реализация односвязного списка #22
Nameless One, как точно не указано, да я и не уверен что знаю что такое шаблонный класс.
Подозреваю что что-то типа модели в mvc... понахватался всего вподряд а конкретно ничего не знаю +))

задача выглядит следующим образом:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    Node* saveA = NULL;
    Node* saveB = NULL;
 
    insert(saveA, "1");
    insert(saveA, "2");
    insert(saveB, "3");
    insert(saveB, "4");
    insert(saveB, "5");
    insert(saveB, "6");
    insert(saveB, "7");
 
    cout << view(saveA) << endl;
    cout << view(saveB) << endl;
 
    insert(saveA, view(saveB));
    clear(saveB);
    cout << view(saveA) << endl;
    cout << view(saveB) << endl;
    clear(saveA);
нужно дополнить методами insert() - делает новый узел в heap и вешает в конце памяти (извиняюсь за тупой перевод) ,
view() и clear() сответственно
на выходе должно быть следующее:

1 2
3 4 5 6 7
1 2 3 4 5 6 7

в принципе все уже работает, только у меня порядок на выходе сверху-вниз,

2 1
7 6 5 4 3
7 6 5 4 3 2 1

так что придется все равно думать над задачкой которую подкинул siger.
Ума не приложу как без ввода новых переменных добится нужного. Блин.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
21.08.2010, 00:28     Не могу понять в чем ошибка: реализация односвязного списка #23
bobromet, Просто сделать двусвязный список. В котором есть не только поле для Stack *last, но также есть Stack *prev.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.08.2010, 05:54     Не могу понять в чем ошибка: реализация односвязного списка #24
Lavroff, это будет уже не стек
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
21.08.2010, 06:35     Не могу понять в чем ошибка: реализация односвязного списка #25
bobromet, вот Вам стек строк на С++, придумайте, как под свои нужды переделать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <stack>
#include <string>
 
int main(){
    std::stack<std::string> stk;
    std::string buf;
    
    std::cout << "Enter some strings (empty row - quit):" << std::endl;
    while ( std::getline(std::cin, buf) ){
        if ( buf.empty() )
            break;
        stk.push(buf);
    }
    std::cout << "Strings in reverse order:" << std::endl;
    while ( ! stk.empty() ){
        std::cout << stk.top() << std::endl;
        stk.pop();
    }
    
    return 0;
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.08.2010, 06:47     Не могу понять в чем ошибка: реализация односвязного списка #26
Блин... Опоздал
Вот простейшая реализация шаблонного стека (если с шаблонами не понятно, удали все записи вида template<class T> и замени везде T типом, который тебе нужен):
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
#ifndef MY_STACK_HPP
#define MY_STACK_HPP
 
#include <stdexcept>
 
namespace my
{
    template<class T>
    class stack
    {
        struct node
        {
            T       value;
            node*   next;
 
            node(const T& val)
                : value(val), next(NULL) {}
        };
        node*       top;
 
    public:
 
        stack();
        ~stack();
        void push(const T& val);
        T pop();
        bool empty() const;
    };
 
    template<class T>
    stack<T>::stack()
        : top(NULL) {}
 
    template<class T>
    stack<T>::~stack()
    {
        while(top)
        {
            node* temp = top;
            top = top->next;
            delete temp;
        }
    }
 
    template<class T>
    void stack<T>::push(const T &val)
    {
        if(top)
        {
            node* newNode = new node(val);
            newNode->next = top;
            top = newNode;
        }
        else
            top = new node(val);
    }
 
    template<class T>
    T stack<T>::pop()
    {
        if(!top)
            throw(std::runtime_error("Can't pop from the empty stack"));
        T retVal = top->value;
        node* delNode = top;
        top = top->next;
        delete delNode;
        return retVal;
    }
 
    template<class T>
    bool stack<T>::empty() const
    {
        return (top == NULL);
    }
}
 
#endif // MY_STACK_HPP
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
#include <iostream>
#include <cstdlib>
 
#include "my_stack.hpp"
 
int main()
{
    try
    {
        my::stack<int> stk;
        std::cout << "Pushing to the stack..." << std::endl;
        for(size_t i= 0; i < 10; ++i, std::cout << i << " ")
            stk.push(i + 1);
        std::cout << std::endl << "Popping from the stack..." << std::endl;
        while(!stk.empty())
            std::cout << stk.pop() << " ";
        std::cout << std::endl;
    }
    catch(std::exception& e)
    {
        std::cerr << e.what() << std::endl;
        return EXIT_FAILURE;
    }
 
    return EXIT_SUCCESS;
}
Стек всегда будет выталкивать элементы в обратном порядке их добавления - потому, что это структура Last In - First Out. Стек не должен поддерживать операции добавления и удаления кроме как с вершины стека, иначе это уже будет не стек.
Если ты хочешь вывести элементы в их порядке добавления, то это можно сделать с помощью двух стеков - выталкиваешь все элементы из первого стека во второй, потом выталкиваешь все элементы из второго, поочередно их распечатывая.
Если ты хочешь сделать то, что тебе сказал siger (кстати, по-моему, он и не говорил, что тебе нужно использовать именно стек), то лучше всего будет написать очередь и использовать ее.
ForEveR
21.08.2010, 10:03
  #27

Не по теме:

Nameless One, Ну хм. Это логично, что двусторонний список - это не стек.

lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
21.08.2010, 13:33  [ТС]     Не могу понять в чем ошибка: реализация односвязного списка #28
bobromet, потом я понял что через void делать нету смысла т.к. когда будем работать с классами это не понадобится
Я имею в виду, что функция без параметров будет.
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
21.08.2010, 21:11     Не могу понять в чем ошибка: реализация односвязного списка #29
Lavroff, я тоже хотел ввести новую переменную, но siger говорит не нужно.)
я ввел переменную в которую записывается следующий узел, потом когда нужно выдать результат откатываюсь на начало и уже тогда начинаю выдавать.
Вот как я это сделал, может какому нибуть нубу вроде меня будет интересно.
наверно это и есть двусвязный список
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
struct Node
{
    Node*next;
    Node*last;
    string daten;
};
void insert(Node*&n, string s)
{
    Node* ptr = new Node;
    ptr->last = n;
    ptr->daten = s;
    ptr->next = NULL;
 
    Node* ptr2 = ptr->last;
    if(ptr2 != NULL)
        ptr2->next = ptr;
    n = ptr;
}
 
void view(Node*n)
{
    Node*ptr = n;
    
    if(n != NULL)
        while(ptr->last != NULL)
            ptr = ptr->last;
 
        while(ptr != NULL)
    {
        cout << ptr->daten << " ";
        ptr = ptr->next;
    }   
}
easybudda, Nameless One круто, спасибо! Не знал что есть такая удобная штука как stack <type> ,
проходящим мимо нубам вот ссылка, там очень коротко и понятно про queue и stack.
http://adorning.ru/2010/01/21/urok-1...ack-and-queue/
с темплейтами еще не разобрался, но вскоре понадобится..недельки через две.
lala_777, ты сам структуру используешь, то есть можно сказать уже работаешь с классом
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
21.08.2010, 21:48     Не могу понять в чем ошибка: реализация односвязного списка #30
Цитата Сообщение от bobromet Посмотреть сообщение
Не знал что есть такая удобная штука как stack...
Да стек и самому не сложно сделать. Вот пример: http://www.cyberforum.ru/cpp/thread1...tml#post916931
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
21.08.2010, 22:28     Не могу понять в чем ошибка: реализация односвязного списка #31
easybudda, я имел ввиду что есть такая библиотечка, ну что ненадо алгоритм ручками писать .)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.08.2010, 22:33     Не могу понять в чем ошибка: реализация односвязного списка
Еще ссылки по теме:

Не могу понять в чем ошибка? C++
В чем ошибка не могу понять? C++
C++ Удаление элемента списка, не могу понять в чем ошибка

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
21.08.2010, 22:33     Не могу понять в чем ошибка: реализация односвязного списка #32
bobromet, В STL вообще много всего полезного имеется.
Yandex
Объявления
21.08.2010, 22:33     Не могу понять в чем ошибка: реализация односвязного списка
Ответ Создать тему
Опции темы

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