Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Tìm kiếm và sắp xếp trong danh sách liên kết đơn
Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm và sắp xếp trong danh sách liên kết đơn.
Chúng ta sẽ cùng nhau tìm hiều lần lượt cách tìm kiếm một giá trị index trong danh sách và thực hiện sắp xếp danh sách theo thứ tự tăng dần. Sắp xếp và tìm kiếm là hai thuật toán không thể thiếu trong các ngôn ngữ lập trình, bì vậy các bạn hãy luyện tập cho thành thạo nhé.
1. Tìm kiếm trong danh sách liên kết đơn
Trong phần này mình sẽ thực hiện tìm kiếm một giá trị index được nhập từ phím trong danh sách liên kết đơn. Đây là một thao tác đơn giản, chỉ cần ta duyệt từng phần tử trong danh sách.
Giả sử chúng ta có giá trị index = 5 là giá trị cần tìm trong danh sách. Lúc này ta cần khai báo một Node tạm pTmp để thay thế cho pHead duyệt danh sách.
Bài viết này được đăng tại [free tuts .net]
Thực hiện vòng lặp while lặp từng phần tử trong danh sách với điều kiện pTmp != Null. Nếu pTmp -> data == index thì thoát khỏi vòng lặp và thông báo đã tìm thấy, ngược lại thì thông báo không tìm thấy.
/* tìm kiếm giá trị index trong danh sách */
Node * SearchNode(SingleList list,int d)
{
Node *pTmp=list.pHead; // khai báo biến tạm pTmp thay thế cho pHead để duyệt danh sách
//Thực hiện vòng lặp các phần tử trong danh sách với điều kiện pTmp != null
while(pTmp!=NULL)
{
if(pTmp->data==d) // nếu tìm thấy index thì thoát khỏi vòng lặp
break; // chưa tìm thấy thì tiếp tục duyệt phần tử kết tiếp
pTmp=pTmp->pNext;
}
return pTmp;
}2. Sắp xếp trong danh sắp liên kết đơn
Ở phần sắp xếp phần tử trong danh sách liên kết đơn, mình sẽ thực hiện sắp xếp bằng cách so sánh và thay đổi giá trị data chứ không thay đổi Node. Tức là chỉ so sánh các giá trị data rồi sắp xếp, các Node vẫn giữ nguyên không dịch chuyển.
Thao tác sắp xếp trong danh sách về cơ bản tương tự như các thuật toán sắp xếp khác, đơn giản chỉ là duyệt từng phần tử rồi so sánh với nhau, sau đó hoán đổi vị trí của chúng.
Đầu tiên ta có một vòng lặp For sử dụng biến pTmp để lặp từng phần tử trong danh sách, vòng lặp For thứ hai sử dụng biến pTmp2 để lặp từng phần tử trong danh sách.
Nếu pTmp > pTmp2 thì hoán đổi vị trí giữa chúng, nếu pTmp < pTmp2 thì tiếp tục so sách các phần tử tiếp theo, cứ như vậy cho đến hết danh sách.
/* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */
void SortList(SingleList &list)
{
// for loop thứ nhất
for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext)
{
//for loop thứ hai
for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
{
if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí
{
int tmp=pTmp->data;
pTmp->data=pTmp2->data;
pTmp2->data=tmp;
}
}
}
}3. Ví dụ tìm kiếm và sắp xếp trong danh sách liên kết đơn
Trong phần ví dụ này chúng ta sẽ sử dụng dữ liệu ở ví dụ trước để áp dụng cho việc tìm kiếm và sắp xếp. Các bạn lưu ý rằng muốn sử dụng được các thao tác mình đã hướng dẫn thì luôn luôn khái báo cấu trúc dữ liệu của DSLK đơn trước nhé.
#include <iostream>
using namespace std;
/* Khai báo giá trị data và con trỏ pNext trỏ tới phần tử kế tiếp */
struct Node
{
int data;// giá trị data của node
Node *pNext;// con trỏ pNext
};
/* Khai báo Node đầu pHead và Node cuối pTail*/
struct SingleList
{
Node *pHead; //Node đầu pHead
Node *pTail; // Node cuối pTail
};
/* khởi tạo giá trị cho Node đầu và Node cuối */
void Initialize(SingleList &list)
{
list.pHead=list.pTail=NULL;// khởi tạo giá trị cho Node đầu và Node cuối là Null
}
/* Đếm số phần tử trong danh sách */
int SizeOfList(SingleList list)
{
Node *pTmp=list.pHead;
int nSize=0;
while(pTmp!=NULL)
{
pTmp=pTmp->pNext;
nSize++;
}
return nSize;
}
/* tạo Node trong danh sách liên kết đơn */
Node *CreateNode(int d)
{
Node *pNode=new Node; //sử dụng pNode để tạo một Node mới
if(pNode!=NULL) // Nếu pNode != Null, tức là pNode có giá trị thì
{
pNode->data=d; // gán giá trị data cho d
pNode->pNext=NULL;// và cho con trỏ pNext trỏ tới giá trị Null
}
else // Nếu pNode == Null, tức là pNode không có giá trị thì xuất thông tin
{
cout<<"Error allocated memory";
}
return pNode;//trả về pNode
}
/* chèn Node đầu danh sách */
void InsertFirst(SingleList &list,int d)
{
Node *pNode=CreateNode(d);
if(list.pHead==NULL)
{
list.pHead=list.pTail=pNode;
}
else
{
pNode->pNext=list.pHead;
list.pHead=pNode;
}
}
/* chèn node vào cuối danh sách */
void InsertLast(SingleList &list,int d)
{
Node *pNode=CreateNode(d);
if(list.pTail==NULL)
{
list.pHead=list.pTail=pNode;
}
else
{
list.pTail->pNext=pNode;
list.pTail=pNode;
}
}
/* chèn node vào giữa danh sách */
void InsertMid(SingleList &list, int pos, int d){
// Nếu pos < 0 hoặc pos lớn hơn kích thước của danh sách thì reuturn
if(pos < 0 || pos >= SizeOfList(list)){
cout<<"Không thể chèn Node!!!";
return;
}
// Nếu pos == 0 thì gọi hàm InsertFirst
if(pos == 0){
InsertFirst(list, d);
}
//Nếu pos == SizeOfList - 1 thì gọi hàm InsertLast
else if(pos == SizeOfList(list)-1){
InsertLast(list, d);
}
//Ngược lại thì thay đổi mối liên kết giữa các phần tử, cụ thể:
else{
Node *pNode = CreateNode(d);
Node *pIns = list.pHead;
Node *pPre = NULL;
int i = 0;
//thực hiện vòng lặp tìm pPre và pIns
while(pIns != NULL){
if(i == pos)
break;
pPre = pIns;
pIns = pIns ->pNext;
i++;
}
//sau khi tìm được thì thay đổi con trỏ pNext
pPre ->pNext=pNode;
pNode->pNext=pIns;
}
}
/* tìm kiếm giá trị index trong danh sách */
Node * SearchNode(SingleList list,int d)
{
Node *pTmp=list.pHead; // khai báo biến tạm pTmp thay thế cho pHead để duyệt danh sách
//Thực hiện vòng lặp các phần tử trong danh sách với điều kiện pTmp != null
while(pTmp!=NULL)
{
if(pTmp->data==d) // nếu tìm thấy index thì thoát khỏi vòng lặp
break; // chưa tìm thấy thì tiếp tục duyệt phần tử kết tiếp
pTmp=pTmp->pNext;
}
return pTmp;
}
/* sắp xếp trong danh sách liên kết đơn theo thứ tự tăng dần */
void SortList(SingleList &list)
{
// for loop thứ nhất
for(Node *pTmp=list.pHead;pTmp!=NULL;pTmp=pTmp->pNext)
{
//for loop thứ hai
for(Node *pTmp2=pTmp->pNext;pTmp2!=NULL;pTmp2=pTmp2->pNext)
{
if(pTmp->data>pTmp2->data) // nếu giá trị trước > giá trị sau thì hoán đổi hai vị trí
{
int tmp=pTmp->data;
pTmp->data=pTmp2->data;
pTmp2->data=tmp;
}
}
}
}
/* hàm xuất dữ liệu */
void PrintList(SingleList list)
{
Node *pTmp=list.pHead;
if(pTmp==NULL)
{
cout<<"The list is empty!";
return;
}
while(pTmp!=NULL)
{
cout<<pTmp->data<<" ";
pTmp=pTmp->pNext;
}
}
int main() {
SingleList list;
Initialize(list);
//Thêm node đầu danh sách
InsertFirst(list, 5);
InsertFirst(list, 7);
InsertFirst(list, 3);
cout<<"Các Node trong danh sách sau khi InsertFirst là: ";
PrintList(list);
//Thêm node cuối danh sách
InsertLast(list, 4);
InsertLast(list, 2);
InsertLast(list, 6);
cout<<"\nCác Node trong danh sách sau khi InsertLast là: ";
PrintList(list);
//Thêm node giữa danh sách
InsertMid(list, 4, 11);
InsertMid(list, 2, 12);
InsertMid(list, 3, 13);
cout<<"\nCác Node trong danh sách sau khi InsertMid là: ";
PrintList(list);
//Tìm kiếm giá trị index trong danh sách
int index;
cout<<"\nNhập vào số bạn muốn tìm: ";
cin>>index;
Node *pFound = SearchNode(list, index);
if(pFound == NULL){
cout<<"Không tìm thấy số "<<index<<" trong danh sách";
}
else{
cout<<"Đã tìm thấy số "<<index<<" trong danh sách.";
}
//Sắp xếp các phần tử trong danh sách
cout<<"\nDanh sách trước khi sắp xếp: ";
PrintList(list);
SortList(list);
cout<<"\nDanh sách sau khi sắp xếp: ";
PrintList(list);
cout<<"\n-------------------------------------\n";
cout<<"Chương trình này được đăng tại Freetuts.net";
}Kết quả:
Như vậy là chúng ta đã thực hiện xong chương trình tìm kiếm và sắp xếp các phần tử trong danh sách liên kết đơn. Cũng như kết thúc hướng dẫn thao tác tìm kiếm và sắp xếp. Chúc các bạn thực hiện thành công !!!
