Bài tập danh sách liên kết đơn c++ năm 2024

Question

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

/ 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; }

4 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

/ 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; }

5 để 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

/ 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; }

6, 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

/ 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; }

7 để 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

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: "<---\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

/ 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; }

4 và để xuất dữ liệu ta cần một hàm

/ 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; }

5.

/ 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; }

0

Cuối cùng là một hàm tính giai thừa

/ 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; }

0 và hàm tính tổng

/ 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; }

6.

/ 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; }

1

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

/ 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; }

7.

/ 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; }

2

Full code:

/ 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; }

3

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!!!

mẹo hay Khỏe Đẹp Bài tập Học Tốt Sách Top List Danh sách

Bài tập danh sách liên kết đơn c++ năm 2024

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

include

include

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

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội