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.

Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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