THAM KHẢO
Video giải đáp cách setup LIST bởi mảng
I. KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST)
1. Quan niệm danh sách
Mô hình toán học tập của danh sách là một tập hòa hợp hữu hạn các thành phần có và một kiểu, mà bao quát ta hotline là kiểu thành phần (Elementtype). Ta biểu diễn danh sách như là 1 trong chuỗi các phần tử của nó: a1, a2, . . ., anvới n ≥ 0. Trường hợp n=0 ta nói danh sách rỗng (empty list). Ví như n > 0 ta call a1 là phần tử đầu tiên và an là phần tử cuối cùng của danh sách. Số bộ phận của list ta call là độ dài của danh sách.Một tính chất đặc trưng của list là các bộ phận của danh sách có thiết bị tự tuyến đường tính theo địa điểm (position) mở ra của các phần tử. Ta nói ai đứng trước ai+1, với i từ một đến n-1; tương tự ta nói ailà bộ phận đứng sau ai-1, cùng với i trường đoản cú 2 mang lại n. Ta cũng nói ai là thành phần tại vị trí thứ i, hay bộ phận thứ i của danh sách.Ví dụ: Tập đúng theo họ tên những sinh viên của lớp TINHOC 28 được liệt kê trên chứng từ như sau:Nguyễn Trung CangNguyễn Ngọc ChươngLê Thị Lệ SươngTrịnh Vũ ThànhNguyễn Phú Vĩnhlà một danh sách. Danh sách này gồm bao gồm 5 phần tử, mỗi thành phần có một vị trí trong danh sách theo đồ vật tự xuất hiện của nó.Bạn đang xem: Cách dùng list trong c#
2. Các phép toán bên trên danh sách
Để thiết lập cấu hình kiểu tài liệu trừu tượng danh sách (hay gọn ghẽ là danh sách) ta đề xuất định nghĩa những phép toán bên trên danh sách. Cùng như họ sẽ thấy trong tổng thể giáo trình, không có một tập hợp những phép toán nào tương thích cho mọi vận dụng (application). Vì chưng vậy tại chỗ này ta sẽ định nghĩa một số trong những phép toán cơ phiên bản nhất trên danh sách. Để tiện lợi cho vấn đề định nghĩa ta mang sử rằng danh sách gồm các thành phần có mẫu mã là kiểu thành phần (elementType); địa điểm của các phần tử trong danh sách có kiểu dáng là thứ hạng vị trí và vị trí sau bộ phận cuối cùng trong list L là ENDLIST(L). Cần nhấn mạnh rằng quan niệm vị trí (position) là vì ta định nghĩa, nó không hẳn là quý hiếm của các thành phần trong danh sách. Vị trí hoàn toàn có thể là đồng bộ với địa chỉ lưu trữ bộ phận hoặc không.Các phép toán được tư tưởng trên list là: INSERT_LIST(x,p,L): xen thành phần x ( hình trạng ElementType ) tại vị trí p (kiểu position) trong list L. Tức là nếu danh sách là a1, a2, . , ap-1, ap ,. . , an thì sau khi xen ta có hiệu quả a1, a2, . . ., ap-1, x, ap, . . . , an. Giả dụ vị trí p không mãi sau 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ó ngôn từ x đầu tiên trong danh sách L. Locate trả công dụng là địa điểm (kiểu position) của thành phần x vào danh sách. Nếu x không tồn tại trong list thì vị trí sau thành phần cuối cùng của danh sách được trả về, tức là ENDLIST(L). RETRIEVE(p,L) lấy quý giá của bộ phận ở vị trí p. (kiểu position) của list L; nếu địa điểm p không có trong danh sách thì công dụng không xác định (có thể thông tin 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 địa chỉ p không tồn tại trong danh sách thì phép toán không được khái niệm và danh sách L sẽ không còn thay đổi. ENDLIST(L): Trả về vị trí sau phần tử ở đầu cuối của List. NEXT(p,L) cho tác dụng là địa điểm 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 list L thì NEXT(p,L) cho công dụng là ENDLIST(L). Next không xác định nếu p không hẳn là địa chỉ của 1 phần tử vào danh sách. PREVIOUS(p,L) cho hiệu quả là vị trí của bộ phận đứng trước thành phần p trong danh sách. Nếu p. Là bộ phận đầu tiên trong list thì Previous(p,L) ko xác định. Previous cũng không xác định trong trường hòa hợp p không hẳn là địa điểm của phần tử nào vào danh sách.FIRST(L) cho kết quả là vị trí của thành phần đầu tiên vào danh sách. Nếu list rỗng thì ENDLIST(L) được trả về. EMPTY_LIST(L) cho công dụng TRUE nếu danh sách có rỗng, ngược lại nó cho giá trị FALSE. MAKENULL_LIST(L) khởi sinh sản một danh sách L rỗng.Trong kiến tạo các giải thuật sau này chúng ta dùng các phép toán trừu tượng đã được định nghĩa tại chỗ này như là các phép toán nguyên thủy.Muốn thêm phần tử vào đầu tốt cuối danh sách ta hotline phép toán như thế nào và gọi phép toán đó như vậy nào?Ví dụ: Dùng những phép toán trừu tượng trên danh sách, viết một chương trình bé nhận một tham số là danh sách rồi thu xếp danh sách theo sản phẩm công nghệ tự tăng ngày một nhiều (giả sử các phần tử trong list thuộc kiểu có thứ tự).Giả sử SWAP(p,q) thực hiện việc đổi khu vực hai thành phần tại vị trí p và q trong danh sách, công tác con thu xếp được viết như sau:
void sort(List* L) Position p,q; //kiểu địa chỉ của các thành phần trong list p= FIRST(*L); //vị trí bộ phận đầu tiên trong list while (p!=ENDLIST(*L)) q=NEXT(p,*L); //vị trí bộ phận đứng tức thì sau phần tử p while (q!=ENDLIST(*L)) if (RETRIEVE(p,*L) > RETRIEVE(q,*L))
Swap(p,q,*L); // hoán đổi nội dung 2 bộ phận q=NEXT(q,*L); p=NEXT(p,*L);
Tuy nhiên, cần phải nhấn dũng mạnh rằng, đó là các phép toán trừu tượng do bọn họ định nghĩa, nó vẫn chưa được cài đặt trong những ngôn ngữ lập trình. Do đó để thiết đặt giải thuật thành một công tác chạy được thì ta cũng phải setup các phép toán thành các chương trình con trong chương trình. Rộng nữa, trong khi cài đặt cụ thể, một số tham số bề ngoài trong những phép toán trừu tượng không đóng vai trò gì trong lịch trình con setup chúng, thế nên ta hoàn toàn có thể bỏ qua nó trong danh sách tham số của chương trình con. Ví dụ: phép toán trừu tượng INSERT_LIST(x,p,L) bao gồm 3 thông số hình thức: bộ phận muốn thêm x, địa điểm thêm vào p. Và danh sách được cung ứng L. Nhưng mà khi thiết đặt danh sách bởi con trỏ (danh sách links đơn), tham số L là không cần thiết vì với kết cấu này chỉ gồm con trỏ trên vị trí phường phải biến đổi để nối kết cùng với ô chứa phần tử mới. Trong bài giảng này, ta vẫn giữ lại đúng đa số tham số trong cách cài đặt để khiến cho chương trình đồng nhất và trong suốt so với các cách thức cài đặt của cùng một kiểu dữ liệu trừu tượng.
3. Cài đặt danh sách
a. Thiết lập danh sách bởi mảng (danh sách đặc)Ta bao gồm thể setup danh sách bằng mảng như sau: dùng một mảng nhằm lưu giữ thường xuyên các phần tử của danh sách từ vị trí đầu tiên của mảng. Cùng với cách thiết lập này, dĩ nhiên, ta phải ước lượng số thành phần của list để khai báo số thành phần của mảng mang đến thích hợp. Hay thấy rằng số thành phần của mảng buộc phải được khai báo không ít hơn số thành phần của danh sách. Nói tầm thường là mảng còn thừa một số trong những chỗ trống. Ngoài ra ta yêu cầu lưu giữ lại độ dài bây giờ của danh sách, độ lâu năm này cho biết thêm danh sách gồm bao nhiêu phần tử và cho biết thêm phần làm sao của mảng còn trống như trong hình II.1. Ta định nghĩa vị trí của một trong những phần tử trong list là chỉ số của mảng tại địa chỉ lưu trữ bộ phận đó + 1(vì thành phần đầu tiên vào mảng là chỉ số 0).
Hình II.1: thiết đặt danh sách bởi mảngVới hình hình ảnh minh họa trên, ta phải các khai báo cần thiết là:
#define MaxLength ...//Số nguyên thích hợp để chỉ độ dài của danh sáchtypedef ... ElementType;//kiểu của bộ phận trong danh sáchtypedef int Position; //kiểu địa điểm cuả các phần tửtypedef struct ElementType Elements
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 dữ liệu mảng. Phần tiếp theo sau là setup các phép toán cơ phiên bản trên danh sách.Khởi tạo list rỗngDanh sách rỗng là một danh sách không chứa bất kỳ một trong những phần tử như thế nào (hay độ dài list bằng 0). Theo cách khai báo trên, ngôi trường Last chỉ vị trí của bộ phận cuối thuộc trong danh sách và này cũng độ dài bây giờ của danh sách, vày vậy để khởi tạo danh sách rỗng ta chỉ bài toán gán quý giá trường Last này bởi 0.
1. Hãy trình diễn cách gọi thực thi chương trình bé 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à giải pháp truyền tham số khi call chương trình con đó?Kiểm tra danh sách rỗngDanh sách rỗng là 1 danh sách nhưng mà độ nhiều năm của nó bằng 0.
Xen một trong những phần tử vào danh sáchKhi xen phần tử có ngôn từ x vào trên vị trí p. Của list L thì sẽ xuất hiện thêm các khả năng sau:Mảng đầy: mọi thành phần của mảng hồ hết chứa thành phần của danh sách, tức là phần tử cuối thuộc của danh sách nằm ở vị trí ở đầu cuối trong mảng. Nói biện pháp khác, độ nhiều năm của list bằng chỉ số buổi tối đa của mảng; lúc đó không thể chỗ cho phần tử mới, vì chưng vậy việc xen là ko thể thực hiện được, công tác con chạm chán lỗi.Ngược lại ta tiếp tục xét:Nếu p. Không phù hợp lệ (p>last+1 hoặc pL.last+1 thì lúc xen sẽ tạo cho danh sách L không còn là một danh sách đặc nữa bởi vì nó bao gồm một vị trí trong mảng mà chưa tồn tại nội dung.)Nếu vị trí phường hợp lệ thì ta tiến hành xen theo các bước sau:+ Dời các phần tử từ vị trí p. đến cuối list ra sau 1 vị trí.+ Độ dài danh sách tăng 1.+ Đưa thành phần mới vào địa điểm pChương trình nhỏ xen phần tử x vào vị trí p. Của danh sách L hoàn toàn có thể viết như sau:
void Insert_List(ElementType X, Position P, menu *L) if (L->Last==MaxLength) printf("Danh sach day"); else if ((PL->Last+1))
printf("Vi tri khong hop le"); else Position Q; /*Dời các phần tử từ vị trí p. (chỉ số trong mảng là p-1) cho cuối list sang bắt buộc 1 vị trí*/ for(Q=(L->Last-1)+1;Q>P-1;Q--) L->Elements Ngược lại, vị trí vẫn hợp lệ thì ta đề xuất dời các thành phần từ địa chỉ p+1 mang đến cuối danh sách ra trước một vị trí và độ dài danh sách giảm đi một trong những phần tử ( bởi vì đã xóa bớt một phần tử). Xem thêm: Review Vitamin E Kirkland Có Tốt Không? Cách Dùng Vitamin E Của Mỹ Hãng Kirkland Thực ra thì chúng ta chỉ đề xuất sử dụng những phép toán MakeNull_List, Insert_List, Delete_List, Locate và các chương trình bé Read_List, Print_List vừa nói bên trên là có thể giải quyết được bài toán. Để đáp ứng nhu cầu yêu mong đặt ra, ta viết chương trình chính để nối kết đầy đủ chương trình bé lại với nhau như sau: Giả sử 1 lớp có 4 bạn: Đông, Tây, Nam, Bắc có showroom 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 hàng của chúng ta nào, Bắc giữ showroom của Đông, phái nam có showroom của Tây (xem hình II.2).Hình II.2Như vậy, nếu ta xét thiết bị tự các thành phần bằng hình thức chỉ mang lại này thì ta bao gồm một danh sách: Bắc, Đông, Nam, Tây. Hơn nữa để có danh sách này thì ta đề nghị và chỉ việc giữ add của Bắc.Trong sở hữu đặt, nhằm một ô hoàn toàn có thể chỉ mang đến ô không giống ta thiết đặt mỗi ô là một trong những mẩu tin (record, struct) có hai trường: ngôi trường Element giữ giá trị của các phần tử trong danh sách; trường next là một trong những con trỏ giữ địa chỉ cửa hàng của ô kế tiếp.Trường next của phần tử cuối trong danh sách chỉ đến một giá bán trị nhất là NULL. Cấu trúc như vậy gọi là danh sách thiết lập bằng nhỏ trỏ giỏi 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 links đơn=L->Elements
Xóa phần tử ra khỏi danh sáchXoá 1 phần tử tại đoạn p ra khỏi danh sách L ta làm quá trình ngược lại cùng với xen.Trước tiên ta soát sổ vị trí bộ phận cần xóa xem có hợp lệ tuyệt chưa. Giả dụ p>L.last hoặc p
void Delete_List(Position P,List *L) if ((PL->Last)) printf("Vi tri khong hop le"); else if (EmptyList(*L)) printf("Danh sach rong!"); else Position Q; /*Dời các bộ phận từ địa điểm p+1 (chỉ số vào mảng là p) đến cuối list sang trái 1 vị trí*/ for(Q=P-1;QLast-1;Q++) L->Elements=L->Elements
Định vị một phần tử vào danh sáchĐể xác định vị trí thành phần đầu tiên tất cả nội dung x trong danh sách L, ta tiến hành dò tìm từ trên đầu danh sách. Nếu như tìm thấy x thì vị trí của bộ phận tìm tìm ra trả về, nếu không tìm kiếm thấy thì hàm trả về địa điểm sau vị trí của bộ phận cuối cùng trong danh sách, tức là ENDLIST(L) (ENDLIST(L)= L.Last+1). Vào trường hợp tất cả nhiều bộ phận cùng cực hiếm x trong danh sách thì vị trí của thành phần được kiếm tìm thấy trước tiên được trả về.
Position Locate(ElementType X, list L) Position P; int Found = 0; phường = First(L); //vị trí bộ phận đầu tiên /*trong khi chưa tìm thấy cùng chưa hoàn thành danh sách thì xét thành phần kế tiếp*/ while ((P != EndList(L)) && (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 kiến thiết trước LocateFirst(L)=1Retrieve(P,L)=L.Elements
Next(P,L)=P+1Hãy giải thích tại sao nội dung bộ phận tại vị trí p trên danh sách L là L.Elements
int main() danh mục L; ElementType X; Position P; MakeNull_List(&L); //Khởi tạo danh sách rỗng Read_List(&L); printf("Danh sach vua nhap: "); Print_List(L); // In danh sach len man hinh printf("Phan tu can them: "); scanf("%d",&X); printf("Vi tri can them: "); scanf("%d",&P); Insert_List(X,P,&L); printf("Danh sach sau khoản thời gian them phan tu la: "); PrintList(L); printf("Noi dung phan tu can xoa: "); scanf("%d",&X); P=Locate(X,L); Delete_List(P,&L); printf("Danh sach sau thời điểm xoa %d la: ",X); Print_List(L); return 0;
b. Cài đặt danh sách bởi con trỏ ( list liên kết)Cách không giống để setup danh sách là dùng con trỏ nhằm liên kết các ô chứa các phần tử. Trong cách thiết lập này các phần tử của list được giữ trữ trong số ô, mỗi ô hoàn toàn có thể chỉ đến ô chứa bộ phận kế tiếp trong danh sách. Bạn đọc hoàn toàn có thể hình dung phép tắc này qua lấy ví dụ sau:
Để thống trị danh sách ta chỉ cần một vươn lên là giữ địa chỉ ô chứa thành phần đầu tiên của danh sách, có nghĩa là một nhỏ trỏ trỏ đến phần tử đầu tiên trong danh sách. Vươn lên là này gọi là chỉ điểm đầu list (Header) . Để đơn giản và dễ dàng hóa vấn đề, trong cụ thể cài đặt, Header là 1 trong những biến cùng kiểu với các ô cất các thành phần của danh sách và nó hoàn toàn có thể được cấp phát ô nhớ hệt như một ô chứa thành phần của danh sách (hình II.3). Mặc dù Header là 1 trong những ô đặc trưng nên nó không chứa bộ phận nào của danh sách, trường dữ liệu của ô này là rỗng, chỉ gồm trường nhỏ trỏ Next trỏ cho tới ô chứa phần tử đầu tiên thiệt sự của danh sách. Nếu list rỗng thì Header->next trỏ tới NULL. Việc cấp phát ô nhớ mang đến Header như là một trong những ô đựng dữ liệu bình thường nhằm tăng tính đơn giản và dễ dàng của các giải thuật thêm, xoá các bộ phận trong danh sách.Ở phía trên ta đề nghị phân biệt rõ cực hiếm của một phần tử với vị trí (position) của nó trong cấu tạo trên. Ví dụ cực hiếm của phần tử đầu tiên của list trong hình II.3 là a1, trong lúc vị trí của nó là địa chỉ cửa hàng của ô đựng nó, tức là giá trị nằm ở trường next của ô Header. Cực hiếm và địa chỉ của các phần tử của danh sách trong hình II.3 như sau:Phần tử thứGiá trịVị trí1a1HEADER 12a21.........nan(n-1)Sau phần tử cuối cùngKhông xác địnhN và n->next có giá trị làNULL
Như đã thấy vào bảng trên, vị trí của thành phần thứ i là (i-1), do vậy để hiểu rằng vị trí của thành phần thứ i ta cần truy xuất vào ô trang bị (i-1). Khi thêm hoặc xoá một trong những phần tử trong danh sách links tại địa điểm p, ta phải cập nhật lại bé trỏ trỏ tới vị trí này, tức là update lại (p-1). Nói bí quyết khác, để thao tác làm việc vào vị trí phường ta phải biết con trỏ trỏ vào phường mà nhỏ trỏ này chính là (p-1). Vì vậy ta quan niệm p-1 như là 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 hàng của ô đứng ngay phía trước ô cất ai. Hay đúng mực hơn, ta nói, vị trí của bộ phận thứ i là nhỏ trỏ trỏ cho tới ô bao gồm trường next trỏ tới ô chứa thành phần ai bởi vậy vị trí của bộ phận thứ một là con trỏ trỏ đến Header, vị trí bộ phận thứ 2 là bé trỏ trỏ ô chứa phần tử a1, địa chỉ của thành phần thứ 3 là nhỏ trỏ trỏ ô a2, ..., vị trí bộ phận thứ n là con trỏ trỏ ô chứa an-1. Vậy địa chỉ sau bộ phận cuối trong danh sách, tức là ENDLIST, chính là con trỏ trỏ ô chứa phần tử an (xem hình II.3).
Theo định nghĩa này ta có, nếu p. Là địa điểm của thành phần thứ p. Trong danh sách thì cực hiếm của phần tử ở vị trí phường này phía bên trong trường element của ô được trỏ vì chưng p->next. Nói theo cách khác p->next->element cất nội dung của phần tử ở vị trí phường trong danh sách.Các khai báo cần thiết là
typedef ... ElementType; //kiểu của thành phần trong danh sáchtypedef struct Node ElementType Element;//Chứa câu chữ của phần tử Node* Next; /*con trỏ chỉ đến bộ phận kế tiếp vào danh sách*/;typedef Node* Position; // dạng hình vị trítypedef Position List;
Trong khai báo trên, nguyên nhân phải để tên mẫu mã Node trước khi đưa ra các 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ỗngNhư vẫn nói ở phần trên, ta cần sử dụng Header như là 1 biến bé trỏ gồm kiểu giống hệt như kiểu của một ô chứa 1 phần tử của danh sách. Mặc dù trường Element của Header không lúc nào được dùng, chỉ tất cả trường Next dùng để làm trỏ cho tới ô chứa phần tử đầu tiên của danh sách. Vậy nếu như như danh sách rỗng thì trường ô Header vẫn yêu cầu tồn tại và ô này có trường next chỉ mang đến NULL (do ko có 1 phần tử nào). Vày vậy lúc khởi tạo danh sách rỗng, ta phải cấp phép ô nhớ mang đến HEADER với cho con trỏ vào 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ỗngDanh sách rỗng nếu như ngôi trường next vào ô Header trỏ tới NULL.
int Empty_List(List L) return (L->Next==NULL);
Xen một trong những phần tử vào list :Xen 1 phần tử có mức giá trị x vào danh sách L trên vị trí phường ta phải cấp phép một ô bắt đầu để lưu lại trữ phần tử mới này với nối kết lại các con trỏ để lấy ô mới này vào vị trí p Sơ trang bị nối kết và thứ trường đoản cú các làm việc được mang đến trong hình II.4.
Hình II.4: Thêm một trong những phần tử vào list tại vị trí p
void Insert_List(ElementType X, Position P, danh mục *L) Position T; T=(Node*)malloc(sizeof(Node)); T->Element=X; T->Next=P->Next; P->Next=T;
Tham số L (danh sách) trong chương trình nhỏ trên bao gồm bỏ được không? tại sao?Xóa phần tử ra khỏi danh sách
Hình II.5: Xoá phần tử tại vị trí pTương tự như khi xen 1 phần tử vào list liên kết, ước ao xóa 1 phần tử khỏi list ta cần biết vị trí p của phần tử muốn xóa trong list L. Nối kết lại những con trỏ bằng phương pháp cho phường trỏ tới thành phần đứng sau phần tử thứ p. Trong số ngôn ngữ lập trình không có cơ chế tịch thu vùng nhớ auto như ngữ điệu Pascal, C thì ta phải thu hồi 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 giản dễ dàng của lời giải cho yêu cầu đôi khi chúng ta không đề cập mang lại việc tịch thu vùng nhớ cho các ô bị xoá. Chi tiết và trình tự các thao tác làm việc để xoá một trong những phần tử vào danh sách links như vào hình II.5. Công tác con rất có thể được thiết lập như sau:
void Delete_List(Position P, danh sách *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*/ free(T); //thu hồi vùng nhớ
Định vị một trong những phần tử trong list liên kếtĐể định vị bộ phận x trong danh sách L ta tiến hành tìm từ trên đầu danh sách (ô header) giả dụ tìm thấy thì địa chỉ của bộ phận đầu tiên được tìm kiếm thấy sẽ được trả về nếu không thì ENDLIST(L) được trả về. Nếu như x bao gồm trong sách sách cùng hàm Locate trả về vị trí phường mà trong các số ấy ta gồm x = p->next->element.
Position Locate(ElementType X, menu L) Position P; int Found = 0; phường = L; while ((P->Next != NULL) && (Found == 0)) if (P->Next->Element == X) Found = 1; else p. = P->Next; return P;
Thực chất, khi điện thoại tư vấn hàm Locate ngơi nghỉ trên ta có thể truyền giá bán trị mang lại L là ngẫu nhiên giá trị nào. Ví như L là Header thì chương trình nhỏ sẽ tra cứu x từ trên đầu danh sách. Trường hợp L là 1 trong những vị trí p ngẫu nhiên trong list thì chương trình bé Locate sẽ tiến hành định vị bộ phận x từ địa điểm p.Xác định nội dung phần tử:
Nội dung phần tử đang tàng trữ tại vị trí phường trong list L là p->next->Element vày đó, hàm đã trả về quý giá p->next->element nếu phần tử có tồn tại, ngược lại phần tử không trường thọ (p->next=NULL) thì hàm không xác định.
Hãy 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 danh sách?c. So sánh hai phương thức cài đặt
Không thể kết luận phương pháp cài để nào kết quả hơn, nhưng mà nó hoàn toàn tuỳ trực thuộc vào từng áp dụng hay tuỳ thuộc vào các phép toán trên danh sách. Mặc dù ta rất có thể tổng kết một trong những ưu điểm yếu của từng cách thức làm đại lý để lựa chọn cách thức cài đặt thích hợp cho từng ứng dụng:Cài đặt bởi mảng đòi hỏi phải xác minh số phần tử của mảng, vì đó còn nếu như không thể mong lượng được số phần tử trong list thì khó vận dụng cách thiết đặt này một cách công dụng vì nếu như khai báo thiếu địa điểm thì mảng liên tiếp bị đầy, ko thể làm việc được còn ví như khai báo vượt thừa thì lãng phí bộ nhớ. Cài đặt bởi con trỏ phù hợp cho sự biến động của danh sách, danh sách có thể rỗng hoặc mập tuỳ ý chỉ dựa vào vào bộ lưu trữ tối nhiều của máy. Tuy nhiên ta phải tốn thêm vùng nhớ cho những con trỏ (trường next). Cài đặt bằng mảng thì thời gian xen hoặc xoá một trong những phần tử tỉ lệ thành phần với số phần tử đi sau địa chỉ xen/ xóa. Vào khi thiết lập bằng bé trỏ những phép toán này mất chỉ một hằng thời gian. Phép tróc nã nhập vào 1 phần tử vào danh sách, ví dụ như PREVIOUS, chỉ tốn một hằng thời hạn đối với thiết đặt bằng mảng, vào khi đối với danh sách thiết lập bằng con trỏ ta nên tìm từ đầu danh sách cho đến vị trí trước địa chỉ của phần tử hiện hành.Nói chung danh sách links thích phù hợp với danh sách có không ít biến động, có nghĩa là ta liên tiếp thêm, xoá các phần tử.Cho biết ưu yếu điểm của danh sách đặc và danh sách liên kết?d. Setup bằng bé nháyMột số ngôn ngữ lập trình ko có cung cấp kiểu nhỏ trỏ. Vào trường thích hợp này ta rất có thể "giả" bé trỏ để setup danh sách liên kết. Ý tưởng thiết yếu là: cần sử dụng mảng để đựng các phần tử của danh sách, những "con trỏ" sẽ là những biến số nguyên (int) để giữ lại chỉ số của phần tử kế tiếp vào mảng. Để khác nhau giữa "con trỏ thật" và "con trỏ giả" ta gọi những con trỏ giả này là con nháy (cursor). Vậy nên để setup danh sách bằng con nháy ta buộc phải một mảng nhưng mà mỗi thành phần xem như là 1 ô gồm gồm hai trường: ngôi trường Element như thông thường giữ quý hiếm của bộ phận trong list (có thứ hạng Elementtype) trường Next là bé nháy để chỉ tới địa chỉ trong mảng của phần tử kế tiếp. Ví dụ điển hình hình II.6 biểu diễn cho mảng SPACE đang đựng hai list 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 list (giống như header trong danh sách liên kết). Phần tử cuối thuộc của list ta mang đến chỉ tới giá bán trị đặc biệt quan trọng Null, rất có thể xem Null = -1 cùng với một đưa thiết là mảng SPACE không có vị trí nào có chỉ số -1.
Trong hình II.6, list L1 có 3 thành phần : f, o ,r. Chỉ điểm đầu của L1 là con nháy có mức giá trị 5, có nghĩa là nó trỏ vào ô lưu giữ giữ phần tử đầu tiên của L1, ngôi trường next của ô này có giá trị 1 là ô lưu giữ trữ phần tử kế tiếp (tức là o). Ngôi trường next trên ô đựng o là 4 là ô giữ trữ phần tử kế tiếp trong danh sách (tức là r). Sau cùng trường next của ô này cất Null nghĩa là danh sách không còn thành phần kế tiếp.Phân tích tương tự như ta bao gồm L2 gồm 4 thành phần : w, i, n, dHình II.6 Mảng đang cất hai danh sách L1 và L2
Khi xen 1 phần tử vào list ta đem một ô trống vào mảng nhằm chứa thành phần mới này cùng nối kết lại các con nháy. Ngược lại, khi xoá một phần tử khỏi danh sách ta nối kết lại các con nháy nhằm loại thành phần này khỏi danh sách, điều này kéo theo số ô trống vào mảng tạo thêm 1. Vấn đề là làm cố gắng nào nhằm quản lí những ô trống này để tìm hiểu ô làm sao còn trống ô nào đã dùng? một giải pháp là liên kết tất cả các ô trống vào một trong những danh sách đặc biệt gọi là AVAILABLE, khi xen 1 phần tử vào list ta rước ô trống đầu AVAILABLE để chứa phần tử mới này. Lúc xoá một phần tử từ list ta mang đến ô bị xoá nối vào đầu AVAILABLE. Tất yếu khi mới bắt đầu việc xây dựng cấu tạo thì mảng không chứa thành phần nào của ngẫu nhiên một list nào. Hôm nay tất cả các ô của mảng hầu như là ô trống, với như vậy, tất cả các ô hầu như được link vào trong AVAILABLE. Việc khởi tạo AVAILABLE ban sơ có thể thực hiện bằng phương pháp cho phần tử thứ i của mảng trỏ tới phần tử i+1.Các khai báo quan trọng cho danh sách
#define MaxLength ... //Chieu dai mang#define Null -1 //Gia tri Nulltypedef ... ElementType; /*kiểu của các phần tử trong danh sách*/typedef struct
ElementType Elements; /*trường chứa bộ phận trong danh sách*/ int Next; //con nháy trỏ đến bộ phận kế tiếp Node;Node Space
Hình II.7: Khởi sinh sản Available ban đầuKhởi tạo cấu tạo – thiết lập cấu hình available ban đầuTa cho phần tử thứ 0 của mảng trỏ đến phần tử thứ 1,..., thành phần cuối cùng trỏ Null. Chỉ điểm đầu của AVAILABLE là 0 như trong hình II.7
Chuyển một ô từ danh sách này sang list khácTa thấy thực ra của việc xen hay xoá một trong những phần tử là triển khai việc chuyển một ô từ list này sang list khác. Chẳng hạn muốn xen thêm một trong những phần tử vào list L1 vào hình II.6 vào trong 1 vị trí phường nào kia ta cần chuyển một ô từ AVAILABLE (tức là 1 trong ô trống) vào L1 tại địa chỉ p; mong muốn xoá một phần tử tại vị trí p nào kia trong danh sách L2, chẳng hạn, ta đưa ô chứa bộ phận đó sang trọng AVAILABLE, thao tác làm việc này xem như là giải phóng bộ nhớ lưu trữ bị chỉ chiếm bởi phần tử này. Bởi vì đó tốt nhất ta viết một hàm thực hiện thao tác làm việc chuyển một ô từ danh sách này sang list khác với hàm cho hiệu quả kiểu int phụ thuộc vào chuyển thành công hay đại bại (là 0 nếu chuyển không thành công, 1 nếu đưa thành công). Hàm Move sau đây tiến hành chuyển ô được trỏ tới bởi bé nháy p. Vào danh sách khác được trỏ bởi bé nháy Q như vào hình II.8. Hình II.8 trình bày các thao tác làm việc cơ phiên bản để gửi một ô (ô được gửi ta tạm hotline là ô mới):
Hình II.8Chuyển 1 ô từ list này sang danh sách khác (các links vẽ bằng nét đứt biểu diễn cho những liên kết cũ - trước khi giải thuật bắt đầu)Dùng bé nháy temp để trỏ ô được trỏ vì chưng Q.Cho Q trỏ tới ô mới.Cập nhật lại con nháy P bằng phương pháp cho nó trỏ cho tới ô kế tiếp.Nối nhỏ nháy trường next của ô new (ô nhưng mà Q đang trỏ) trỏ vào ô nhưng mà temp vẫn 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 cài đặt này, quan niệm vị trí tương tự như như định nghĩa vị trí vào trường hợp thiết đặt bằng con trỏ, tức là, địa chỉ của thành phần thứ I trong danh sách là chỉ số của ô trong mảng chứa con nháy trỏ đến ô chứa phần tử thứ i. Lấy ví dụ như xét danh sách L1 trong hình II. 6, vị trí của phần tử thứ 2 trong danh sách (phần tử có giá trị o) là 5, chưa hẳn là 1; vị trí của thành phần thứ 3 (phần tử có mức giá trị r ) là 1, chưa hẳn là 4. địa chỉ của thành phần thứ 1 (phần tử có giá trị f) được có mang là -1, vì không tồn tại ô như thế nào trong mảng chứa nhỏ nháy trỏ đến ô chứa thành phần f.
void Insert_List(ElementType X, int P, int *L)if (P==-1) //Xen dau danh sachif (Move(&Available,L)) Space<*L>.Elements=X;else printf("Loi! Khong nhỏ bo nho trong");else //Chuyen mot o tu Available vao vi tri Pif (Move(&Available,&Space
.Next))// O nhan X la o tro boi Space
.Next Space .Next,&Available)) printf("Loi trong khi xoa"); //else Khong lam gi
Xoá 1 phần tử trong danh sáchMuốn xoá một phần tử trên 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ư như phép thêm vào, trường hợp p=-1 thì xoá phần tử đầu danh sách.
void Delete_List(int p, int *L) if (p==-1) //Neu la o dau tien if (!Move(L,&Available)) printf("Loi trong những khi xoa"); // else Khong lam gi ca else if (!Move(&Space
report this adCác khóa học qua video:Lập trình C Java C# SQL server PHP HTML5-CSS3-JavaScript« Prev: giải thuật và thiết kế - C: III. Hình trạng dữ liệu, cấu trúc dữ liệu, Kiểu dữ liệu trừu tượng (DATA TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES)
