Читайте также:
|
Тема: «Классы связанных списков в приложениях Java».
Целью лабораторной работы является освоение навыков:
· объявления структуры связанного списка;
· организации интерфейсов для работы со списками;
· организации возможностей добавления и удаления элементов списка.
Задание: Разработать программу, в которой осуществляется построение связанных списков и операции с ними.
Текст Java – программы
public class LinkedList {
/**
* Интерфейс, определяющий методы для организации списков
**/
public interface Linkable {
public Linkable getNext(); // Возвращает следующий элемент списка
public void setNext(Linkable node); // Устанавливает следующий элемент
//списка
}
// У этого класса есть принимаемый по умолчанию конструктор:
// public LinkedList() {}
/** Поле класса, содержащее первый элемент списка */
Linkable head;
/** Возвращение первого узла списка */
public synchronized Linkable getHead() { return head; }
/** Вставляет узел в начало списка */
public synchronized void insertAtHead(Linkable node) {
node.setNext(head);
head = node;
}
/** Вставляет узел в конец списка */
public synchronized void insertAtTail(Linkable node) {
if (head == null) head = node;
else {
Linkable p, q;
for(p = head; (q = p.getNext())!= null; p = q) /* пустой цикл */;
p.setNext(node);
}
}
/** Удаляет и возвращает узел, находящийся в начале списка */
public synchronized Linkable removeFromHead() {
Linkable node = head;
if (node!= null) {
head = node.getNext();
node.setNext(null);
}
return node;
}
/** Удаляет и возвращает узел, находящийся в конце списка */
public synchronized Linkable removeFromTail() {
if (head == null) return null;
Linkable p = head, q = null, next = head.getNext();
if (next == null) {
head = null;
return p;
}
while((next = p.getNext())!= null) {
q = p;
p = next;
}
q.setNext(null);
return p;
}
/**
* Удаляет из списка узел, совпадающий с заданным.
* Для проверки на == совпадение используется метод equals().
**/
public synchronized void remove(Linkable node) {
if (head == null) return;
if (node.equals(head)) {
head = head.getNext();
return;
}
Linkable p = head, q = null;
while((q = p.getNext())!= null) {
if (node.equals(q)) {
p.setNext(q.getNext());
return;
}
p = q;
}
}
/** Класс с методом main() для тестирования LinkedList */
public static class Test {
/**
* Тестовый класс, реализующий интерфейс Linkable
**/
static class LinkableInteger implements Linkable {
int i; // Данные, содержащиеся в узле
Linkable next; // Ссылка на следующий узел списка
public LinkableInteger(int i) { this.i = i; } // Конструктор
public Linkable getNext() { return next; } // Часть Linkable
public void setNext(Linkable node) { next = node; } // Linkable
public String toString() { return i + ""; } // для вывода
public boolean equals(Object o) { // для сравнения
if (this == o) return true;
if (!(o instanceof LinkableInteger)) return false;
if (((LinkableInteger)o).i == this.i) return true;
return false;
}
}
/**
* Вставляет несколько узлов, удаляет и выводит элементы списка
**/
public static void main(String[] args) {
LinkedList ll = new LinkedList(); // Создание списка
ll.insertAtHead(new LinkableInteger(1)); // вставка данных
ll.insertAtHead(new LinkableInteger(2));
ll.insertAtHead(new LinkableInteger(3));
ll.insertAtHead(new LinkableInteger(4));
ll.insertAtTail(new LinkableInteger(5));
ll.insertAtTail(new LinkableInteger(6));
System.out.println(ll.removeFromHead()); // удаление и вывод узла
System.out.println(ll.removeFromTail()); // удаление и вывод узла
ll.remove(new LinkableInteger(2)); // удаление узла
// Вывод содержимого списка.
for(Linkable l = ll.getHead(); l!= null; l = l.getNext())
System.out.println(l);
}
}
}
Дата добавления: 2015-09-11; просмотров: 70 | Поможем написать вашу работу | Нарушение авторских прав |