Bài Tập Thực Hành Với Danh Sách Liên Kết đơn - Freetuts

Trong hướng dẫn này mình sẽ giải một số bài tập đơn giản liên quan đến danh sách liên kết đơn.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Phần này giúp các bạn ôn lại bài và biết cách áp dụng kiến thức đã học vào bài tập thực tế.

Chúng ta sẽ thực hiện giải hai bài tập:

• Bài tập về danh sách liên kết đơn kiểu cơ sở
• Bài tập về danh sách liên kết đơn kiểu cấu trúc

Qua hai bài tập này các bạn có thể quản lý được danh sách liên kết và thao tác với nó một cách thành thạo.

Bài viết này được đăng tại [free tuts .net]

1. Bài tập về danh sách liên kết đơn kiểu cơ sở

Trong bài tập này chúng ta sẽ thực hiện giải một bài toán như sau:

s(x,n) = x1 + x2 + x3 + ... + xn

Xây dựng danh sách liên kết đơn có pHead, pTail. Nhập x, n tạo thành danh sách liên kết( Mỗi nút có 2 giá trị x và i, i chạy từ 1 -> n), dùng con trỏ để khai báo cho danh sách liên kết.

Viết hàm xuất ra tổng các phần tử trong danh sách liên kết.

Gợi ý:

Để giải bài toán này việc đầu tiên ta cần cấu trúc dữ liệu của danh sách liên kết đơn. Giá trị data là x và i, mối liên kết là pNext. Khởi tạo cho pHead và pTail bằng NULL.

/* Tạo cấu trúc dữ liệu cho danh sách liên kết đơn */ struct Node { int x; int i; Node *pNext; }; struct SingleList { Node *pHead; Node *pTail; }; /* Khởi tạo cho pHead và pTail */ void Initialize(SingleList *&list) { list=new SingleList; list->pHead=list->pTail=NULL; }

Sau đó viết một hàm tạo Node dựa vào cấu trúc dữ liệu vừa viết.

/* Tạo Node */ Node *CreateNode(int x,int i) { Node *pNode=new Node; if(pNode==NULL) { cout<<"Loi cap phat bo nho"; exit(0); } pNode->i=i; pNode->x=x; pNode->pNext=NULL; return pNode; }

Trong bài tập này ta cần thêm Node vào cuối danh sách, vì vậy chúng ta cần tạo một hàm InsertLast() với tham số truyền vào là x và i.

/* insertlast */ void InsertLast(SingleList *&list,int x,int i) { Node *pNode=CreateNode(x,i); if(list->pTail==NULL) list->pHead=list->pTail=pNode; else { list->pTail->pNext=pNode; list->pTail=pNode; } }

Một hàm PrintList() để in danh sách liên kết.

/*printlist*/ void PrintList(SingleList *list) { Node *pTmp=list->pHead; while(pTmp!=NULL) { if(pTmp->pNext!=NULL) cout<<pTmp->x<<"^"<<pTmp->i<<"+"; else cout<<pTmp->x<<"^"<<pTmp->i; pTmp=pTmp->pNext; } }

Và cuối cùng là hàm tính tổng SumOfList(), dùng để tính tổng các phần tử trong danh sách liên kết đơn.

/* Hàm tính tổng */ double SumOfList(SingleList *list) { double sum=0; for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) { double value=pow(pTmp->x,pTmp->i); sum+=value; } return sum; }

Để hiển thị và kiểm tra kết quả ta cần có hàm main() để làm điều này.

int main(int argc, char** argv) { SingleList *list; Initialize(list); int n,x; cout<<"Nhập n:"; cin>>n; cout<<"Nhập x:"; cin>>x; for(int i=1;i<=n;i++) { InsertLast(list,x,i); } cout<<"Danh sách liên kết đơn: \n"; PrintList(list); double sum=SumOfList(list); cout<<"\nTổng các phần tử trong danh sách: "<<sum; }

Full code:

#include <iostream> #include <math.h> using namespace std; /* Tạo cấu trúc dữ liệu cho danh sách liên kết đơn */ struct Node { int x; int i; Node *pNext; }; struct SingleList { Node *pHead; Node *pTail; }; /* Khởi tạo cho pHead và pTail */ void Initialize(SingleList *&list) { list=new SingleList; list->pHead=list->pTail=NULL; } /* Tạo Node */ Node *CreateNode(int x,int i) { Node *pNode=new Node; if(pNode==NULL) { cout<<"Loi cap phat bo nho"; exit(0); } pNode->i=i; pNode->x=x; pNode->pNext=NULL; return pNode; } /* insertlast */ void InsertLast(SingleList *&list,int x,int i) { Node *pNode=CreateNode(x,i); if(list->pTail==NULL) list->pHead=list->pTail=pNode; else { list->pTail->pNext=pNode; list->pTail=pNode; } } /*printlist*/ void PrintList(SingleList *list) { Node *pTmp=list->pHead; while(pTmp!=NULL) { if(pTmp->pNext!=NULL) cout<<pTmp->x<<"^"<<pTmp->i<<"+"; else cout<<pTmp->x<<"^"<<pTmp->i; pTmp=pTmp->pNext; } } /* Hàm tính tổng */ double SumOfList(SingleList *list) { double sum=0; for(Node *pTmp=list->pHead;pTmp!=NULL;pTmp=pTmp->pNext) { double value=pow(pTmp->x,pTmp->i); sum+=value; } return sum; } int main(int argc, char** argv) { SingleList *list; Initialize(list); int n,x; cout<<"Nhập n:"; cin>>n; cout<<"Nhập x:"; cin>>x; for(int i=1;i<=n;i++) { InsertLast(list,x,i); } cout<<"Danh sách liên kết đơn: \n"; PrintList(list); double sum=SumOfList(list); cout<<"\nTổng các phần tử trong danh sách: "<<sum; cout<<"\n----------------------------\n"; cout<<"Chương trình này được đăng tại Freetuts.net"; }

Kết quả:

Bài tập về danh sách liên kết đơn kiểu cấu trúc

Trong bài tập này ta thực hiện một bài toán như sau:

• Tạo một cấu trúc phân số a/b.
• Xây dựng danh sách liên kết đơn có pHead, pTail. Dùng vòng for để thêm các phân số vào danh sách.
• Xuất danh sách theo dãy số.
• Xuất kết quả cuối cùng.

Gợi ý:

Tương tự như bài 1, ta thực hiện tạo cấu trúc dữ liệu cho danh sách liên kết đơn, một cấu trúc PhanSo. Sau đó, khởi tạo giá trị cho pHead và pTail bằng NULL.

/* Tạo cấu trúc cho phân số */ struct PhanSo { int tu; int mau; }; /* Tạo cấu trúc dữ liệu cho danh sách liên kết đơn */ struct Node { PhanSo *data; Node *pNext; }; struct SingleList { Node *pHead; Node *pTail; }; /* Khởi tạo cho pHead và pTail */ void Initialize(SingleList *&list) { list=new SingleList; list->pHead=list->pTail=NULL; }

Tiếp đến viết một hàm tạo Node với cấu trúc dữ liệu ở trên.

/* Tạo node */ Node *CreateNode(int tu,int mau) { Node *pNode=new Node; if(pNode==NULL) { cout<<"Loi bo nho"; exit(0); } PhanSo *ps=new PhanSo; ps->mau=mau; ps->tu=tu; pNode->data=ps; pNode->pNext=NULL; return pNode; }

Để thêm dữ liệu cho danh sách ta cần một hàm InsertLast() và để xuất dữ liệu ta cần một hàm PrintList().

/* Insertlast */ void InsertLast(SingleList *&list,int tu,int mau) { Node *pNode=CreateNode(tu,mau); if(list->pTail==NULL) { list->pHead=list->pTail=pNode; } else { list->pTail->pNext=pNode; list->pTail=pNode; } } /* printlist */ void PrintList(SingleList *list) { Node *pTmp=list->pHead; while(pTmp!=NULL) { PhanSo *ps=pTmp->data; cout<<ps->tu<<"/"<<ps->mau<<"+"; pTmp=pTmp->pNext; } }

Cuối cùng là một hàm tính giai thừa GiaiThua() và hàm tính tổng SumOfList().

/* hàm tính giai thừa */ int GiaiThua(int n) { if(n<=1) return 1; return n*GiaiThua(n-1); } /* hàm tính tổng */ double SumOfList(SingleList *list) { double sum=0; Node *pTmp=list->pHead; while(pTmp!=NULL) { PhanSo *ps=pTmp->data; sum=sum+(ps->tu*1.0/ps->mau); pTmp=pTmp->pNext; } return sum; }

Để hiển thị và kiểm tra kết quả ta cần một hàm main().

int main(int argc, char** argv) { SingleList *list; Initialize(list); int n,x; cout<<"Nhập n:"; cin>>n; cout<<"Nhập x:"; cin>>x; for(int i=1;i<=n;i++) { int tu=(int) pow(x,i); int mau=GiaiThua(i); InsertLast(list,tu,mau); } cout<<"Danh sách liên kết: \n"; PrintList(list); double sum=SumOfList(list); cout<<"\nTổng các phần tử trong danh sách: "<<sum; }

Full code:

#include <iostream> #include <math.h> using namespace std; /* Tạo cấu trúc cho phân số */ struct PhanSo { int tu; int mau; }; /* Tạo cấu trúc dữ liệu cho danh sách liên kết đơn */ struct Node { PhanSo *data; Node *pNext; }; struct SingleList { Node *pHead; Node *pTail; }; /* Khởi tạo cho pHead và pTail */ void Initialize(SingleList *&list) { list=new SingleList; list->pHead=list->pTail=NULL; } /* Tạo node */ Node *CreateNode(int tu,int mau) { Node *pNode=new Node; if(pNode==NULL) { cout<<"Loi bo nho"; exit(0); } PhanSo *ps=new PhanSo; ps->mau=mau; ps->tu=tu; pNode->data=ps; pNode->pNext=NULL; return pNode; } /* Insertlast */ void InsertLast(SingleList *&list,int tu,int mau) { Node *pNode=CreateNode(tu,mau); if(list->pTail==NULL) { list->pHead=list->pTail=pNode; } else { list->pTail->pNext=pNode; list->pTail=pNode; } } /* printlist */ void PrintList(SingleList *list) { Node *pTmp=list->pHead; while(pTmp!=NULL) { PhanSo *ps=pTmp->data; cout<<ps->tu<<"/"<<ps->mau<<"+"; pTmp=pTmp->pNext; } } /* hàm tính giai thừa */ int GiaiThua(int n) { if(n<=1) return 1; return n*GiaiThua(n-1); } /* hàm tính tổng */ double SumOfList(SingleList *list) { double sum=0; Node *pTmp=list->pHead; while(pTmp!=NULL) { PhanSo *ps=pTmp->data; sum=sum+(ps->tu*1.0/ps->mau); pTmp=pTmp->pNext; } return sum; } int main(int argc, char** argv) { SingleList *list; Initialize(list); int n,x; cout<<"Nhập n:"; cin>>n; cout<<"Nhập x:"; cin>>x; for(int i=1;i<=n;i++) { int tu=(int) pow(x,i); int mau=GiaiThua(i); InsertLast(list,tu,mau); } cout<<"Danh sách liên kết: \n"; PrintList(list); double sum=SumOfList(list); cout<<"\nTổng các phần tử trong danh sách: "<<sum; cout<<"\n-------------------------------\n"; cout<<"Chương trình nay được đăng tại Freetuts.net"; }

Kết quả:

Như vậy là chúng ta đã thực hiện xong hai bài tập áp dụng các thao tác trong danh sách liên kết đơn, các bạn hãy luyện tập thật nhiều các bài tập khác nữa nhé. Chúc các bạn thực hiện thành công!!!