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

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.

test php

banquyen png

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

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ả:

bai tap ren luyen 1 PNG

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 :

bai tap ren luyen 3 PNG

  • 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à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<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ổ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: "<

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ả:

bai tap ren luyen 2 PNG

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