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

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

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

Съдържание

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

Видео

Презентация

Мисловни карти

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

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

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

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

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

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

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

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

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

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

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

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

-     Множества

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

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

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

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

Списък

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

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

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

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

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

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

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

-     int Add(object) - добавя елемент в края на списъка

-     void Insert(int, object) - добавя елемент на предварително избрана позиция в списъка

-     void Clear() – изтрива всички елементи от списъка

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

-     void Remove(object) – премахва съответния елемент

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

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

-     this[int] – индексатор, позволява достъп на елементите по подадена позиция

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

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

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

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

public class CustomArrayList {       private object[] arr;         private int count;         /// <summary>       /// Returns the actual list length       /// </summary>       public int Count       {             get             {                   return count;             }       }         private static readonly int INITIAL_CAPACITY = 4;         /// <summary>       /// Initializes the array-based list – allocate memory       /// </summary>       public CustomArrayList()       {             arr = new object[INITIAL_CAPACITY];             count = 0;       }

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

/// <summary> /// Adds element to the list /// </summary> /// <param name="item">The element you want to add</param> public void Add(object item) {       Insert(count, item); }   /// <summary> /// Inserts the specified element at а given /// position in this list /// </summary> /// <param name="index"> /// Index, at which the specified element is to be inserted /// </param> /// <param name="item">Element to be inserted</param> /// <exception cref="System.IndexOutOfRangeException">Index is invalid</exception> public void Insert(int index, object item) {       if (index > count || index < 0)       {             throw new IndexOutOfRangeException(                   "Invalid index: " + index);       }       object[] extendedArr = arr;       if (count + 1 == arr.Length)       {             extendedArr = new object[arr.Length * 2];       }       Array.Copy(arr, extendedArr, index);       count++;       Array.Copy(arr, index, extendedArr, index + 1, count - index - 1);       extendedArr[index] = item;       arr = extendedArr; }

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

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

/// <summary> /// Returns the index of the first occurrence /// of the specified element in this list. /// </summary> /// <param name="item">The element you are searching</param> /// <returns> /// The index of given element or -1 is not found /// </returns> public int IndexOf(object item) {       for (int i = 0; i < arr.Length; i++)       {             if (item == arr[i])             {                   return i;             }       }         return -1; }   /// <summary> /// Clears the list /// </summary> public void Clear() {       arr = new object[INITIAL_CAPACITY];       count = 0; }   /// <summary> /// Checks if an element exists /// </summary> /// <param name="item">The item to be checked</param> /// <returns>If the item exists</returns> public bool Contains(object item) {       int index = IndexOf(item);       bool found = (index != -1);       return found; }   /// <summary> /// Retrieves the element on the set index /// </summary> /// <param name="index">Index of the element</param> /// <returns>The element on the current position</returns> public object this[int index] {       get       {             if (index >= count || index < 0)             {                   throw new ArgumentOutOfRangeException(                         "Invalid index: " + index);             }             return arr[index];       }       set       {             if (index >= count || index < 0)             {                   throw new ArgumentOutOfRangeException(                         "Invalid index: " + index);             }             arr[index] = value;       } }

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

/// <summary> /// Removes the element at the specified index /// </summary> /// <param name="index"> /// The index, whose element you want to remove /// </param> /// <returns>The removed element</returns> public object Remove(int index) {       if (index >= count || index < 0)       {             throw new ArgumentOutOfRangeException(                   "Invalid index: " + index);       }         object item = arr[index];       Array.Copy(arr, index + 1, arr, index, count - index + 1);       arr[count - 1] = null;       count--;         return item; }   /// <summary> /// Removes the specified item /// </summary> /// <param name="item">The item you want to remove</param> /// <returns>Item index or -1 if item does not exists</returns> public int Remove(object item) {       int index = IndexOf(item);       if (index == -1)       {             return index;       }         Array.Copy(arr, index + 1, arr, index, count - index + 1);       count--;         return index; }

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

Нека сега разгледаме примерна употреба на класа, който току що създадохме. Добавен е и Main() метод, в който ще демонстрираме някои от операциите. В приложения код първо създаваме списък с покупки, а после го извеждаме на екрана. След това ще задраскаме маслините и ще проверим дали имаме да купуваме хляб.

public static void Main() {       CustomArrayList shoppingList = new CustomArrayList();       shoppingList.Add("Milk");       shoppingList.Add("Honey");       shoppingList.Add("Olives");       shoppingList.Add("Beer");       shoppingList.Remove("Olives");       Console.WriteLine("We need to buy:");       for (int i = 0; i < shoppingList.Count; i++)       {             Console.WriteLine(shoppingList[i]);       }       Console.WriteLine("Do we have to buy Bread? " +             shoppingList.Contains("Bread")); }

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

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

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

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

/// <summary> /// Represents dynamic list implementation /// </summary> public class DynamicList {       private class Node       {             private object element;             private Node next;               public object Element             {                   get { return element; }                   set { element = value; }             }               public Node Next             {                   get { return next; }                   set { next = value; }             }               public Node(object element, Node prevNode)             {                   this.element = element;                   prevNode.next = this;             }               public Node(object element)             {                   this.element = element;                   next = null;             }       }         private Node head;       private Node tail;       private int count; /*...*/ }

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

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

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

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

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

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

/// <summary> /// Add element at the end of the list /// </summary> /// <param name="item">The element you want to add</param> 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 да имат коректни стойности).

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

/// <summary> /// Removes and returns element on the specific index /// </summary> /// <param name="index"> /// The index of the element you want to remove /// </param> /// <returns>The removed element</returns> /// <exception cref="System.ArgumentOutOfRangeException">Index is invalid</exception> public object Remove(int index) {       if (index >= count || index < 0)       {             throw new ArgumentOutOfRangeException(                   "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;       }       else if (prevNode == null)       {             head = currentNode.Next;       }       else       {             prevNode.Next = currentNode.Next;       }         // Find last element       Node lastElement = null;       if (this.head != null)       {             lastElement = this.head;             while (lastElement.Next != null)             {                   lastElement = lastElement.Next;             }       }       tail = lastElement;         return currentNode.Element; }

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

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

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

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

Накрая пренасочваме tail към края на списъка.

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

Изтриването по стойност на елемент работи като изтриването по индекс, но има 2 особености: търсеният елемент може и да не съществува и това налага допълнителна проверка; в списъка може да има елементи със стойност null, които трябва да предвидим и обработим по специален начин (вижте в кода). За да работи коректно изтриването, е необходимо елементите в масива да са сравними, т.е. да имат коректно реализирани методите Equals() и GetHashCode() от System.Оbject. Накрая отново намираме последния елемент и насочваме tail към него.

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

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

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

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

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

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

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

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

Класът ArrayList

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

-     Add(object) – добавяне на нов елемент

-     Insert(int, object) – добавяне на елемент на определено място (индекс)

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

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

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

-     Clear() – изтрива елементите на списъка

-     this[int] – индексатор, позволява достъп на елементите по подадена позиция

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

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

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

using System; using System.Collections;   class ProgrArrayListExample {       public static void Main()       {             ArrayList list = new ArrayList();             list.Add("Hello");             list.Add(5);             list.Add(3.14159);             list.Add(DateTime.Now);               for (int i = 0; i < list.Count; i++)             {                   object value = list[i];                   Console.WriteLine(                         "Index={0}; Value={1}\n", i, value);             }       } }

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

Index=0; Value=Hello Index=1; Value=5 Index=2; Value=3.14159 Index=3; Value=29.12.2009 23:17:01

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

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

ArrayList list = new ArrayList(); list.Add(2); list.Add(3); list.Add(4); int sum = 0; for (int i = 0; i < list.Count; i++) {       int value = (int)list[i];       sum = sum + value; } Console.WriteLine("Sum = " + sum);   // Output: Sum = 9

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

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

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

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

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

Този тип T може да бъде всеки наследник на класа System.Object, примерно string или DateTime. Ето няколко примера:

List<int> intList = new List<int>(); List<bool> boolList = new List<bool>(); List<double> realNumbersList = new List<double>();

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

Класът List<T>

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

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

List<int> intList = new List<int>();

Създаденият по този начин списък може да съдържа като стойности само цели числа и не може да съдържа други обекти, например символни низове. Ако се опитаме да добавим към List<int> обект от тип string, ще получим грешка по време на компилация. Чрез шаблонните типове компилаторът на C# ни пази от грешки при работа с колекции.

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

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

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

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

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

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

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

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

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

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

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

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

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

public static List<int> GetPrimes(int start, int end) {       List<int> primesList = new List<int>();       for (int num = start; num <= end; num++)       {             bool prime = true;             double numSqrt = Math.Sqrt(num)             for (int div = 2; div <= numSqrt; div++)             {                   if (num % div == 0)                   {                         prime = false;                         break;                   }             }             if (prime)             {                   primesList.Add(num);             }       }       return primesList; }   public static void Main() {       List<int> primes = GetPrimes(200, 300);       foreach (var item in primes)       {             Console.WriteLine("{0} ", item);       } }

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

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

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

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

                

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

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

public static List<int> Union(             List<int> firstList, List<int> secondList) {       List<int> union = new List<int>();       union.AddRange(firstList);       foreach (var item in secondList)       {             if (!union.Contains(item))             {                   union.Add(item);             }       }       return union; }   public static List<int> Intersect(List<int>             firstList, List<int> secondList) {       List<int> intersect = new List<int>();       foreach (var item in firstList)       {             if (secondList.Contains(item))             {                   intersect.Add(item);             }       }         return intersect; }   public static void PrintList(List<int> list) {       Console.Write("{ ");       foreach (var item in list)       {             Console.Write(item);             Console.Write(" ");       }       Console.WriteLine("}"); }   public static void Main() {       List<int> firstList = new List<int>();       firstList.Add(1);       firstList.Add(2);       firstList.Add(3);       firstList.Add(4);       firstList.Add(5);       Console.Write("firstList = ");       PrintList(firstList);         List<int> secondList = new List<int>();       secondList.Add(2);       secondList.Add(4);       secondList.Add(6);       Console.Write("secondList = ");       PrintList(secondList);         List<int> unionList = Union(firstList, secondList);       Console.Write("union = ");       PrintList(unionList);         List<int> intersectList =             Intersect(firstList, secondList);       Console.Write("intersect = ");       PrintList(intersectList); }

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

Ще решим проблема по още един начин: като използваме метода AddRange<T>(IEnumerable<T> collection) от класа List<T>:

public static void Main() {       List<int> firstList = new List<int>();       firstList.Add(1);       firstList.Add(2);       firstList.Add(3);       firstList.Add(4);       firstList.Add(5);       Console.Write("firstList = ");       PrintList(firstList);         List<int> secondList = new List<int>();       secondList.Add(2);       secondList.Add(4);       secondList.Add(6);       Console.Write("secondList = ");       PrintList(secondList);         List<int> unionList = new List<int>();       unionList.AddRange(firstList);       for (int i = unionList.Count-1; i >= 0; i--)       {             if (secondList.Contains(unionList[i]))             {                   unionList.RemoveAt(i);             }       }       unionList.AddRange(secondList);       Console.Write("union = ");       PrintList(unionList);         List<int> intersectList = new List<int>();       intersectList.AddRange(firstList);       for (int i = intersectList.Count-1; i >= 0; i--)       {             if (!secondList.Contains(intersectList[i]))             {                   intersectList.RemoveAt(i);             }       }       Console.Write("intersect = ");       PrintList(intersectList); }

За да направим сечение правим следното: слагаме всички елементи от първия списък (чрез AddRange()), след което премахваме всички елементи, които не се съдържат във втория. Задачата може да бъде решена дори още по-лесно използвайки методът RemoveAll(Predicate<T> match), но употребата му е обвързана с използване на конструкции наречени делегати и ламбда изрази, които се разглеждат в главата Ламбда изрази и LINQ заявки. Обединението правим като добавим елементите от първия списък, след което премахнем всички, които се съдържат във втория списък, след което добавяме всички елементи от втория списък.

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

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

В C# превръщането на списък в масив става лесно с използването на предоставения метод ToArray(). За обратната операция можем да използваме конструктора на List<T>(System.Array). Нека видим пример демонстриращ употребата им:

public static void Main() {       int[] arr = new int[] { 1, 2, 3 };       List<int> list = new List<int>(arr);       int[] convertedArray = list.ToArray(); }

Класът LinkedList<T>

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

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

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

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

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

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

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

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

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

Класът LinkedList<T> е за предпочитане тогава, когато се налага добавяне/премахване на елементи на произволно място в списъка и когато достъпа до елементите е последователен. Когато обаче се търсят елементи или се достъпват по индекс, то List<T> се оказва по-подходящия избор. От гледна точка на памет, LinkedList<T> е по-икономичен, тъй като заделя памет за точно толкова елементи, колкото са текущо необходими.

Стек

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

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

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

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

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

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

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

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

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

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

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

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

Класът Stack<T>

В C# можем да използваме имплементирания стандартно в .NET Framework клас System.Collections.Generics.Stack<T>. Той е имплементиран статично чрез масив, като масива се преоразмерява при необходимост.

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

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

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

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

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

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

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

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

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

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

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

public static void Main() {       Stack<string> stack = new Stack<string>();       stack.Push("1. Ivan");       stack.Push("2. Nikolay");       stack.Push("3. Maria");       stack.Push("4. George");       Console.WriteLine("Top = " + stack.Peek());       while (stack.Count > 0)       {             string personName = stack.Pop();             Console.WriteLine(personName);       } }

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

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

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

public static void Main() {       string expression =       "1 + (3 + 2 - (2+3) * 4 - ((3+1)*(4-2)))";       Stack<int> stack = new Stack<int>();       bool correctBrackets = true;         for (int index = 0; index < expression.Length; index++)       {             char ch = expression[index];             if (ch == '(')             {                   stack.Push(index);             }             else if (ch == ')')             {                   if (stack.Count == 0)                   {                         correctBrackets = false;                         break;                   }                   stack.Pop();             }       }       if (stack.Count != 0)       {             correctBrackets = false;       }       Console.WriteLine("Are the brackets correct? " +             correctBrackets); }

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

Are the brackets correct? True

Опашка

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

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

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

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

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

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

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

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

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

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

Класът Queue<T>

В C# се използва статичната реализация на опашка чрез класа Queue<T>. Тук отново можем да укажем типа на елементите, с които ще работим, тъй като опашката и свързаният списък са шаблонни типове.

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

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

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

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

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

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

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

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

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

public static void Main() {       Queue<string> queue = new Queue<string>();       queue.Enqueue("Message One");       queue.Enqueue("Message Two");       queue.Enqueue("Message Three");       queue.Enqueue("Message Four");         while (queue.Count > 0)       {             string msg = queue.Dequeue();             Console.WriteLine(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() {       int n = 3;       int p = 16;         Queue<int> queue = new Queue<int>();       queue.Enqueue(n);       int index = 0;       Console.WriteLine("S =");       while (queue.Count > 0)       {             index++;             int current = queue.Dequeue();             Console.WriteLine(" " + current);             if (current == p)             {                   Console.WriteLine();                   Console.WriteLine("Index = " + index);                   return;             }             queue.Enqueue(current + 1);             queue.Enqueue(2 * current);       } }

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

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

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

Упражнения

1.      Напишете програма, която прочита от конзолата поредица от цели положителни числа. Поредицата спира когато се въведе празен ред. Програмата трябва да изчислява сумата и средното аритметично на поредицата. Използвайте List<int>.

2.   Напишете програма, която прочита N цели числа от конзолата и ги отпечатва в обратен ред. Използвайте класа Stack<int>.

3.      Напишете програма, която прочита от конзолата поредица от цели положителни числа, поредицата спира когато се въведе празен ред, и ги сортира възходящо.

4.      Напишете метод, който намира най-дългата подредица от равни числа в даден List<int> и връща като резултат нов List<int> със тази подредица. Напишете програма, която проверява дали този метод работи коректно.

5.      Напишете програма, която премахва всички отрицателни числа от дадена редица.

Пример: array = {19, -10, 12, -6, -3, 34, -2, 5} à {19, 12, 34, 5}

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

Пример: array = {4, 2, 2, 5, 2, 3, 2, 3, 1, 5, 2} à {5, 3, 3, 5}

7.      Напишете програма, която по даден масив от цели числа в интервала [0..1000], намира по колко пъти се среща всяко число.

Пример: array = {3, 4, 4, 2, 3, 3, 4, 3, 2}

2 à 2 пъти

3 à 4 пъти

4 à 3 пъти

8.      Мажорант на масив от N елемента е стойност, която се среща поне N/2+1 пъти. Напишете програма, която по даден масив от числа намира мажоранта на масива и го отпечатва. Ако мажоранта не съществува – отпечатва "The majorant does not exists!”.

Пример: {2, 2, 3, 3, 2, 3, 4, 3, 3} à 3

9.      Дадена е следната поредица:

S1 = N;

S2 = S1 + 1;

S3 = 2*S1 + 1;

S4 = S1 + 2;

S5 = S2 + 1;

S6 = 2*S2 + 1;

S7 = S2 + 2;

...

Използвайки класа Queue<T> напишете програма, която по дадено N отпечатва на конзолата първите 50 числа от тази поредица.

Пример: N=2 à 2, 3, 5, 4, 4, 7, 5, 6, 11, 7, 5, 9, 6, ...

10.   Дадени са числа N и M и следните операции:

N = N+1

N = N+2

N = N*2

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

Пример: N = 5, M = 16

Поредицата е: 5 à 7 à 8 à 16       

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

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

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

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

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

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

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

18.   Даден е лабиринт с размери N x N. някои от клетките на лабиринта са празни (0) а други са запълнени (х). Можем да се движим от празна клетка до друга празна клетка, ако двете имат обща стена. При дадена начална позиция (*) изчислете и попълнете лабиринта с минималната дължина от началната позиция до всяка друга. Ако някоя клетка не може да бъде достигната я попълнете с "u”.

Пример:

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

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

2.      Използвайте Stack<int>.

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

4.      Използвайте List<int>. Сортирайте списъка и след това с едно обхождане намерете началния индекс и броя елементи на най-дългата подредица от равни числа. Направете нов списък и го попълнете с толкова на брой елементи.

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

6.      Сортирайте елементите на списъка, след което ги пребройте. Вече знаем кои елементи се срещат нечетен брой пъти. Направете нов списък и с едно обхождане на списъка добавяме само елементите, който се срещат четен брой пъти.

7.      Направете си масив occurrences с размер 1001. След това обхождаме списъка с числа и за всяко число number увеличаваме съответната стойност на occurrences (occurrences[number]++). Така на всеки индекс, където стойността е различна от 0 има срещане на числото и го принтираме.

8.      Използвайте списък. Сортирайте списъка и така ще получите равните числа едно до друго. Обхождаме масива като броим по колко пъти се среща всяко число. Ако в даден момент едни число се среща N/2+1, то това число е мажоранта и няма нужда да проверяваме повече. Ако след позиция N/2+1 се появи ново число (до момента не е намерен мажорант и текущото число се смени), няма нужда да проверяваме повече за мажорант – дори и в случай, че списъка е запълнен до края с текущото число, то няма как да се срещне N/2+1 пъти.

9.      Използвайте опашка. В началото добавете N и след това за всяко текущо число M добавете към опашката М+1, 2*М + 1 и М+2. На всяка стъпка отпечатвайте М и ако в даден момент отпечатаните числа станат 50, спрете цикъла.

10.   Използвайте структурата от данни опашка. Изваждайте елементите на нива до момента, в който стигнете до M. Пазете информация за числата, чрез които сте сигнали до текущото число. Първо в опашката сложете N. За всяко извадено число, вкарвайте 3 нови (ако числото, което сте извадили е X, вкарайте X * 2, X + 2 и X + 1). Като оптимизация на решението се постарайте да избягвате повторенията на числа в опашката.

11.   Имплементирайте клас DoubleLinkedListNode, който има полета Previous, Next и Value.

12.   Използвайте едносвързан списък (подобен на списъка от предната задача, но има само поле Next, без поле Previous.

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

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

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

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

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

18.   Използвайте обхождане в ширина (Breath-First Search), като започваме обхождането от позицията маркирана с ‘*’. В всяка непосетена съседна клетка на текущата клетка, записваме текущото число + 1, като приемаме, че стойността на ‘*’ е 0. След като опашката се изпразни, обхождаме цялата матрица и ако на някоя клетка имаме 0, записваме стойност ‘u’.

Демонстрации (сорс код)

Изтеглете демонстрационните примери към настоящата глава от книгата: Линейни-структури-от-данни-Демонстрации.zip.

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

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