0 / 0 / 0
Регистрация: 08.11.2014
Сообщений: 3
1

Удаление из двусвязного циклического списка

08.11.2014, 15:54. Показов 2112. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Начал реализовывать структуру данных - Фибоначчиевы кучи. Столкнулся с проблемой при написании функции удаления минимального элемента. Конкретно не могу удалить элемента из списка. Вот мои наработки. Помогите плз)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct fib_heap
{
    int key; //ключ
    char *value; //Значение
    bool mark; // Метка, изменения узла
    ui degree; // количество дочерних узлов
 
    fib_heap *parent; // Указатель на родителя
    fib_heap *child; // Указатель на потомка
    fib_heap *left; //Указатель на левый дочерний
    fib_heap *right; // Указатель на правый дочерний
};
 
struct heap
{
    fib_heap *min;
    int n;
};

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
fib_heap *fib_heap_extract_min(heap *root)
{
    fib_heap *z = root->min;
 
    if (z == NULL)
        return NULL;
 
    fib_heap *x = NULL;
 
    for (x = z; x != NULL; x = x->child)
    {
        fib_heap_add_node_to_root_list(x, root->min);
        x->parent = NULL;
    }
 
    fib_heap_remove_node_root_list(z, root->min);
 
    if (z == z->right)
        root->min = NULL;
    else
    {
        root->min = z->right;
        fib_heap_cons(root);
    }
 
    root->n = root->n - 1;
 
    return z;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void fib_heap_add_node_to_root_list(fib_heap *node, fib_heap *min)
{
    if (min == NULL)
    {
        return;
    }
 
    if (min->left == min)
    {
        min->left = node;
        min->right = node;
        node->right = min;
        node->left = min;
    }
    else
    {
        node->left->left = min->left;
        min->left = node;
        node->right = min;
        node->left = node->left;
        node->left->right = node;
    }
}
Нужно написать функцию fib_heap_remove_node_root_list(z, root->min). Не могу разобраться
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.11.2014, 15:54
Ответы с готовыми решениями:

Подсчитать размер циклического двусвязного списка
Привет. Как подсчитать размер замкнутого двусвязного списка?

Удаление элемента из двусвязного списка
Помогите пожалуйста найти где я ошибся. Элементы в список добавляются, вывод на экран тоже...

Удаление элемента из двусвязного списка
Доброго всем времени суток. Нужна помощь. Есть двусвязный список. Функции передаем какое то...

Удаление элемента из двусвязного списка
Собственно, в коде все рабочее, кроме удаления. После ввода элемента выдает ошибку 0xC0000005....

2
0 / 0 / 0
Регистрация: 08.11.2014
Сообщений: 3
09.11.2014, 16:28  [ТС] 2
Up!
0
0 / 0 / 1
Регистрация: 22.12.2014
Сообщений: 2
22.12.2014, 23:46 3
Цитата Сообщение от tooper Посмотреть сообщение
Начал реализовывать структуру данных - Фибоначчиевы кучи. Столкнулся с проблемой при написании функции удаления минимального элемента. Конкретно не могу удалить элемента из списка. Вот мои наработки. Помогите плз)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct fib_heap
{
    int key; //ключ
    char *value; //Значение
    bool mark; // Метка, изменения узла
    ui degree; // количество дочерних узлов
 
    fib_heap *parent; // Указатель на родителя
    fib_heap *child; // Указатель на потомка
    fib_heap *left; //Указатель на левый дочерний
    fib_heap *right; // Указатель на правый дочерний
};
 
struct heap
{
    fib_heap *min;
    int n;
};

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
fib_heap *fib_heap_extract_min(heap *root)
{
    fib_heap *z = root->min;
 
    if (z == NULL)
        return NULL;
 
    fib_heap *x = NULL;
 
    for (x = z; x != NULL; x = x->child)
    {
        fib_heap_add_node_to_root_list(x, root->min);
        x->parent = NULL;
    }
 
    fib_heap_remove_node_root_list(z, root->min);
 
    if (z == z->right)
        root->min = NULL;
    else
    {
        root->min = z->right;
        fib_heap_cons(root);
    }
 
    root->n = root->n - 1;
 
    return z;
}

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void fib_heap_add_node_to_root_list(fib_heap *node, fib_heap *min)
{
    if (min == NULL)
    {
        return;
    }
 
    if (min->left == min)
    {
        min->left = node;
        min->right = node;
        node->right = min;
        node->left = min;
    }
    else
    {
        node->left->left = min->left;
        min->left = node;
        node->right = min;
        node->left = node->left;
        node->left->right = node;
    }
}
Нужно написать функцию fib_heap_remove_node_root_list(z, root->min). Не могу разобраться
ты понял как реализовать функцию fib_heap_remove_node_root_list? можешь помочь с ней?
0
22.12.2014, 23:46
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.12.2014, 23:46
Помогаю со студенческими работами здесь

Удаление элемента из двусвязного списка
Надо удалить элемент из двусвязного списка, если выполняется условие (2013-(current->god)<3). Я...

Удаление структуры из двусвязного списка
Доброго времени суток! Пытаюсь создать функцию удаления из списка структуры, не выполняется цикл...

Добавление и удаление элементов из двусвязного списка
Разбираю списки. Посмотрите код правильно ли я все понимаю?))) путаюсь с указателями. может можно...

Удаление элемента из двусвязного списка по значению
Есть такой код, который позволяет добавлять элементы в список и выводить, а мне нужно доделать еще...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru