Đăng ký nhận thông tin về những video mới nhất
Tóm Tắt
THAM KHẢO
Video hướng dẫn cách setup LIST bằng mảng
I. KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST)
1. Khái niệm danh sách
Mô hình toán học của danh sách là một tập hợp hữu hạn các phần tử có cùng một kiểu, mà tổng quát ta gọi là kiểu phần tử (Elementtype). Ta biểu diễn danh sách như là một chuỗi các phần tử của nó: a1, a2,. . ., anvới n ≥ 0. Nếu n=0 ta nói danh sách rỗng (empty list). Nếu n > 0 ta gọi a1 là phần tử đầu tiên và an là phần tử cuối cùng của danh sách. Số phần tử của danh sách ta gọi là độ dài của danh sách.
Một đặc thù quan trọng của list là những thành phần của list có thứ tự tuyến tính theo vị trí ( position ) Open của những thành phần. Ta nói ai đứng trước ai + 1, với i từ 1 đến n-1 ; Tương tự ta nói ailà thành phần đứng sau ai-1, với i từ 2 đến n. Ta cũng nói ai là thành phần tại vị trí thứ i, hay thành phần thứ i của list .
Ví dụ : Tập hợp họ tên những sinh viên của lớp TINHOC 28 được liệt kê trên giấy như sau :
- Nguyễn Trung Cang
- Nguyễn Ngọc Chương
- Lê Thị Lệ Sương
- Trịnh Vũ Thành
- Nguyễn Phú Vĩnh
là một list. Danh sách này gồm có 5 thành phần, mỗi thành phần có một vị trí trong list theo thứ tự Open của nó .
2. Các phép toán trên danh sách
Để thiết lập kiểu tài liệu trừu tượng list ( hay ngắn gọn là list ) ta phải định nghĩa những phép toán trên list. Và như tất cả chúng ta sẽ thấy trong hàng loạt giáo trình, không có một tập hợp những phép toán nào thích hợp cho mọi ứng dụng ( application ). Vì vậy ở đây ta sẽ định nghĩa 1 số ít phép toán cơ bản nhất trên list. Để thuận tiện cho việc định nghĩa ta giả sử rằng list gồm những thành phần có kiểu là kiểu thành phần ( elementType ) ; vị trí của những thành phần trong list có kiểu là kiểu vị trí và vị trí sau thành phần ở đầu cuối trong list L là ENDLIST ( L ). Cần nhấn mạnh vấn đề rằng khái niệm vị trí ( position ) là do ta định nghĩa, nó không phải là giá trị của những thành phần trong list. Vị trí hoàn toàn có thể là như nhau với vị trí tàng trữ thành phần hoặc không .
Các phép toán được định nghĩa trên list là :
INSERT_LIST(x,p,L): xen phần tử x ( kiểu ElementType ) tại vị trí p (kiểu position) trong danh sách L. Tức là nếu danh sách là a1, a2,., ap-1, ap ,.., an thì sau khi xen ta có kết quả a1, a2,. . ., ap-1, x, ap,. .., an. Nếu vị trí p không tồn tại trong danh sách thì phép toán không được xác định.
LOCATE(x,L) thực hiện việc định vị phần tử có nội dung x đầu tiên trong danh sách L. Locate trả kết quả là vị trí (kiểu position) của phần tử x trong danh sách. Nếu x không có trong danh sách thì vị trí sau phần tử cuối cùng của danh sách được trả về, tức là ENDLIST(L).
RETRIEVE(p,L) lấy giá trị của phần tử ở vị trí p (kiểu position) của danh sách L; nếu vị trí p không có trong danh sách thì kết quả không xác định (có thể thông báo lỗi).
DELETE_LIST(p,L) chương trình con thực hiện việc xoá phần tử ở vị trí p (kiểu position) của danh sách. Nếu vị trí p không có trong danh sách thì phép toán không được định nghĩa và danh sách L sẽ không thay đổi.
ENDLIST(L): Trả về vị trí sau phần tử cuối cùng của List.
NEXT(p,L) cho kết quả là vị trí của phần tử (kiểu position) đi sau phần tử p; nếu p là phần tử cuối cùng trong danh sách L thì NEXT(p,L) cho kết quả là ENDLIST(L). Next không xác định nếu p không phải là vị trí của một phần tử trong danh sách.
PREVIOUS(p,L) cho kết quả là vị trí của phần tử đứng trước phần tử p trong danh sách. Nếu p là phần tử đầu tiên trong danh sách thì Previous(p,L) không xác định. Previous cũng không xác định trong trường hợp p không phải là vị trí của phần tử nào trong danh sách.
FIRST(L) cho kết quả là vị trí của phần tử đầu tiên trong danh sách. Nếu danh sách rỗng thì ENDLIST(L) được trả về.
EMPTY_LIST(L) cho kết quả TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE.
MAKENULL_LIST(L) khởi tạo một danh sách L rỗng.
Trong phong cách thiết kế những giải thuật sau này tất cả chúng ta dùng những phép toán trừu tượng đã được định nghĩa ở đây như thể những phép toán nguyên thủy .
Muốn thêm thành phần vào đầu hay cuối list ta gọi phép toán nào và gọi phép toán đó như thế nào ?
Ví dụ : Dùng những phép toán trừu tượng trên list, viết một chương trình con nhận một tham số là list rồi sắp xếp list theo thứ tự tăng dần ( giả sử những thành phần trong list thuộc kiểu có thứ tự ) .
Giả sử SWAP ( p, q ) thực thi việc đổi chỗ hai thành phần tại vị trí p và q trong list, chương trình con sắp xếp được viết như sau :
void sort ( List * L ) {
Position p, q ;
/ / kiểu vị trí của những thành phần trong list
p = FIRST ( * L ) ;
/ / vị trí thành phần tiên phong trong list
while ( p ! = ENDLIST ( * L ) ) {
q = NEXT ( p, * L ) ;
/ / vị trí thành phần đứng ngay sau thành phần p
while ( q ! = ENDLIST ( * L ) ) {
if ( RETRIEVE ( p, * L ) > RETRIEVE ( q, * L ) )
Swap ( p, q, * L ) ; / / hoán đổi nội dung 2 thành phần
q = NEXT ( q, * L ) ;
}
p = NEXT ( p, * L ) ;
}
}
Tuy nhiên, cần phải nhấn mạnh vấn đề rằng, đây là những phép toán trừu tượng do tất cả chúng ta định nghĩa, nó chưa được thiết lập trong những ngôn từ lập trình. Do đó để setup giải thuật thành một chương trình chạy được thì ta cũng phải thiết lập những phép toán thành những chương trình con trong chương trình. Hơn nữa, trong khi setup đơn cử, một số ít tham số hình thức trong những phép toán trừu tượng không đóng vai trò gì trong chương trình con thiết lập chúng, do vậy ta hoàn toàn có thể bỏ lỡ nó trong list tham số của chương trình con. Ví dụ : phép toán trừu tượng INSERT_LIST ( x, p, L ) có 3 tham số hình thức : thành phần muốn thêm x, vị trí thêm vào p và list được thêm vào L. Nhưng khi setup list bằng con trỏ ( list link đơn ), tham số L là không thiết yếu vì với cấu trúc này chỉ có con trỏ tại vị trí p phải biến hóa để nối kết với ô chứa thành phần mới. Trong bài giảng này, ta vẫn giữ đúng những tham số trong cách thiết lập để làm cho chương trình giống hệt và trong suốt so với những chiêu thức setup của cùng một kiểu tài liệu trừu tượng .
3. Cài đặt danh sách
a. Cài đặt danh sách bằng mảng (danh sách đặc)
Ta có thể cài đặt danh sách bằng mảng như sau: dùng một mảng để lưu giữ liên tiếp các phần tử của danh sách từ vị trí đầu tiên của mảng. Với cách cài đặt này, dĩ nhiên, ta phải ước lượng số phần tử của danh sách để khai báo số phần tử của mảng cho thích hợp. Dễ thấy rằng số phần tử của mảng phải được khai báo không ít hơn số phần tử của danh sách. Nói chung là mảng còn thừa một số chỗ trống. Mặt khác ta phải lưu giữ độ dài hiện tại của danh sách, độ dài này cho biết danh sách có bao nhiêu phần tử và cho biết phần nào của mảng còn trống như trong hình II.1. Ta định nghĩa vị trí của một phần tử trong danh sách là chỉ số của mảng tại vị trí lưu trữ phần tử đó + 1(vì phần tử đầu tiên trong mảng là chỉ số 0).
Hình II. 1 : Cài đặt list bằng mảng
Với hình ảnh minh họa trên, ta cần các khai báo cần thiết là:
# define MaxLength …
/ / Số nguyên thích hợp để chỉ độ dài của list
typedef … ElementType ; / / kiểu của thành phần trong list
typedef int Position ; / / kiểu vị trí cuả những thành phần
typedef struct {
ElementType Elements [ MaxLength ] ;
/ / mảng chứa những thành phần của list
Position Last ; / / giữ độ dài list
} List ;
Trên đây là sự màn biểu diễn kiểu tài liệu trừu trượng list bằng cấu trúc tài liệu mảng. Phần tiếp theo là thiết lập những phép toán cơ bản trên list .
Khởi tạo danh sách rỗng
Danh sách rỗng là một list không chứa bất kể một thành phần nào ( hay độ dài list bằng 0 ). Theo cách khai báo trên, trường Last chỉ vị trí của thành phần ở đầu cuối trong list và đó cũng độ dài hiện tại của list, vì thế để khởi tạo list rỗng ta chỉ việc gán giá trị trường Last này bằng 0 .
void MakeNull_List ( List * L )
{ L -> Last = 0 ; }
1. Hãy trình diễn cách gọi thực thi chương trình con tạo list rỗng trên ?
2. Hãy lý giải cách khai báo tham số hình thức trong chương trình con và cách truyền tham số khi gọi chương trình con đó ?
Kiểm tra danh sách rỗng
Danh sách rỗng là một list mà độ dài của nó bằng 0 .
int Empty_List ( List L ) {
return L.Last = = 0 ;
}
Xen một phần tử vào danh sách
Khi xen thành phần có nội dung x vào tại vị trí p của list L thì sẽ Open những năng lực sau :
- Mảng đầy: mọi phần tử của mảng đều chứa phần tử của danh sách, tức là phần tử cuối cùng của danh sách nằm ở vị trí cuối cùng trong mảng. Nói cách khác, độ dài của danh sách bằng chỉ số tối đa của mảng; Khi đó không còn chỗ cho phần tử mới, vì vậy việc xen là không thể thực hiện được, chương trình con gặp lỗi.
- Ngược lại ta tiếp tục xét:
Nếu p không hợp lệ ( p > last + 1 hoặc p < 1 ) thì chương trình con gặp lỗi ; ( Vị trí xen p < 1 thì khi đó p không phải là một vị trí thành phần trong trong list đặc. Nếu vị trí p > L.last + 1 thì khi xen sẽ làm cho list L không còn là một list đặc nữa vì nó có một vị trí trong mảng mà chưa có nội dung. )
Nếu vị trí p hợp lệ thì ta triển khai xen theo những bước sau :
+ Dời những thành phần từ vị trí p đến cuối list ra sau 1 vị trí .
+ Độ dài list tăng 1 .
+ Đưa thành phần mới vào vị trí p
Chương trình con xen thành phần x vào vị trí p của list L hoàn toàn có thể viết như sau :
void Insert_List ( ElementType X, Position P, List * L ) {
if ( L -> Last = = MaxLength )
printf ( ” Danh sach day ” ) ;
else if ( ( P < 1 ) | | ( P > L -> Last + 1 ) )
printf ( ” Vi tri khong hop le ” ) ;
else {
Position Q. ;
/ * Dời những thành phần từ vị trí p ( chỉ số trong mảng là p-1 ) đến cuối list sang phải 1 vị trí * /
for ( Q = ( L -> Last-1 ) + 1 ; Q > P-1 ; Q — )
L -> Elements [ Q ] = L -> Elements [ Q-1 ] ;
/ / Đưa x vào vị trí p
L -> Elements [ P-1 ] = X ;
/ / Tăng độ dài list lên 1
L -> Last + + ;
}
}
Xóa phần tử ra khỏi danh sách
Xoá một thành phần ở vị trí p ra khỏi list L ta làm việc làm ngược lại với xen .
Trước tiên ta kiểm tra vị trí thành phần cần xóa xem có hợp lệ hay chưa. Nếu p > L.last hoặc p < 1 thì đây không phải là vị trí của thành phần trong list .
trái lại, vị trí đã hợp lệ thì ta phải dời những thành phần từ vị trí p + 1 đến cuối list ra trước một vị trí và độ dài list giảm đi 1 thành phần ( do đã xóa bớt 1 thành phần ) .
void Delete_List ( Position P, List * L ) {
if ( ( P < 1 ) | | ( P > L -> Last ) )
printf ( ” Vi tri khong hop le ” ) ;
else if ( EmptyList ( * L ) )
printf ( ” Danh sach rong ! ” ) ;
else {
Position Q. ;
/ * Dời những thành phần từ vị trí p + 1 ( chỉ số trong mảng là p ) đến cuối list sang trái 1 vị trí * /
for(Q=P-1;Q
L -> Elements [ Q ] = L -> Elements [ Q. + 1 ] ;
L -> Last — ;
}
}
Định vị một phần tử trong danh sách
Để xác định vị trí thành phần tiên phong có nội dung x trong list L, ta thực thi dò tìm từ đầu list. Nếu tìm thấy x thì vị trí của thành phần tìm thấy được trả về, nếu không tìm thấy thì hàm trả về vị trí sau vị trí của thành phần sau cuối trong list, tức là ENDLIST ( L ) ( ENDLIST ( L ) = L.Last + 1 ). Trong trường hợp có nhiều thành phần cùng giá trị x trong list thì vị trí của thành phần được tìm thấy tiên phong được trả về .
Position Locate ( ElementType X, List L ) {
Position P. ;
int Found = 0 ;
P. = First ( L ) ; / / vị trí thành phần tiên phong
/ * trong khi chưa tìm thấy và chưa kết thúc list thì xét thành phần sau đó * /
while ( ( P. ! = EndList ( L ) ) và và ( Found = = 0 ) )
if ( Retrieve ( P., L ) = = X ) Found = 1 ;
else P = Next ( P., L ) ;
return P. ;
}
Lưu ý : Các phép toán sau phải thiết kế trước Locate
- First(L)=1
- Retrieve(P,L)=L.Elements[P-1]
- EndList(L)=L.Last+1
- Next(P,L)=P+1
Hãy lý giải tại sao nội dung thành phần tại vị trí P. trên list L là L.Elements [ P-1 ] ?
Các phép toán khác cũng thuận tiện setup nên xem như bài tập dành cho bạn đọc .
Ví dụ : Vận dụng các phép toán trên danh sách đặc để viết chương trình nhập vào một danh sách các số nguyên và hiển thị danh sách vừa nhập ra màn hình. Thêm phần tử có nội dung x vào danh sách tại ví trí p (trong đó x và p được nhập từ bàn phím). Xóa phần tử đầu tiên có nội dung x (nhập từ bàn phím) ra khỏi danh sách.
Hướng xử lý :
Giả sử ta đã setup vừa đủ những phép toán cơ bản trên list. Để triển khai nhu yếu như trên, ta cần thiết kế thêm một số ít chương trình con sau :
- Nhập danh sách từ bàn phím (READ_LIST(L)) (Phép toán này chưa có trong kiểu danh sách)
- Hiển thị danh sách ra màn hình (in danh sách) (PRINT_LIST(L)) (Phép toán này chưa có trong kiểu danh sách).
Thực ra thì tất cả chúng ta chỉ cần sử dụng những phép toán MakeNull_List, Insert_List, Delete_List, Locate và những chương trình con Read_List, Print_List vừa nói trên là hoàn toàn có thể xử lý được bài toán. Để phân phối nhu yếu đặt ra, ta viết chương trình chính để nối kết những chương trình con lại với nhau như sau :
int main ( ) {
List L ;
ElementType X ;
Position P. ;
MakeNull_List ( và L ) ; / / Khởi tạo list rỗng
Read_List ( và L ) ;
printf ( ” Danh sach vua nhap : ” ) ;
Print_List ( L ) ; / / In danh sach len man hinh
printf ( ” Phan tu can them : ” ) ;
scanf ( ” % d “, và X ) ;
printf ( ” Vi tri can them : ” ) ;
scanf ( ” % d “, và P. ) ;
Insert_List ( X, P., và L ) ;
printf ( ” Danh sach sau khi them phan tu la : ” ) ;
PrintList ( L ) ;
printf ( ” Noi dung phan tu can xoa : ” ) ;
scanf ( ” % d “, và X ) ;
P. = Locate ( X, L ) ;
Delete_List ( P., và L ) ;
printf ( ” Danh sach sau khi xoa % d la : “, X ) ;
Print_List ( L ) ;
return 0 ;
}
b. Cài đặt danh sách bằng con trỏ ( danh sách liên kết)
Cách khác để thiết lập list là dùng con trỏ để link những ô chứa những thành phần. Trong cách thiết lập này những thành phần của list được tàng trữ trong những ô, mỗi ô hoàn toàn có thể chỉ đến ô chứa thành phần tiếp nối trong list. Bạn đọc hoàn toàn có thể tưởng tượng chính sách này qua ví dụ sau :
Giả sử 1 lớp có 4 bạn : Đông, Tây, Nam, Bắc có địa chỉ lần lượt là d, t, n, b. Giả sử : Đông có địa chỉ của Nam, Tây không có địa chỉ của bạn nào, Bắc giữ địa chỉ của Đông, Nam có địa chỉ của Tây ( xem hình II. 2 ) .
Hình II. 2
Như vậy, nếu ta xét thứ tự những thành phần bằng chính sách chỉ đến này thì ta có một list : Bắc, Đông, Nam, Tây. Hơn nữa để có list này thì ta cần và chỉ cần giữ địa chỉ của Bắc .
Trong cài đặt, để một ô có thể chỉ đến ô khác ta cài đặt mỗi ô là một mẩu tin (record, struct) có hai trường: trường Element giữ giá trị của các phần tử trong danh sách; trường next là một con trỏ giữ địa chỉ của ô kế tiếp.Trường next của phần tử cuối trong danh sách chỉ đến một giá trị đặc biệt là NULL. Cấu trúc như vậy gọi là danh sách cài đặt bằng con trỏ hay danh sách liên kết đơn hay ngắn gọn là danh sách liên kết.
Hình II. 3 Danh sách link đơn
Để quản lý danh sách ta chỉ cần một biến giữ địa chỉ ô chứa phần tử đầu tiên của danh sách, tức là một con trỏ trỏ đến phần tử đầu tiên trong danh sách. Biến này gọi là chỉ điểm đầu danh sách (Header). Để đơn giản hóa vấn đề, trong chi tiết cài đặt, Header là một biến cùng kiểu với các ô chứa các phần tử của danh sách và nó có thể được cấp phát ô nhớ y như một ô chứa phần tử của danh sách (hình II.3). Tuy nhiên Header là một ô đặc biệt nên nó không chứa phần tử nào của danh sách, trường dữ liệu của ô này là rỗng, chỉ có trường con trỏ Next trỏ tới ô chứa phần tử đầu tiên thật sự của danh sách. Nếu danh sách rỗng thì Header->next trỏ tới NULL. Việc cấp phát ô nhớ cho Header như là một ô chứa dữ liệu bình thường nhằm tăng tính đơn giản của các giải thuật thêm, xoá các phần tử trong danh sách.
Ở đây ta cần phân biệt rõ giá trị của một thành phần và vị trí ( position ) của nó trong cấu trúc trên. Ví dụ giá trị của thành phần tiên phong của list trong hình II. 3 là a1, Trong khi vị trí của nó là địa chỉ của ô chứa nó, tức là giá trị nằm ở trường next của ô Header. Giá trị và vị trí của những thành phần của list trong hình II. 3 như sau :
| Phần tử thứ | Giá trị | Vị trí |
|---|---|---|
|
1 |
a1 | HEADER 1 |
| 2 | a2 | 1 |
| … | … | … |
| n | an | ( n-1 ) |
| Sau thành phần sau cuối | Không xác lập |
N và n -> next có giá trị là
NULL |
Như đã thấy trong bảng trên, vị trí của thành phần thứ i là ( i-1 ), như vậy để biết được vị trí của thành phần thứ i ta phải truy xuất vào ô thứ ( i-1 ). Khi thêm hoặc xoá một thành phần trong list link tại vị trí p, ta phải update lại con trỏ trỏ tới vị trí này, tức là update lại ( p-1 ). Nói cách khác, để thao tác vào vị trí p ta phải biết con trỏ trỏ vào p mà con trỏ này chính là ( p-1 ). Do đó ta định nghĩa p-1 như thể vị trí của p. Có thể nói nôm na rằng vị trí của thành phần ai là địa chỉ của ô đứng ngay phía trước ô chứa ai. Hay đúng chuẩn hơn, ta nói, vị trí của thành phần thứ i là con trỏ trỏ tới ô có trường next trỏ tới ô chứa thành phần ai Như vậy vị trí của thành phần thứ 1 là con trỏ trỏ đến Header, vị trí thành phần thứ 2 là con trỏ trỏ ô chứa thành phần a1, vị trí của thành phần thứ 3 là con trỏ trỏ ô a2, …, vị trí thành phần thứ n là con trỏ trỏ ô chứa an-1. Vậy vị trí sau thành phần cuối trong list, tức là ENDLIST, chính là con trỏ trỏ ô chứa thành phần an ( xem hình II. 3 ) .
Theo định nghĩa này ta có, nếu p là vị trí của thành phần thứ p trong list thì giá trị của thành phần ở vị trí p này nằm trong trường element của ô được trỏ bởi p -> next. Nói cách khác p -> next -> element chứa nội dung của thành phần ở vị trí p trong list .
Các khai báo cần thiết là
typedef … ElementType ; / / kiểu của thành phần trong list
typedef struct Node {
ElementType Element ; / / Chứa nội dung của thành phần
Node * Next ; / * con trỏ chỉ đến thành phần tiếp nối trong list * /
} ;
typedef Node * Position ; / / Kiểu vị trí
typedef Position List ;
Trong khai báo trên, tại sao phải đặt tên kiểu Node trước khi đưa ra những trường trong kiểu đó ?
Cách khai báo sau còn đúng không ?
typedef struct
{
ElementType Element ;
Node * Next ;
} Node ;
Tạo danh sách rỗng
Như đã nói ở phần trên, ta dùng Header như là một biến con trỏ có kiểu giống như kiểu của một ô chứa một phần tử của danh sách. Tuy nhiên trường Element của Header không bao giờ được dùng, chỉ có trường Next dùng để trỏ tới ô chứa phần tử đầu tiên của danh sách. Vậy nếu như danh sách rỗng thì trường ô Header vẫn phải tồn tại và ô này có trường next chỉ đến NULL (do không có một phần tử nào). Vì vậy khi khởi tạo danh sách rỗng, ta phải cấp phát ô nhớ cho HEADER và cho con trỏ trong trường next của nó trỏ tới NULL.
void MakeNull_List ( List * Header ) {
( * Header ) = ( Node * ) malloc ( sizeof ( Node ) ) ;
( * Header ) -> Next = NULL ;
}
Kiểm tra một danh sách rỗng
Danh sách rỗng nếu như trường next trong ô Header trỏ tới NULL.
int Empty_List ( List L ) {
return ( L -> Next = = NULL ) ;
}
Xen một phần tử vào danh sách :
Xen một thành phần có giá trị x vào list L tại vị trí p ta phải cấp phép một ô mới để tàng trữ thành phần mới này và nối kết lại những con trỏ để đưa ô mới này vào vị trí p. Sơ đồ nối kết và thứ tự những thao tác được cho trong hình II. 4 .
Hình II. 4 : Thêm một thành phần vào list tại vị trí p
void Insert_List ( ElementType X, Position P, List * L ) {
Position T ;
T = ( Node * ) malloc ( sizeof ( Node ) ) ;
T -> Element = X ;
T -> Next = P -> Next ;
P. -> Next = T ;
}
Tham số L ( list ) trong chương trình con trên có bỏ được không ? Tại sao ?
Xóa phần tử ra khỏi danh sách
Hình II. 5 : Xoá thành phần tại vị trí p
Tương tự như khi xen một thành phần vào list link, muốn xóa một thành phần khỏi list ta cần biết vị trí p của thành phần muốn xóa trong list L. Nối kết lại những con trỏ bằng cách cho p trỏ tới thành phần đứng sau thành phần thứ p. Trong những ngôn từ lập trình không có chính sách tịch thu vùng nhớ tự động hóa như ngôn từ Pascal, C thì ta phải tịch thu vùng nhớ của ô bị xóa một những tường minh trong giải thuật. Tuy nhiên vì tính đơn thuần của giải thuật do đó nhiều lúc tất cả chúng ta không đề cập đến việc tịch thu vùng nhớ cho những ô bị xoá. Chi tiết và trình tự những thao tác để xoá một thành phần trong list link như trong hình II. 5. Chương trình con hoàn toàn có thể được thiết lập như sau :
void Delete_List ( Position P, List * L ) {
Position T ;
if ( P -> Next ! = NULL ) {
T = P -> Next ; / * / giữ ô chứa thành phần bị xoá để tịch thu vùng nhớ * /
P. -> Next = T -> Next ; / * nối kết con trỏ trỏ tới thành phần thứ p + 1 * / không lấy phí ( T ) ; / / tịch thu vùng nhớ
}
}
Định vị một phần tử trong danh sách liên kết
Để xác định thành phần x trong list L ta triển khai tìm từ đầu list ( ô header ) nếu tìm thấy thì vị trí của thành phần tiên phong được tìm thấy sẽ được trả về nếu không thì ENDLIST ( L ) được trả về. Nếu x có trong sách sách và hàm Locate trả về vị trí p mà trong đó ta có x = p -> next -> element .
Position Locate ( ElementType X, List L ) {
Position P. ;
int Found = 0 ; P = L ;
while ( ( P -> Next ! = NULL ) và và ( Found = = 0 ) )
if ( P -> Next -> Element = = X ) Found = 1 ;
else P = P -> Next ;
return P. ;
}
Thực chất, khi gọi hàm Locate ở trên ta hoàn toàn có thể truyền giá trị cho L là bất kể giá trị nào. Nếu L là Header thì chương trình con sẽ tìm x từ đầu list. Nếu L là một vị trí p bất kể trong list thì chương trình con Locate sẽ thực thi xác định thành phần x từ vị trí p .
Xác định nội dung phần tử:
Nội dung phần tử đang lưu trữ tại vị trí p trong danh sách L là p->next->Element Do đó, hàm sẽ trả về giá trị p->next->element nếu phần tử có tồn tại, ngược lại phần tử không tồn tại (p->next=NULL) thì hàm không xác định.
ElementType Retrieve ( Position P, List L ) {
if ( P -> Next ! = NULL )
return P -> Next -> Element ;
}
Hãy phong cách thiết kế hàm Locate bằng cách sử dụng những phép toán trừu tượng cơ bản trên list ?
c. So sánh hai phương pháp cài đặt
Không thể Kết luận giải pháp thiết lập nào hiệu suất cao hơn, mà nó trọn vẹn tuỳ thuộc vào từng ứng dụng hay tuỳ thuộc vào những phép toán trên list. Tuy nhiên ta hoàn toàn có thể tổng kết 1 số ít ưu điểm yếu kém của từng giải pháp làm cơ sở để lựa chọn giải pháp thiết lập thích hợp cho từng ứng dụng :
- Cài đặt bằng mảng đòi hỏi phải xác định số phần tử của mảng, do đó nếu không thể ước lượng được số phần tử trong danh sách thì khó áp dụng cách cài đặt này một cách hiệu quả vì nếu khai báo thiếu chỗ thì mảng thường xuyên bị đầy, không thể làm việc được còn nếu khai báo quá thừa thì lãng phí bộ nhớ.
- Cài đặt bằng con trỏ thích hợp cho sự biến động của danh sách, danh sách có thể rỗng hoặc lớn tuỳ ý chỉ phụ thuộc vào bộ nhớ tối đa của máy. Tuy nhiên ta phải tốn thêm vùng nhớ cho các con trỏ (trường next).
- Cài đặt bằng mảng thì thời gian xen hoặc xoá một phần tử tỉ lệ với số phần tử đi sau vị trí xen/ xóa. Trong khi cài đặt bằng con trỏ các phép toán này mất chỉ một hằng thời gian.
- Phép truy nhập vào một phần tử trong danh sách, chẳng hạn như PREVIOUS, chỉ tốn một hằng thời gian đối với cài đặt bằng mảng, trong khi đối với danh sách cài đặt bằng con trỏ ta phải tìm từ đầu danh sách cho đến vị trí trước vị trí của phần tử hiện hành.Nói chung danh sách liên kết thích hợp với danh sách có nhiều biến động, tức là ta thường xuyên thêm, xoá các phần tử.
Cho biết ưu khuyết điểm của list đặc và list link ?
d. Cài đặt bằng con nháy
Một số ngôn ngữ lập trình không có cung cấp kiểu con trỏ. Trong trường hợp này ta có thể “giả” con trỏ để cài đặt danh sách liên kết. Ý tưởng chính là: dùng mảng để chứa các phần tử của danh sách, các “con trỏ” sẽ là các biến số nguyên (int) để giữ chỉ số của phần tử kế tiếp trong mảng. Để phân biệt giữa “con trỏ thật” và “con trỏ giả” ta gọi các con trỏ giả này là con nháy (cursor). Như vậy để cài đặt danh sách bằng con nháy ta cần một mảng mà mỗi phần tử xem như là một ô gồm có hai trường: trường Element như thông lệ giữ giá trị của phần tử trong danh sách (có kiểu Elementtype) trường Next là con nháy để chỉ tới vị trí trong mảng của phần tử kế tiếp. Chẳng hạn hình II.6 biểu diễn cho mảng SPACE đang chứa hai danh sách L1, L2. Để quản lí các danh sách ta cũng cần một con nháy chỉ đến phần tử đầu của mỗi danh sách (giống như header trong danh sách liên kết). Phần tử cuối cùng của danh sách ta cho chỉ tới giá trị đặc biệt Null, có thể xem Null = -1 với một giả thiết là mảng SPACE không có vị trí nào có chỉ số -1.
Trong hình II.6, danh sách L1 gồm 3 phần tử : f, o ,r. Chỉ điểm đầu của L1 là con nháy có giá trị 5, tức là nó trỏ vào ô lưu giữ phần tử đầu tiên của L1, trường next của ô này có giá trị 1 là ô lưu trữ phần tử kế tiếp (tức là o). Trường next tại ô chứa o là 4 là ô lưu trữ phần tử kế tiếp trong danh sách (tức là r). Cuối cùng trường next của ô này chứa Null nghĩa là danh sách không còn phần tử kế tiếp.
Phân tích tương tự như ta có L2 gồm 4 thành phần : w, i, n, d
Hình II. 6 Mảng đang chứa hai list L1 và L2
Khi xen một thành phần vào list ta lấy một ô trống trong mảng để chứa thành phần mới này và nối kết lại những con nháy. Ngược lại, khi xoá một thành phần khỏi list ta nối kết lại những con nháy để loại thành phần này khỏi list, điều này kéo theo số ô trống trong mảng tăng lên 1. Vấn đề là làm thế nào để quản lí những ô trống này để biết ô nào còn trống ô nào đã dùng ? một giải pháp là link toàn bộ những ô trống vào một list đặc biệt quan trọng gọi là AVAILABLE, khi xen một thành phần vào list ta lấy ô trống đầu AVAILABLE để chứa thành phần mới này. Khi xoá một thành phần từ list ta cho ô bị xoá nối vào đầu AVAILABLE. Tất nhiên khi mới khởi đầu việc thiết kế xây dựng cấu trúc thì mảng chưa chứa thành phần nào của bất kể một list nào. Lúc này toàn bộ những ô của mảng đều là ô trống, và như vậy, toàn bộ những ô đều được link vào trong AVAILABLE. Việc khởi tạo AVAILABLE khởi đầu hoàn toàn có thể thực thi bằng cách cho thành phần thứ i của mảng trỏ tới thành phần i + 1 .
Các khai báo cần thiết cho danh sách
# define MaxLength … / / Chieu dai mang
# define Null – 1 / / Gia tri Null
typedef … ElementType ; / * kiểu của những thành phần trong list * /
typedef struct {
ElementType Elements ; / * trường chứa thành phần trong list * /
int Next ; / / con nháy trỏ đến thành phần tiếp nối
} Node ;
Node Space [ MaxLength ] ; / / Mang toan cuc
int Available ;
Hình II. 7 : Khởi tạo Available bắt đầu
Khởi tạo cấu trúc – Thiết lập available ban đầu
Ta cho phần tử thứ 0 của mảng trỏ đến phần tử thứ 1,…, phần tử cuối cùng trỏ Null. Chỉ điểm đầu của AVAILABLE là 0 như trong hình II.7
void Initialize ( ) {
int i ;
for(i=0; i
Space [ i ]. Next = i + 1 ;
Space [ MaxLength-1 ]. Next = NULL ;
Available = 0 ;
}
Chuyển một ô từ danh sách này sang danh sách khác
Ta thấy thực chất của việc xen hay xoá một phần tử là thực hiện việc chuyển một ô từ danh sách này sang danh sách khác. Chẳng hạn muốn xen thêm một phần tử vào danh sách L1 trong hình II.6 vào một vị trí p nào đó ta phải chuyển một ô từ AVAILABLE (tức là một ô trống) vào L1 tại vị trí p; muốn xoá một phần tử tại vị trí p nào đó trong danh sách L2, chẳng hạn, ta chuyển ô chứa phần tử đó sang AVAILABLE, thao tác này xem như là giải phóng bộ nhớ bị chiếm bởi phần tử này. Do đó tốt nhất ta viết một hàm thực hiện thao tác chuyển một ô từ danh sách này sang danh sách khác và hàm cho kết quả kiểu int tùy theo chuyển thành công hay thất bại (là 0 nếu chuyển không thành công, 1 nếu chuyển thành công). Hàm Move sau đây thực hiện chuyển ô được trỏ tới bởi con nháy P vào danh sách khác được trỏ bởi con nháy Q như trong hình II.8. Hình II.8 trình bày các thao tác cơ bản để chuyển một ô (ô được chuyển ta tạm gọi là ô mới):
Hình II. 8
Chuyển 1 ô từ list này sang list khác ( những link vẽ bằng nét đứt màn biểu diễn cho những link cũ – trước khi giải thuật khởi đầu )
- Dùng con nháy temp để trỏ ô được trỏ bởi Q.
- Cho Q trỏ tới ô mới.
- Cập nhật lại con nháy P bằng cách cho nó trỏ tới ô kế tiếp.
- Nối con nháy trường next của ô mới (ô mà Q đang trỏ) trỏ vào ô mà temp đang trỏ.
int Move ( int * p, int * q ) {
int temp ;
if ( * p = = Null )
return 0 ; / / Khong co o de chuyen
else
{
temp = * q ;
* q = * p ;
* p = Space [ * q ]. Next ;
Space [ * q ]. Next = temp ;
return 1 ; / / Chuyen thanh cong
}
}
Trong cách thiết lập này, khái niệm vị trí tựa như như khái niệm vị trí trong trường hợp setup bằng con trỏ, tức là, vị trí của thành phần thứ I trong list là chỉ số của ô trong mảng chứa con nháy trỏ đến ô chứa thành phần thứ i. Ví dụ xét list L1 trong hình II. 6, vị trí của thành phần thứ 2 trong list ( thành phần có giá trị o ) là 5, không phải là 1 ; vị trí của thành phần thứ 3 ( thành phần có giá trị r ) là 1, không phải là 4. Vị trí của thành phần thứ 1 ( thành phần có giá trị f ) được định nghĩa là – 1, vì không có ô nào trong mảng chứa con nháy trỏ đến ô chứa thành phần f .
Xen một phần tử vào danh sách
Muốn xen một thành phần vào list ta cần biết vị trí xen, gọi là p, rồi ta chuyển ô đầu của available vào vị trí này. Chú ý rằng vị trí của thành phần tiên phong trong list được định nghĩa là – 1, do đó nếu p = – 1 có nghĩa là triển khai việc thêm vào đầu list .
void Insert_List ( ElementType X, int P., int * L ) {
if ( P = = – 1 ) / / Xen dau danh sach
{
if ( Move ( và Available, L ) ) Space [ * L ]. Elements = X ;
else printf ( ” Loi ! Khong con bo nho trong ” ) ;
}
else / / Chuyen mot o tu Available vao vi tri P
{
if ( Move ( và Available, và Space [ P ]. Next ) )
/ / O nhan X la o tro boi Space [ p ]. Next Space [ Space [ P ]. Next ]. Elements = X ;
else printf ( ” Loi ! Khong con bo nho trong ” ) ;
}
}
Xoá một phần tử trong danh sách
Muốn xoá một thành phần tại vị trí p trong list ta chỉ cần chuyển ô chứa thành phần tại vị trí này vào đầu AVAILABLE. Tương tự như phép thêm vào, nếu p = – 1 thì xoá thành phần đầu list .
void Delete_List ( int p, int * L ) {
if ( p = = – 1 ) / / Neu la o dau tien
{
if ( ! Move ( L, và Available ) ) printf ( ” Loi trong khi xoa ” ) ;
/ / else Khong lam gi ca
}
else
if (!Move(&Space[p].Next,&Available))
printf ( ” Loi trong khi xoa ” ) ;
/ / else Khong lam gi
}
Source: https://final-blade.com
Category: Kiến thức Internet
