Kinh nghiệm - Thủ thuật

Danh sách liên kết đơn nối vòng là một danh sách liên kết đơn mà phần tử cuối cùng chỉ vào (có liên kết với) phần tử đầu tiên của danh sách.

Tương tự như khởi tạo danh sách liên kết đơn nhưng ta dùng hai con trỏ pHead, pTail trỏ vào phần tử đầu tiên và cuối cùng của danh sách. Vì là danh sách liên kết đơn nối vòng nên ta có thể hiển thị danh sách từ con trỏ pHead hoặc pTail.

Hàm mô phỏng thao tác khởi tạo danh sách liên kết đơn nối vòng bằng ngôn ngữ C như sau:

void Khoitao(Node * & pHead)

 {

   pHead = NULL; // tro dau

 }

Thêm một phần tử vào danh sách

Thêm một node vào đầu danh sách

Danh sách liên kết đơn nối vòng không có phần tử đầu danh sách rõ rệt, nhưng  ta có thể đánh dấu một phần tử bất kỳ trên danh sách xem như phần tử đầu danh sách để thực hiện thêm phần tử vào đầu danh sách.

Thuật toán:

Bước 1:Khai báo một biến con trỏ Node * pHeadtrỏ vào đầu danh sách(xem như pHead là con trỏ trỏ vào phần tử đầu danh sách).                      

   Và một con trỏ chỉ vào node cần thêm vào Node * e; một con trỏ Node * qlà con trỏ trung gian để tạo liên kết vòng khi thêm Node mới vào cho danh sách, ban đầu q được trỏ vào đầu danh sách pHead: q=pHead;

Bước 2:Kiểm tra nếu danh sách rỗng thì thực hiện cho Node mới vào danh sách:

                            e->Next =e;

           pHead=e;

     Ngược lại: Chuyển qua bước 3

   Bước 3: Cho con trỏ e->Next trỏ vào đầu danh sách

                           e->Next= pHead;  

               Tìm Node chứa liên kết vòng cũ của danh sách thông qua con trỏ q:

           while(q->Next!=pHead)       

            q=q->Next;

Thiết lập liên kết vòng đến Node mới thêm vào đầu danh sách:

           q->Next=e;

Cho con trỏ danh sách pHead trỏ vào con trỏ chứa địa chỉ của Node mới:

 pHead=e;

Hủy con trỏ e và con trỏ q khi công việc thêm đã hoàn thành:

e= NULL;   delete(e);

q= NULL;   delete(q);

Cài đặt thuật toán bằng ngôn ngữ C:

//Them mot phan tu vao dau danh sach lien ket don noi vong

void Themdau(int x, Node * & pHead)

{  

// Buoc 1: Tao Node e moi chua gia tri can them vao

   Node * e,*q;

   q=pHead;

   e = new Node;

   e->Data = x;

   e->Next = NULL;

//Buoc 2: Kiem tra ds rong thi them node vao dau danh sach

   if(pHead==NULL)

   {      e->Next =e;

           pHead=e;

   }           

   else

    {   

       e->Next= pHead;          

       while(q->Next!=pHead)       

            q=q->Next;                       

       q->Next=e;

       pHead=e;      

    }   

    e= NULL;

    delete(e);  

    q= NULL;

    delete(q);     

}

Demo chương trình