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:
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.
Dưới đây là một số điểm cần nhớ về Danh sách liên kết:
Dưới đây là các loại Danh sách liên kết (Linked List) đa dạng:
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:
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) { cout<key<<" "; q=q->next; } cout<<endl; } // Hàm tính trung bình cộng của các node trong danh sách: double TBC(ref &head) { int sum,count; sum=count=0; ref q=head; while(q!=NULL) { sum+=q->key; count++; q=q->next; } if(count!=0) return double(sum)/count; else return 0.0; } // Đếm số node có trong danh sách: int DemPhantu(ref &head) { int count=0; ref q=head; while(q!=NULL) { count++; q=q->next; } return count; } // Kiểm tra số nguyên tố: int KTSNT(int n){ if(n<2) return 0; for(int i=2;i<=n/2;i++) if(n%i==0) return 0; return 1; } // Đếm số nguyên tố: int DemSNT(ref &head){ ref p=head; int count=0; if(p==NULL) return 0; while(p!=NULL) { if(KTSNT(p->key)) count++; p=p->next; } return count; } // Tính trung bình số nguyên tố trong danh sách: double TBSNT(ref &head) { ref p=head; int Sum=0; int count=0; if(p==NULL) return 0.0; while(p!=NULL){ if(KTSNT(p->key)) { 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)) cout<key<<" "; p=p->next; } } // In đảo ngược danh sách (note: In lậu liên kết giữa các node chưa đảo ngươc được) void InDaoNguoc(ref &head) { int dem=0,count=0; ref p=head; while(p!=NULL) { count++; p=p->next; } ref q; while(count>0) { if(dem>=0) q=head; for(int i=0;iif(i>0) 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<<"\nDanh sach so nguyen to:"<<endl; Display(l1); cout<<"\nDanh sach so con lai:"<<endl; Display(l2); } // Tìm node x trong danh sách nếu tìm thấy thì tách danh sách ra thành 2 danh sách. // danh sách 1 là danh sách từ đầu đến vị trí node x. // danh sách 2 là danh sách tính từ vi trí node x đến cuối danh sách ban đầu. void TachDSX(ref &head,ref &l,int x) { init(l); ref q=head; if(q==NULL) return; q=search(head,x); while(q!=NULL){ InsertFirst(l,q->key); q=q->next; } ref r=q=search(head,x); while(r!=NULL){ r=r->next; DelX(head,q->key); q=r; } cout<<"Dach sach tu dau den x:"<<endl; Display(head); cout<<"Dach sach x den cuoi danh sach:"<<endl; InDaoNguoc(l); } int main(int argc, char* argv[]) { int x; ref head,head1,head2; ref q,r; printf("Nhap gia tri duong(am ket thuc):"); scanf(“%d”,&x); init(head); while(x>=0) { InsertFirst(head,x); Printf("Nhap gia tri duong(am ket thuc):"); Scanf(“%d”,&x); } Printf("Danh sach theo chieu nghich:\n"); Display(head); Printf(“\n”); TachNT(head,head1,head2); int c; cout<<"Nhap c can tim:";cin>>c; cout<<endl; TachDSX(head,head1,c); cout<<"\nDanh sach theo chieu thuan :"<<endl; InDaoNguoc(head); cout<<"\nCac so nguyen to trong danh sach:"<<endl; InSNT(head); int t;cout<<"\nNhap phan tu de chen vao phan tu chan dau tien=",cin>>t; ChenVaoChanDau(head,t); cout<<"\nChen "<" vao phan tu chan dau tien:"<<endl; Display(head);*/ if(ChanCuoi(head)==NULL)cout<<"\nDanh sach rong or khong co phan tu chan nao."<<endl; else cout<<"\nChan cuoi trong danh sach="<key<<endl; if(XetDS(head)==1) cout<<"\nTang"<<endl; else if(XetDS(head)==2) cout<<"\nGiam"<<endl; else cout<<"\nKhong Thu tu or danh sach rong."<<endl; cout<<"\nTrung binh cong cua cac phan tu trong danh sach:"<endl; cout<<"\nSo phan tu la so nguyen to="<endl; cout<<"\nTrung binh cong cua cac phan tu la so nguyen to trong danh sach:"<endl; cout<<"\nSo phan tu trong danh sach la="<endl; int y;cout<<"Nhap gia tri can xoa=",cin>>y; DelX(head,y); cout<<"Dang sach sau khi da xoa "<":"<<endl; Display(head); int z;cout<<"Nhap vi tri can xet=",cin>>z; if(z<0||z>=DemPhantu(head)-1) cout<<"\nSau vi tri "<" khong co phan tu hoac khong co trong mang!"<<endl; else{ XoaPhanTuSauk(head,z); cout<<"\nSau khi xoa phan tu sau vi tri "<":"<<endl; Display(head); } cout<<"Nhap gia tri can tim:"; cin>>x; q=search(head,x); if(q!=NULL) //tim thay { cout<<"Nhap gia tri can them:"; cin>>x; InsertMiddle(q,x);//chen phan tu q sau x Display(head); } else cout<<"Khong tim thay!!!"<<endl; //hoan doi 2 vi tri trong danh sach HoanDoi(head,q,r); cout<<"Danh sach sau khi hoan doi 2 vi tri vua nhap:"<<endl; Display(head); DelList(head); if(head==NULL) cout<<"Xoa thanh cong"<<endl; else cout<<"Khong thanh cong"<<endl; return 0; }
