Bài giảng Lập trình C: Các cấu trúc dữ liệu trong C#

Nội dung text: Bài giảng Lập trình C: Các cấu trúc dữ liệu trong C#

1. 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. Collections 1. 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. 1
2. 1. 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 Stack – Chè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. 2
3. Ví dụ sử dụng Stack namespace 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(); } } } 3
4. Lưu ý về Stack Class - Capacity 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< Capacity thì Push có số phép toán là O(1), ngược lại là O(n) (n = Count). Pop có số phép toán là O(1). - Stack cho phép chèn phần tử null, hoặc các phần tử có giá trị bằng nhau. 4
5. Stack Class In C# - Contructor Tên Mô tả Stack() Khởi tạo Stack trống, capacity ban đầu mặc định. Stack(ICollection) Khởi tạo Stack chứa các phần tử copy từ một tập hợp (mảng), capacity ban đầu bằng số phần tử được copy. Stack(Int32) Khởi tạo Stack trống, capacity ban đầu bằng giá trị truyền vào. (Dùng Contructor này tốt nhất) WHY? 5
6. Methods Tên Mô tả Clear Removes tất cả các đối tượng trong Stack. Clone Tạo bản sao của Stack. Contains Xác định xem phần tử có trong Stack. CopyTo Copy stack ra mảng 1 chiều, bắt đầu từ vị trí chỉ định. (Nếu mảng chứa các KDL khác nhau ?) Peek Trả về đối tượng trên đỉnh Stack không remove nó khỏi stack. Pop Remove và trả về đối tượng trên đỉnh stack. Push Chèn một đối tượng vào đỉnh stack ToArray Copy stack ra một mảng mới. 6
7. 3. Queue - Queue (Hàng đợi) là cấu trúc theo kiểu FIFO (First In First Out), phần tử vào trước sẽ được lấy ra trước. - Hai thao tác cơ bản trên hàng đợi + Chèn phần tử: Luôn chèn vào cuối hàng đợi (enqueue) + Lấy ra phần tử: Lấy ra từ đầu hàng đợi (dequeue) - Lớp Queue thuộc namespace System.Collections, biểu diễn ngăn xếp (FIFO) các đối tượng non – generic. Để sử dụng kiểu generic dùng System.Collections.Generic.Queue . - Lớp Queue hiện thực các giao diện ICollection, IEnumerable, ICloneable. 7
8. Ví 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(); } } 8
9. Lưu ý về Queue Class - Queue 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. 9
10. Contructors Tên Mô 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. 10
11. Methods Name Description Clear Removes all objects from the Queue. Clone Creates a shallow copy of the Queue. Contains Determines whether an element is in the Queue. CopyTo Copies the Queue elements to an existing one -dimensional Array, starting at the specified array index. Dequeue Removes and returns the object at the beginning of the Queue. Enqueue Adds an object to the end of the Queue. Peek Returns the object at the beginning of the Queue without removing it. TrimToSize Sets the capacity to the actual number of elements in the Queue. 11
12. Phần II. Collections 1. ArrayList 2. Hastable 3. Dictionary 12
13. 1. 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. 13
14. Ví dụ sử dụng ArrayList using 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(); } } 14
15. Contructors Name Description ArrayList() Initializes a new instance of the ArrayList class that is empty and has the default initial capacity. ArrayList(ICollec Initializes a new instance of the tion) 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 capacity 15
16. Methods Name Description Add Adds an object to the end of the ArrayList. AddRange Adds the elements of an ICollection to the end of the ArrayList. BinarySear Overloaded. Uses a binary search algorithm to locate ch 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. 16
17. Methods (conti ) Name Description Insert 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