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

Рекурсивная структура - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.67
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 13:35     Рекурсивная структура #1
Добрый день!
Стоит задача написать односвязный список.
Как все работает в общем я представляю, а конкретно я понимаю это так:

имеем общую структуру элемента:
C++
1
2
3
4
5
struct List
{
 int item;
 List *Next;
};
*(ниже описание, того, как я представляю работу "создания нового элемента в списке" с "нуля").
1. создается голова списка
C++
1
2
List* Head;
Head->Next=NULL;
2. при создании нового (El_1) элемента списка, указатель который был в голове "Head", принимает адрес значения
El_1->item; где El_1->item=x ( x - вводимое число при вставке нового элемента).
C++
1
2
3
Head->Next=&El_1->item;
El_1->item=x; // где x произвольное значение
El_1->Next=NULL;
3. при создании нового элемента(второго) (El_2) , указатель El_1, то есть El_1->Next = адрес El_2->item, а El_2->Next=NULL;

C++
1
2
3
El_1->Next=&El_2->item;
El_2->item=x; // где x произвольное значение
El_2->Next=NULL;
//и тд. с другими элементами.
Вопрос 1: я правильно понимаю систему? если да, то как перебирать элементы с головы к низу (пока Next!=NULL)
Вопрос 2:
Код:
C++
1
2
3
4
5
struct List
{
 int item;
 List *Next;
};
что касается этой структуры, она создана рекурсивно, когда я представляю, как для нее выделяется память, то вижу, что создается одна структура, потом в ней ещё одна, в той стркутуре ещё одна и тд. ( при этом программа будет создавать структуру в структуре пока не закончится память), так, как:
в строчке
C++
1
2
3
4
5
struct List// создастся структура
{
 int item;// потом элемент этой структуры
 List *Next;//потом опять структура и так до бесконечности( пока память не закончится)
};
я просто не могу понять, как при создании нового элемента в память записывается эта структура.. помогите, люди разобраться с этим) так, как в основном проблема у меня с пониманием этой структуры.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2013, 13:35     Рекурсивная структура
Посмотрите здесь:

C++ рекурсивная((
C++ Структура, доступная из всех файлов проекта ("глобальная" структура)
C++ рекурсивная функция
Рекурсивная функция C++ C++
C++ Рекурсивная функция
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
13.05.2013, 13:54     Рекурсивная структура #2
Цитата Сообщение от Netly Посмотреть сообщение
что касается этой структуры, она создана рекурсивно,
Нет.
Цитата Сообщение от Netly Посмотреть сообщение
struct List// создастся структура
Считайте, что это тип данных.
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 13:57  [ТС]     Рекурсивная структура #3
как тогда быть со строчкой в объявлении структуры?
C++
1
List *Next;
как под неё выделяется память?
она указывает на адрес самой себя?
то есть, например:
C++
1
2
3
4
5
struct List
{
 int item; // к примеру item = 31, адрес в памяти 42149193
 List *Next;// Next= 42149193 ?
};
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
13.05.2013, 14:18     Рекурсивная структура #4
Цитата Сообщение от Netly Посмотреть сообщение
как под неё выделяется память?
Память должна выделяться при добавлении очередного узла к списку.
Цитата Сообщение от Netly Посмотреть сообщение
она указывает на адрес самой себя?
Если элемент единственный Next должен быть равен 0 (NULL);
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
13.05.2013, 14:41     Рекурсивная структура #5
Цитата Сообщение от Netly Посмотреть сообщение
List *Next;
Это просто указатель.

Добавлено через 9 минут
Вот пример
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>
 
struct Node
{
    int value;
    void* p;
    Node(int _value)
        : value(_value), p(nullptr)
    {
            
    }
};
 
int main()
{
    Node* list = new Node(5);
    
    list->p = (void*) new Node(6);
    
    // It is necessary to make check!
    
    std::cout << list->value << " " << ((Node*)list->p)->value << std::endl;
    
    // Need delete!
    
}
http://ideone.com/0a3SVp

Добавлено через 20 секунд
Цитата Сообщение от go Посмотреть сообщение
Это просто указатель.
Просто его кастовать не надо.
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 14:41  [ТС]     Рекурсивная структура #6
Цитата Сообщение от Tulosba Посмотреть сообщение
Память должна выделяться при добавлении очередного узла к списку.
Это я понимаю, но не представляю, как это можно вообразить в виде блоков памяти, как тут:
http://algorithmlib.org/spisok_turn ( там изображения в виде блоков памяти). Я сам себя запутал)
C++
1
2
3
4
5
6
struct List
{
int item; // к примеру item = 31, адрес в памяти 42149193
List *Next; // должно быть Next = 42149193 ? 
//только, что пробовал создать 1 элемент и вытянул адрес Next и item - дало два разных адреса (
};

Если элемент единственный Next должен быть равен 0 (NULL);
с этим уже разобрался.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
13.05.2013, 14:44     Рекурсивная структура #7
Цитата Сообщение от Netly Посмотреть сообщение
C++
1
2
int item; // к примеру item = 31, адрес в памяти 42149193 
List *Next; // должно быть Next = 42149193 ?
Такого быть не должно. Иначе у Вас список замкнутый на себя.
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 15:20  [ТС]     Рекурсивная структура #8
Цитата Сообщение от Tulosba Посмотреть сообщение
Такого быть не должно. Иначе у Вас список замкнутый на себя.
Спасибо Экспертам за ответы
я тоже так думаю, но в голове получается рекурсия)
вот, похожая тема, которая тоже не до конца раскрыта Структуры, содержащие указатели на самих себя

Ваши ответы натолкнули меня на новые вопросы, ответы на которые ищу по тематике - "Структуры со ссылками на себя". Может кому пригодится)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2013, 15:35     Рекурсивная структура #9
Netly, вот вам мой пример стека
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
template <typename E>
class Tstack{
public:
    struct stack{
        E inf;
        stack *next;
    };
    stack *head;
    Tstack(){
        head =  NULL;
    }
    void push(E x){
        stack *st = new stack;
        st->inf = x;
        st->next = head;
        head = st;
    }
    bool empty(){
        return !head;
    }
    E top(){
        return head->inf;
    }
    E pop(){
        stack *nhead = head;
        E c = head->inf;
        head = nhead->next;
        delete nhead;
        return c;
    }
    void show(){
        stack *st = head;
        while (st) {
            cout << st->inf << " ";
            st = st->next;
        }
    }
};
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
13.05.2013, 15:45     Рекурсивная структура #10
Netly, Да дружище я сам когда токо познакомился со списком тоже не сильно понимал, со временем осознаешь как это. Да видимо ты еще что такое укозатель до конца не понимаешь - это просто адресс на ячейку памяти. Утета от фигня List *Next; указывает на следующий элемент данный, который как бы ноль, значит для того чтобы обойти все элементы то тебе в самом классе нужно хранить указатель на первый элемент списка например List* first; и при обходе просто делаешь first->next - это следующий за первым элемент first->next->next - это следующий за вторым.
Да и вообще как писать список единого правила нет. Как втулил так и втулил лишь бы работало. Можно сделать двусвязный список добавить еще и List* prev тогда просто рекурсисно идешь вглубь пока prev не равно 0 , если prev равно 0 то значит это первый элемент списка, можно не рекурсивно, а просто в цикле.
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 16:33  [ТС]     Рекурсивная структура #11
Цитата Сообщение от ninja2 Посмотреть сообщение
Netly, Да дружище я сам когда токо познакомился со списком тоже не сильно понимал, со временем осознаешь как это. Да видимо ты еще что такое укозатель до конца не понимаешь - это просто адресс на ячейку памяти. Утета от фигня List *Next; указывает на следующий элемент данный, который как бы ноль, значит для того чтобы обойти все элементы то тебе в самом классе нужно хранить указатель на первый элемент списка например List* first; и при обходе просто делаешь first->next - это следующий за первым элемент first->next->next - это следующий за вторым.
Да и вообще как писать список единого правила нет. Как втулил так и втулил лишь бы работало. Можно сделать двусвязный список добавить еще и List* prev тогда просто рекурсисно идешь вглубь пока prev не равно 0 , если prev равно 0 то значит это первый элемент списка, можно не рекурсивно, а просто в цикле.
Спасибо за пояснения, в моей голове понемногу проясняется картина)
Нам дали псевдокод на практике на создание "Линейного списка", но не объяснили, многих некоторых деталей, более того, когда нас учили "основам C++", структуры мы "прошли" за одну пару, а на паре давались только понятия о том, как создать структуру или массив структур, но работу структур с функциями, структур с указателями на себя и тд. нам не объясняли и на практике мы не проходили этого в прошлом семестре, в общем то что успел понять, то и имею, сейчас перечитываю более информированные статьи о структурах.

Добавлено через 31 минуту
Цитата Сообщение от go Посмотреть сообщение
Это просто указатель.
Вопрос: если это просто указатель, разве нельзя переделать структуру на такую?
C++
1
2
3
4
5
struct List
{
 int item;
 int *Next;
};
в смысле, они равносильны?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2013, 16:52     Рекурсивная структура
Еще ссылки по теме:

C++ В текстовом файле структура – информация о компьютерах. Структура с полями: название, стоимость.
C++ Структура DateTime, битовая структура
C++ Структура «База», сущности «Универсам» и «Продукты», структура «Товар»

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
13.05.2013, 16:52     Рекурсивная структура #12
Цитата Сообщение от Netly Посмотреть сообщение
в смысле, они равносильны?
нет. Указатель должен указывать на элемент списка, а не на значение в этом элементе. Иначе нельзя будет "путешествовать" по списку через цепочку Next->Next->...Next
Yandex
Объявления
13.05.2013, 16:52     Рекурсивная структура
Ответ Создать тему
Опции темы

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