Danh sách đa liên kết trong ngôn ngữ lập trình C/C++

Cũng giống như danh sách liên kết đơn thì danh sách đa liên kết cũng là một dạng danh sách liên kết nhưng nó có nhiều mối liên kết (danh sách liên kết đơn chỉ có một liên kết đến phần tử đứng sau nó). Bài viết dưới đây Isinhvien sẽ chia sẻ đến các bạn cách biểu diễn, các thao tác cơ bản trên danh sách đa liên kết đầy đủ chi tiết nhất để giúp các bạn hiểu rõ hơn về dạng danh sách liên kết này nhé!

Biểu diễn danh sách đa liên kết

Giả sử ta cần một danh sách đa liên kết các công nhân gồm họ tên và tuổi. Khi đó, có thể ta sẽ cần sắp xếp thứ tự họ tên, cũng có thể cần sắp xếp theo độ tuổi, đây sẽ là lúc thích hợp để ta dùng danh sách đa liên kết. Vì vậy, mỗi phần tử trong danh sách đa liên kết là một bản ghi ngoài các trường chứa dữ liệu của bản thân nó thì còn có thêm 2 trường liên kết. Trường liên kết thứ nhất ta có thể đặt tên là next1 dùng để chỉ đến phần tử đứng ngay sau nó theo thứ tự họ tên, trường liên kết thứ hai (next2) chỉ đến phần tử đứng ngay sau nó theo thứ tự độ tuổi.

struct element
{   
   string Name;
   int Age;
   element *next1, *next2;
};
typedef element *List;
List F1, F2;

Trong đó, biến con trỏ F1 chỉ đến phần tử đầu tiên trong danh sách được sắp theo thứ tự họ tên tăng dần, biến con trỏ F2 chỉ đến phần tử đầu tiên được sắp theo thứ tự độ tuổi tăng dần.

Các phép toán trên danh sách đa liên kết

1. Khởi tạo danh sách đa liên kết

Khi mới khởi tạo danh sách là rỗng, ta cho F1 và F2 nhận giá trị NULL

void Create(List &F1, List &F2)
{ 
    F1=NULL; 
    F2=NULL;
}

2. Liệt kê các phần tử trong danh sách đa liên kết

Ở đây, ta có thể liệt kê theo thứ tự họ tên hoặc thứ tự độ tuổi tùy vào mục đích sử dụng:

Liệt kê theo thứ tự họ tên: Ta liệt kê bắt đầu từ phần tử đầu tiên chỉ bởi biến con trỏ F1, và dựa vào trường liên kết next1 để lần lượt liệt kê các phần tử tiếp theo.

void Display1(List F1)
{ 
   List p;
   p=F1;
   while (p != NULL)
   { 
      cout << (*p).Name << " " << (*p).Age; 
      p=(p)*.next1;
   }
}

Liệt kê theo thứ tự độ tuổi: Ta liệt kê bắt đầu từ phần tử đầu tiên chỉ bởi biến con trỏ F2, và dựa vào trường liên kết next2 để lần lượt liệt kê các phần tử tiếp theo.

void Display1(List F2)
{
   List p;
   p=F2;
   while (p != NULL)
   {
      cout << (*p).Name << " " << (*p).Age;
      p=(p)*.next2;
   }   
}

3. Tìm một phần tử trong danh sách đa liên kết

Giả sử t cần tìm phần tử có họ và tên x, độ tuổi là y. Trong danh sách sắp xếp theo thứ tự họ tên có phần tử đầu tiên được chỉ bởi biến con trỏ F1, ta tìm từ phần tử đầu tiên trở đi cho đến khi tìm được phần tử có họ tên là x, độ tuổi là y, hoặc đã kiểm tra xong phần tử cuối cùng mà không có thì dừng. Hàm Search(F1, x, y) kiểu List, tìm và trả về địa chỉ của phần tử đầu tiên tìm được hoặc trả về giá trị NULL nếu tìm không có.

List Search (List F1, string x, int y) 
{ 
    List p; 
    p=F1; 
    while ( (p!=NULL &&  x > (*p).Name)  || ( x == (*p).Name       
             && (*p).Age!=y ) ) 
             p= (*p).next1; 
    if ( (p!=NULL) && (x==(*p).Name) && ((*p).cc==y) ) return p;  
    else return NULL; 
}

4. Thêm một phần tử vào danh sách đa liên kết

Giả sử cần thêm một phần tử có họ tên là x, tuổi là y vào danh sách. Biến con trỏ p chỉ đến phần tử mới cần thêm vào. Biến con trỏ before chỉ đến phần tử đứng ngay trước phần tử mới theo thứ tự họ tên và thứ tự độ tuổi. Biến con trỏ after chỉ đến phần tử đứng ngay sau phần tử được chỉ bởi before.

void InsertElement (List &F1, List &F2, string x, int y z) 
{  
    List p, before, after; 
    p=new element; 
    (*p).Name = x; 
    (*p).Age = y;  
    // Tim before va after theo ho ten 
      after=F1; 
      while ( (after!=NULL) && ((*p).Name < x) ) { 
         before=after; 
         after=(*after).next1; }; 
         (*p).next1=after; 
         if (F1==after) F1=p; 
         else (*before).next1=p; 
    // Tim before va after theo do tuoi
       after=F2; 
       while ( (after!=NULL) && ( (*after).Age < y)){  
          before=after;
          after=(*after).next2; 
       }; 
       (*p).next2=after;
       if (F2==after) F2=p;
       else (*before).next2=p;
}

5. Xóa một phần tử khỏi danh sách liên kết

Giả sử ta cần xóa một phần tử có họ và tên x, tuổi y ra khỏi danh sách, ta cần 1 biến con trỏ p chỉ đến phần tử cần xóa. Biến con trỏ before lần lượt chỉ đến phần tử đứng ngay
trước phần tử cần xóa theo thứ tự họ tên và thứ tự chiều cao.

void DeleteElement(List &F1, List &F2, string x, int y) 
{ 
   List p, t, before; 
   // Tim p 
   // Tim before theo ho ten 
   p=F1;  
   while ( (p!=NULL &&  (*p).Name < x) || ( (*p).Name == x
         && (*p).Age!=y  ) ) 
   {  
       before = p; 
       p=(*p).next1; 
   } 
   if ( (p!=NULL) && (*p).Name == x && (*p).Age==y ) 
   // nếu tìm có 
   {  
       if (F1==p) F1=(*p).next1; 
       else (*before).next1=(*p).next1; 
   // Tim before theo do tuoi
       t=F2; 
       while (t!=p) 
      { 
         before = t; 
         t = (*t).next2; 
      } 
      if (F2==p) F2=(*p).next2; 
      else (*before).next2 = (*p).next2; 
      delete p; 
   } 
}

Trên đây là tất tần tật những chía sẻ của Isinhvien về cách biễu diễn cũng như các pháp toán thao tác trên danh sách đa liên kết. Nếu các bạn thấy bài viết hay, ý nghĩa thì hãy chia sẻ đến với bạn bè của mình nhé! Đừng quên theo dõi Isinhvien để cập nhật thêm nhiều kiến thức hay mỗi ngày. Chúc các bạn nhiều sức khỏe và thành công trong cuộc sống!