Ngộ nhận ra bài này mình viết code rất dở, để khi nào rảnh sẽ edit lại. Danh sách liên kết có những ứng dụng rất thú vị Hôm nay Kỹ Thuật Lập Trình được học danh sách liên kết, vì ở dưới chăm chú sửa cái code thực hành mà không bắt kịp vấn đề, dù những định nghĩa căn bản đều hiểu. Cần phải tìm hiểu nó một cách cụ thể. 1.Khái niệm: Danh sách liên kết (linked list) là một cấu trúc dữ liệu bao gồm một nhóm các nút (nodes) tao thành một chuỗi. Thông thường mỗi nút gồm dữ liệu (data) ở nút đó và tham chiếu (reference) đến nút kế tiếp trong chuỗi. Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất. (Nguồn: Wikipedia)
Ưu điểm:
Nhược điểm:
Phân loại:
Cấu trúc:
Data: Thành phần chứa một hay nhiều biến dữ liệu. Next ptr: Tham chiếu trỏ đến phần tử kế tiếp trong cấu trúc.
Struct LLnode {DataType Data;LLnode* next;}; 2.Các phép toán:Cho cấu trúc đơn giản: struct LLintNode {int Data;struct LLintNode* Next;}; Đếm số phần tử của Linked List:Duyệt từng phần tử rồi đếm, cho đến khi nào gặp phần tử cuối.
int LengthLL(LLNode* head) {int length = 0;while (head != NULL) {++length;head = head ->Next;}return length;} Thêm một phần tử vào cuối linked list:Nếu danh sách rỗng, thêm nút vào head. Ngược lại, tìm phần tử cuối cùng của danh sách rồi thêm nút mới vào Next của nút cuối cùng đó:
void AddLast(LLNode** head, int data) {LLNode** tmp = head; LLNode* NewNode;NewNode = (LLNode*) malloc(sizeof(LLNode));NewNode->Data = data;NewNode->Next = NULL; if ((*tmp) == NULL) {(*tmp) = NewNode;} else {while ((*tmp)->Next !=NULL) {tmp = &((*tmp)->Next);}(*tmp)->Next = NewNode;}} Xóa phần tử cuối cùng:Tìm phần tử cuối cùng của danh sách, rồi gán bằng NULL.
void RemoveLast(LLNode** head) { LLNode** tmp = head; if ((*tmp) !=NULL) { while ((*tmp)->Next != NULL) { tmp = &((*tmp)->Next); } } (*tmp) = NULL; } Thêm phần tử vào đầu danh sách:
void AddFirst(LLNode** head, int Data) { LLNode** tmp = head; LLNode* NewNode; NewNode = (LLNode*) malloc(sizeof(LLNode)); NewNode->Data = Data; NewNode->Next = (*head); (*tmp) = NewNode; } Xóa phần tử đầu tiên:Nếu danh sách khác rỗng, đưa phần tử Next lên phía trước.
void RemoveFirst(LLNode** head) { LLNode** tmp = head; if ((*tmp) != NULL) { (*tmp) = (*tmp)->Next; }} Tìm kiếm phần tử trong danh sách:
LLNode* FindNode(LLNode** head,LLNode* src) { LLNode** tmp = head; while ( src->Data != (*tmp)->Data) { tmp = &((*tmp)->Next); } return (*tmp); } Chèn thêm 1 phần tử sau phần tử currrent:
int InsertNode(LLNode** head, LLNode* current, LLNode* NewNode) { LLNode** tmp = head; while ((current != (*tmp)) && (*tmp != NULL)) { tmp = &((*tmp)->Next); } if (*tmp == NULL) { return 0; } else { NewNode->Next= current->Next; current->Next = NewNode; (*tmp) = current; return 1; } } Xóa phần tử bất kì biết trước dữ liệu:int RemoveNode(LLNode** head, LLNode* current) { LLNode** tmp = head; while ((current != (*tmp)) && (*tmp != NULL)) { tmp = &((*tmp)->Next); } if (*tmp == NULL) { return 0; } else { (*tmp) = (*tmp)->Next; return 1; }} 3.Tham khảo:http://xlinux.nist.gov/dads//HTML/linkedList.html http://jcsites.juniata.edu/faculty/kruse/cs240/linkedlist1.htm http://www.cprogramming.com/tutorial/lesson15.html http://diendan.congdongcviet.com/archive/index.php/t-25238.html Page 2
2
Bạn đang thắc mắc? Ghi câu hỏi của bạn và đăng ở chế độ cộng đồng (?) Bài viết này có một danh sách các nguồn tham khảo, nhưng vẫn chưa đáp ứng khả năng kiểm chứng được bởi thân bài vẫn còn thiếu các chú thích trong hàng. (March 2012) Trong khoa học máy tính, danh sách liên kết (tiếng Anh: linked list) là một tập hợp tuyến tính các phần tử dữ liệu, với thứ tự không được đưa ra bởi vị trí vật lý của chúng trong bộ nhớ. Thay vào đó, mỗi phần tử chỉ đến (Pointer) phần tử tiếp theo. Nó là một cấu trúc dữ liệu bao gồm một tập hợp các nút cùng thể hiện một dãy. Ở dạng cơ bản nhất, mỗi nút chứa: dữ liệu, và một tham chiếu (hay nói cách khác là liên kết) tới nút kế tiếp trong dãy. Cấu trúc này cho phép chèn hay loại bỏ phần tử khỏi bất kì vị trí nào trong trong chuỗi một cách hiệu quả trong quá trình lặp. Các biến thể phức tạp hơn như thêm các liên kết bổ sung, cho phép chền hay loại bỏ các nút hiệu quả hơn tại vị trí bất kì. Một nhược điểm của danh sách liên kết là thời gian truy cập là tuyến tính (và khó thực thi ống dẫn). Truy cập nhanh hơn, ví dụ như truy cập ngẫu nhiên, là không khả thi. Mảng có vùng đệm (cache locality) tốt hơn so với danh sách liên kết.
Danh sách liên kết là một trong những cấu trúc dữ liệu đơn giản và phổ biến nhất. Nó có thể được dùng để hiện thực một số kiểu dữ liệu trừu tượng phổ biến khác, bao gồm danh sách (list), ngăn xếp (stack), hàng đợi, mảng kết hợp, và S-expression, mặc dù không có gì lạ khi hiện thực các cấu trúc dữ liệu đó mà không dựa trên nền tảng của danh sách liên kết. Lợi ích chính của danh sách liên kết so với mảng thông thường là các phần tử danh sách có thể được chèn hay xóa một cách dễ dàng mà không cần phân bổ lại hoặc sắp xếp lại toàn bộ cấu trúc vì các mục dữ liệu không cần được lưu trữ liên tục trong bộ nhớ hay trên đĩa, trong khi tái cấu trúc một mảng tại thời gian chạy là một hoạt động tốn kém hơn nhiều. Danh sách liên kết cho phép chèn hay xóa nút tại bất kì điểm nào trong danh sách. Mặc khác, vì bản thân danh sách liên kết được liên kết đơn giản nên không cho phép truy cập ngẫu nhiên tới dữ liệu hoặc bất kì hình thức đánh chỉ mục hiệu quả nào, nhiều toán tử cơ bản như lấy nút cuối cùng của danh sách, tìm một nút có chứa dữ liệu đã cho, hay tìm vị trí của nút để chèn một nút mới sẽ yêu cầu lặp qua hầu hết hoặc tất cả các phần tử của danh sách. Những ưu điểm và nhược điểm của danh sách liên kết được đưa ra dưới đây. Danh sách liên kết là động, vì vậy độ dài của nó có thể tăng hay giảm khi cần thiết. Mỗi nút không cần phải theo nút trước đó trong bộ nhớ.
|
