close

Вход

Забыли?

вход по аккаунту

?

lab2 volodin

код для вставкиСкачать
 Цели: Приобретение навыков работы со сложными структурами данных на примере решения задачи копирования связанных структур данных, называемых в данной работе для краткости графами.
Задание:
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
Документ
Категория
Рефераты
Просмотров
11
Размер файла
31 Кб
Теги
lab2, volodin
1/--страниц
Пожаловаться на содержимое документа