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#




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ỹ 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


 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>];

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);
}
}


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

//Đị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;

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

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