Bài giảng Các cấu trúc dữ liệu trong C#

Các cấu trúc dữ liệu trong C#I. Xây dựng cấu trúc dữ liệu trong C#1. Stack 2. Queue.II. Collections1. Các lớp và giao diện thường sử dụng trong namespace: System.Collections và System.Collections.Generic.2. Sử dụng các phương thức và thuộc tính của lớp: ArrayList.11. Stack- Stack là một cấu trúc theo kiểu LIFO (Last In First Out), phần tử vào sau cùng sẽ được lấy ra trước.- Hai thao tác cơ bản trên StackChèn phần tử: Luôn chèn vào đỉnh Stack (push)Lấy ra phần tử: Luôn lấy ra từ đỉnh Stack (pop)- Lớp Stack thuộc namespace System.Collections, biểu diễn ngăn xếp (LIFO) các đối tượng non – generic. Để sử dụng kiểu generic dùng System.Collections.Generic.Stack.Lớp Stack hiện thực các giao diện ICollection, IEnumerable, ICloneable.2Ví dụ sử dụng Stacknamespace DataStructures{ class Program { static void Main(string[] args) { int [] a = {10,20,30}; Stack s = new Stack(a); s.Push(1); s.Push("abccd"); Console.WriteLine(s.Count); Console.ReadLine(); } }}3Lưu ý về Stack ClassCapacity là số lượng các phần tử mà stack có thể chứa. Stack có thể chứa các phần tử có kiểu dữ liệu khác nhau. Thuộc tính Count để chỉ số phần tử hiện trong Stack.Khi 1 phần tử được thêm vào (Push), capacity tự động tăng, và tổ chức lại bộ nhớ. Nếu Count.Lớp Queue hiện thực các giao diện ICollection, IEnumerable, ICloneable.7Ví dụ sử dụng Queue class Program { static void Main(string[] args) { int [] a = {10,20,30,10}; Queue q = new Queue(a); q.Enqueue(22); while (q.Count > 0) Console.WriteLine(q.Dequeue()); Console.ReadLine(); } }8Lưu ý về Queue ClassQueue rất hữu ích trong việc lưu và xử lý các thông điệp theo thứ tự được gửi đến. Trong queue các phần tử được chèn ở một đầu, lấy ra ở đầu khác. capacity của queue là số phần tử nó có thể chứa, count là số các phần tử hiện có trong queue. Khi Insert 1 phần tử vào, capacity tự động tăng, capacity có thể giảm khi gọi phương thức TrimToSize().growth factor là hệ số nhân của capacity khi tăng kích thước, giá trị mặc định là 2.0. Capacity tăng tối thiểu là 4? Queue cho phép chèn giá trị null, và các phần tử có giá trị bằng nhau.9ContructorsTênMô tảQueue() Initializes a new instance of the Queue class that is empty, has the default initial capacity, and uses the default growth factor.Queue(ICollection) Initializes a new instance of the Queue class that contains elements copied from the specified collection, has the same initial capacity as the number of elements copied, and uses the default growth factor.Queue(Int32) Initializes a new instance of the Queue class that is empty, has the specified initial capacity, and uses the default growth factor.Queue(Int32, Single) Initializes a new instance of the Queue class that is empty, has the specified initial capacity, and uses the specified growth factor.10MethodsNameDescriptionClear Removes all objects from the Queue.Clone Creates a shallow copy of the Queue.Contains Determines whether an element is in the Queue.CopyToCopies the Queue elements to an existing one-dimensional Array, starting at the specified array index.DequeueRemoves and returns the object at the beginning of the Queue.EnqueueAdds an object to the end of the Queue.Peek Returns the object at the beginning of the Queue without removing it.TrimToSizeSets the capacity to the actual number of elements in the Queue.11Phần II. Collections1. ArrayList2. Hastable3. Dictionary121. ArrayList- Hiện thực giao diện IList, sử dụng 1 mảng có kích thước có thể thay đổi nếu cần.- Thuộc namespace: System.Collections.- Capacity của ArrayList là số lượng các phần tử mà ArrayList có thể chứa, khi 1 phần tử được thêm vào, Capacity có thể tăng nếu cần. Giá trị Capacity có thể giảm khi sử dụng phương thức TrimToSize() hoặc gán giá trị. Thuộc tính Count là số phần tử hiện có trong ArrayList.Có thể sử dụng index để truy cập các phần tử của ArrayList, index cơ sở là 0.Các phần tử có thể có kiểu dữ liệu khác nhau, cho phép giá trị null. 13Ví dụ sử dụng ArrayListusing System;using System.Collections;public class SamplesArrayList { public static void Main() { // Creates and initializes a new ArrayList. ArrayList myAL = new ArrayList(); myAL.Add("Hello"); myAL.Add("World"); myAL.Add("!"); // Displays the properties and values of the ArrayList. Console.WriteLine( "myAL" ); Console.WriteLine( " Count: {0}", myAL.Count ); Console.WriteLine( " Capacity: {0}", myAL.Capacity ); Console.Write( " Values:" ); PrintValues( myAL ); } public static void PrintValues( IEnumerable myList ) { foreach ( Object obj in myList ) Console.Write( " {0}", obj ); Console.WriteLine(); }}14ContructorsNameDescriptionArrayList() Initializes a new instance of the ArrayList class that is empty and has the default initial capacity.ArrayList(ICollection) Initializes a new instance of the ArrayList class that contains elements copied from the specified collection and that has the same initial capacity as the number of elements copied.ArrayList(Int32) Initializes a new instance of the ArrayList class that is empty and has the specified initial capacity15MethodsNameDescriptionAdd Adds an object to the end of the ArrayList.AddRange Adds the elements of an ICollection to the end of the ArrayList.BinarySearch Overloaded. Uses a binary search algorithm to locate a specific element in the sorted ArrayList or a portion of it.Clear Removes all elements from the ArrayList.Clone Creates a shallow copy of the ArrayList.Contains Determines whether an element is in the ArrayList.CopyTo Overloaded. Copies the ArrayList or a portion of it to a one-dimensional array.IndexOf Overloaded. Returns the zero-based index of the first occurrence of a value in the ArrayList or in a portion of it.16Methods (conti)NameDescriptionInsert Inserts an element into the ArrayList at the specified index.InsertRange Inserts the elements of a collection into the ArrayList at the specified index.LastIndexOf Overloaded. Returns the zero-based index of the last occurrence of a value in the ArrayList or in a portion of it.Remove Removes the first occurrence of a specific object from the ArrayList.RemoveAt Removes the element at the specified index of the ArrayList.RemoveRange Removes a range of elements from the ArrayList.Sort Overloaded. Sorts the elements in the ArrayList or a portion of it.ToArray Overloaded. Copies the elements of the ArrayList to a new array.TrimToSize Sets the capacity to the actual number of elements in the ArrayList.17