Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676

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

04.04.2024, 15:00. Показов 2759. Ответов 30
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вот написал такое, всё работает, был бы благодарен за подсказки по явным косякам или неправильным подходам. Я классами ранее не пользовался поэтому делал методом научного тыка.
Собственно описание: MinList реализует список узлов Node, которые ссылаются друг на друга в порядке возрастания. Метод Peek извлекает постоянно минимальный элемент один за другим, метод Start позволяет сбросить позицию для Peek и начать выборку с начала.

Данный список я решил реализовать для алгоритма Дейкстры, так как при обработке узлов требуются по порядку те, что имеют минимальный вес
В результате тестов я выяснил что много узлов имеют только по два соседа, что позволяет Дейкстру запускать на ограниченных данных (в том числе в многопроцессорном режиме), а реализация MinList для 6.5 млн узлов вырождается всего до 20-25 элементов за раз.

результат работы кода
Code
1
2
3
4
1 5 8 15 19 25 35 50 51 555 5555
1 5 8 15 19 25 35 50 51 555 5555
8 15 19 25 35 50 51 555 5555
1 2 4 5 8 12 34
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
using System.Text;
 
var ml = new MinList();
ml.Insert(new Node(5));
ml.Insert(new Node(1));
ml.Insert(new Node(50));
ml.Insert(new Node(15));
ml.Insert(new Node(555));
ml.Insert(new Node(19));
ml.Insert(new Node(51));
ml.Insert(new Node(25));
ml.Insert(new Node(35));
ml.Insert(new Node(5555));
ml.Insert(new Node(8));
Console.WriteLine(ml.ToString());
 
ml.Start();
var n = ml.Peek();
while (n != null)
{
    Console.Write(n.ToString());
    Console.Write(" ");
    n = ml.Peek();
}
Console.WriteLine();
 
ml.Start();
n = ml.Peek();
n = ml.Peek();
n = ml.Peek();
while (n != null)
{
    Console.Write(n.ToString());
    Console.Write(" ");
    n = ml.Peek();
}
Console.WriteLine();
 
ml.Clear();
 
int[] arr = new int[] { 4, 2, 8, 1, 5, 34, 12 };
 
ml.Fill(arr);
Console.WriteLine(ml.ToString());
 
public class Node
{
    public int Value { get; set; }
    public Node PrevNode { get; set; }
    public Node NextNode { get; set; }
    public Node(int value)
    {
        Value = value;
    }
    public Node()
    {
    }
    public string ToString()
    {
        return Value.ToString();
    }
}
public class MinList
{
    private int _size { get; set; }
    public Node CurrentNode;
    public Node FirstNode;
    public Node LastNode;
    public MinList()
    {
        _size = 0;
    }
    public bool Start()
    {
        if (Count() == 0) return false;
        CurrentNode = FirstNode;
        return true;
    }
    public Node Peek()
    {
        if (CurrentNode == null) return null;
        var n = CurrentNode;
        CurrentNode = CurrentNode.NextNode;
        return n;
    }
    public int Count()
    {
        return _size;
    }
    public bool IsFirst(Node node)
    {
        return node.PrevNode == null;
    }
    public bool IsLast(Node node)
    {
        return node.NextNode == null;
    }
    public bool Swap(Node node1, Node node2)
    {
        if (node1 == null || node2 == null) return false;
        var tempNode = node1;
        node1 = node2;
        node2 = tempNode;
        if (IsFirst(node1)) FirstNode = node1;
        if (IsFirst(node2)) FirstNode = node2;
        if (IsLast(node1)) LastNode = node1;
        if (IsLast(node2)) LastNode = node2;
        return true;
    }
    public bool SwapPrev(Node node)
    {
        return Swap(node, node.PrevNode);
    }
    public bool SwapNext(Node node)
    {
        return Swap(node, node.NextNode);
    }
    private Node Append(Node node)
    {
        FirstNode = node;
        LastNode = node;
        _size++;
        return node;
    }
    private Node InsertFirst(Node node)
    {
        if (Count() == 0) return Append(node);
        _size++;
        node.NextNode = FirstNode;
        FirstNode.PrevNode = node;
        FirstNode = node;
        return node;
    }
    private Node InsertLast(Node node)
    {
        if (Count() == 0) return Append(node);
        _size++;
        node.PrevNode = LastNode;
        LastNode.NextNode = node;
        LastNode = node;
        return node;
    }
    public Node Insert(Node node)
    {
        if (Count() == 0) return Append(node);
        if (Count() == 1 && node.Value < FirstNode.Value) return InsertFirst(node);
        if (Count() == 1 && node.Value >= FirstNode.Value) return InsertLast(node);
        if (node.Value <= FirstNode.Value) return InsertFirst(node);
        if (node.Value > LastNode.Value) return InsertLast(node);
        var tempNode = FirstNode.NextNode;
        while (node.Value > tempNode.Value)
        {
            tempNode = tempNode.NextNode;
        }
        _size++;
        node.PrevNode = tempNode.PrevNode;
        tempNode.PrevNode.NextNode = node;
        tempNode.PrevNode = node;
        node.NextNode = tempNode;
        return node;
    }
    public List<Node> Fill(IEnumerable<int> dataList)
    {
        List<Node> list = new List<Node>();
        foreach (int dl in dataList)
        {
            list.Add(Insert(new Node(dl)));
        }
        Start();
        return list;
    }
    public void Clear()
    {
        _size = 0;
        CurrentNode = null;
        FirstNode = null;
        LastNode = null;
    }
    public string ToString()
    {
        StringBuilder sb = new StringBuilder();
        Start();
        var tempNode = CurrentNode;
        while (tempNode != null)
        {
            sb.Append(tempNode.ToString());
            sb.Append(' ');
            tempNode = tempNode.NextNode;
        }
        return sb.ToString();
    }
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
04.04.2024, 15:00
Ответы с готовыми решениями:

Как добавить элементы в контейнер, который создан на основе двунаправленного упорядоченного замкнутого списка?
?Как добавить элементы в контейнер, который создан на основе двунаправленного не замкнутого списка с заголовком

Проверить существование под-узлов у узлов корневого элемента Xml файла
Есть следующий код для получения имен всех под-узлов корневого элемента Xml файла: List&lt;string&gt; nodes = new List&lt;string&gt;(); ...

Получение списка дочерних узлов из XML
Здравствуйте, помогите с реализацией, застрял... Есть XML-файл подобного вида: &lt;?xml version=&quot;1.0&quot;...

30
Любознательный
 Аватар для YuS_2
7407 / 2260 / 361
Регистрация: 10.03.2016
Сообщений: 5,216
05.04.2024, 14:49
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от belalugoci Посмотреть сообщение
И таким весь интернет забит.
Чем забит?
Вам говорят о том, что граф - это не список. Вы приводите название функции и пояснение о том, что в ней используются список вершин, список ребер и источник вершин в виде аргументов. Как это опровергает высказывание:
Цитата Сообщение от wizard41 Посмотреть сообщение
Список и граф - не одно и то же!
?
Граф - это, как минимум, система, описывающая отношения элементов (вершин), для множеств, ну я не знаю... вроде, подробно там расписано.
Список - это коллекция элементов, организованная определенным образом... не более того, но и не менее... сама по себе, она никак не описывает связи вершин...
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
05.04.2024, 15:12  [ТС]
Цитата Сообщение от YuS_2 Посмотреть сообщение
Вам говорят о том, что граф - это не список
зачем мне это говорить в принципе? я где-то яростно доказываю обратное? Я писал только что у меня граф в виде списка. Это абсолютно нормально и допустимо. Прикопались именно к этому.

Цитата Сообщение от YuS_2 Посмотреть сообщение
Вы приводите название функции и пояснение о том, что в ней используются список вершин, список ребер и источник вершин в виде аргументов. Как это опровергает высказывание
а вы за контекстом следите, фразу "Список и граф - не одно и то же!" написали на мои слова: "пока здесь только вы не в состоянии список преобразовать в граф". Я нигде не утверждал что список и граф это одно и то же. Так что не нужно оправдывать человека в его глупости.

Цитата Сообщение от YuS_2 Посмотреть сообщение
сама по себе, она никак не описывает связи вершин
Если граф нельзя было бы представить в сиде списка, то это автоматически не позволило бы с графами работать, потому что в ОЗУ вы так или иначе будете работать с указателями на память, процессору вообще незнакомы такие вещи как графы, если это не какой-то специализированный ЦПУ. Поэтому в ОЗУ что список что граф будут однофигственно представлены набором связей указателей и ячеек с данными. То есть по отношению к пользователю и граф и список - чисто виртуальные конструкции данных.
А граф можно выразить через список и список представить в виде графа, тут нет никаких препятствий, что я успешно и делаю. Почему у великого математика это вызывает проблемы - ну я хз. (а у вас почему?)

Добавлено через 1 минуту
Цитата Сообщение от wizard41 Посмотреть сообщение
работать со списком и графом имелось в виду. Разные вещи
вы перечитайте на что вы мне давали ответ и о чем вообще шел разговор, поздно метаться.
0
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
05.04.2024, 15:15
belalugoci, вам бесполезно что-либо доказывать.
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
05.04.2024, 15:37  [ТС]
wizard41,
alles funktioniert wunderbar
und von Ihnen werden wir es nicht erwarten, den Dijkstra-Algorithmus zu ersetzen!
0
Любознательный
 Аватар для YuS_2
7407 / 2260 / 361
Регистрация: 10.03.2016
Сообщений: 5,216
05.04.2024, 15:46
Цитата Сообщение от belalugoci Посмотреть сообщение
а вы за контекстом следите
Не так чтобы внимательно, скорее по диагонали...
Цитата Сообщение от belalugoci Посмотреть сообщение
написали на мои слова: "пока здесь только вы не в состоянии список преобразовать в граф". Я нигде не утверждал что список и граф это одно и то же.
Ну, строго говоря, взять и преобразовать любой список в граф нельзя... Да, с помощью списка можно описать граф... но это две большие разницы... так что никакой глупости Вам не говорили.

Цитата Сообщение от belalugoci Посмотреть сообщение
Если граф нельзя было бы представить в сиде списка
А тут, пользуясь Вашим же приемом - а можно ссылку, где об этом именно сказано?

Цитата Сообщение от belalugoci Посмотреть сообщение
список представить в виде графа
Это утверждение требует наглядности...
Например, список:
[1,17,38,113] - в какой граф его можно преобразовать?
Учитывая:
Цитата Сообщение от YuS_2 Посмотреть сообщение
Граф - это... система, описывающая отношения элементов (вершин), для множеств...
Список - это коллекция элементов, организованная определенным образом
0
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
05.04.2024, 15:46
Цитата Сообщение от belalugoci Посмотреть сообщение
alles funktioniert wunderbar
ну и?
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
05.04.2024, 15:58  [ТС]
Цитата Сообщение от YuS_2 Посмотреть сообщение
Например, список
не сферический список в вакууме, а список, который описывает граф в моем сообщении №14
претензия у обсуждателей крутится вокруг моих слов и моих данных.

Добавлено через 2 минуты
Цитата Сообщение от wizard41 Посмотреть сообщение
ну и?
пока вы строчили неделю хлёсткие ответы в духе всемирного математического кружка, я просто пишу, запускаю и считаю. В мире оно всё так работает. А вы пока уже больше чем за 15 обещанных минут - ни грамма не сказали.
а про
Цитата Сообщение от wizard41 Посмотреть сообщение
Дейкстра тут вообще ни боком ни рылом
доказательств не будет, а трепать языком может любой.
0
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
05.04.2024, 16:03
belalugoci, заниматься подменой понятий, конечно, никто запретить не может. Что у вас там в голове - только вам известно. Но пытаясь выставить свои мысли здесь как некие "постулаты", вы, прежде всего, позоритесь сами.
Не теребите людей по напрасну. Понятно, что вам покоя не дает факт "не доказанности" своей кривой истины.
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
05.04.2024, 17:05  [ТС]
Цитата Сообщение от wizard41 Посмотреть сообщение
Понятно
понятно пока только одно - что вы бла-бла-бла пустозвон брехун )
где реализация обхода графа написанная за 15 минут с перерывами "на покурить"? я не ваш студент которому вы можете лить в уши, а он слушает, потому что от вас зависит. ну, профессор, где код? отмазка про то что вы ничего не поняли не проканает, здесь я тупой и так могу говорить, а вы умный, значит вы в состоянии простой список описывающий граф обойти каким-то хитрейшим алгоритмом и затмить дейкстру, которую причем не я сам выбрал, мне его тут же посоветовали использовать.
0
Эксперт JavaЭксперт по электроникеЭксперт .NET
 Аватар для wizard41
3463 / 2784 / 575
Регистрация: 04.09.2018
Сообщений: 8,757
Записей в блоге: 3
05.04.2024, 18:13
belalugoci, для того что бы что-то делать - надо ясно представлять задачу. От вас так и не дождался прояснения.
Все на уровне непонятных абстракций и неведомо чего, мало относящееся к реальному жизненному примеру.
Цитата Сообщение от belalugoci Посмотреть сообщение
где реализация обхода графа написанная за 15 минут
Их тьма, написаны давно. Но ничто из этого не подойдет вам, т.к. вы глубоко заблудились в том что делаете.
0
 Аватар для belalugoci
475 / 294 / 29
Регистрация: 01.06.2018
Сообщений: 3,676
05.04.2024, 18:19  [ТС]
Цитата Сообщение от wizard41 Посмотреть сообщение
для того что бы что-то делать - надо ясно представлять задачу
куда яснее - оптимальный путь в графе.

Цитата Сообщение от wizard41 Посмотреть сообщение
От вас так и не дождался прояснения
скорее не хватило соображайки чтобы понять очевидное, вон с Г-Д-Е аж дважды переспрашивал и так и не понял наверное до сих пор.

Цитата Сообщение от wizard41 Посмотреть сообщение
Все на уровне непонятных абстракций
каких абстракций? всё написано, нарисовано, разжёвано.

Цитата Сообщение от wizard41 Посмотреть сообщение
мало относящееся к реальному жизненному примеру
а в чем жизненность должна проявляться?

Цитата Сообщение от wizard41 Посмотреть сообщение
Их тьма, написаны давно
а причем здесь отговорки про какие-то там написанные реализации. Вы чётко обозначили свою позицию, так что пишите, или вы трепло и болтун.

Цитата Сообщение от wizard41 Посмотреть сообщение
Но ничто из этого не подойдет вам
если, как вы утверждаете, вы не поняли мою ахинею, то каким образом вы можете дать оценку - подойдёт мне что-то или нет? мистика

Цитата Сообщение от wizard41 Посмотреть сообщение
т.к. вы глубоко заблудились в том что делаете
и на основании чего сделан такой вывод. у меня всё работает, так может всё же вы не понимаете что-то и не в состоянии с этим работать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
05.04.2024, 18:19

Процедура печати всех листьевых узлов бинарного упорядоченного дерева
напишите процедуру печати всех листьевых узлов бинарного упорядоченного дерева,пожалуйста

Вывести все элементы списка в виде списка кортежей, упорядоченного по убыванию по значениям
Разработать класс TotalDict со следующими возможностями: class TotalDict(dict): pass 1. Объект выводит себя в консоли...

Используя производные классы, определить класс упорядоченного списка. Применить его для построения списка объектов типа Текстовая строка
Используя производные классы, определить класс упорядоченного списка. Применить его для построения списка объектов типа Текстовая строка.

Формирование упорядоченного списка из целых чисел; удаление из списка отрицательные чисел и удвоение положительных
Составить программу, которая: • обеспечивает первоначальный ввод целых чисел и формирует из них упорядоченного списка; • затем ...

Создание упорядоченного списка
помогите пожалуйста. я ввожу многочлен (a+bx^3+cx^2+dx). моя процедура выделяет одночлены (a,bx^3,cx^2,dx). Многочлен должен быть...


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

Или воспользуйтесь поиском по форуму:
31
Ответ Создать тему
Новые блоги и статьи
Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ"
Adler 06.10.2026
Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .
ИИ не может найти нужный язык в списке
Supersumestria 05.10.2026
Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO
zorxor 05.10.2026
Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru