Необходимо реализовать функции сериализации и десериализации данных двусвязного списка, который имеет структуру, представленную ниже:
class ListNode
{
public ListNode Prev;
public ListNode Next;
public ListNode Rand;
public string Data;
}class ListRand
{
public ListNode Head;
public ListNode Tail;
public int Count;
public void Serialize(FileStream s)
{
}
public void Deserialize(FileStream s)
{
}
}Важными условиями сериализации является:
- взаимное соотношение его элементов между собой — в том числе ссылок на Rand элементы
- алгоритмическая сложность решения должна быть меньше квадратичной
- нельзя добавлять новые поля в исходные классы ListNode и ListRand
- тест нужно выполнить без использования библиотек или стандартных средств сериализации
Для выполнения задания можно использовать любой общеиспользуемый язык. В моём случае решение было реализовано на языке C#.
Собираем ноды, затем наполняем их данными. Для сравнения нод и данных, которые хранятся в них, использовал контрольную сумму через GetHashCode().
// Create doubly-linked list with 5 nodes and 3 random refs
var cons = new NodeConstructor(5, 3);
var deployer = new NodeDeployer(cons);
deployer.Deploy();Создаем экземпляр класса ListRand.
var listRand = new ListRand
{
Head = cons.Head,
Tail = cons.Tail,
Count = cons.Size
};Затем запускаем методы Serialize() и Deserialize(), передавая FileStream. Для проверки работы алгоритма был написан подручный класс NodeInspector.
// Serialization of deployed nodes
const string path = @"..\..\..\Data\data.dat";
var fsWrite = new FileStream(path, FileMode.Create);
listRand.Serialize(fsWrite);
NodeInspector.HardInspectByNodesForward(listRand.Head);
// Deserialization of deployed nodes
var fsRead = new FileStream(path, FileMode.Open);
listRand.Deserialize(fsRead);
NodeInspector.HardInspectByNodesForward(listRand.Head);Алгоритм сериализации данных построен на сборке всех нод в словарь. Где потом, при записи в файл мы ссылки на случайные элементы списка заменяем индексом этой ноды их словаря. Если же нет ссылки на случайный элемент, то заменяем значением-флагом -1.
for (var (curr, index) = (Head, 0); curr != null; curr = curr.Next, index++)
{
nodes.Add(curr, index);
}writer.Write(curr.Data);
writer.Write(curr.Rand != null ? nodes[curr.Rand] : -1);Для десериализации используется обратный алгоритм, но с небольшим исключением. Ссылки на рандомные элементы списка появляются после полного анализа данных.
for (var (curr, i) = (Head, 0); curr != null && i < Count; curr = curr.Next, i++)
{
curr.Rand = rawNodes[i].randIndex != -1 ? nodes[rawNodes[i].randIndex] : null;
// Check for (-1) flag in data, then pass null to field
}Правильность структуры списка можно проверить по контрольной сумме хешей, в поле Data.
Nodes constructed. Size: 5, Rands: 3
Nodes deployed.
Head: #32854180, Tail: #02606490
Serialization of ListNodes complete.
Node: #32854180, Prev: #00000000, Next: #27252167, Rand: #32854180, Data: (32854180)
Node: #27252167, Prev: #32854180, Next: #43942917, Rand: #27252167, Data: (27252167)
Node: #43942917, Prev: #27252167, Next: #59941933, Rand: #32854180, Data: (43942917)
Node: #59941933, Prev: #43942917, Next: #02606490, Rand: #00000000, Data: (59941933)
Node: #02606490, Prev: #59941933, Next: #00000000, Rand: #00000000, Data: (02606490)
Deserialization is finished.
Node: #09799115, Prev: #00000000, Next: #21083178, Rand: #09799115, Data: (32854180)
Node: #21083178, Prev: #09799115, Next: #55530882, Rand: #21083178, Data: (27252167)
Node: #55530882, Prev: #21083178, Next: #30015890, Rand: #09799115, Data: (43942917)
Node: #30015890, Prev: #55530882, Next: #01707556, Rand: #00000000, Data: (59941933)
Node: #01707556, Prev: #30015890, Next: #00000000, Rand: #00000000, Data: (02606490)
Nodes constructed. Size: 10, Rands: 10
Nodes deployed.
Head: #32854180, Tail: #30015890
Serialization of ListNodes complete.
Node: #32854180, Prev: #00000000, Next: #27252167, Rand: #32854180, Data: (32854180)
Node: #27252167, Prev: #32854180, Next: #43942917, Rand: #09799115, Data: (27252167)
Node: #43942917, Prev: #27252167, Next: #59941933, Rand: #27252167, Data: (43942917)
Node: #59941933, Prev: #43942917, Next: #02606490, Rand: #21083178, Data: (59941933)
Node: #02606490, Prev: #59941933, Next: #23458411, Rand: #32854180, Data: (02606490)
Node: #23458411, Prev: #02606490, Next: #09799115, Rand: #02606490, Data: (23458411)
Node: #09799115, Prev: #23458411, Next: #21083178, Rand: #43942917, Data: (09799115)
Node: #21083178, Prev: #09799115, Next: #55530882, Rand: #59941933, Data: (21083178)
Node: #55530882, Prev: #21083178, Next: #30015890, Rand: #27252167, Data: (55530882)
Node: #30015890, Prev: #55530882, Next: #00000000, Rand: #30015890, Data: (30015890)
Deserialization is finished.
Node: #15368010, Prev: #00000000, Next: #04094363, Rand: #15368010, Data: (32854180)
Node: #04094363, Prev: #15368010, Next: #36849274, Rand: #63208015, Data: (27252167)
Node: #36849274, Prev: #04094363, Next: #32001227, Rand: #04094363, Data: (43942917)
Node: #32001227, Prev: #36849274, Next: #19575591, Rand: #41962596, Data: (59941933)
Node: #19575591, Prev: #32001227, Next: #42119052, Rand: #15368010, Data: (02606490)
Node: #42119052, Prev: #19575591, Next: #63208015, Rand: #19575591, Data: (23458411)
Node: #63208015, Prev: #42119052, Next: #41962596, Rand: #36849274, Data: (09799115)
Node: #41962596, Prev: #63208015, Next: #43527150, Rand: #32001227, Data: (21083178)
Node: #43527150, Prev: #41962596, Next: #56200037, Rand: #04094363, Data: (55530882)
Node: #56200037, Prev: #43527150, Next: #00000000, Rand: #56200037, Data: (30015890)