Глава 16. Линейни структури от данни

Автори

Цвятко Конов

Светлин Наков

В тази тема...

Много често, когато решаваме някоя задача, ни се налага да използваме определена съвкупност от данни (например масив). В зависимост от кон­крет­ната задача ни се налага да прилагаме различни операции върху тази съвкупност от данни. В настоящата тема ще се запознаем с някои от основните представяния на данните в програмирането. Ще видим как при определена задача една структура е по-ефективна и удобна от друга. Ще разгледаме структурите "списък", "стек" и "опашка" и тяхното приложе­ние. Подробно ще се запознаем и с някои от реализациите на тези структури.

Съдържание

• Автори
• В тази тема...
• Абстрактни структури от данни
• Списъчни структури
• Упражнения
• Решения и упътвания
• Дискусионен форум

Видео

Презентация

Абстрактни структури от данни

Преди да се запознаем с класовете в Java, които ни позволяват по лесен начин да работим с някои често използвани структури от данни (като списъци и хеш-таблици), нека първо разгледаме понятията "структури от данни" и "абстрактни структури от данни".

Какво е структура данни?

Много често, когато пишем програми ни се налага да работим с множество от обекти (данни). Понякога добавяме и премахваме елементи, друг път искаме да ги подредим или да обработваме данните по друг специфичен начин. Поради това са изработени различни начини за съхранение на данните в зависимост от задачата, като най-често между елементите съществува някаква наредба (например обект А е преди обект Б).

В този момент на помощ ни идват структурите данни – множество от данни организирани на основата на логически и математически закони. Много често избора на правилната структура прави програмата много по-ефективна – можем да спестим памет и време за изпълнение.

Какво е абстрактен тип данни?

Най-общо абстрактният тип данни (АТД) дава определена дефиниция (абстракция) на конкретната структура т.е. определя допустимите опера­ции и свойства, без да се интересува от конкретната реализация. Това позволява един тип абстрактни данни да има различни реализации, респективно различна ефективност.

Основни структури от данни в програмирането

Могат ясно да се различат няколко групи структури:

-     Линейни – към тях спадат списъците, стековете и опашките

-     Дървовидни – различни типове дървета

-     Речници – хеш-таблици

-     Множества

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

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

Списъчни структури

Най–често срещаните и използвани са линейните (списъчни) структури. Те представляват абстракция на всякакви видове редици, последовател­ности, поредици и други подобни от реалния свят.

Списък

Най–просто можем да си представим списъка като редица от елементи. Например покупките от магазина или задачите за деня представляват списъци. В списъка можем да четем всеки един елементите напр. покупките, както и да добавяме нови покупки в него. Можем спокойно да задраскваме (изтрием) покупки или да ги разместваме.

Абстрактна структура данни "списък"

Нека сега дадем една по-строга дефиниция на структурата списък:

Списък е линейна структура от данни, която съдържа поредица от елементи. Списъкът има свойството дължина (брой елементи) и елемен­тите му са наредени последователно.

Списъкът позволява добавяне елементи на всяко едно място както и премахването им, както и последователното им обхождането. Както споменахме по-горе един АТД може да има няколко реализации. Пример за такъв АТД е интерфейсът java.util.List.

Интерфейсите в Java изграждат една "рамка" за техните имплементации – класовете. Тази рамка представлява съвкупност от методи и свойства, които всеки клас, имплементиращ интерфейса, трябва да реализира (типът данни "интерфейс" в Java ще дискутираме подробно в главата "Принципи на обектно-ориентираното програмиране").

Всеки АТД реално определя някакъв интерфейс. Нека разгледаме интер­фейса java.util.List. Основните методи, които той декларира, са:

-     void add(int, Object) - добавя елемент на предварително избрана позиция

-     boolean contains(Object) – проверява дали елемента се съдържа в списъка

-     Object get(int) – взима елемента на съответната позиция

-     boolean isEmpty() – проверява дали списъка е празен

-     boolean remove(Object) – премахва съответния елемент

-     Object remove(int) – премахва елемента на дадена позиция

-     int indexOf(Object) – връща позицията на елемента

Нека видим няколко от основните реализации на АТД списък и обясним в какви ситуации се използва всяка от тях.

Статичен списък (реализация чрез масив)

Масивите изпълняват много от условията АТД списък, но имат една съществена разлика – списъците позволяват добавяне на нови елементи, докато масивите имат фиксиран размер.

Въпреки това е възможна реализация на списък чрез масив, който автоматично увеличава размера си при нужда (по подобие на класа StringBuilder). Такъв списък се нарича статичен. Ето една имплемен­тация на статичен списък, реализиран чрез разширяем масив:

public class CustomArrayList {     private Object[] arr;     private int count;     private static final int INITIAL_CAPACITY = 4;       /** Initializes the array-based list – allocate memory **/     public CustomArrayList() {         arr = new Object[INITIAL_CAPACITY];         count = 0;     }       /**      * @return the actual list length      */     public int getLength() {         return count;     } }

Първо си създаваме масива, в който ще пазим елементите, както и брояч за това колко имаме в момента. След това добавяме и конструктора, като инициализираме нашия масив с някакъв начален капацитет, за да не се налага да го преоразмеряваме, когато добавим нов елемент. Нека разгле­даме някои от типичните операции:

/**  * Adds element to the list  * @param item - the element you want to add  */ public void add(Object item) {     add(count, item); }   /**  * Inserts the specified element at given position in this list  * @param index -  *        index at which the specified element is to be inserted  * @param item -  *        element to be inserted  * @throws IndexOutOfBoundsException  */ public void add(int index, Object item) {     if (index>count || index<0) {         throw new IndexOutOfBoundsException(             "Invalid index: " + index);     }     Object[] extendedArr = arr;     if (count + 1 == arr.length) {         extendedArr = new Object[arr.length * 2];     }       System.arraycopy(arr, 0, extendedArr, 0, index);            count++;     System.arraycopy(         arr, index, extendedArr, index+1, count-index-1);     extendedArr[index] = item;     arr = extendedArr; }

Реализирахме операцията добавяне на нов елемент, както и вмъкване на нов елемент. Тъй като едната операция е частен случай на другата, методът за добавяне вика този за вмъкване. Ако масивът ни се напълни заделяме два пъти повече място и копираме елементите от стария в новия масив.

Сигурно се чудите какви са тези коментари, оградени със звездички. Това са специални коментари в Java, които могат да се вграждат в програмата и обясняват какво прави всеки клас и всеки метод от класа. Те се наричат Javadoc коментари. Те могат да описва предназначението на методите, техните параметри, връщаната стойност и хвърляните изключения.

Нека се върнем към реализацията на списък чрез масив. Реализираме операциите търсене на елемент, намиране на елемент по индекс, и проверка за това дали даден елемент се съдържа в списъка:

/**  * Returns the index of the first occurrence of the specified  * element in this list.  *  * @param item - the element you are searching  * @return the index of given element or -1 is not found  */ public int indexOf(Object item) {     if (item == null) {         for (int i = 0; i < arr.length; i++) {             if (arr[i] == null)                 return i;         }     } else {         for (int i = 0; i < arr.length; i++)             if (item.equals(arr[i]))                 return i;     }     return -1; }   /**  * Clears the list  */ public void clear() {     arr = new Object[0];     count = 0; }   /**  * Checks if an element exists  * @param item – the item to be checked  * @return if the item exists  */ public boolean contains(Object item) {     int index = indexOf(item);     boolean found = (index != -1);     return found; }   /**  * @return the object on given position  */ public Object elementAt(int index) {     if (index>=count || index<0) {         throw new IndexOutOfBoundsException(             "Invalid index: " + index);     }     return arr[index]; }

Добавяме и операции за изтриване на елементи:

/**  * Removes the element at the specified index  * @param index - the index, whose element you want to remove  * @return the removed element  */ public Object remove(int index) {     if (index>=count || index<0) {         throw new IndexOutOfBoundsException(             "Invalid index: " + index);     }     Object item = arr[index];     System.arraycopy(arr, index+1, arr, index, count-index+1);     arr[count - 1] = null;     count--;     return item; }   /**  * Removes the specified item and returns its index or -1  * if item does not exists  * @param item - the item you want to remove */ public int remove(Object item) {     int index = indexOf(item);     if (index == -1) {         return index;     }     System.arraycopy(arr, index+1, arr, index, count-index+1);     count--;     return index; }

В горните методи премахваме елементи. За целта първо намираме търсения елемент, премахваме го, след което преместваме елементите след него, за да нямаме празно място на съответната позиция.

Нека сега видим как да използваме този наш клас. Добавяме и main() метод, в който ще демонстрираме някои от операциите. Да си направим списък с покупки и да го изведем на екрана. Освен това ще видим дали имаме да купуваме хляб и ще задраскаме маслините:

public static void main(String[] args){     CustomArrayList shoppingList = new CustomArrayList();     shoppingList.add("Milk");     shoppingList.add("Honey");     shoppingList.add("Olives");     shoppingList.add("Beer");     shoppingList.remove("Olives");     System.out.println("We need to buy:");     for(int i=0; i<shoppingList.getLength(); i++) {         System.out.println(shoppingList.elementAt(i));     }     System.out.println("Do we have to buy Bread? " +         shoppingList.contains("Bread")); }

Ето как изглежда изходът от програмата:

Свързан списък (динамична реализация)

Както видяхме, статичният списък има един сериозен недостатък – опера­циите добавяне и премахване от средата на списъка изискват преподреж­дане на елементите. При често добавяне и премахване (особено при голям брой елементи) това може да доведе до ниска производителност. В такива случаи се използват т. нар. свързани списъци. Разликата при тях е в структурата на елементите – докато при статичния списък елементите съдържат само конкретния обект, при динамичния списък елементите пазят информация за следващия елемент. Ето как изглежда свързаният списък в паметта:

За динамичната реализация ще са ни необходими два класа – класът Node – който ще представлява един отделен елемент от списъка и главният клас DynamicList:

/**  * Represents dynamic list implementation  * @author Tsvyatko Konov  * @author Svetlin Nakov  */ public class DynamicList {       private class Node{         Object element;         Node next;                 Node(Object element, Node prevNode) {             this.element = element;             prevNode.next = this;         }                 Node(Object element) {             this.element = element;             next = null;         }     }         private Node head;     private Node tail;     private int count;

Първо виждаме помощния клас Node съдържащ указател към следващия елемент, както и поле за обекта, който пази. Както виждаме класът е вложен в класа DynamicList и следователно може да се достъпва само от него. Отвън такъв клас не съществува. За нашия DynamicList създаваме три полета head – указател към началния елемент, tail – указател към последния елемент и count – брояч за елементите.

Създаваме си и конструктор:

public DynamicList() {     this.head = null;     this.tail = null;     this.count = 0; }

При първоначално конструиране списъкът е празен и затова head = tail = null и count=0.

Ще реализираме всички основни операции: добавяне и премахване на еле­менти, както и търсене на елемент.

Да започнем с операцията добавяне. Тя е относително проста:

/**  * Add element at the end of the list  * @param item - the element you want to add  */ public void add(Object item) {     if (head == null) {         // We have empty list         head = new Node(item);         tail = head;     } else {         // We have non-empty list         Node newNode = new Node(item, tail);         tail = newNode;     }     count++; }

Разглеждат се два случая: празен списък и непразен списък. И в двата случая се стремим да добавим елемента в края на списъка и след добавянето всички променливи (head, tail и count да имат коректни стойности).

Следва операцията изтриване по индекс. Тя е значително по-сложна от добавянето:

/**  * Removes and returns element on the specific index  * @param index - the index of the element you want to remove  * @return the removed element  * @exception IndexOutOfBoundsException - when index is invalid  */ public Object remove(int index) {     if (index>=count || index<0) {         throw new IndexOutOfBoundsException(             "Invalid index: " + index);     }       // Find the element at the specified index     int currentIndex = 0;     Node currentNode = head;     Node prevNode = null;     while (currentIndex < index) {         prevNode = currentNode;         currentNode = currentNode.next;         currentIndex++;     }         // Remove the element     count--;     if (count==0) {         head = null;         tail = null;     } else if (prevNode == null) {         head = currentNode.next;     } else {         prevNode.next = currentNode.next;     }     return currentNode.element; }

Първо се проверява дали посоченият за изтриване индекс съществува и ако не съществува се хвърля подходящо изключение. След това се намира елементът за изтриване чрез придвижване от началото на списъка към следващия елемент index на брой пъти. След като е намерен елементът за изтриване (currentNode), той се изтрива като се разглеждат 3 възможни случая:

-     Списъкът остава празен след изтриването à изтриваме целия списък (head = null; tail = null).

-     Елементът е в началото на списъка (няма предходен) à правим head да сочи елемента веднага след изтрития (или в частност към null, ако няма такъв).

-     Елементът е в средата или в края на списъка à насочваме елемент преди него да сочи към елемента след него (или в частност към null, ако няма следващ).

Следва реализацията на изтриването на елемент по стойност:

Изтриването по стойност на елемент работи като изтриването по индекс, но има 2 особености: търсеният елемент може и да не съществува и това налага допълнителна проверка; в списъка може да има елементи със стойност null, които трябва да предвидим и обработим по специален начин (вижте в кода). За да работи коректно изтриването, е необходимо елементите в масива да са сравними, т.е. да имат коректно реализиран модата equals() от java.lang.Object.

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

Търсенето на елемент работи както в метода за изтриване: започва се отначалото на списъка и се преравят последователно следващите един след друг елементи докато не се стигне до края на списъка.

Останаха още два сравнително лесни метода – достъп до елемент по индекс и извличане на дължината на списъка (броя елементи):

Нека накрая видим нашия пример, този път реализиран чрез динамичен свързан списък.

Както и очакваме, резултатът е същият както при реализацията на списък чрез масив:

Това показва, че можем да реализираме една и съща абстрактна струк­тура от данни по фундаментално различни начини, но в крайна сметка ползвателите на структурата няма да забележат разлика в резултатите при използването й. Единствената разлика ще е в скоростта на работа и в обема на заеманата памет.

Двойно свързани списъци

Съществува и т. нар. двойно свързан списък (двусвързан списък), при който всеки елемент съдържа стойността си и два указателя – към предходен и към следващ елемент (или null, ако няма такъв). Това ни позволява да обхождаме списъка, както напред така и в обратна посока. Това позволява някои операции да бъдат реализирани малко по-лесно. Ето как изглежда двусвързаният списък в паметта:

Класът ArrayList

След като се запознахме с някои от основните реализации на списъците, ще се спрем на класовете в Java, които ни предоставят списъчни струк­тури "на готово". Първият от тях е класът ArrayList, който представлява динамично-разширяем масив. Той е реализиран по сходен начин със статичната реализация на списък, която разгледахме по-горе. Имаме възможност да добавяме, премахваме и търсим елементи. Някои по-важни методи, които можем да използваме са:

-     add(Object) – добавяне на нов елемент

-     add(index, Object) – добавяне елемент на определено място (индекс)

-     size() – връща броя на елементите в списъка

-     remove(Object) – премахване определен елемент

-     remove(index) – премахване на елемента на определено място (индекс)

-     clear() – изчистване на списъка

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

Класът ArrayList – пример

В класа ArrayList можем да записваме всякакви елементи – числа, символни низове и други обекти. Ето един малък пример:

import java.util.ArrayList; import java.util.Date;   public class ArrayListExample {     public static void main(String[] args) {         ArrayList list = new ArrayList();         list.add("Hello");         list.add(5);         list.add(3.14159);         list.add(new Date());                 for (int i=0; i<list.size(); i++) {             Object value = list.get(i);             System.out.printf("Index=%d; Value=%s\n", i, value);         }     } }

В примера създаваме ArrayList и записваме в него няколко елемента от различни типове: String, int, double и Date. След това итерираме по елементите и ги отпечатваме. Ако изпълним примера, ще получим следния резултат:

Index=0; Value=Hello Index=1; Value=5 Index=2; Value=3.14159 Index=3; Value=Sat Nov 29 23:17:01 EET 2008

ArrayList с числа – пример

Ако искаме да си направим масив от числа и след това да обработим числата, примерно да намерим тяхната сума, се налага да преобразуваме типа Object към число, защото ArrayList не може да пази числа и пази винаги обекти. Ето примерен код, който сумира елементите на ArrayList:

ArrayList list = new ArrayList(); list.add(2); list.add(3); list.add(4); int sum = 0; for (int i=0; i<list.size(); i++) {     Integer value = (Integer) list.get(i);     sum = sum + value.intValue(); } System.out.println("Sum = " + sum); // Output: Sum = 9

Ако пуснете горния пример в Eclipse, ще получите множество забележки, идващи от компилатора, които ви напомнят, че ползвате непараметри­зиран тип на данните, което не е добра практика. Преди да ви покажем още примери за работа с класа ArrayList ще да ви запо­знаем с една концепция в Java, наречена "шаблонни типове данни". Тя дава възмож­ност да се параметризират списъците и колекциите в Java и улеснява значително работата с тях.

Шаблонни класове (generics)

Когато използваме класа ArrayList, а и всички класове, имплементиращи интерфейса java.util.List, се сблъскваме с проблема, който видяхме по-горе: когато добавяме нов елемент от даден клас ние го предаваме като обект от тип Object. Когато по-късно търсим даден елемент, ние го получаваме като Object и се налага да го превърнем в изходния тип. Не ни се гарантира, обаче, че всички елементи в списъка ще бъдат от един и същ тип. Освен това превръщането от един тип в друг отнема време, което забавя излишно изпълнението на програмата.

За справяне в описаните проблеми на помощ идват шаблонните класове. Образно казано те са шаблони създадени да работят с един или няколко типа, като при създаването си ние указваме какъв точно тип обекти ще съхраняваме в тях. Създаването на инстанция от даден шаблонен тип, примерно GenericType, става като в счупени скоби се зададе типа, от който трябва да бъдат елементите му:

GenericType<T> instance = new GenericType<T>();

Този тип T може да бъде всеки наследник на класа java.lang.Object, примерно String или Date. Понеже числата не са обекти и не наследяват класа Object, ако трябва да ги използваме като тип в шаблонен клас, трябва да използваме съответния им обвиващ (wrapper) клас. Така вместо примитив­ния тип int трябва да ползваме класа Integer, a вместо типа boolean трябва да ползваме класа Boolean. Ето няколко примера:

ArrayList<Integer> intList = new ArrayList<Integer>(); ArrayList<Boolean> boolList = new ArrayList<Boolean>(); ArrayList<Double> realNumbersList = new ArrayList<Double>();

Нека сега разгледаме някои от шаблонните колекции в Java.

Класът ArrayList<T>

ArrayList<T> е шаблонният вариант на ArrayList. При инициализацията на обект от тип ArrayList<T> указваме типа на елементите, който ще съдържа списъка, т. е. заместваме означения с T тип с някой истински тип данни (например число или стринг).

Например искаме да създадем списък от целочислени елементи. Можем да го направим по следния начин:

ArrayList<Integer> genericList = new ArrayList<Integer>();

Създаденият по този начин списък може да приема като стойности цели числа, но не може и други обекти, например символни низове. Ако се опитаме да добавим към ArrayList<Integer> обект от тип String, ще получим грешка по време на компилация. Чрез шаблонните типове компилаторът на Java ни пази от грешки при работа с колекции.

Забележете, че не посочваме типа int, а неговия обвиващ тип Integer. Причината за това е фактът, че шаблоните приемат като параметър само референтни типове (обекти) и не могат да работят с обикновени стой­ностни типове, които не се пазят в динамичната памет. По тази причина ползването на ArrayList<String> става директно, а ползването на списък от int или double изисква да ползваме съответните обвиващи типове: ArrayList<Integer> и ArrayList<Double>.

Класът ArrayList – представяне чрез масив

Класът ArrayList се представя в паметта като масив, от който една част съхранява елементите му, а останалите са свободни и се пазят като резервни. Благодарение на резервните празни елементи в масива опера­цията добавяне почти винаги успява да добави новия елемент без да разширява (преоразмерява) масива. Понякога, разбира се, се налага преоразмеряване, но понеже всяко преоразмеряване увдвоява размера на масива, това се случва толкова рядко, че може да се пренебрегне на фона на броя добавяния. Можем да си представим един ArrayList като масив, който има някакъв капацитет и запълненост до определено ниво:

Благодарение на резервното пространство в масива, съхраняващ елемен­тите на класа ArrayList<Т>, той е изключително удобна структура от данни, когато е необходимо бързо добавяне на елементи, извличане на всички елементи и пряк достъп до даден елемент по индекс.

Може да се каже, че ArrayList<Т> съчетава добрите страни на списъците и масивите – бързо добавяне, променлив размер и директен достъп по индекс.

Класът ArrayList – истинско представяне в паметта

Ако трябва да сме точни, трябва да отбележим, че горната картинка всъщност не отразява точното представяне на класа ArrayList<T> в паметта. Причината за това е, че в Java няма истински шаблонни типове, а само имитация на такива. Всички шаблонни типове Т изчезват още по време на компилация и се преобразуват в Object, т. е. долните три дефиниции след компилация стават абсолютно еднакви:

ArrayList<Integer> genericList = new ArrayList<Integer>(); ArrayList<Object> objList = new ArrayList<Object>(); ArrayList plainList = new ArrayList ();

Всички параметрирзирани колекции в Java са всъщност колекции от обекти и по тази причина работят по-бавно, отколкото масивите от прими­тивни типове (например int[]). При записването на нов елемент от примитивен тип в ArrayList той се премества в динамичната памет. При достъп до елемент от ArrayList, той се връща като обект и след това може да бъде преобразуван обратно към примитивен тип (например към число).

Нека сме изпълнили следния код:

ArrayList<Integer> list = new ArrayList<Integer>(); list.add(2); list.add(3); list.add(4); list.add(5);

Истинската картинка, която отразява представянето на ArrayList в паметта е следната:

Вижда се, че всяка отделна стойност на списъка от числа е обект от тип Integer, разположен в динамичната памет (heap). В масива се пазят не самите стойности на елементите, а техните адреси (указатели). По тази причина достъпът до елементите на ArrayList<Integer> е по-бавен, отколкото достъпът до елементите на int[].

Кога да използваме ArrayList<T>?

Както вече обяснихме, класът ArrayList<T> използва вътрешно масив за съхранение на елементите, който удвоява размера си, когато се препълни. Тази негова специфика води до следните особености:

-     Търсенето по индекс става много бързо – можем да достъпваме с еднаква скорост всеки един от елементите независимо от общия им брой.

-     Търсенето по стойност на елемент работи с толкова сравнения, колкото са елементите, т.е. не е бързо.

-     Добавянето и премахването на елементи е бавна операция – когато добавяме или премахваме елементи, особено, ако те не се намират в края на списъка, се налага да разместваме всички останали еле­менти, а това е много бавна операция.

-     При добавяне понякога се налага и увеличаване на капацитета на масива, което само по себе си е бавна операция, но се случва много рядко и средната скорост на добавяне на елемент към ArrayList не зависи от броя елементи, т.е. работи много бързо.

Използвайте ArrayList<T>, когато не очаквате често вмъкване и премахване на елементи, но очаквате да добавяте нови елементи в края или ползвате елементите по индекс.

Прости числа в даден интервал – пример

След като се запознахме отвътре с реализацията на структурата списък и класа ArrayList<T>, нека видим как да използваме този клас. Ще разгле­даме проблема за намиране на простите числа в някакъв интервал. За целта ще използваме следния алгоритъм:

public static ArrayList<Integer> getPrimes(int start, int end) {     ArrayList<Integer> primesList = new ArrayList<Integer>();     for (int num = start; num <= end; num++) {         boolean prime = true;         for (int div = 2; div <= Math.sqrt(num); div++) {             if (num % div == 0) {                 prime = false;                 break;             }         }         if (prime)             primesList.add(num);     }     return primesList; }   public static void main(String[] args) {     ArrayList<Integer> primes = getPrimes(200, 300);     for (int p : primes) {         System.out.printf("%d ", p);     }     System.out.println(); }

От математиката знаем, че ако едно число не е просто, то съществува поне един делител в интервала [2 …к орен квадратен от даденото число]. Точно това използваме в примера по-горе. За всяко число търсим дали има делител в този интервал. Ако срещнем, то числото не е просто и можем да продължим със следващото. Постепенно чрез добавяне на прости числа пълним списъка, след което го обхождаме и го извеждаме на екрана. Ето го и изходът от горния код:

Обединение и сечение на списъци – пример

Нека сега разгледаме един по-интересен пример. Имаме за цел да напишем програма, която може да намира обединенията и сеченията на две множества числа.

Обединение                                 Сечение             

          

Можем да приемем, че имаме два списъка и искаме да вземем елементите, които се намират и в двата едновременно (сечение) или търсим тези, които се намират поне в единия от двата (обединение).

Нека разгледаме едно възможно решение на задачата:

public static ArrayList<Integer> union(ArrayList<Integer>         firstList, ArrayList<Integer> secondList) {     ArrayList<Integer> union = new ArrayList<Integer>();         union. addAll(firstList);             for (Integer item : secondList) {         if (!union.contains(item)) {             union.add(item);         }     }     return union; }   public static ArrayList<Integer> intersect(ArrayList<Integer>         firstList, ArrayList<Integer> secondList) {     ArrayList<Integer> intersect = new ArrayList<Integer>();     for (Integer item : firstList) {         if (!secondList.contains(item)) {             intersect.add(item);         }     }     return intersect; }   public static void printList(ArrayList<Integer> list) {     System.out.print("{ ");     for (Integer item : list) {         System.out.print(item);         System.out.print(" ");     }     System.out.println("}"); }   public static void main(String[] args) {     ArrayList<Integer> firstList = new ArrayList<Integer>();     firstList.add(1);     firstList.add(2);     firstList.add(3);     firstList.add(4);     firstList.add(5);     System.out.print("firstList = ");     printList(firstList);       ArrayList<Integer> secondList = new ArrayList<Integer>();     secondList.add(2);     secondList.add(4);     secondList.add(6);     System.out.print("secondList = ");     printList(secondList);       ArrayList<Integer> unionList = union(firstList, secondList);     System.out.print("union = ");     printList(unionList);       ArrayList<Integer> intersectList =         intersect(firstList, secondList);     System.out.print("intersect = ");     printList(intersectList); }

Програмната логика в това решение директно следва определенията за обединение и сечение на множества. Ползваме операциите търсене на елемент в списък и добавяне на елемент към списък.

Ще решим проблема по още един начин: като използваме методите addAll(Collection c) и retainAll(Collection c) от интерфейса java. util.Collection, който ArrayList имплементира:

public static void main(String[] args) {     ArrayList<Integer> firstList = new ArrayList<Integer>();     firstList.add(1);     firstList.add(2);     firstList.add(3);     firstList.add(4);     firstList.add(5);     System.out.print("firstList = ");     printList(firstList);       ArrayList<Integer> secondList = new ArrayList<Integer>();     secondList.add(2);     secondList.add(4);     secondList.add(6);     System.out.print("secondList = ");     printList(secondList);       ArrayList<Integer> unionList = new ArrayList<Integer>();     unionList.addAll(firstList);     unionList.removeAll(secondList);     unionList.addAll(secondList);     System.out.print("union = ");     printList(unionList);       ArrayList<Integer> intersectList = new ArrayList<Integer>();     intersectList.addAll(firstList);     intersectList.retainAll(secondList);     System.out.print("intersect = ");     printList(intersectList); }

За да направим сечение правим следното: слагаме всички елементи от първия списък, след което премахваме всички елементи, които не се съдържат във втория (чрез retainAll()). Обединението правим като добавим елементите от първия списък, след което премахнем всички които се съдържат и в двата (чрез removeAll()), след което добавяме всички елементи от втория списък.

Резултатът и от двете програми изглежда по един и същ начин:

Превръщане на ArrayList в масив и обратното

Тъй като класът ArrayList<T> и масивите много си приличат, често се налага да преобразуваме от ArrayList<T> към масив T[] и обратното. За преобразуването на масив към ArrayList няма стандартен метод или конструктор. За обратното преобразование има системен метод toArray(), но той има някои особености: изисква да му се подаде като параметър резултатният масив и след това да се извърши преобразование на върнатата стойност. Нека видим тези преобразования в действие:

ArrayConversions.java

import java.util.ArrayList; import java.util.Arrays;   public class ArrayConversions {     public static void main(String[] args) {         int[] arr = new int[] {1, 2, 3};                 // Convert the array to ArrayList         ArrayList<Integer> list =             new ArrayList<Integer>(arr.length);         for (int i=0; i<arr.length; i++) {             list.add(arr[i]);         }           // Append new number to the ArrayList         list.add(4);                 // Convert the ArrayList to array         Integer[] ints =                  (Integer[]) list.toArray(new Integer[list.size()]);                 // Print the array         System.out.println(Arrays.toString(ints));     } }

Ако изпълним програмата, ще получим следния резултат:

[1, 2, 3, 4]

За съжаление в Java шаблонните класове и масивите не са измислени добре (както е направено в .NET, JavaScript и PHP) и поради това нямаме директна съвместимост между ArrayList и масив. Остава ни да се надяваме някой ден на Sun и на Java обществото да им дойде акъла и да поправят грешката си. До тогава ще преминаваме междумасиви и списъци ръчно, както в примера по-горе.

Класът LinkedList<T>

Този клас представлява динамична реализация на двусвързан списък. Еле­ментите му пазят информация за обекта, който съхраняват, и указател към следващия и предишния елемент.

Кога да използваме LinkedList<T>?

Видяхме, че динамичната и статичните реализации имат специфика по отношение бързодействие на различните операции. С оглед на структу­рата на свързания списък трябва да имаме предвид следното:

-     Добавянето на елементи в LinkedList става много бързо – незави­симо от броя на елементите.

-     Можем да добавяме бързо в началото и в края на списъка (за разлика от ArrayList<T>).

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

-     Изтриването на елемент е бавна операция, защото включва търсене.

Основни операции в класа LinkedList<T>

LinkedList<T> притежава същите операции като ArrayList<T>, което прави двата класа взаимозаменяеми в зависимост от конкретната задача. По-късно ще видим, че LinkedList<T> се използва и при работа с опашки.

Кога да ползваме LinkedList<T>?

Като цяло класът LinkedList<T> се използва много рядко, защото ArrayList<T> върши същата работа не по-бавно, а предлага в допълнение и други бързи операции.

Стек

Да си представим няколко кубчета, които сме наредили едно върху друго. Можем да слагаме ново кубче на върха, както и да махаме най-горното кубче. Или да си представим една ракла. За да извадим прибраните дрехи или завивки от дъното на раклата, трябва първо да махнем всичко, което е върху тях.

Точно тази конструкция представлява стекът – можем да добавяме еле­менти и да извличаме последният добавен елемент, но не и предход­ните (които са затрупани под него). Стекът е често срещана и използвана структура от данни. Стек се използва и вътрешно от Java виртуалната машина за съхранение на променливите в програмата и параметрите при извикване на метод.

Абстрактна структура данни "стек"

Стекът представлява структура от данни с поведение “последният влязъл първи излиза". Както видяхме в примера с кубчетата, елементите могат да се добавят и премахват само от върха на стека.

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

Статичен стек (реализация с масив)

Както и при статичния списък и можем да използваме масив за пазене на елементите на стека. Можем да имаме индекс или указател, който сочи към елемента, който се намира на върха. Обикновено при запълване на масива следва заделяне на двойно повече памет, както това се случва при статичния списък (ArrayList).

Ето как можем да си представим един статичен стек:

Както и при статичния масив се поддържа свободна буферна памет с цел по-бързо добавяне.

Свързан стек (динамична реализация)

За динамичната реализация ще използваме елементи, които пазят, освен обекта, и указател към елемента, който се намира “по-долу". Тази реализация решава ограниченията, които има статичната реализация както и необходимостта от разширяване на масива при нужда:

Когато стекът е празен, върхът има стойност null. При добавяне на нов елемент, той се добавя на мястото, където сочи върхът, след което върхът се насочва към новия елемент. Премахването става по аналогичен начин.

Класът Stack<T>

В Java можем да използваме класа java.util.Stack<T>, предоставя структурата от данни стек. Използвана е статичната имплементация като вътрешният масив се преоразмерява при необходимост.

Класът Stack<T> – основни операции

Реализирани са всички необходими операции за работа със стек:

-     push(T) – позволява ни добавянето на нов елемент на върха на стека

-     pop() – връща ни най-горния елемент като го премахва от стека

-     peek() – връща най горния елемент без да го премахва

-     size() – връща броя на елементите в стека

-     clear() – премахва всички елементи

-     contains(T) – проверява дали елемента се съдържа в стека

-     toArray() – връща масив, съдържащ елементите от стека

Използване на стек – пример

Нека сега видим един прост пример как да използваме стек. Ще добавим няколко елемента, след което ще ги вземе всички и ще ги изведем на конзолата.

public static void main(String[] args) {     Stack<String> stack = new Stack<String>();     stack.push("1. Ivan");     stack.push("2. Nikolay");     stack.push("3. Maria");     stack.push("4. George");     System.out.println("Top = " + stack.peek());     while (stack.size() > 0) {         String personName = stack.pop();         System.out.println(personName);     } }

Тъй като стекът е структура “последен влязъл – пръв излязъл", програмата ще изведе записите в ред обратен на реда на добавянето. Ето как нейният изход:

Проверка за съответстващи скоби – пример

Да разгледаме следната задача: имаме числов израз, на който искаме да проверим дали броят на отварящите скоби е равен на броя на затваря­щите. Спецификата на стека ни позволява да проверяваме дали скобата, която сме срещнали има съответстваща затваряща. Когато срещнем отва­ряща, я добавяме към стека. При срещане на затваряща вадим елемент от стека. Ако стекът остане празен преди края на програмата, в момент, в който трябва да извадим още един елемент, значи скобите са некоректно поставени. Същото важи и ако накрая в стека останат някакви елементи. Ето една примерна реализация:

public static void main(String[] args) {     String expression =     "1 + (3 + 2 - (2+3) * 4 - ((3+1)*(4-2)))";     Stack<Integer> stack = new Stack<Integer>();     boolean correctBrackets=true;       for (int index = 0; index < expression.length(); index++) {         char ch = expression.charAt(index);         if (ch == '(') {             stack.push(index);         } else if (ch == ')') {             if(stack.isEmpty()){                 correctBrackets=false;                 break;             }             stack.pop();                    }     }     if(!stack.isEmpty())         correctBrackets=false;     System.out.println("Are the brackets correct? " +         correctBrackets); }

Ето как изглежда изходът е примерната програма:

Are the brackets correct? true

Опашка

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

Нека, например, искаме да си купим билет за концерт. Ако отидем по-рано ще си купим едни от билети. Ако обаче се забавим ще трябва да се наредим на опашката и да изчакаме всички желаещи преди нас да си купят билети. Нямаме право да се прередим, защото охраната ще ни се скара. Това поведение е аналогично за обектите в АТД опашка.

Абстрактна структура данни "опашка"

Абстрактната структура опашка изпълнява условието "първият влязъл първи излиза". Добавените елементи се нареждат в края на опашката, а при извличане поредният елемент се взима от началото (главата) й.

Както и при списъка за структурата от данни опашка отново е възможна статична и динамична реализация.

Статична опашка (реализация с масив)

В статичната опашка отново ще използваме масив за пазене на данните. При добавяне на елемент той се добавя на индекса, който следва края, след което края започва да сочи към ново добавения елемент. При премахване на елемент, се взима елемента, към който сочи главата, след което главата започва да сочи към следващия елемент. По този начин опашката се придвижва към края на масива. Когато стигне до края, при добавяне на нов елемент той се добавя на първо място. Ето защо тази имплементация се нарича още зациклена опашка, тъй като мислено залепяме началото и края на масива и опашката обикаля в него:

Свързана опашка (динамична реализация)

Динамичната реализация на опашката много прилича на тази на свързания списък. Елементите отново съдържат две части – обекта и указател към предишния елемент:

Тук обаче елементите се добавят на опашката, а се вземат от главата, като нямаме право да взимаме или добавяме елементи на друго място.

Интерфейсът Queue<T>

В Java се използва динамичната реализация на опашка чрез интерфейса Queue<T>. Както видяхме, интерфейсите декларират определени методи и свойства (т. е. АТД). При инициализация ние използваме класа LinkedList<T>, като му указваме да има пове­дение на опашка, т.е. получаваме имплементация със свързани елементи, която ще притежава методите на характерни за опашка. Тук отново можем да укажем типа на елементите, с които ще работим, тъй като опашката и свързаният списък са шаблонни типове.

Интерфейсът Queue<T> – основни операции

Queue<T> ни предоставя основните операции характерни за структурата опашка. Ето някои от често използваните:

-     offer(T) – добавя елемент накрая на опашката

-     poll() – взима елемента от началото на опашката и го премахва

-     peek() – връща елементът от началото на опашката без да го премахва

-     clear() – премахва всички елементи от опашката

-     contains(Т) – проверява дали елемента се съдържа в опашката

Използване на опашка – пример

Нека сега разгледаме прост пример. Да си създадем една опашка и добавим в нея няколко елемента. След това ще извлечем всички чакащи елементи и ще ги изведем на конзолата:

public static void main(String[] args) {     Queue<String> queue = new LinkedList<String>();     queue.offer("Message One");     queue.offer("Message Two");     queue.offer("Message Three");     queue.offer("Message Four");       while (queue.size() > 0) {         String msg = queue.poll();         System.out.println(msg);     } }

Ето как изглежда изходът е примерната програма:

Message One Message Two Message Three Message Four

Вижда се, че елементите излизат от опашката в реда, в който са постъпили в нея.

Редицата N, N+1, 2*N – пример

Нека сега разгледаме задача, в която използването на структурата опашка ще бъде много полезна за реализацията. Да вземем редицата числа, чиито членове се поличават по-следния начин: първият елемент е N; вторият получаваме като съберем N с 1; третият – като умножим първия с 2 и така последователно умножаваме всеки елемент с 2 и го добавяме накрая на редицата, след което го събираме с 1 и отново го поставяме накрая на редицата. Можем да илюстрираме този процес със следната фигура:

Както виждаме, процесът се състои във взимане на елементи от началото на опашка и поставянето на други в края й. Нека сега видим примерна реализация, в която N=3 и търсим номера на член със стойност 16:

public static void main(String[] args) {     int n = 3;     int p = 16;       Queue<Integer> queue = new LinkedList<Integer>();     queue.offer(n);     int index = 0;     System.out.print("S =");     while (queue.size() > 0) {         index++;         int current = queue.poll();         System.out.print(" " + current);         if (current == p) {             System.out.println();             System.out.println("Index = " + index);             return;         }         queue.offer(current + 1);         queue.offer(2 * current);     } }

Ето как изглежда изходът е примерната програма:

S = 3 4 6 5 8 7 12 6 10 9 16 Index = 11

Както видяхме, стекът и опашката са две специфични структури с опре­делени правила за достъпа до елементите в тях. Опашка използваме, когато очакваме да получим елементите в реда, в който сме ги поставили, а стек – когото елементите ни трябват в обратен ред.

Упражнения

1.  Реализирайте структурата двойно свързан динамичен списък – списък, чиито елементи имат указател, както към следващия така и към пред­хождащия го елемент. Реализирайте операциите добавяне, премахване и търсене на елемент, добавяне на елемент на определено място (индекс), извличане на елемент по индекс и метод, който връща масив с елементите на списъка.

2.  Създайте клас DynamicStack представляващ динамична реализация на стек. Добавете методи за необходимите операции.

3.  Реализирайте структурата дек. Това е специфична струк­тура, позволя­ваща елементи да бъдат добавяни и премахвани от двата й края. Нека освен това, елемент поставен от едната страна да може да бъде премахнат само от същата. Реализирайте операции за премах­ване добавяне и изчистване на дека. При невалидна операция пода­вайте подходящо изключение.

4.  Реализирайте структурата “зациклена опашка" с масив, който при нужда удвоява размера си. Имплементирайте необходимите методи за добавяне към опашката, извличане на елемента, който е наред и поглеждане на елемента, който е наред, без да го премахвате от опашката. При невалидна операция пода­вайте подходящо изключение.

5.  Реализирайте сортиране на числа в динамичен свързан списък, без да използвате допълнителен масив.

6.  Използвайки опашка реализирайте пълно обхождане на всички дирек­тории на твърдия ви диск и ги отпечатвайте на конзолата. Реализи­райте алгоритъма "обхождане в ширина" – Breadth-First-Search (BFS) – може да намерите стотици статии за него в Интернет.

7.  Използвайки опашка реализирайте пълно обхождане на всички дирек­тории на твърдия ви диск и ги отпечатвайте на конзолата. Реализи­райте алгоритъма "обхождане в дълбочина" – Depth-First-Search (DFS) – може да намерите стотици статии за него в Интернет.

Решения и упътвания

1.  Вижте динамичната реализация на едносвързан списък, която разгле­дахме в секцията "Свързан списък".

2.  Вижте динамичната реализация на едносвързан списък, която разгле­дахме в секцията "Свързан списък".

3.  Използвайте два стека с общо дъно. По този начин, ако добавяме елементи отляво на дека ще влизат в левия стек, след което ще могат да бъдат премахнати отново оттам. Аналогично за десния стек.

4.  Използвайте масив. Когато стигнем до последния индекс ще добавим следващия елемент в началото на масива. За точното пресмятане на индексите използвайте остатък от делене на дължината на масива. При нужда от преоразмеряване на масива можете да го направите по ана­логия с реализираното преоразмеряване в секцията "Статичен списък".

5.  Използвайте просто сортиране по метода на мехурчето. Започваме от най левия елемент, като проверяваме дали е по-малък от следващия. Ако не, им сменяме местата. После сравняваме със следващия и т.н. докато достигнем до такъв, който е по-голям от него или не стигнем края на масива. Връщаме се в началото и взимаме пак първия като повтаряме процедурата. Ако първият е по-малък, взимаме следващия и започваме да сравняваме. Повтаряме тези операции докато не стигнем до момент, в който сме взели последователно всички елементи и на нито един не се наложило да бъде преместен.

6.  Алгоритъмът е много лесен: започваме от празна опашка, в която слагаме коренната директория (от която стартира обхождането). След това докато опашката не остане празна, изваждаме от нея поредната директория, отпечатваме я и прибавяме към опашката всички нейни поддиректории. По този начин ще обходим файловата система в шири­на. Ако в нея няма цикли (както е под Windows), процесът ще е краен.

7.  Ако в решението на предната задача заместим опашката със стек, ще получим обхождане в дълбочина. Хитро, нали?

Дискусионен форум

Коментирайте книгата и задачите в нея във: форума на софтуерната академия.