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

Bài tập thực hành với danh sách liên kết đơn

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.

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 hiepsiit.com"; }

Kết quả: