Форум программистов, компьютерный форум 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++ не могу понять в чем ошибка
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
18.08.2010, 21:21     Не могу понять в чем ошибка: реализация односвязного списка #2
C++
1
2
3
4
5
6
7
8
9
10
void addList(list &start)
{
        list *temp;
        temp=new list;
        cin >> temp->key;
        temp->next=start;
        start=*temp;
        delete temp;
        
}
если что, я не вчитывался
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
18.08.2010, 21:39     Не могу понять в чем ошибка: реализация односвязного списка #3
Тоже мучаюсь со стеком,
подскажите что не так в моей програмке - выдает только последнее число.

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
struct Stack
{
    Stack *last;
    int data;
} *top;
 
Stack* insert(Stack *i, int num)
{
    Stack *ptr = new Stack;
    ptr->last =i;
    ptr->data = num;
    i = ptr;
    return i;
}
 
void View()
{
    Stack *ptr = top;
    while(ptr != NULL)
    {   
        cout << ptr->data << endl;
        ptr = ptr->last;
    }
}
 
void main()
{
    Stack *str = NULL;
    int num = 5;
    for(int i = 0; i < 9; i++)
    {
        top = insert(str, num);
        num++;
    }
    View();
    system("pause");
}
lala_777, скопипастил улучшенный вариант твоей проги - выдает только первое число, наверно ты еще что-то изменил кроме addList(...). Если твой код работает корректно, запости сразу
все изменения, у нас проблемы похожие.

Блин, просто жесть, с 11 часов сижу.
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
18.08.2010, 21:45  [ТС]     Не могу понять в чем ошибка: реализация односвязного списка #4
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
#include <iostream>
using namespace std;
 
struct list
{
    int key;
    list *next;
};
list *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++)
        start=addList(start);
 
    printList(start);
    
    cin.get();
    cin.get();
 
    return 0;
}
 
 
list *addList(list *start)
{
    list *temp;
    temp=new list;
    cin >> temp->key;
    temp->next=start;
    start=temp;
    
    return start;
}
 
void printList(list *start)
{
    list *now=start;
 
    while(now!=NULL)
    {
        cout << now->key << " ";
        now=now->next;
    }
 
}
Вот это вроде работает.
iama, спасибо Вам большое!
siger
13 / 13 / 1
Регистрация: 27.02.2010
Сообщений: 46
18.08.2010, 21:52     Не могу понять в чем ошибка: реализация односвязного списка #5
bobromet обратите внимание на что у вас указывал str.

Вот рабочий вариант функции main.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
        Stack *str = NULL;
        int num = 5;
        for(int i = 0; i < 9; i++)
        {
                top = insert(str, num);
        str = top;
        num++;
        }
        View();
   //     system("pause");
   return 0;
}
Также необходиму добавить функцию очистки памяти.
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
18.08.2010, 22:10     Не могу понять в чем ошибка: реализация односвязного списка #6
siger, оооо.. какая прелесть, какое облегчение!
как я мог пропустить, спасибо!

lala_777, теперь работает, молодца +)
siger
13 / 13 / 1
Регистрация: 27.02.2010
Сообщений: 46
18.08.2010, 22:15     Не могу понять в чем ошибка: реализация односвязного списка #7
В качестве развлечения можете написать тоже самое, но чтобы элементы добавлялись в конец списка, а не в начало.
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
19.08.2010, 01:11     Не могу понять в чем ошибка: реализация односвязного списка #8
siger, так они ведь и так вроде в конец добавляются. )
siger
13 / 13 / 1
Регистрация: 27.02.2010
Сообщений: 46
19.08.2010, 01:24     Не могу понять в чем ошибка: реализация односвязного списка #9
да. глюкнул. тогда в начало


У вас список в конце имеет вид: 10 9 8 7 6 5 4 3 2 1
А я говорю чтоб добавлялись в виде: 1 2 3 4 5 6 7 8 9 10
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
19.08.2010, 14:07  [ТС]     Не могу понять в чем ошибка: реализация односвязного списка #10
Здравствуйте еще раз!
По мере освоения материала, возник еще один вопрос. Кто-то выше упоминал о том, что хорошо было бы реализовать функцию удаления списка из памяти.
Немного подумав, я написал следующий кусок кода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void deleteAll(list *head)
{
    list *now, nowNext;
    now=head;
    nowNext=now->next;
 
    while(nowNext!=NULL)
    {
        delete now;
        now=nowNext;
        nowNext=now->next;
    }
}
Но потом нашел в интернете вот такую функцию
C++
1
2
3
4
5
6
7
8
9
10
11
void Spisok::OCHISTKA ()
//Удаление однонаправленного списка из памяти.
// phead - указатель на заглавное звено списка.
{
  node *q,*q1;// Рабочие указатели.
 
  q = phead;
  q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
  while (q1!=NULL)
    { q = q1; q1 = (*q1).sled; delete q;}
}
Может я ошибаюсь (это и пытаюсь выяснить) но эта, вторая, функция, не удаляет первый элемент списка (голову). Правильно ли работает моя функция? Или я что-то не так понял? Спасибо.
iama
 Аватар для iama
1249 / 974 / 48
Регистрация: 30.07.2010
Сообщений: 5,297
19.08.2010, 14:11     Не могу понять в чем ошибка: реализация односвязного списка #11
lala_777, она и не удаляет:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void Spisok::OCHISTKA ()
{
  node *q,*q1;
 
  q = phead;
  q1 = (*q).sled; // в q1 2 элемент
  while (q1!=NULL)
    { 
        q = q1; // заносим в q уже второй элемент
        q1 = (*q1).sled; 
        delete q; // его и удаляем
     }
}
lala_777
0 / 0 / 0
Регистрация: 22.11.2009
Сообщений: 9
19.08.2010, 15:13  [ТС]     Не могу понять в чем ошибка: реализация односвязного списка #12
А моя - будет удалять? Я правильно понимаю?
siger
13 / 13 / 1
Регистрация: 27.02.2010
Сообщений: 46
19.08.2010, 17:35     Не могу понять в чем ошибка: реализация односвязного списка #13
Да будет.
Ну лучше периписать её так:
C
1
2
3
4
5
6
7
8
9
10
void deleteAll(list *head)
{
        list *now;
        while(head!=NULL)
        {
                now=head->next;
                delete head;
                head=now;
        }
}
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
19.08.2010, 21:03     Не могу понять в чем ошибка: реализация односвязного списка #14
Если не трудно, глянте на прогу, я знаю что есть грабли на которые я наступлю и именно на контрольной.
Почему в методе insert если удалить поинтер выдается ошибка?

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
struct Stack
{
    Stack *last;
    int data;
};
 
void insert(Stack *&st, int num)
{
    Stack *ptr = new Stack;
    ptr->data = num;
    ptr->last = st;
    st = ptr;
    //delete ptr;    выдает ошибку
}
 
void view(Stack *st)
{
    if(st == NULL)
        cout << "\nStack is empty\n";
    
    Stack *ptr = st;
    while(ptr != NULL)
    {
        cout << ptr->data << " ";
        ptr = ptr->last;
    }   
    cout << endl;
    delete ptr;
}
 
void clear(Stack *&st)
{   
    Stack *ptr = st;    
    while(ptr != NULL)
    {
        st = st->last;
        delete ptr;
        ptr = st;
    }
    delete ptr;
}
 
void main()
{
    Stack * p1 = NULL;
    Stack * p2 = NULL;
    int a = 3, b = 5;
 
    for(int i = 0; i < 6; i++)
    {
        insert(p1, a);
        insert(p2, b);
        a++;
        b += a;
    }
    view(p1);
    view(p2);
    clear(p1);
    view(p1);
    view(p2);
}
siger, что имеется в виду в твоей задачке, нужно добавить в структуру новую переменную которая показывает на следующее звено и потом начать считывать с первой ячейки, чтобы получилось
1 2 3 4 5 6 7 8 9 10
или считать обычным методом(сверху -> вниз), записать в массив а потом прогнать задом-наперед?
Я подозреваю что такое задание тоже может быть.
siger
13 / 13 / 1
Регистрация: 27.02.2010
Сообщений: 46
19.08.2010, 21:38     Не могу понять в чем ошибка: реализация односвязного списка #15
bobromet А если подумать что вы удаляете?
Почему

ptr - указывает на элемент списка.

Допустим у вас был список вида 5->4->3->2->1

ptr->data = 6;
А список примет вид: 6->5->4->3->2->1

Вы удаляете указатель на 6, в результате возращается мусор, и даже не NULL. Функция view пытается отобразить неизвестно что, вот и ошибка.


По поводу такого списка 1 2 3 4 5 6 7 8 9 10 не массив, ни новая переменная не нужна.

Если добавить указатель на следуешие звено, то получится двухсвязаный список.

P.S. Если хотите можете еще написать удаление элемента, вставка элемента в указаное место. Все теже операции с двусвязаным списком.

P.P.S. Еще можно кольцевой список, двоичные деревья.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
19.08.2010, 21:43     Не могу понять в чем ошибка: реализация односвязного списка #16
bobromet, Указатель на ссылку??? Вы что вообще делаете то?? оО
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;
}
если этот момент, то подругому у меня неполучается .(
Все эти игры с указателями сбивают с толку. Был бы очень рад увидеть правильный вариант.
Еще раз всем спасибо, ваши замечания на вес золота, сейчас бы так и сидел думая что все правильно, хорошо когда не один .)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
19.08.2010, 22:19     Не могу понять в чем ошибка: реализация односвязного списка #18
bobromet, Я бы и сам рад был увидеть правильное решение (ибо мозг отказывается работать). Но использование указателя на ссылку - это точно бредово.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.08.2010, 02:23     Не могу понять в чем ошибка: реализация односвязного списка
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
bobromet
24 / 24 / 1
Регистрация: 06.03.2010
Сообщений: 59
20.08.2010, 02:23     Не могу понять в чем ошибка: реализация односвязного списка #20
Nameless One, именно это я и хотел сделать так как нужен метод работающий с разными стеками.
lala_777 тоже интересовался выше как сделать через void.
Yandex
Объявления
20.08.2010, 02:23     Не могу понять в чем ошибка: реализация односвязного списка
Ответ Создать тему
Опции темы

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