Введение в Java
Урок 33. Инверсия списка
На этом уроке мы рассморим с вами решение классической задачи - инверсии (т. е. размещению элементов в обратном порядке) списка. Список устроен следующим образом: каждый элемент списка содаржит, во-первых, собственные данные и, во-творых, содержить ссылку на следущий элемент списка. Если следующего элемента списка нет, то в ссылке на следующий элемент содержится null. Вот тык выглядит код:
public class ListReverse
{
// Ссылка на следующий элемент списка.
public ListReverse next = null;
// Данные.
public int data = 0;
// Конструктор.
public ListReverse(ListReverse next, int data)
{
this.next = next;
this.data = data;
}
}
Как видно из кода, мы назвали наш класс ListReverse. В нем есть ссылка на следующий экземпляр класса ListReverse, у того на следующий и т. п.. У последнего в списке эта ссылка равна null.
Так как нам надо показывать для проверки содержимое нашего списка до и после инверсии, то напишем метод showAll, который будет показывать все элементы списка, задаваемого своим первым элементом. Для того, чтобы не плодить классы, мы поместим этод метод прямо в наш класс ListReverse, и следаем его статическим. При этом список, подлежащий показу, мы передадим в качестве параметра:
static public void showAll(ListReverse list)
{
// Если список пуст.
if(list == null)
{
System.out.println("List is empty");
return;
}
// Пробегаем все лементы списка.
ListReverse curr = list;
while (curr != null){
System.out.println(curr.data);
curr = curr.next;
}
}
Этот метод мы пометим прямо в класс ListReverse.
Теперь пишем метод для инверсии. Его мы тоже сделаем статическим методом класса ListReverse, и в качестве параметра в него будет передаваться список для инверсии, а в качестве возвращаемого значения - отинверсированный список. Вот его код:
static public ListReverse reverse(ListReverse list)
{
// Если список пуст или содердит только один элемент.
if(list == null || list.next == null)
{
return list;
}
// Если в списке больше одного элемента,
// то заводим вспомогательные переменные
// и переменную для результата (res).
ListReverse aux0 = list;
ListReverse res = list.next;
ListReverse aux1 = list.next;
// Этот элемент будет в инвертированном списке последним.
aux0.next = null;
// Пробегаем весь список.
while(aux1.next != null){
aux1 = aux1.next;
res.next = aux0;
aux0 = res;
res = aux1;
};
res.next = aux0;
return res;
}
С классом ListReverse все. Теперь напишем класс для проверки. Вот его код:
public class ListReverseTest {
public static void main(String[] args) {
// Создаем список a.
// Последний элемент списка.
ListReverse a = new ListReverse(null, 0);
a = new ListReverse(a, 1);
a = new ListReverse(a, 22);
a = new ListReverse(a, -441);
// Показ элементов списка до инверсии.
ListReverse.showAll(a);
// Инверсия списка.
a = ListReverse.reverse(a);
// Показ элементов списка после инверсии.
ListReverse.showAll(a);
}
}
Результатом программы будет, естественно, -441 22 1 0 0 1 22 -441.
|
