Цели: Приобретение навыков работы со сложными структурами данных на примере решения задачи копирования связанных структур данных, называемых в данной работе для краткости графами. Задание: 1.Изучить и реализовать программы примера Factory 2.Придумать способ представления графа (в смысле примера Factory) в текстовом файле и дополнить пример Factory средствами "ввода" и "вывода" графа, т.е. его преобразования из текстового представления в программное и наоборот. Развитие примера следует обеспечить на основе концепции наследования (рекомендуется производный класс назвать NodeFactory2). Представление графа в текстовом файле Формализованное описание разработанного языка описания структуры графа в формате БНФ: <Начальный символ грамматики> ::= <узел>;[{<узел >;}] <узел>::=<идентификатор узла>-><пусто>|<список смежных узлов>; <список смежных узлов>::=<идентификатор узла>[{,<идентификатор узла>}] Шаблон описания связи: %NODE1% -> %NODE2%, ..., %NODEN%; * %NODE% - имя узла связи; * -> - символ наличия связи. Указывает то, что левая %NODE% имеет связь с правой %NODE%; * , - необходим для разделения имён узлов, расположенных с правой стороны от символа -> ; * ; - конец описание связи. Пример: A->B,С; Исходный код: Класс NodeLink package graphi; import java.util.ArrayList; public class NodeLink { Node node; ArrayList<String> links; int numberLinks; NodeLink(Node n) { node = n; links = new ArrayList<String>(); numberLinks = 0; } void addLink(String str) { links.add(numberLinks, str); numberLinks++; }; String getLink(int index) { String str = links.get(index); return str; } } Класс NodeFactory2 package graphi; import java.io.*; import java.util.ArrayList; import java.util.Iterator; public class NodeFactory2 extends NodeFactory{ // рекурсивная функция создания списка объектов класса Link Link addLinks(ArrayList<NodeLink> nls, NodeLink nl, int indexLink) { Link link = null; if (indexLink == (nl.numberLinks-1)) { // Этот блок выполниться если связь // в списке связей является последней String str = nl.links.get(indexLink); for(NodeLink nodelink:nls) if (nodelink.node.data.equals(str)) { link = new Link(nodelink.node); break; } } else { // Если это не последняя связь то эта функция вызовит себя // и рекурсия не окнчится пока не найдется последняя связь Link outLink = addLinks(nls, nl, (indexLink+1) ); String str = nl.links.get(indexLink); for(NodeLink nodelink:nls) if (nodelink.node.data.equals(str)) { link = new Link(nodelink.node,outLink); break; } } return link; } Node buildingGraph(ArrayList<NodeLink> nls) { for (NodeLink nodelink: nls) { if (nodelink.numberLinks!=0){ // функция addLinks будет рекурсивно вызывать саму // себя, пока не создаст список ссылок начиная с конца. // Затем последнюю созданную ссылку присвоет Node nodelink.node.link = addLinks(nls,nodelink,0); } } NodeLink nl = nls.get(0); Node node = nl.node; return node; } public void writeGraph() throws IOException { try { BufferedWriter writer = new BufferedWriter( new FileWriter( new File("D:/graph.txt"))); BiNode p = last.next; while (p != last) { writer.write(p.oldNode.data + "->"); Link q = p.oldNode.link; while (q != null) { writer.write(q.node.data); q = q.link; if (q!=null) writer.write(","); } p = p.next; writer.write(";"); } writer.close(); } catch(IOException ex) { ex.printStackTrace(); } } public Node readGraph() throws IOException { ArrayList<NodeLink> arrayNodeLinks = new ArrayList<NodeLink>(); String line = null; try { BufferedReader reader = new BufferedReader( new FileReader( new File("D:/graph.txt"))); line = reader.readLine(); reader.close(); System.out.println(line); } catch(IOException ex) { ex.printStackTrace(); } // разбиваем строку на несколько связей String[] tokens = line.split(";"); for(String token:tokens) { // разбиваем строку на Node и Link String[] strNodeLinks = token.split("->"); Node node = new Node(strNodeLinks[0]); // создаём обёкт класса NodeLink и добавляем туда Node NodeLink nodelink = new NodeLink(node); // если узел имеет связи if (strNodeLinks.length>1) { String[] strLinks = strNodeLinks[1].split(","); // добавляем все возможные связи for(String strLink:strLinks) nodelink.addLink(strLink); } // сохраняем объект класса NodeLink в массиве arrayNodeLinks.add(nodelink); } Node node = buildingGraph(arrayNodeLinks); return node; } } Класс NodeFactoryDemo package graphi; class NodeFactoryDemo { public static void main(String[] args) { NodeFactory2 f = new NodeFactory2(); Node n1 = GraphSamples.mkNode1(); Node n2 = null; System.out.println("------ n1"); f.view(n1); try{ f.writeGraph(); } catch(Exception ex) { ex.printStackTrace(); } System.out.println("------ n2"); try{ n2 = f.readGraph(); } catch(Exception ex) { ex.printStackTrace(); } f.view(n2); Node n11 = GraphSamples.mkNode2(); Node n12 = null; System.out.println("------ n11"); f.view(n11); try{ f.writeGraph(); } catch(Exception ex) { ex.printStackTrace(); } System.out.println("------ n12"); try{ n12 = f.readGraph(); } catch(Exception ex) { ex.printStackTrace(); } f.view(n12); System.out.println("The END!"); } } Вывод программы: ------ n1 A -> BC B -> C C -> ------ n2 A -> BC B -> C C -> ------ n11 A -> BC B -> C C -> D D -> A ------ n12 A -> BC B -> C C -> D D -> A The END! Файл graph.txt будет содержать последний сохраненный граф: A->B,C;B->C;C->D;D->A; Вывод: ходе лабораторной работы были получены навыки работы со сложными структурами данных, а также с системой ввода/вывода языка Java. 1
1/--страниц