Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/12: Рейтинг темы: голосов - 12, средняя оценка - 5.00
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
1

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

18.08.2010, 21:12. Просмотров 2216. Ответов 31
Метки нет (Все метки)

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 минут
Я имею в виду, чтобы не нужно было возвращать указатель на первый элемент снова.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.08.2010, 21:12
Ответы с готовыми решениями:

Удаление элемента списка, не могу понять в чем ошибка
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;locale.h&gt; #include...

не могу понять в чем ошибка
Задание: Найти наибольший элемент каждой пары из массива А и записать их в...

Не могу понять в чем ошибка?
Выдает ошибки а в чем проблемма не пойму (программирую недавно) ...

не могу понять в чем ошибка.
Здравствуйте. Извините если подобные темы уже есть или это типичный вопрос но я...

Не могу понять в чем ошибка
Дано задание: &quot;Имеется текстовый файл. Игнорируя исходное деление этого файла...

31
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
20.08.2010, 06:43 21
bobromet, а стек нужно обязательно сделать в виде структуры без методов, или можно сделать в виде (шаблонного) класса?
0
bobromet
24 / 24 / 3
Регистрация: 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.
Ума не приложу как без ввода новых переменных добится нужного. Блин.
0
ForEveR
В астрале
Эксперт С++
7996 / 4755 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
21.08.2010, 00:28 23
bobromet, Просто сделать двусвязный список. В котором есть не только поле для Stack *last, но также есть Stack *prev.
0
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
21.08.2010, 05:54 24
Lavroff, это будет уже не стек
0
easybudda
Модератор
Эксперт CЭксперт С++
10107 / 6016 / 1507
Регистрация: 25.07.2009
Сообщений: 11,404
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;
}
1
Nameless One
Эксперт С++
5786 / 3435 / 351
Регистрация: 08.02.2010
Сообщений: 7,448
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 (кстати, по-моему, он и не говорил, что тебе нужно использовать именно стек), то лучше всего будет написать очередь и использовать ее.
1
ForEveR
21.08.2010, 10:03
  #27

Не по теме:

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

0
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
21.08.2010, 13:33  [ТС] 28
bobromet, потом я понял что через void делать нету смысла т.к. когда будем работать с классами это не понадобится
Я имею в виду, что функция без параметров будет.
0
bobromet
24 / 24 / 3
Регистрация: 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, ты сам структуру используешь, то есть можно сказать уже работаешь с классом
0
easybudda
Модератор
Эксперт CЭксперт С++
10107 / 6016 / 1507
Регистрация: 25.07.2009
Сообщений: 11,404
21.08.2010, 21:48 30
Цитата Сообщение от bobromet Посмотреть сообщение
Не знал что есть такая удобная штука как stack...
Да стек и самому не сложно сделать. Вот пример: http://www.cyberforum.ru/cpp/thread160544.html#post916931
0
bobromet
24 / 24 / 3
Регистрация: 06.03.2010
Сообщений: 59
21.08.2010, 22:28 31
easybudda, я имел ввиду что есть такая библиотечка, ну что ненадо алгоритм ручками писать .)
0
ForEveR
В астрале
Эксперт С++
7996 / 4755 / 651
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
21.08.2010, 22:33 32
bobromet, В STL вообще много всего полезного имеется.
0
21.08.2010, 22:33
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.08.2010, 22:33

Не могу понять в чем ошибка
Мне нужно сделать менюшку, в которую я записываю данный в бинарный файл, но...

Не могу понять в чем ошибка?
#include &lt;stdlib.h&gt; #include &lt;iostream.h&gt; #include &lt;conio.h&gt; #include...

Не могу понять в чем ошибка?!
Задание: -Визначити кількість вузлів дерева, в яких є два нащадки. -функция...


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

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

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