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
Sắp xếp
Tính toán
Đếm



Các thuật toán:

•
•

•
•



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
<kiểu dữ liệu> [ , ] <tên biến mảng>;

 Ví dụ: int [ ] array;
Khởi tạo
<tên biến mảng> = new <kiểu DL> [<số dòng>,<số cột>];
 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
<kiểu dữ liệu> [ ][ ] <tên biến mảng>;
 Ví dụ: int [ ][ ] array;
Khởi tạo
<tên biến mảng> = new <kiểu DL> [<số dòng>] [ ];
 Ví dụ: int [ ][ ] array = new int [ 3 ] [ ];
Khởi tạo từng dòng
<tên biến mảng> [<vị trí dòng>] = new <kiểu DL> [<số cột>];

 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
IEnumerable
IComparer

Mục đích
Liệt kê thông qua một tập hợp
bằng cách sử dụng foreach.
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
(CompareTo)

Object

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 <Tên_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 <Tên_class_con>: Icomparer

{
private <Tên_class>.<Tên_class_con>.ComparisionType CmpType;
public enum ComparisionType
{
field1,
field2,
…
};
public <Tên_class>.<Tên_class_con>.ComparisionType CType
{
get {return CmpType;}
set {CmpType = value;}
}
//Xem tiếp trang Khoa
sauCông nghệ Thông tin - Đại học Ngân hàng TP.HCM
17


IComparer
public int Compare(<Tên_class> lhs, <Tên_class> 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 <Tên_class>: Icomparable
{ …
public static <Tên_class_con> GetComparer()
{
return new <Tên_class>.<Tên_class_con>;
}
public int CompareTo(<Tên_class> 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(<Tên_class> rhs,
<Tên_class>.<Tên_class_con>.ComparisionType w)
{
switch(w)
{
case <Tên_class>.<Tên_class_con>.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


Danh sách liên kết


Đặt vấn đề:
 Thêm phần tử vào mảng, chi phí O(n)
 Xóa một phần tử trong mảng, chi phí O(n)
 Khó cấp phát
Tách các phần tử riêng rẽ, tìm
cách liên kết chúng

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
21


Danh sách liên kết
Địa chỉ liên kết

Data



Thành

phần dữ
liệu

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
22


Danh sách liên kết


Một dãy tuần tự các nút (Node) liên kết với nhau bằng địa chỉ



Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ



Có thể mở rộng tuỳ ý (chỉ giới hạn bởi dung lượng bộ nhớ)



Thao tác Chèn/Xóa không cần phải dịch chuyển phần tử



Có thể truy xuất đến các phần tử khác thông qua địa chỉ

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
23



Danh sách liên kết
 Thêm một

phần tử

 Xóa

một phần tử

 Liệt

kê

 Tính toán

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
24


Danh sách liên kết
public class Node<T>: IComparable
where T: IComparable<T>
{
private T data;
private Node<T> next;
public Node(T data)
{
this.data = data;

this.next = null;
}
//Đóng gói DL
//các phương thức
}

Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
25