A
B
C
D
A
B
C
D
2
KHOA CÔNG NGHỆ THÔNG TIN
A
B
C
D
A
B
C
D
3
KHOA CÔNG NGHỆ THÔNG TIN
DANH SÁCH LIÊN KẾT ĐƠN (LIST)
5
KHOA CÔNG NGHỆ THÔNG TIN
x2
x0
x3
x1
6
KHOA CÔNG NGHỆ THÔNG TIN
pNext
Info
7
KHOA CÔNG NGHỆ THÔNG TIN
pHead
pTail
3f 4
4f
4f 7
5f
5f 6
NULL
Trong ví dụ trên thành phần dữ liệu là 1 số nguyên
8
KHOA CÔNG NGHỆ THÔNG TIN
Tạo 1 danh sách liên kết đơn rỗng
Tạo 1 nút có trường Info bằng x
Tìm một phần tử có Info bằng x
Thêm một phần tử có khóa x vào danh sách
Hủy một phần tử trong danh sách
Duyệt danh sách
Sắp xếp danh sách liên kết đơn
9
KHOA CÔNG NGHỆ THÔNG TIN
Đầu tiên thiết lập Node
class Node {
public int iData; public Node pNext;
public Node(int value) {
this.iData = value; this.pNext = null;
}
}
10
KHOA CÔNG NGHỆ THÔNG TIN
Khai báo thông tin danh sách class MyLinkedList
{
Node pHead, pTail;
public MyLinkedList() {
pHead = null; pTail = null;
}
}
11
KHOA CÔNG NGHỆ THÔNG TIN
Nguyên tắc thêm: Khi thêm 1 phần tử vào List thì có làm cho pHead, pTail thay đổi? Các vị trí cần thêm 1 phần tử vào List:
‐ Thêm vào đầu List
‐ Thêm vào cuối List
‐ Thêm vào sau 1 phần tử q trong list
13
KHOA CÔNG NGHỆ THÔNG TIN
Thêm nút p vào đầu danh sách liên kết đơn
Bắt đầu:
Nếu List rỗng thì
+ pHead = p; + pTail = pHead;
Ngược lại
+ p.pNext = pHead;
+ pHead = p
14
KHOA CÔNG NGHỆ THÔNG TIN
pHead
2 f 3 3f
3 f 4 4f
4 f 8 …
9f
10 2fN
pHead=P
P.pNext=pHead
P
15
KHOA CÔNG NGHỆ THÔNG TIN
public void AddHead(Node p) {
if (pHead == null) // kiểm tra nếu danh sách đang rỗng (pHead == null) {
pHead = pTail = p; // Node p vừa là đầu, vừa là cuối }
else // nếu danh sách không rỗng {
p.pNext = pHead; // Nếu xem Node p đứng ở đầu danh sách pHead = p; // Node p giờ đây được cập nhật là Node đầu danh sách
}
}
16
KHOA CÔNG NGHỆ THÔNG TIN
Ta cần thêm nút p vào cuối list đơn
Bắt đầu:
Nếu List rỗng thì
+ pHead = p; + pTail = pHead;
Ngược lại
+ pTail.pNext=p; + pTail=p
17
KHOA CÔNG NGHỆ THÔNG TIN
pTail
5f
3 f
4 4f
4f 8 5f
5 N9f
pTail=P
9f
pTail.pNext
6 N
P
18
KHOA CÔNG NGHỆ THÔNG TIN
public void AddTail(Node p) {
if (pHead == null) // kiểm tra nếu danh sách đang rỗng
{
pHead = pTail = p; // Node p vừa là đầu, vừa là cuối
} else // nếu danh sách không rỗng {
pTail.pNext = p; // Nếu xem Node p đứng ở cuối danh sách pTail = p; // Node p giờ đây được cập nhật là Node cuối danh sách
}
}
19
KHOA CÔNG NGHỆ THÔNG TIN
Ta cần thêm nút p vào sau nút q trong list đơn
Bắt đầu:
Nếu (q!=null) thì
B1: p.pNext = q.pNext B2: + q.pNext = p
+ nếu q = pTail thì pTail=p
20
KHOA CÔNG NGHỆ THÔNG TIN
q
4 f
5 f
3 f
5 ..
4 4f
8 5 9 f f q.pNext=P
9 f
7
P.pNext = q.pNext
N 5 f
P
21
KHOA CÔNG NGHỆ THÔNG TIN
void AddAfterQ(Node q, Node p) {
if(q != null) {
p.pNext = q.pNext; //B1 q.pNext = p; //B2 if(q == pTail){ pTail = p;}
} else //chèn vào đầu danh sách
AddHead(p);// thêm p vào đầu list
}
22
KHOA CÔNG NGHỆ THÔNG TIN
Nguyên tắc: Phải cô lập phần tử cần hủy trước hủy. Các vị trị cần hủy:
‐ Hủy phần tử đứng đầu List ‐ Hủy phần tử có khoá bằng x ‐ Hủy phần tử đứng sau q trong danh sách liên kết đơn Ở phần trên, các phần tử trong DSLK đơn được cấp phát vùng nhớ động bằng hàm new, thì sẽ được giải phóng vùng nhớ bằng hàm delete.
23
KHOA CÔNG NGHỆ THÔNG TIN
Bắt đầu:
Nếu (pHead!=NULL) thì
B1: p=pHead //p là phần tử cần hủy
B2:
+ pHead = pHead.pNext //tách p ra khỏi ds
+ p = null // Hủy biến động do p trỏ đến
B3:
Nếu pHead==NULL thì pTail=NULL
24
KHOA CÔNG NGHỆ THÔNG TIN
pHead = pHead.pNext
pHead
2f
3f
4f
1f 7
2f
6
3f
3
4f
…8
P = pHead
P
25
KHOA CÔNG NGHỆ THÔNG TIN
void RemoveHead()
{
if (pHead != null) {
Node p = pHead; //B1 pHead = pHead.pNext; // B2 p = null;
if(pHead == null) {pTail = null;} //B3
}
26
}
KHOA CÔNG NGHỆ THÔNG TIN
Bắt đầu
Nếu (q != null) thì //q tồn tại trong List B1: p = q.pNext;// p là phần tử cần hủy B2: Nếu (p != null) thì // q không phải là phần tử cuối
+ q.pNext = p.pNext;// tách p ra khỏi xâu + nếu (p == pTail) // nút cần hủy là nút cuối
pTail = q;
+ p = null ;// hủy p
27
KHOA CÔNG NGHỆ THÔNG TIN
p-=q.pNext
p
q 2f
3f
4f
pHead
3f4f
1f 7
2f
6
3
4f
…8
q.pNext = p.pNext
28
KHOA CÔNG NGHỆ THÔNG TIN
int RemoveAfterQ(Node q)
Node p; int x; if (q != null) {
p = q.pNext; //p là nút cần xoá if (p != null) // q không phài là nút cuối {
if (p == pTail) //nút cần xoá là nút cuối cùng
pTail = q;// cập nhật lạ pTail
q.pNext = p.pNext; x = p.Data; p = null;
} return 1;
} else
{
}
return 0;
29
KHOA CÔNG NGHỆ THÔNG TIN
Bước 1:
Tìm phần tử p có khoá bằng x, và q đứng trước p
Bước 2:
Nếu (p != NULL) thì //tìm thấy phần tử có khoá bằng x
Hủy p ra khỏi List bằng cách hủy phần tử đứng sau q
Ngược lại
Báo không tìm thấy phần tử có khoá
30
KHOA CÔNG NGHỆ THÔNG TIN
{
Node q, p = pHead;
int RemoveX(int x)
{
q = p;
while((p != null) && (p.Data != x)) //tìm
}
if(p == null) //không tìm thấy phần tử có khoá bằng x
return 0;
if(q != null)//tìm thấy phần tử có khoá bằng x
q.pNext = p.pNext;
p = null;
else //phần tử cần xoá nằm đầu List
pHead = p.pNext;
p = p.Next;
}
return 1;
31
KHOA CÔNG NGHỆ THÔNG TIN
Tìm tuần tự (hàm trả về), các bước của thuật toán tìm nút có Info bằng x trong list đơn
Bước 1: p=pHead;// địa chỉ của phần tử đầu trong
list đơn
Bước 2:
Trong khi p!=NULL và p.Info != x
p=p.pNext;// xét phần tử kế
Bước 3: + Nếu p != NULL thì p lưu địa chỉ của nút có
Info = x
+ Ngược lại : Không có phần tử cần tìm
32
KHOA CÔNG NGHỆ THÔNG TIN
pHead
4 f
5 f
2 f
3 f
56
1 f 34
3
4
8 8
P
X = 8
Tìm thấy, hàm trả về địa chỉ của nút tìm thấy là 4f
33
KHOA CÔNG NGHỆ THÔNG TIN
Node Search(int x) {
Node p; p = pHead; while((p != null) && (p.Data != x))
p = p.pNext;
return p;
}
34
KHOA CÔNG NGHỆ THÔNG TIN
Duyệt danh sách là thao tác thường được thực hiện khi
có nhu cầu cần xử lý các phần tử trong danh sách như:
Đếm các phần tử trong danh sách
Tìm tất cả các phần tử trong danh sách thỏa điều
kiện
Hủy toàn bộ danh sách
35
KHOA CÔNG NGHỆ THÔNG TIN
Bước 1:
p = pHead;// p lưu địa chỉ của phần tử đầu trong List
Bước 2:
Trong khi (danh sách chưa hết) thực hiện
+ xử lý phần tử p
+ p = p.pNext;// qua phần tử kế
36
KHOA CÔNG NGHỆ THÔNG TIN
void PrintList() {
Node p; p = pHead; //p trỏ vào phần tử đầu ds while(p != null)// khi chưa duyệt hết ds {
Console.WriteLine(p.iData); // in giá trị p = p.pNext;// dịch chuyển p đến nút kế
}
}
37
KHOA CÔNG NGHỆ THÔNG TIN
Bước 1:
Trong khi (danh sách chưa hết) thực hiện • B11:
p = pHead; pHead = pHead.pNext;// cập nhật pHead
• B12:
Hủy p
Bước 2:
pTail = NULL;// bảo toàn tính nhất quán khi xâu rỗng
38
KHOA CÔNG NGHỆ THÔNG TIN
pTail
pHead
2f
3f
4f
5f
5f N9
3f
2f
6
3
4f
1f 7
8
p
39
KHOA CÔNG NGHỆ THÔNG TIN
void RemoveList() {
Node p; while(pHead != null)//còn phần tử trong List {
p = pHead; pHead = p.pNext; p = null;
}
}
40
KHOA CÔNG NGHỆ THÔNG TIN
Có hai cách tiếp cận Cách 1: Thay đổi thành phần Info
pHead
pTail
5f
3f 4
4f
4f 7
5f
6
N
pHead
pTail
5f
3f 4
4f
4f 6
5f
7
N
41
KHOA CÔNG NGHỆ THÔNG TIN
Cách 2: Thay đổi thành phần pNext (thay đổi trình tự móc nối của các phần tử sao cho tạo lập nên được thứ tự mong muốn)
pHead
pTail
5f
3f 4
4f
4f 7
5f
6
N
pHead
pTail
5f
3f 4
5f
4f 7
N
6
4f
42
KHOA CÔNG NGHỆ THÔNG TIN
Thay đổi thành phần Info (dữ liệu)
Ưu: Cài đặt đơn giản, tương tự như sắp xếp mảng Nhược:
Đòi hỏi thêm vùng nhớ khi hoán vị nội dung của 2 phần tử -
> chỉ phù hợp với những xâu có kích thước Info nhỏ
Khi kích thước Info (dữ liệu) lớn chi phí cho việc hoán vị
thành phần Info lớn
Làm cho thao tác sắp xếp chậm
Thay đổi thành phần pNext
Ưu:
Kích thước của trường này không thay đổi, do đó không phụ
thuộc vào kích thước bản chất dữ liệu lưu tại mỗi nút.
Thao tác sắp xếp nhanh
Nhược: Cài đặt phức tạp
43
KHOA CÔNG NGHỆ THÔNG TIN
void SelectionSort()
Node p, q, min; p = pHead; while (p != pTail) {
min = p; q = p.pNext; while (q != null) {
{
min = q;
if (q.Data < min.Data)
} HoanVi(ref min.Data, ref p.Data); p = p.pNext;
}
}
q = q.pNext;
44
KHOA CÔNG NGHỆ THÔNG TIN
Các thuật toán sắp xếp xâu (List) bằng các thay đổi thành phần pNext (thành phần liên kết) có hiệu quả cao như:
‐ Thuật toán sắp xếp Quick Sort
‐ Thuật toán sắp xếp Merge Sort
‐ Thuật toán sắp xếp Radix Sort
45
KHOA CÔNG NGHỆ THÔNG TIN
Yêu cầu: Viết chương trình thành lập 1 xâu đơn, trong đó
thành phần dữ liệu của mỗi nút là 1 số nguyên dương.
Liệt kê tất thành phần dữ liệu của tất cả các nút trong xâu
1.
Tìm 1 phần tử có khoá bằng x trong xâu.
2.
Xoá 1 phần tử đầu xâu
3.
Xoá 1 phần tử có khoá bằng x trong xâu
4.
Sắp xếp xâu tăng dần theo thành phần dữ liệu (Info)
5.
Chèn 1 phần tử vào xâu, sao cho sau khi chèn xâu vẫn tăng
6.
dần theo trường dữ liệu
46
KHOA CÔNG NGHỆ THÔNG TIN
Dùng xâu đơn để lưu trữ danh sách các học viên
trong lớp học
Dùng xâu đơn để quản lý danh sách nhân viên
trong một công ty, trong cơ quan
Dùng xâu đơn để quản lý danh sách các cuốn sách
trong thư viện
Dùng xâu đơn để quản lý các băng đĩa trong tiệm
cho thuê đĩa.
47
KHOA CÔNG NGHỆ THÔNG TIN
Yêu cầu: Thông tin của một sinh viên gồm, mã số sinh viên, tên sinh viên, điểm trung bình.
1. Hãy khai báo cấu trúc dữ liệu dạng danh sách liên kết để lưu danh sách sinh viên nói trên.
2. Nhập danh sách các sinh viên, và thêm từng sinh viên vào đầu danh sách (việc nhập kết thúc khi tên của một sinh viên bằng rỗng)
3. Tìm một sinh viên có trong lớp học hay không
4. Xoá một sinh viên có mã số bằng x (x nhập từ bàn phím)
5. Liệt kê thông tin của các sinh viên có điểm trung bình lớn hơn hay bằng 5.
6. Xếp loại và in ra thông tin của từng sinh viên, biết rằng cách xếp loại như sau:
ĐTB <=3.6 : Loại yếu
ĐTB>=50 và ĐTB<6.5 : Loại trung bình
ĐTB>=6.5 và ĐTB < 7.0: Loại trung bình khá
ĐTB>=7.0 và ĐTB <8.0: Loại khá
ĐTB>=8.0 và ĐTB < 9.0: Loại giỏi.
ĐTB>=9.0 : Loại xuất sắc
7.
Sắp xếp và in ra danh sách sinh viên tăng theo điểm trung bình.
8.
Chèn một sinh viên vào danh sách sinh viên tăng theo điểm trung bình nói trên, sao cho sau khi chèn danh sách sinh viên vẫn tăng theo điểm trung bình
48
KHOA CÔNG NGHỆ THÔNG TIN
Viết mã giả, chụp hình nộp: Cấu trúc dữ liệu danh sách liên kết đơn quản lý số nguyên:
1. Khai báo Node
2. Khai báo MyLinkedList gồm các thao tác:
- Void AddHead(Node p)
- Void AddTail ( Node p)
- Void AddAfterQ( Node q, Node p)
- Bool Search( int value)
- Remove(int value)
- RemoveAfterQ(Node q, Node p)
- RemoveList()
49
KHOA CÔNG NGHỆ THÔNG TIN
DANH SÁCH LIÊN KẾT KÉP
A
B
C
D
52
KHOA CÔNG NGHỆ THÔNG TIN
53
KHOA CÔNG NGHỆ THÔNG TIN
54
KHOA CÔNG NGHỆ THÔNG TIN
55
KHOA CÔNG NGHỆ THÔNG TIN
• Minh họa hình vẽ
pHead
A
B
C
D
pTail
X
56
KHOA CÔNG NGHỆ THÔNG TIN
57
KHOA CÔNG NGHỆ THÔNG TIN
• Minh họa thêm 1 phần tử vào sau danh sách
pTail
pHead
A
B
C
D
X
58
KHOA CÔNG NGHỆ THÔNG TIN
public void AddTail(ref List l, Node p)
{
if (l.pHead == null) // kiểm tra nếu ds rỗng (pHead == null)
{
l.pHead = l.pTail = p; // Node p vừa là đầu, vừa là cuối
}
else // nếu danh sách không rỗng
{
l.pTail.pNext = p; // Nếu Node p đứng ở cuối ds
p.pPrev = l.pTail; // Node p gọi pPrev sẽ đến được Node cuối danh sách (pTail)
l.pTail = p; // Node p giờ đây được cập nhật là Node cuối danh sách
}
}
59
KHOA CÔNG NGHỆ THÔNG TIN
• Minh họa thêm nút X vào sau nút q
pTail
pHead
q
A
B
C
D
X
60
KHOA CÔNG NGHỆ THÔNG TIN
void AddAfterQ(ref List l, Node tam, Node q)
{
Node p;
p = q.pNext;
if( q != null )//them vao duoc
{
tam.pNext = p;
tam.pPre = q;
q.pNext = tam;
if( p != null )
p.pPrev = tam;
if(q == l.pTail) //them vao sau danh sach lien ket.
l.pTail = tam;
}
else // chèn vào đầu danh sách
AddHead(ref l, p);
}
61
KHOA CÔNG NGHỆ THÔNG TIN
• Minh hoạ thêm 1 nút vào trước nút q
pTail
pHead
q
A
B
C
D
X
62
KHOA CÔNG NGHỆ THÔNG TIN
void AddBeforeQ(ref List l, Node tam, Node q)
{
Node p = q.pPrev;
if( q != null )
{
tam.pNext = q;
tam.pPrev = p;
q.pPre = tam;
p.pNext = tam;
if(p != null)
l.pHead = tam;
if(q == l.pHead)
else
}
}
AddTail(ref l, p);
63
KHOA CÔNG NGHỆ THÔNG TIN
int DeleteFirst(ref List l) {
Node p; int x = 0; if(l.pHead != null) {
p = l.pHead; x = p.Data; l.pHead = l.pHead.pNext; l.pHead.pPrev = null; p = null; if(l.pHead == null)
l.pTail = null; else l.pHead.pPrev = null; return x;
}
}
64
KHOA CÔNG NGHỆ THÔNG TIN
void DeleteEnd(ref List l ) {
Node p; int x = 0; if(l.pTail != null) //tuc xau co hon mot phan tu {
p = l.pTail; x = p.Data; l.pTail = l.pTail.Prev; l.pTail.pNext = null; p = null; if(l.pHead == null)
l.pTail = null;
else l.pHead.pPrev = null; return x;
}
}
65
KHOA CÔNG NGHỆ THÔNG TIN
void DeleteLastQ(ref List l, Node q) {
p = q.pNext; if(p != null) {
q.pNext = p.pNext; if(p == l.pTail)//xoa dung nu't cuoi
else
l.pTail = q; //Nut xoa khong phai nut cuoi p.pNext.pPrev = q;
p = null;
Node p;//luu node dung sau node q if(q != null) {
} else
DeleteFirst(ref l);
}
}
66
KHOA CÔNG NGHỆ THÔNG TIN
void DeleteBeforeQ(ref List l, Node q) {
Node p; if(q != null) //tuc ton tai node q {
p = q.pPrev; if(p != null) {
q.pPrev = p.pPrev; if(p == l.pHead)//p la Node dau cua danh sach
l.pHead = q; else //p khong phai la node dau
p.pPrev.pNext = q;
p = null;
}
} else
DeleteEnd(ref l);
}
67
KHOA CÔNG NGHỆ THÔNG TIN
void DeleteX(ref List l, int x)
Node q = null;
{
{
for (Node p = l.pHead; p != null; p = p.pNext)
{
if (q == null)
DeleteFirst(ref l);
else
DeleteLastQ(ref l, q);
break;
}
q = p;
if (p.Data == x)
}
}
68
KHOA CÔNG NGHỆ THÔNG TIN
void DoiChoTrucTiep(ref List l) {
Node p,q; p = l.pHead; while(p != l.pTail) {
q = p.pNext; while(q != NULL) {
if(p.Data > q.Data)
HoanVi(ref p.Data, q.Data);
q = q.pNext;
} p = p.pNext;
}
}
69
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP (15 phút): Tạo danh sách sau: ["hanoi", "saigon", "danang", "nhatrang", "cantho"]. Sau đó viết các lệnh sau a)Chèn hue vào vị trí 3? b)Sửa danang thành phuyen? c)Chèn cantho vào vị trí 2? d)Xóa cantho? e)Xóa tất cả cantho? f)Đổi chỗ saigon và nhatrang? g) Tìm kiếm cantho?
70
