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

Как удалить узел в связном списке? - C++

Восстановить пароль Регистрация
 
Виталий123
-96 / 5 / 2
Регистрация: 29.11.2011
Сообщений: 84
28.09.2012, 00:45     Как удалить узел в связном списке? #1
привет всем! подскажите пожалуйста в подробностях как происходит удаление узла в алгоритме связного списка ??
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
39
#include "stdafx.h"
#include <conio.h>
#include <iostream>
#include <locale.h>
 
using namespace std;
 
struct node
{
    int item; node* next;
    static int count;
    node(int x, node* t): item(x), next(t) { count++; }
};
 
int node::count(0);
 
typedef node* link;
 
int _tmain(int argc, char* argv[])
{
    setlocale(LC_ALL, "");
    cout<<"Задача Иосифа."<<endl;
    int i, N = atoi(argv[1])
        , M = atoi(argv[2]);
    link t = new node(1, 0);
    t->next = t;
    link x = t;
    for(i = 2; i <= N; i++)
        x = (x->next = new node(i, t));
    while(x != x->next)
    {
        for(i = 1; i < M; i++) x = x->next;
        x->next = x->next->next; // удалить узел
    }
    cout<<x->item<<endl;
    cout<<"Количество узлов равно "<<node::count<<endl;
    _getch();
    return 0;
}
буду очень благодарен !
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
veverix
39 / 39 / 2
Регистрация: 14.09.2012
Сообщений: 85
28.09.2012, 01:17     Как удалить узел в связном списке? #2
Создается временный указатель, куда записывается адрес удаляемого объекта.
В указателе предыдущего объекта на удаляемый присваивается адрес следующего после удаляемого.
Удаляется объект по временному указателю.
Виталий123
-96 / 5 / 2
Регистрация: 29.11.2011
Сообщений: 84
28.09.2012, 19:15  [ТС]     Как удалить узел в связном списке? #3
veverix, вроде бы понятно... и еще вопрос , затем нужно так писать x->next->next; (x->next = x->next->next) что именно делает самый правый next ?
veverix
39 / 39 / 2
Регистрация: 14.09.2012
Сообщений: 85
29.09.2012, 17:44     Как удалить узел в связном списке? #4
Обьясню на примере.

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

1 > 2 > 3 > 4 > 5

Нужно удалить элемент номер 3. Если мы его просто удалим, то доступа к элементам 4 и 5 мы не получим, потому что адрес 4 будет утерян. Посему, мы сначала записываем в качестве следующего после 2 4 элемент, адрес третьего сохранив во временной адресной переменной. После чего по этому адресу удаляем 3 элемент.
m1Rr0r
 Аватар для m1Rr0r
247 / 230 / 15
Регистрация: 05.02.2010
Сообщений: 3,213
Завершенные тесты: 2
29.09.2012, 17:54     Как удалить узел в связном списке? #5
1 -> 2 -> 3 -> 4 -> 5
Удалить 3.
1->2->??? ???->4->5
запоминаем адрес 3
temp = 3;
1->2->3->4->5 и 1->2->temp->4->5 одинаковы
после 2 ссылаемся на 4, при этом 3-й элемент не будет потерян, на него так же ссылается temp;
1->2->4->5
2->next = 4;
удаляем 3;
Yandex
Объявления
29.09.2012, 17:54     Как удалить узел в связном списке?
Ответ Создать тему
Опции темы

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