Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.69/16: Рейтинг темы: голосов - 16, средняя оценка - 4.69
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
1

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

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

Author24 — интернет-сервис помощи студентам
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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.08.2010, 21:12
Ответы с готовыми решениями:

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

Не могу понять в чем ошибка
Прога простейшая Создает фигуры и совершает действия с ними. Решил добавить метод по подсчету...

Не могу понять в чём ошибка
Вот исходничек: &lt;?php if (isset($_GET)&amp;&amp;isset($_GET)&amp;&amp;isset($_GET)): { $Host = ($_GET); ...

Не могу понять в чем ошибка!
n:=StringGrid1.RowCount; m:=StringGrid1.ColCount; for i:=1 to n do begin for j:=1 to m do...

31
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
20.08.2010, 06:43 21
Author24 — интернет-сервис помощи студентам
bobromet, а стек нужно обязательно сделать в виде структуры без методов, или можно сделать в виде (шаблонного) класса?
0
25 / 25 / 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
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
21.08.2010, 00:28 23
bobromet, Просто сделать двусвязный список. В котором есть не только поле для Stack *last, но также есть Stack *prev.
0
Эксперт С++
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
21.08.2010, 05:54 24
Lavroff, это будет уже не стек
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
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
Эксперт С++
5828 / 3479 / 358
Регистрация: 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
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
21.08.2010, 13:33  [ТС] 28
bobromet, потом я понял что через void делать нету смысла т.к. когда будем работать с классами это не понадобится
Я имею в виду, что функция без параметров будет.
0
25 / 25 / 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/... and-queue/
с темплейтами еще не разобрался, но вскоре понадобится..недельки через две.
lala_777, ты сам структуру используешь, то есть можно сказать уже работаешь с классом
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
12458 / 7482 / 1753
Регистрация: 25.07.2009
Сообщений: 13,762
21.08.2010, 21:48 30
Цитата Сообщение от bobromet Посмотреть сообщение
Не знал что есть такая удобная штука как stack...
Да стек и самому не сложно сделать. Вот пример: https://www.cyberforum.ru/cpp/... post916931
0
25 / 25 / 3
Регистрация: 06.03.2010
Сообщений: 59
21.08.2010, 22:28 31
easybudda, я имел ввиду что есть такая библиотечка, ну что ненадо алгоритм ручками писать .)
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
21.08.2010, 22:33 32
bobromet, В STL вообще много всего полезного имеется.
0
21.08.2010, 22:33
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.08.2010, 22:33
Помогаю со студенческими работами здесь

Не могу понять в чем ошибка
Проблема в следующем, при вводе необходимых данных появляется ошибка, а именно, при переводе на $,...

Не могу понять, в чем ошибка
import cgi import smtplib from email.mime.multipart import MIMEMultipart from email.mime.text...

Не могу понять в чем ошибка
Здрасте!!! Тока начал изучать язык php. Изучал по урокам Попова, но зашел в тупик. Установил...

Не могу понять в чем ошибка
Помогите пожалуйста найти ошибку в коде ппроцедуры: procedure TForm1.Button1Click(Sender:...


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

Или воспользуйтесь поиском по форуму:
32
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru