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.

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

Bạn đang đọc: Tìm kiếm và sắp xếp trong danh sách liên kết đơn

, 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 thi 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 hề thiếu trong những ngôn từ lập trình, bì vậy những bạn hãy rèn luyện cho thành thạo nhé .

Tóm Tắt

1. Tìm kiếm trong danh sách liên kết đơn

Trong phần này mình sẽ thực thi 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 thuần, chỉ cần ta duyệt từng thành phần trong danh sách .

tim kiem sap xep 1 PNG

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.

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.

Xem thêm: Lấy Lại Mật Khẩu Facebook Qua Bạn Bè Khôi Phục 100%

tim kiem sap xep 2 PNG

Thao tác sắp xếp trong danh sách về cơ bản tựa như như những thuật toán sắp xếp khác, đơn thuần chỉ là duyệt từng thành phần 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 thành phần trong danh sách, vòng lặp For thứ hai sử dụng biến pTmp2 để lặp từng thành phần 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 tất cả chúng ta sẽ sử dụng tài liệu ở ví dụ trước để vận dụng cho việc tìm kiếm và sắp xếp. Các bạn chú ý quan tâm rằng muốn sử dụng được những thao tác mình đã hướng dẫn thì luôn luôn khái báo cấu trúc tài liệu của DSLK đơn trước nhé .

#include 
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<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ố "<Kết quả:
Xem thêm: Hướng dẫn cách cài đặt khóa màn hình máy tính đơn giản nhất


Như vậy là tất cả chúng ta đã triển khai xong chương trình tìm kiếm và sắp xếp những thành phần 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 những bạn thực thi thành công xuất sắc ! ! !

Source: https://final-blade.com
Category: Kiến thức Internet

admin

final-blade.com