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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
#1

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

18.08.2010, 21:12. Просмотров 2135. Ответов 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
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Не могу понять в чем ошибка: реализация односвязного списка (C++):

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

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

не могу понять в чем ошибка - C++
помогите найти ошибку

Не могу понять в чем ошибка - C++
написать программу в CodeBlocks, никак не могу понять в чем ошибка. Найти периметр эллипса по двум радиусам. #include &lt;iostream&gt; ...

Не могу понять в чем ошибка - C++
Добрый вечер, есть задача: ********/index.asp?main=task&amp;id_task=315 Я решаю ее таким образом: #include &lt;fstream&gt; char...

не могу понять в чем ошибка - C++
Вот мое задание: Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Х до Х с шагом dx. Функция F: -ax^2...

31
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
19.08.2010, 21:43 #16
bobromet, Указатель на ссылку??? Вы что вообще делаете то?? оО
0
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
19.08.2010, 22:18 #17
siger, спасибо, буду думать!
Lavroff, что конкретно вы имеете ввиду?
C++
1
2
3
4
5
6
7
8
9
10
11
void clear(Stack *&st)
{       
        Stack *ptr = st;        
        while(ptr != NULL)
        {
                st = st->last;
                delete ptr;
                ptr = st;
        }
    delete ptr;
}
если этот момент, то подругому у меня неполучается .(
Все эти игры с указателями сбивают с толку. Был бы очень рад увидеть правильный вариант.
Еще раз всем спасибо, ваши замечания на вес золота, сейчас бы так и сидел думая что все правильно, хорошо когда не один .)
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
19.08.2010, 22:19 #18
bobromet, Я бы и сам рад был увидеть правильное решение (ибо мозг отказывается работать). Но использование указателя на ссылку - это точно бредово.
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
20.08.2010, 01:58 #19
Lavroff, это не указатель на ссылку, это ссылка на указатель

Добавлено через 9 минут
Если мы передаем функции указатель, то мы можем изменить значение, на которое он указывает. Но чтобы изменить значение самого указателя (например, выделить внутри функции память для динамического массива или удалить ее), нам нужно передавать адрес самого указателя (т.е. указатель на указатель) или ссылку на указатель. Сравни:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdlib>
 
void new5int(int* ptr)
{
    ptr = new int[5];
    for(size_t i = 0; i < 5; ++i)
        ptr[i] = 5;
}
 
int main()
{
    int *ptr = NULL;
    new5int(ptr);
    for(size_t i = 0; i < 5; ++i)
        std::cout << ptr[i] << std::endl;
    return EXIT_SUCCESS;
}
С вот этим:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdlib>
 
void new5int(int*& ptr)
{
    ptr = new int[5];
    for(size_t i = 0; i < 5; ++i)
        ptr[i] = 5;
}
 
int main()
{
    int *ptr = NULL;
    new5int(ptr);
    for(size_t i = 0; i < 5; ++i)
        std::cout << ptr[i] << std::endl;
    return EXIT_SUCCESS;
}
Или вот этим:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdlib>
 
void new5int(int** ptr)
{
    (*ptr) = new int[5];
    for(size_t i = 0; i < 5; ++i)
        (*ptr)[i] = 5;
}
 
int main()
{
    int *ptr = NULL;
    new5int(&ptr);
    for(size_t i = 0; i < 5; ++i)
        std::cout << ptr[i] << std::endl;
    return EXIT_SUCCESS;
}
1
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
20.08.2010, 02:23 #20
Nameless One, именно это я и хотел сделать так как нужен метод работающий с разными стеками.
lala_777 тоже интересовался выше как сделать через void.
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
20.08.2010, 06:43 #21
bobromet, а стек нужно обязательно сделать в виде структуры без методов, или можно сделать в виде (шаблонного) класса?
0
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.
Ума не приложу как без ввода новых переменных добится нужного. Блин.
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
21.08.2010, 00:28 #23
bobromet, Просто сделать двусвязный список. В котором есть не только поле для Stack *last, но также есть Stack *prev.
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
21.08.2010, 05:54 #24
Lavroff, это будет уже не стек
0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
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
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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 / 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, ты сам структуру используешь, то есть можно сказать уже работаешь с классом
0
easybudda
Модератор
Эксперт CЭксперт С++
9664 / 5614 / 952
Регистрация: 25.07.2009
Сообщений: 10,778
21.08.2010, 21:48 #30
Цитата Сообщение от bobromet Посмотреть сообщение
Не знал что есть такая удобная штука как stack...
Да стек и самому не сложно сделать. Вот пример: http://www.cyberforum.ru/cpp/thread160544.html#post916931
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.08.2010, 21:48
Привет! Вот еще темы с ответами:

Не могу понять в чем ошибка - C++
Всем доброго время суток целый день бьюсь, не понимаю в чем ошибка: #include &lt;iostream&gt; using std::endl; int myFunc(unsigned short...

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

Не могу понять в чем ошибка? - C++
Выдает ошибки а в чем проблемма не пойму (программирую недавно) Unit1.cpp(94): W8004 'p' is assigned a value that is never used ...

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


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
21.08.2010, 21:48
Ответ Создать тему
Опции темы

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