Bài giảng Cơ sở Lập trình (Fundamental of Programming) - Chương 6: Mảng, chỉ mục và tập hợp - Nguyễn Thị Khiêm Hòa

Chương 6: Mảng, chỉ mục và tập hợp Giảng viên: Ths. Nguyễn Thị Khiêm Hòa Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM Nội dung  Mảng  Giao diện tập hợp Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2 Danh sách  Định nghĩa Danh sách là dãy hữu hạn có thứ tự của các phần tử thuộc một lớp đối tượng.  Ký hiệu: L(a1, a2, , an)  Danh sách tuyến tính là danh sách mà quan hệ lân cận giữa các phần tử được hiển thị Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3 Danh sách  Tổ chức lưu trữ danh sách trong bộ nhớ  Mảng - Danh sách đặc  Danh sách liên kết – Danh sách động Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 4 Mảng  Tập hợp các phần tử cùng kiểu dữ liệu, nằm liên tiếp trong bộ nhớ  Có chỉ số bắt đầu từ 0  Giá trị mặc định của từng phần tử trong mảng quy định theo từng kiểu đối tượng  Mảng là đối tượng  Kích thước: có thể là 1 hoặc nhiều chiều Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 5 Tạo mảng  Khai báo [ ] ;  Ví dụ: int [ ] array;  Khởi tạo [ ] = new [];  Ví dụ: int[ ] array = new int[5];  Mảng đối tượng [ ] = new [];  Ví dụ: Animal [ ] animals = new Animal [10]; Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 6 Khởi tạo và truy xuất mảng  Có thể dùng dấu { } để khởi tạo giá trị cho các phần tử mảng int[] numbers = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}; numbers[4] = 6; string[] animal = {"Mouse", "Cat", "Lion"}; animal[1]= "Elephant"; string someAnimal = animal[2]; Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7 Câu lệnh foreach  Dùng câu lệnh foreach để lặp lại việc truy xuất từng phần tử trong mảng int[] numbers = {4,5,6,1,2,3,-2,-1,0}; int Tong = 0; foreach (int a in numbers) { Tong += a; } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 8 Truyền tham số mảng vào phương thức  Dùng từ khóa params để truyền tham số mảng public int Sum(params int[] list) { int total = 0; foreach ( int i in list ) { total += i; } return total; } ... int [] pe; ... int value = pe.Sum( 1, 3, 5, 7, 9, 11 ); Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9 Chỉ mục đối tượng  Dùng từ khóa this với get và set trong properties public class Zoo { private Animal[] theAnimals; public Animal this[int i] { get {return theAnimals[i];} set {theAnimals[i] = value;} } . . . } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10 Chỉ mục đối tượng public class MyList { private string [] str; private int idx = 0; public string this[int index] { get {return str[index];} set {str[index] = value;} } public MyList(params string[] InitStr) { str = new String[256]; foreach (string s in InitStr) str[idx++] = s; } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11 Chỉ mục đối tượng public void Add(string st) { if (idx > str.Length) return; else str[idx++] = st; } public int GetNumEntries() { return idx; } }//end class Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 12 Chỉ mục đối tượng public class Test { static void Main() { MyList ml = new MyList("Cau truc du lieu", "CSDL"); ml.Add("Lap trinh huong doi tuong"); ml.Add("Phan tich thiet ke he thong"); string sttest = "Co so du lieu"; ml[1] = sttest; for (int i = 0; i < ml.GetNumEntries();i++) Console.WriteLine("{0}", ml[i]); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13 Chỉ mục đối tượng Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14 Bài tập Thực hiện  Xây dựng lớp mảng số nguyên, thực hiện việc tính tổng, tổng chẳn, tổng lẻ trong mảng  Xây dựng lớp Zoo chứa các động vật có trong lớp Animal. 45 min Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 15 Các lớp đối tượng tập hợp (Collections)  Khái niệm  Sử dụng lớp ArrayList, List  Hàng đợi (Queue), ngăn xếp (Stack) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 16 Khái niệm  Danh sách, hàng đợi, ngăn xếp là một số các CTDL thông thường trong ứng dụng  Danh sách (List): là tập hợp các phần tử truy xuất bởi chỉ mục (index) Ví dụ: mảng; ArrayList Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 17 ArrayList Class  Hạn chế của mảng  Không linh động  Tốn bộ nhớ  Lớp ArrayList cho phép gia tăng số phần tử khi cần  Có thể chứa các phần tử dữ liệu không cùng kiểu. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18 ArrayList Class  Khai báo:  Thư viện using System.Collection  ArrayList ArrayList = new ArrayList();  Thư viện System.Collection Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19 Các thuộc tính của ArrayList  Thuộc tính  Capacity  Count  Ghi chú:  Thuộc tính Capacity có giá trị mặc định là 16, khi số phần tử lớn hơn, Capacity tự động nhân đôi.  Nếu gán giá trị cho Capacity < Count thì sẽ sinh ra lỗi ArgumentOutofRangeException Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 20 Phương thức ArrayList Class  Add  Sort  AddRange  BinarySearch  Clear  Reverse  CopyTo  TrimToSize  Remove  RemoveAt  RemoveRange Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 21 ArrayList Class public class Employee { private int empID; public Employee(int empID) { this.empID = empID; } public int EmpID { get { return empID;} set { empID = value;} } public override string ToString() { return empID.ToString(); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 22 ArrayList Class Class Test { static void main() { ArrayList empArr = new ArrayList(); for(int i=0; i<5; i++) empArr.Add(new Employee(i*5)); for(int i=0; i<empArr.Count; i++) Console.Write(“{0}”,empArr[i].ToString()); Console.WriteLine(“\nempArr.Capacity:{0}”, empArr.Capacity); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 23 ArrayList Class  Kết quả: 0 5 10 15 20 empArr.Capacity: 16 Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 24 List  Là mảng đối tượng không giới hạn số phần tử.  Khai báo List tên_biến = new List;  Ví dụ: List empArray = new List; Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 25 List  Các phương thức:  Thuộc tính  Add  Capacity  Clear  Count  Remove  RemoveAt  Sort  BinarySearch  Reverse Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 26 Hàng đợi (Queue)  Hàng đợi: tập hợp các đối tượng hoạt động theo cơ chế FIFO Ví dụ: hàng đợi lệnh trong hệ điều hành Front Append Take Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 27 Hàng đợi (Queue)  Phương thức  Clear(): Xóa hàng đợi  Dequeue(): Xóa và trả về phần tử đầu tiên  Enqueue(): Thêm một phần tử vào hàng đợi  Peek(): Trả về phần tử đầu tiên nhưng không xóa.  Thuộc tính  Count: Số phần tử hiện tại trong hàng đợi. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 28 Hàng đợi public class Test { public static void main() { Queue intQueue = new Queue(); for(int i = 0; i < 5; i++) intQueue.Enqueue(i*5); Console.Write(“intQueue values: \t”); PrintValues(intQueue); intQueue.Dequeue(); intQueue.Dequeue(); Console.Write(“intQueue values: \t”); PrintValues(intQueue); intQueue.Peek(); Console.Write(“intQueue values: \t”); PrintValues(intQueue); Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM } 29 Hàng đợi public static void PrintValue(IEnumerable mc) { Ienumerator myEnumerator = mc.GetEnumerator(); while(myEnumerator.MoveNext()) Console.Write(“{0}\t”, myEnumerator.Current); Console.WriteLine(); } } //end Test Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 30 Ngăn xếp (Stack)  Ngăn xếp: tập hợp các đối tượng hoạt động theo cơ chế LIFO Ví dụ: cơ chế giải thuật đệ quy Pop Push Top Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 31 Ngăn xếp (Stack) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 32 Ngăn xếp (Stack) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 33 Ngăn xếp (Stack)  Phương thức  Clear(): Xóa ngăn xếp  Pop(): Xóa và trả về phần tử đầu tiên  Push(): Thêm một phần tử vào ngăn xếp  Peek(): Trả về phần tử đầu tiên nhưng không xóa.  Thuộc tính  Count: Số phần tử hiện tại trong ngăn xếp. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 34 Ngăn xếp public class Test { public static void main() { Stack intStack = new Stack(); for(int i = 0; i < 8; i++) intStack.Push(i*5); Console.Write(“intStack values: \t”); PrintValues(intStack); intStack.Pop(); intStack.Pop(); Console.Write(“intStack values: \t”); PrintValues(intStack); intStack.Peek(); Console.Write(“intStack values: \t”); PrintValues(intStack); } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 35 Ngăn xếp public static void PrintValue(IEnumerable mc) { Ienumerator myEnumerator = mc.GetEnumerator(); while(myEnumerator.MoveNext()) Console.Write(“{0}\t”, myEnumerator.Current); Console.WriteLine(); } } //end Test Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 36 Bài tập Thực hiện  Sử dụng ngăn xếp để thực hiện đổi một số hệ thập phân sang hệ n (n=2, 4, 6, 8, 16..)  Nhập một dãy số nguyên, in ra dãy theo thứ tự đảo ngược. 30 min Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 37 Giao diện tập hợp  .NET cung cấp giao diện chuẩn cho việc liệt kê, so sánh, và tạo tập hợp. Giao diện Mục đích IEnumerable Liệt kê thông qua một tập hợp bằng cách sử dụng foreach. IComparer So sánh giữa hai đối tượng lưu giữ trong tập hợp để sắp xếp các đối tượng trong tập hợp Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 38 IEnumerable  Dùng liệt kê đối tượng thông qua câu lệnh foreach  Phương thức GetEnumerator(): trả về sự thực thi của IEnumerator cho phép liệt kê các phần tử trong tập hợp.  Phương thức MoveNext(): tăng index của tập hợp lên 1 và kiểm tra chỉ mục có vượt quá số phần tử của tập hợp  Thuộc tính Current: dữ liệu tại vị trí hiện hành của tập hợp Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 39 IEnumerable public static void PrintValue(IEnumerable mc) { IEnumerator myEnum = mc.GetEnumerator(); while(myEnum.MoveNext()) Console.Write(“{0}\t”, myEnum.Current); Console.WriteLine(); } } //end Test Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 40 IComparer  Cung cấp các phương thức thực hiện việc so sánh và sắp xếp tập hợp. Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 41 IComparer static void Main(string[] args) { string[] myArray = {"Dog","Elephant","Cat","Pig", "Bear"}; PrintArray(myArray); Array.Sort(myArray); PrintArray(myArray); Console.ReadLine(); } public static void PrintArray(params string [] list) { for (int i = 0; i < list.Length; i++) Console.WriteLine(" [{0}] : {1}",i,list[i]); Console.WriteLine(); } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 42 IComparerable public class Employee: IComparable { private int empID; public Employee(int empID) { this.empID = empID;} public int EmpID { get { return empID;} set { empID = value;} } public override string ToString() { return empID.ToString();} public int CompareTo(object o) { Employee r = (Employee) o; return this.empID.CompareTo(r.empID); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 43 IComparerable public class Tester { static void Main() { ArrayList empArray = new ArrayList(); Random r = new Random(); // đưa vào mảng for( int i = 0; i < 5; i++) { empArray.Add( new Employee(r.Next(10)+100)); } // in tất cả nội dung PrintValue(empArray); // sắp xếp lại mảng Employee empArray.Sort(); // hiển thị tất cả nội dung của mảng Employee PrintValue(empArray); } } Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 44 Q&A Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 45