Линейни Структури - Основи

Теория

Линейни Структури от Данни в Java

Линейните структури от данни играят важна роля в програмирането. Те предоставят начини за съхранение и манипулиране на множество от елементи, като предлагат различни модели за достъп и обработка. Най-често използваните линейни структури в Java са масивите, свързаните списъци (LinkedLists), стековете (Stacks) и опашките (Queues).

Свързан Списък (LinkedList)

• Описание: Свързаните списъци са последователност от елементи, разположени произволно в паметта, където всеки елемент сочи към следващия.

• Предимства и Недостатъци:

  • Предимства: Гъвкавост при добавяне и изтриване на елементи.
  • Недостатъци: По-бавен достъп до елементите; използва повече памет за съхранение на адреси.

• Примерен Код:

  LinkedList<String> ll = new LinkedList<String>();
  ll.add("Пример");
  ll.add("за");
  ll.add("LinkedList");
  System.out.println("Съдържание: " + ll);

Динамичен Масив (ArrayList)

• Описание: Динамичният масив е разновидност на масива, който позволява добавяне и изтриване на елементи, като автоматично управлява своя размер.

• Предимства и Недостатъци:

  • Предимства: Гъвкавост; лесен за употреба.
  • Недостатъци: Може да бъде неефективен при чести реалокации на паметта.

• Примерен Код:

  ArrayList<String> arrList = new ArrayList<String>();
  arrList.add("Пример");
  arrList.add("за");
  arrList.add("ArrayList");

Стек (Stack)

• Описание: Стекът е структура от данни, работеща по принципа последен влязъл, първи излязъл (LIFO).

• Примерен Код:

  Stack<String> stack = new Stack<String>();
  stack.push("Последен");
  stack.push("Първи");
  System.out.println("На върха е: " + stack.peek());

Опашка (Queue)

• Описание: Опашката е структура от данни, работеща по принципа първи влязъл, първи излязъл (FIFO).

• Примерен Код:

  Queue<String> queue = new LinkedList<String>();
  queue.offer("Първи");
  queue.offer("Последен");
  System.out.println("На началото е: " + queue.peek());

Заключение

Линейните структури от данни предоставят различни начини за управление на колекции от елементи в Java. В зависимост от нуждите на конкретната задача, програмистите могат да избират между различни структури като списъци, масиви, стекове и опашки, за да оптимизират своите програми. В следващите лекции ще разгледаме по-сложни структури като дървета и хеш таблици.

Сортиране в Линейни Структури от Данни

Сортирането е ключова операция при работа с линейни структури от данни, като списъци и масиви. В Java, сортирането може да се извърши чрез вградените методи в класа Collections или чрез дефиниране на собствени критерии за сортиране с помощта на Comparator интерфейса.

Сортиране с Collections.sort()

Методът Collections.sort() може да се използва за сортиране на обекти от тип List. За да работи, елементите в списъка трябва да имплементират интерфейса Comparable.

Пример:

import java.util.ArrayList;
import java.util.Collections;

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(5);
numbers.add(3);
numbers.add(8);
Collections.sort(numbers); // Сортира във възходящ ред

Сортиране с Comparator

Comparator е интерфейс, който предоставя възможност за дефиниране на собствени правила за сортиране. Той е полезен, когато искаме да сортираме обекти, които не имплементират Comparable, или когато искаме да сортираме по някакъв специфичен, нетрадиционен начин.

Пример:

import java.util.Comparator;

class Person {
    String name;
    int age;
    // Конструктор, getters и setters
}

Comparator<Person> compareByName = new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return p1.getName().compareTo(p2.getName());
    }
};

Collections.sort(peopleList, compareByName); // Сортира хората по име

Сортиране на Обратно

Използвайки Collections.reverseOrder(), можем да сортираме списъци в обратен ред.

Пример:

ArrayList<String> names = new ArrayList<>();
names.add("Анна");
names.add("Иван");
names.add("Георги");
Collections.sort(names, Collections.reverseOrder()); // Сортира в обратен ред

Код

Линейни Структури от Данни в Java

Линейните структури от данни са фундаментални в програмирането и предоставят разнообразни начини за съхранение и манипулиране на данни. Нека разгледаме практически примери на някои основни линейни структури в Java - списъци, стекове и опашки.

Свързан Списък (LinkedList)

Примерът показва създаването на свързан списък, добавяне на елементи и извършване на основни операции:

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<String> linkedList = new LinkedList<>();
        // Добавяне на елементи
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.addFirst("Strawberry");
        linkedList.addLast("Cherry");

        // Извеждане на елементите на списъка
        System.out.println("LinkedList: " + linkedList);

        // Изтриване на елемент
        linkedList.remove("Banana");
        System.out.println("След изтриване: " + linkedList);

        // Достъп до конкретен елемент
        String firstElement = linkedList.getFirst();
        System.out.println("Първи елемент: " + firstElement);
    }
}

Динамичен Масив (ArrayList)

Примерът демонстрира създаването на ArrayList, добавяне, изтриване и обхождане на елементите:

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<String> arrayList = new ArrayList<>();
        // Добавяне на елементи
        arrayList.add("Java");
        arrayList.add("Python");
        arrayList.add(0, "C#");

        System.out.println("ArrayList: " + arrayList);

        // Изтриване на елемент
        arrayList.remove("Python");
        System.out.println("След изтриване: " + arrayList);

        // Обхождане на елементите
        for(String language : arrayList) {
            System.out.println(language);
        }
    }
}

Стек (Stack)

Този пример показва как да се работи със стек - добавяне, изваждане и визуализация на елементите:

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        // Добавяне на елементи
        stack.push("Google");
        stack.push("Apple");
        stack.push("Microsoft");

        // Показване на последния добавен елемент
        System.out.println("На върха на стека е: " + stack.peek());

        // Изваждане на елемент
        while (!stack.isEmpty()) {
            System.out.println("Изваден елемент: " + stack.pop());
        }
    }
}

Опашка (Queue)

Примерът демонстрира използването на Queue за създаване на опашка, добавяне на елементи, извличане и обхождане:

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();

        // Добавяне на елементи в опашката
        queue.offer("Клиент1");
        queue.offer("Клиент2");
        queue.offer("Клиент3");

        System.out.println("Опашка: " + queue);

        // Извличане на елемент от опашката
        while (!queue.isEmpty()) {
            String client = queue.poll();
            System.out.println("Обслужен клиент: " + client);
        }
        
        // След като всички клиенти са обслужени, опашката е празна
        System.out.println("Опашката след обслужване: " + queue);
    }
}

В този пример, използваме LinkedList като реализация на интерфейса Queue. Операциите offer и poll са основните методи за управление на елементите в опашката. offer добавя елемент в края на опашката, докато poll изважда и връща елемента от началото на опашката, премахвайки го от нея.

Сортиране на ArrayList с Comparator

Примерът показва как да сортираме ArrayList на стрингове във възходящ и низходящ ред:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class SortingExample {
    public static void main(String[] args) {
        ArrayList<String> cities = new ArrayList<>();
        cities.add("София");
        cities.add("Пловдив");
        cities.add("Варна");

        // Сортиране във възходящ ред
        Collections.sort(cities);
        System.out.println("Сортирано във възходящ ред: " + cities);

        // Сортиране в низходящ ред
        Collections.sort(cities, Collections.reverseOrder());
        System.out.println("Сортирано в низходящ ред: " + cities);
    }
}

Сортиране на Обекти с Comparator

Можем също така да дефинираме Comparator за сортиране на списък от обекти по определен атрибут:

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public String toString() {
        return name + " (" + age + ")";
    }
}

public class PersonSortingExample {
    public static void main(String[] args) {
        ArrayList<Person> people = new ArrayList<>();
        people.add(new Person("Иван", 30));
        people.add(new Person("Мария", 25));
        people.add(new Person("Георги", 35));

        // Сортиране по име
        Collections.sort(people, new Comparator<Person>() {
            public int compare(Person p1, Person p2) {
                return p1.name.compareTo(p2.name);
            }
        });

        System.out.println("Сортирани по име: " + people);

        // Сортиране по възраст
        Collections.sort(people, new Comparator<Person>() {
            public int compare(Person p1, Person p2) {
                return Integer.compare(p1.age, p2.age);
            }
        });

        System.out.println("Сортирани по възраст: " + people);
    }
}