Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Chia sẻ: Cxzvscv Cxzvscv | Ngày: | Loại File: PDF | Số trang:32

Thêm vào BST

Báo xấu

89
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung cơ bản của chương 3 Danh sách nằm trong bài giảng cấu trúc dữ liệu và giải thuật nhằm trình bày về các nội dung chính: danh sách và các phép toán trên danh sách, danh sách đặc, danh sách liên kết, từ đó giúp sinh viên hểu rõ về CTDL danh sách, phương pháp xây dựng lớp đối tượng danh sách đặc, danh sách liên kết và các kiểu dữ liệu đặc biệt trên C#.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 3 - ThS. Nguyễn Thị Khiêm Hòa (ĐH Ngân hàng TP.HCM)

Chương 3: Danh sách 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  Danh sách và các phép toán trên danh sách  Danh sách đặc  Danh sách liên kết Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 2
Mục tiêu  Hiểu rõ về CTDL danh sách  Phương pháp xây dựng lớp đối tượng danh sách đặc, danh sách liên kết và các kiểu dữ liệu đặc biệt trên C#  Đánh giá ưu khuyết điểm của giải thuật trên từng loại danh sách để chọn kiểu dữ liệu phù hợp Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 3
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 4
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 5
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 6
Mảng một chiều  Khai báo  Khởi tạo  Truy xuất: Chỉ mục đối tượng • Tìm kiếm  Các thuật toán: • Sắp xếp • Tính toán • Đếm  Kỹ thuật • Lính canh • Cờ hiệu Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 7
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 8
Mảng đa chiều  Là mảng một chiều mà mỗi phần tử là một mảng khác  Trên C# hỗ trợ hai kiểu mảng đa chiều:  Mảng đa chiều cùng kích thước (Rectangle)  Mảng đa chiều không cùng kích thước (Jagged Array) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 9
Mảng đa chiều cùng kích thước  Khai báo [ , ] ;  Ví dụ: int [ ] array;  Khởi tạo = new [,];  Ví dụ: int [ , ] array = new int [ 3, 5 ];  Duyệt mảng: for (int i = 0; i < rows; i++) for (int j = 0; j < columns; j++) Xử_lý A{i,j]; Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 10
Mảng đa chiều khác kích thước  Khai báo [ ][ ] ;  Ví dụ: int [ ][ ] array;  Khởi tạo = new [] [ ];  Ví dụ: int [ ][ ] array = new int [ 3 ] [ ];  Khởi tạo từng dòng [] = new [];  Ví dụ: array[0] = new int [ 3 ];  Truy xuất: Tên_biến_mảng [rows][columns] Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 11
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 12
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. Sort() IComparer IComparable Object (CompareTo) Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 13
IComparer  Định nghĩa cách thức so sánh cho đối tượng class : Icomparable { … public int CompareTo(Object o) { Tên_class r = (Tên_class) o; return this.Tên_Field.CompareTo(r.Tên_Field); } }  Phương thức CompareTo có tham số đối tượng, so sánh với chính nó. Trả về {-1, 0, 1} Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 14
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 15
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 16
IComparer  Định nghĩa nhiều cách thức so sánh cho đối tượng class : Icomparer { private ..ComparisionType CmpType; public enum ComparisionType { field1, field2, … }; public ..ComparisionType CType { get {return CmpType;} set {CmpType = value;} } //Xem tiếp trang Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM sau 17
IComparer public int Compare( lhs, rhs) { return lhs.CompareTo(rhs.CmpType); } }//end class con Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 18
IComparer //Định nghĩa class chính class : Icomparable { … public static GetComparer() { return new .; } public int CompareTo( rhs) { Tên_class r = (Tên_class) rhs; return this.Tên_Field.CompareTo(rhs.Tên_Field); }//Phương thức so sánh mặc định //Xem tiếp trang sau Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 19
IComparer //Định nghĩa class chính public int CompareTo( rhs, ..ComparisionType w) { switch(w) { case ..ComparisionType.field1: return this.field1.CompareTo(rhs.field1); case … } return 0; } //Định nghĩa class con tại đây … }//end class chính Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM 20