С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.66/58: Рейтинг темы: голосов - 58, средняя оценка - 4.66
1 / 1 / 0
Регистрация: 19.11.2012
Сообщений: 28

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

13.05.2013, 13:35. Показов 11840. Ответов 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;//потом опять структура и так до бесконечности( пока память не закончится)
};
я просто не могу понять, как при создании нового элемента в память записывается эта структура.. помогите, люди разобраться с этим) так, как в основном проблема у меня с пониманием этой структуры.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
13.05.2013, 13:35
Ответы с готовыми решениями:

В текстовом файле структура – информация о компьютерах. Структура с полями: название, стоимость.
Ребят, помогите пожалуйста, 29 июня экзамен по "Основы программирования",кто сколько сможет сделать задач, тем всей группой поставим...

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

структура array предназначена для хранения строки типа char. Структура имеет функцию, которая позволяет изменить символ
структура array предназначена для хранения строки типа char. Структура имеет функцию, которая позволяет изменить символ с указанным...

11
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
13.05.2013, 13:54
Цитата Сообщение от Netly Посмотреть сообщение
что касается этой структуры, она создана рекурсивно,
Нет.
Цитата Сообщение от Netly Посмотреть сообщение
struct List// создастся структура
Считайте, что это тип данных.
1
1 / 1 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 13:57  [ТС]
как тогда быть со строчкой в объявлении структуры?
C++
1
List *Next;
как под неё выделяется память?
она указывает на адрес самой себя?
то есть, например:
C++
1
2
3
4
5
struct List
{
 int item; // к примеру item = 31, адрес в памяти 42149193
 List *Next;// Next= 42149193 ?
};
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
13.05.2013, 14:18
Цитата Сообщение от Netly Посмотреть сообщение
как под неё выделяется память?
Память должна выделяться при добавлении очередного узла к списку.
Цитата Сообщение от Netly Посмотреть сообщение
она указывает на адрес самой себя?
Если элемент единственный Next должен быть равен 0 (NULL);
0
go
Эксперт С++
3646 / 1378 / 243
Регистрация: 16.04.2009
Сообщений: 4,526
13.05.2013, 14:41
Цитата Сообщение от 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 Посмотреть сообщение
Это просто указатель.
Просто его кастовать не надо.
0
1 / 1 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 14:41  [ТС]
Цитата Сообщение от 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);
с этим уже разобрался.
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
13.05.2013, 14:44
Цитата Сообщение от Netly Посмотреть сообщение
C++
1
2
int item; // к примеру item = 31, адрес в памяти 42149193 
List *Next; // должно быть Next = 42149193 ?
Такого быть не должно. Иначе у Вас список замкнутый на себя.
1
1 / 1 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 15:20  [ТС]
Цитата Сообщение от Tulosba Посмотреть сообщение
Такого быть не должно. Иначе у Вас список замкнутый на себя.
Спасибо Экспертам за ответы
я тоже так думаю, но в голове получается рекурсия)
вот, похожая тема, которая тоже не до конца раскрыта Структуры, содержащие указатели на самих себя

Ваши ответы натолкнули меня на новые вопросы, ответы на которые ищу по тематике - "Структуры со ссылками на себя". Может кому пригодится)
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
13.05.2013, 15:35
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;
        }
    }
};
1
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
13.05.2013, 15:45
Netly, Да дружище я сам когда токо познакомился со списком тоже не сильно понимал, со временем осознаешь как это. Да видимо ты еще что такое укозатель до конца не понимаешь - это просто адресс на ячейку памяти. Утета от фигня List *Next; указывает на следующий элемент данный, который как бы ноль, значит для того чтобы обойти все элементы то тебе в самом классе нужно хранить указатель на первый элемент списка например List* first; и при обходе просто делаешь first->next - это следующий за первым элемент first->next->next - это следующий за вторым.
Да и вообще как писать список единого правила нет. Как втулил так и втулил лишь бы работало. Можно сделать двусвязный список добавить еще и List* prev тогда просто рекурсисно идешь вглубь пока prev не равно 0 , если prev равно 0 то значит это первый элемент списка, можно не рекурсивно, а просто в цикле.
0
1 / 1 / 0
Регистрация: 19.11.2012
Сообщений: 28
13.05.2013, 16:33  [ТС]
Цитата Сообщение от 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;
};
в смысле, они равносильны?
0
:)
Эксперт С++
4773 / 3267 / 497
Регистрация: 19.02.2013
Сообщений: 9,046
13.05.2013, 16:52
Цитата Сообщение от Netly Посмотреть сообщение
в смысле, они равносильны?
нет. Указатель должен указывать на элемент списка, а не на значение в этом элементе. Иначе нельзя будет "путешествовать" по списку через цепочку Next->Next->...Next
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
13.05.2013, 16:52
Помогаю со студенческими работами здесь

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

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

Структура и вложенная структура
Подскажите как сделать задание, такого рода Иванов Математика 80 История 60 Физика 67 ...

Тип структура. Описать, используя тип структура
Описать, используя тип структура, данные на учеников (фамилия, улица, дом, квартира). Составить программу, определяющую, сколько учеников...

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


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

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru