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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 36, средняя оценка - 4.67
Netly
0 / 0 / 0
Регистрация: 19.11.2012
Сообщений: 28
#1

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

13.05.2013, 13:35. Просмотров 5075. Ответов 11
Метки нет (Все метки)

Добрый день!
Стоит задача написать односвязный список.
Как все работает в общем я представляю, а конкретно я понимаю это так:

имеем общую структуру элемента:
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++
Ребят, помогите пожалуйста, 29 июня экзамен по "Основы программирования",кто сколько сможет сделать задач, тем всей группой поставим "+"...

Структура «База», сущности «Универсам» и «Продукты», структура «Товар» - C++
1. Создать структуру «База», включающую не менее 3 полей. 2. Создать сущности «Универсам» и «Продукты» описанной структуры. 3. Создать...

Структура DateTime, битовая структура - C++
Условие: Структура содержит информацию о дате и времени некоторого события: struct datetime { unsigned short Year; // год ...

Структура, доступная из всех файлов проекта ("глобальная" структура) - C++
Есть четыре структуры (body, gun, enemy, st), описанные в main.cpp. К main.cpp подключен хедер save.h, в котором имеется функция void...

рекурсивная(( - C++
Proc67. Описать рекурсивную функцию MinRec(A,N)1|MaxRec(A,N)2 вещественного типа, которая находит минимальный1|максимальный2 элемент...

Рекурсивная функция - C++
С клавиатуры вводится массив из 20 элементов. Заменить все отрицательные элементы суммой чётных! int x,h; void input(int i){ ...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
go
Эксперт C++
3586 / 1366 / 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
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
13.05.2013, 14:18 #4
Цитата Сообщение от Netly Посмотреть сообщение
как под неё выделяется память?
Память должна выделяться при добавлении очередного узла к списку.
Цитата Сообщение от Netly Посмотреть сообщение
она указывает на адрес самой себя?
Если элемент единственный Next должен быть равен 0 (NULL);
go
Эксперт C++
3586 / 1366 / 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
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
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
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
231 / 187 / 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;
};
в смысле, они равносильны?
Tulosba
:)
Эксперт С++
4393 / 3236 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
13.05.2013, 16:52 #12
Цитата Сообщение от Netly Посмотреть сообщение
в смысле, они равносильны?
нет. Указатель должен указывать на элемент списка, а не на значение в этом элементе. Иначе нельзя будет "путешествовать" по списку через цепочку Next->Next->...Next
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2013, 16:52
Привет! Вот еще темы с ответами:

Рекурсивная функция - C++
Написать на языке С рекурсивную функцию вычисляющую количество полных расстановок скобок в произведении n чисел

Рекурсивная функция. - C++
Доброго времени суток. Мне необходимо написать рекурсивную функцию для решения задачи: Помогите пожалуйста придумать алгоритм, никак...

Рекурсивная функция[] - C++
Доброго времени суток. Мне необходимо написать рекурсивную функцию для решения задачи: Помогите пожалуйста в решении данной...

Рекурсивная функция С++ - C++
Написать рекурсивную функцию (+ саму программу), которая подсчитывает сумму элементов одномерного массива.


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

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

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