Chương 3: Danh sách
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
32 trang |
Chia sẻ: phuongt97 | Lượt xem: 374 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Danh sách - Nguyễn Thị Khiêm Hòa, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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
Các thuật toán:
• 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 Khoasau Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
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
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: IComparable >
where T: IComparable
{
private T data;
private Node 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
Danh sách liên kết
//Đóng gói dữ liệu: Properties
public T Data
{
get{ return this.data;}
set{ this.data = value;}
}
public Node Next
{
get { return this.next; }
set { this.next = value;}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
26
Danh sách liên kết
//các phương thức dùng để so sánh sắp xếp
public int CompareTo(Node rhs)
{
return data.CompareTo(rhs.data);
}
public bool Equals(Node rhs)
{
return this.data.Equals(rhs.data);
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
27
Danh sách liên kết
public class LinkList
where T: IComparable
{
private Node head;
public LinkList()
{
this.head = null;
}
//các phương thức
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
28
Danh sách liên kết
public void InsertFirst(T data)
{
if(head == null)
head = new Node(data);
else
{
Node node = new Node(data);
node.next = head;
head = node;
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
29
Danh sách liên kết
//In danh sách
public void PrintList()
{
while(head != null)
{
Console.Write("{0} ", this.head.Data);
head = head.Next;
}
}
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
30
Danh sách liên kết
class Program
{ static void Main(string[] args)
{
Random r = new Random();
LinkList intList = new LinkList();
for (int i = 0; i < 10; i++)
{
int nextInt = r.Next(10);
Console.Write("{0} ", nextInt);
intList.InsertFirst(nextInt);
}
Console.WriteLine("\nDanh sach cac so:");
intList.PrintList();
Console.Read();
}
} Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
31
Q&A
Khoa Công nghệ Thông tin - Đại học Ngân hàng TP.HCM
32
Các file đính kèm theo tài liệu này:
- bai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_3_danh_sach.pdf