Решение задачи сериализации дерева на C#

Опубликовано May 8, 2012 в Загрузка кода проектов, Наши старые тестовые задания, Тестовые проекты (2-3 часа) | 6 коммент.

, ,

Решение задачи сериализации дерева на C#

В посте Сериализация дерева сформулировано условие задачи о сериализации/десериализации дерева. Здесь будет приведен один из возможных вариантов ее решения на языке C#. Решение это интересно тем, что будут использованы стандартные средства языка и продемонстрирован подход, который непосредственно применить в C++ не представляется возможным. Таким образом, будет продемонстрирована разница в возможностях двух языков и умение ею пользоваться для наиболее эффективного решения задач.

Итак, предлагается сериализация дерева в текстовый файл в XML формате, так как для этого в языке имеются готовые средства настолько мощные, что писать код собственно методов сериализации нет необходимости, а нужно только знать возможности стандартной сериализации и уметь грамотно ими воспользоваться. Для демонстрации достаточно ограничиться двумя производными классами, исключив DoubleHolder, а CharArrayHolder естественным образом заменить классом StringHolder, поле данных которого имеет обычный тип string.

Замечания и упрощения

С целью экономии времени, а так же для того, чтобы сконцентрироваться на сути задачи, в решении допущены определенные упрощения и отступления от канонов. А именно:

  • Во всех классах все поля объявлены с модификатором public.
  • Отсутствует обработка исключений.
  • Работа с файлами упрощена до предела, имя файла задается хардкодом, обработка ошибок отсутствует.
  • Поле ID (ключ для узла) добавлено в базовый класс в целях иллюстрации – по условию оно не нужно, но, возможно, что кто-то захочет его ввести, создавая свой собственный алгоритм сериализации/десериализации, основанный на использовании уникальных ключей узлов.
  • Рассуждения по поводу выбора оптимального типа данных для строковых значений (например, StringBuilder) считаются выходящими за рамки задачи.
  • Комментарии и объяснения опущены, предполагается, что текст программы является в достаточной степени самодокументированным, а относящаяся к делу теория легко обнаружится по ссылке MSDN base topic reference.

Код решения задачи сериализации дерева на C#

 
//MSDN base topic reference http://msdn.microsoft.com/ru-ru/library/3z3z5s6h.aspx
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Xml;
using System.Xml.Serialization;
 
    public class BaseHolder
    {
        public int ID;
        public List<BaseHolder> Next = new List<BaseHolder>();
    }
 
    public class Tree
    {
        public BaseHolder TreeRoot;
    }
 
    public class StringHolder : BaseHolder
    {
        public StringHolder() { }
 
        public string Data;
    }
 
    public class IntHolder : BaseHolder
    {
        public IntHolder() { }
 
        public int Data;
    }
 
    public class Run
    {
        public static void Main()
        {
            Run test = new Run();
 
            XmlAttributeOverrides attrOverrides = new XmlAttributeOverrides();
 
            Tree Tree = test.TestTreeCreation();
 
            string filename = "d:\\Tree.xml";
 
            attrOverrides = test.PrepareOverriddenAttributes();
 
            test.WrightSerializedTree(filename, attrOverrides, Tree);
 
            Tree NewTree = test.ReadSerializedTree(filename, attrOverrides);
        }
 
         private XmlAttributeOverrides PrepareOverriddenAttributes()
        {
            XmlAttributeOverrides attrOverrides = new XmlAttributeOverrides();
            XmlAttributes attrs = new XmlAttributes();
 
            /* Override the BaseHolder class.*/
            XmlElementAttribute attr = new XmlElementAttribute("Alumni", typeof(StringHolder));
            attrs.XmlElements.Add(attr);
 
            XmlElementAttribute attr1 = new XmlElementAttribute("Alumnu", typeof(IntHolder));
            attrs.XmlElements.Add(attr1);
 
            attrOverrides.Add(typeof(Tree), "TreeRoot", attrs);
 
            return attrOverrides;
        }
 
        private void WrightSerializedTree(string filename, XmlAttributeOverrides attrOverrides, Tree Tree)
        {
            TextWriter myStreamWriter = new StreamWriter(filename);
 
            XmlSerializer mySerializer = new XmlSerializer (typeof(Tree), attrOverrides);
 
            mySerializer.Serialize(myStreamWriter, Tree);
            myStreamWriter.Close();
        }
 
        private Tree ReadSerializedTree(string filename, XmlAttributeOverrides attrOverrides)
        {
            XmlSerializer readSerializer = new XmlSerializer(typeof(Tree), attrOverrides);
 
            FileStream fs = new FileStream(filename, FileMode.Open);
 
            Tree Tree = new Tree();
            Tree = (Tree)readSerializer.Deserialize(fs);
            fs.Close();
            return Tree;
        }
 
        private Tree TestTreeCreation()
        {
            Tree Tree = new Tree();
 
            //Creating simple tesing data
            StringHolder g1 = new StringHolder();
            g1.ID = 1;
            g1.Data = "Alma Mater";
 
            StringHolder g2 = new StringHolder();
            g2.ID = 2;
            g2.Data = "CM";
            g2.Next = null;
            g1.Next.Add((BaseHolder)g2);
 
            IntHolder g3 = new IntHolder();
            g3.ID = 3;
            g3.Data = 333;
            g1.Next.Add((BaseHolder)g3);
 
            StringHolder g4 = new StringHolder();
            g4.ID = 4;
            g4.Data = "UNI444";
            g4.Next = null;
            g3.Next.Add((BaseHolder)g4);
 
            IntHolder g5 = new IntHolder();
            g5.ID = 5;
            g5.Data = 555;
            g5.Next = null;
            g3.Next.Add((BaseHolder)g5);
 
            Tree.TreeRoot = g1;
            return Tree;
        }
 
    }

Улучшенный код C#

using System.Collections.Generic;
using System.IO;
using System.Xml.Serialization;
 
    public class BaseHolder
    {
        public int ID;
        public List<BaseHolder> Child = new List<BaseHolder>();
    }
 
    public class Tree
    {
        public BaseHolder TreeRoot;
    }
 
    public class StringHolder : BaseHolder
    {
        public string Data;
    }
 
    public class IntHolder : BaseHolder
    {
        public int Data;
    }
 
    public class DoubleHolder : BaseHolder
    {
        public double Data;
    }
 
    public class Run
    {
        public static void Main()
        {
            var tree = TestTreeCreation();
 
            const string filename = "d:\\Tree.xml";
 
            var attrOverrides = PrepareOverriddenAttributes();
 
            WrightSerializedTree(filename, attrOverrides, tree);
 
            var newTree = ReadSerializedTree(filename, attrOverrides);
 
            WrightSerializedTree(@"d:\\newTree.xml", attrOverrides, newTree);
        }
 
         private static XmlAttributeOverrides PrepareOverriddenAttributes()
        {
            var attrOverrides = new XmlAttributeOverrides();
            var attrs = new XmlAttributes();
 
            /* Override the BaseHolder class.*/
            var attr = new XmlElementAttribute("Alumni", typeof(StringHolder));
            attrs.XmlElements.Add(attr);
 
            var attr1 = new XmlElementAttribute("Alumnu", typeof(IntHolder));
            attrs.XmlElements.Add(attr1);
 
            var attr2 = new XmlElementAttribute("Alumnd", typeof(DoubleHolder));
            attrs.XmlElements.Add(attr2);
 
            attrOverrides.Add(typeof(Tree), "TreeRoot", attrs);
 
            return attrOverrides;
        }
 
        private static void WrightSerializedTree(string filename, XmlAttributeOverrides attrOverrides, Tree tree)
        {
            var myStreamWriter = new StreamWriter(filename);
 
            var mySerializer = new XmlSerializer (typeof(Tree), attrOverrides);
 
            mySerializer.Serialize(myStreamWriter, tree);
            myStreamWriter.Close();
        }
 
        private static Tree ReadSerializedTree(string filename, XmlAttributeOverrides attrOverrides)
        {
            var readSerializer = new XmlSerializer(typeof(Tree), attrOverrides);
 
            var fs = new FileStream(filename, FileMode.Open);
 
            var tree = (Tree)readSerializer.Deserialize(fs);
            fs.Close();
            return tree;
        }
 
        private static Tree TestTreeCreation()
        {
            var tree = new Tree();
 
            //Creating simple tesing data
            var g1 = new StringHolder {ID = 1, Data = "Alma Mater"};
 
            var g2 = new StringHolder {ID = 2, Data = "CM"};
            g1.Child.Add(g2);
 
            var g3 = new IntHolder {ID = 3, Data = 333};
            g1.Child.Add(g3);
 
            var gDouble = new DoubleHolder {ID = 6, Data = 66.66 };
            g1.Child.Add(gDouble);
 
            var g4 = new StringHolder {ID = 4, Data = "UNI444"};
            g3.Child.Add(g4);
 
            var g5 = new IntHolder {ID = 5, Data = 555};
            g3.Child.Add(g5);
 
            tree.TreeRoot = g1;
            return tree;
        }
    }

Результат - сравнение файлов сериализованных деревьев


Автор публикации: