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
Bạn đang đọc: Bài tập thực hành với danh sách liên kết đơn
, không được copy dưới mọi hình thức.
Phần này giúp những bạn ôn lại bài và biết cách vận dụng kiến thức và kỹ năng đã học vào bài tập trong thực tiễn .
Chúng ta sẽ thực thi 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 những bạn hoàn toàn có thể quản trị được list link và thao tác với nó một cách thành thạo .
Tóm Tắt
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 tất cả chúng ta sẽ triển khai giải một bài toán như sau :
s(x,n) = x1 + x2 + x3 + ... + xn
Xây dựng list link đơn có pHead, pTail. Nhập x, n tạo thành list link ( 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 list link .
Viết hàm xuất ra tổng những thành phần trong list link .
Gợi ý:
Để giải bài toán này việc tiên phong ta cần cấu trúc tài liệu của list link đơn. Giá trị data là x và i, mối link 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 tài 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<x<<"^"< i<<"+"; else cout< x<<"^"< 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: "<Full code:
#include#include 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< x<<"^"< i<<"+"; else cout< x<<"^"< 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: "< 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 thi 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 tài 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àmPrintList()
./* 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<tu<<"/"< 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ổngSumOfList()
./* 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: "<Full code:
#include#include 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< tu<<"/"< 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: "< Kết quả:
Như vậy là tất cả chúng ta đã triển khai xong hai bài tập vận dụng những thao tác trong list link đơn, những bạn hãy rèn luyện thật nhiều những bài tập khác nữa nhé. Chúc những bạn thực thi thành công xuất sắc ! ! !Xem thêm: Chi tiết bài học Lớp lưu trữ trong C++
Source: https://final-blade.com
Category: Kiến thức Internet