Toàn Tập Về Danh Sách Liên Kết - Thư Viện Hướng Dẫn

Danh Sách Liên Kết là gì?

Một Danh sách liên kết (Linked List) là một dãy các cấu trúc dữ liệu được kết nối với nhau thông qua các liên kết (link). Hiểu một cách đơn giản thì Danh sách liên kết là một cấu trúc dữ liệu bao gồm một nhóm các nút (node) tạo thành một chuỗi. Mỗi nút gồm dữ liệu ở nút đó và tham chiếu đến nút kế tiếp trong chuỗi. Danh sách liên kết là cấu trúc dữ liệu được sử dụng phổ biến thứ hai sau mảng.

Dưới đây là các khái niệm cơ bản liên quan tới Danh sách liên kết:

• Link (liên kết): mỗi link của một Danh sách liên kết có thể lưu giữ một dữ liệu được gọi là một phần tử.
• Next: Mỗi liên kết của một Danh sách liên kết chứa một link tới next link được gọi là Next.
• First: một Danh sách liên kết bao gồm các link kết nối tới first link được gọi là First.

Biểu diễn Danh sách liên kết (Linked List):

Danh sách liên kết có thể được biểu diễn như là một chuỗi các nút (node). Mỗi nút sẽ trỏ tới nút kế tiếp.

Head-> [data;next]->[data;next]->[data;next]->null.

Cấu trúc dữ liệu Danh sách liên kết (Linked List)

Dưới đây là một số điểm cần nhớ về Danh sách liên kết:

• Danh sách liên kết chứa một phần tử link thì được gọi là First.
• Mỗi link mang một trường dữ liệu và một trường link được gọi là Next.
• Mỗi link được liên kết với link kế tiếp bởi sử dụng link kế tiếp của nó. – Link cuối cùng mang một link là null để đánh dấu điểm cuối của danh sách.

Các loại Danh sách liên kết (Linked List)

Dưới đây là các loại Danh sách liên kết (Linked List) đa dạng:

• Danh sách liên kết đơn (Simple Linked List): chỉ duyệt các phần tử theo chiều về trước.
• Danh sách liên kết đôi (Doubly Linked List): các phần tử có thể được duyệt theo chiều về trước hoặc về sau.
• Danh sách liên kết vòng (Circular Linked List): phần tử cuối cùng chứa link của phần tử đầu tiên như là next và phần tử đầu tiên có link tới phần tử cuối cùng như là prev.

Các hoạt động cơ bản trên Danh sách liên kết

Dưới đây là một số hoạt động cơ bản có thể được thực hiện bởi một danh sách liên kết:

• Hoạt động chèn: thêm một phần tử vào đầu danh sách liên kết.
• Hoạt động xóa (phần tử đầu): xóa một phần tử tại đầu danh sách liên kết.
• Hiển thị: hiển thị toàn bộ danh sách.
• Hoạt động tìm kiếm: tìm kiếm phần tử bởi sử dụng khóa (key) đã cung cấp.
• Hoạt động xóa (bởi sử dụng khóa): xóa một phần tử bởi sử dụng khóa (key) đã cung cấp.
• Hoạt động chèn trong Danh sách liên kết

Sau đây là toàn bộ code xử lý một số trường hợp với danh sách liên kết:

Code:

#include "stdafx.h" #include // Khai báo 1 danh sách liên kết: struct Node { int key; Node *next; }; typedef Node *ref; // Khởi tạo 1 danh sách rỗng: void init(ref &head) { head=NULL; } // Cấp phát 1 node mới trong danh sách: Node* New(int x){ ref p; p=new Node; if(p==NULL) return NULL; p->key=x; p->next=NULL; return p; } // Chèn phần tử vào đầu danh sách: void InsertFirst(ref &head,int x) { ref p= new Node; p->key=x; p->next=head; head=p; } // Chèn phần tử vào danh sách chưa có thứ tự: void InsertMiddle(ref q,int x) { ref p; p=new Node; p->key=x; p->next=q->next; q->next=p; } // Thêm phần tử vào danh sách đã có thứ tự: void InsertOrder(ref &head,int x) { ref q,p,r; p=new Node; p->key=x; r=head; int count=1; while(r!=NULL && count) if(r->keynext; } else count=0; if(r==head) head=p; else p->next=q->next; p->next=r; } // Tìm phần tử x trong danh sách chưa có thứ tự: ref search(ref &head,int x) { ref q; q=head; while(q!=NULL && q->key!=x) q=q->next; return q; } // Tìm phần tử x trong danh sách đã có thứ tự: ref search(ref &head,int x) { ref q; q=head; while(q!=NULL && q->key!=x&&q->keynext; if (q->key==x)return q; else return NULL; } // Xóa phần tử đầu tiên trong danh sách: void DelFirst(ref &head) { ref q; q=head; head=q->next; delete(q); } // Xóa phần tử giữa và cuối danh sách: void DelMiddleEnd(ref p) { ref q; q=p->next; p->next=q->next; delete(q); } // Xóa node có giá trị x: void DelX(ref &head,int x) { ref q,p; int Found=0; q=head; while(q!=NULL && !Found) if(q->key!=x) { p=q; q=q->next; } else Found=1; if(Found) { if(q==head) head=q->next; else p->next=q->next; delete(q); } } // Xóa phần tử sau vị trí k(1 2 3 4 5)nhập vị trí k=2,xóa phần tử 4 void XoaPhanTuSauk(ref &head,int k) { ref r,p; int count=0,found=0; r=head; while(r!=NULL&&found==0) { if(count==k) { p=r->next; r->next=p->next; delete(p); found=1; } count++; r=r->next; } } // Xóa toàn bộ danh sách: void DelList(ref &head) { ref q=head; while(q!=NULL) { DelFirst(head); q=head; } } // Hiển thị danh sách liên kết đơn: void Display(ref &head) { ref q; q=head; while(q!=NULL) { coutkey)) { count++; Sum+=p->key; } p=p->next; } if(count!=0) return (double)Sum/count; else return 0.0; } // Hoán đổi 2 node trong danh sách: void HoanDoi(ref &head,ref &q,ref &r){ if(q!=NULL) // p q r { r=q->next; if(q!=head) { ref p=head; while(p->next!=q) p=p->next; p->next=q->next; } else head=q->next; q->next=r->next; r->next=q; } } // In số nguyên tố có trong danh sách: void InSNT(ref &head) { ref p=head; if(p==NULL) return; while(p!=NULL){ if(KTSNT(p->key)) cout0) { if(dem>=0) q=head; for(int i=0;i0) q=q->next; printf("%d\t",q->key); count--; dem++; } } // Chèn x vào giá trị chẵn đầu tiên trong danh sách: void ChenVaoChanDau(ref &head,int x) { ref p=head; if(p==NULL) InsertFirst(head,x); int found=0; while(p!=NULL&&found==0){ if(p->key%2==0) { InsertMiddle(p,x); found=1;} else p=p->next; } } // Tìm node la chẵn cuối cùng trong danh sách: ref ChanCuoi(ref &head) { ref p=head; ref q; int found=0; if(p==NULL) return NULL; while(p!=NULL){ if(p->key%2==0){q=p;found=1;} p=p->next; } if(found)return q; else return NULL; } // Xét xem danh sách tăng hay giảm hay không có thứ tự: int XetDS(ref &head) { ref p,r; p=head; if(p==NULL) return 0; r=p->next; int count1=0; int count2=0; while(r!=NULL){ if(p->keykey) count1++; else if(p->key>r->key) count2++; else{ count1=0,count2=0;} p=p->next; r=p->next; } if(count1==DemPhantu(p)-1) return 1;//tang if(count2==DemPhantu(p)-1) return 2;//giam else return 0; } // Tách danh sách ban đầu thành 2 danh sách con // danh sách 1:chứa các node là số nguyên tố. // danh sách 2:chứa các node còn lại. void TachNT(ref head,ref &l1,ref &l2) { init(l1); init(l2); ref q,p=head; if(p==NULL) return ; while(p!=NULL){ int k=p->key; q=New(k); if(KTSNT(k))InsertFirst(l1,q->key); else InsertFirst(l2,q->key); p=p->next; } cout