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

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

13.05.2013, 13:35. Показов 11788. Ответов 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
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru