DanH Sach Lien Ket Vong

Danh Sách liên kết vòng là danh sách liên kết nhưng trướng next của nút cuối chỉ nút đầu tiên trong danh sách.

Không nói dài dòng chúng ta sẽ nghiên cứu luôn về cách cài đặt danh sách liên kết vòng bằng biến động.
C Code:Lựa chọn code | Ẩn/Hiện code
int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
}

1. Khai báo cấu trúc một nút strong danh sách liên kết vòng.
Khai báo một nút là một mẫu tin (struct) có hai trường là info và next.
Trường info: chứa nội dung của nút.
Trường next: là con trỏ chỉ nút, dùng chỉ nút kế trong danh sách liên kết vòng.

struct node
{
      int info;
            struct node *next;
};
//khai bao kieu con tro chi den nut
typedef struct node *NODEPTR;
Chúng ta quản lý danh sách liên kết vòng qua con trỏ plist chỉ nút cuối của danh sách. Con trỏ plist có thể khai báo toàn cục hay cụ bộ.


2. Các tác vụ trên danh sách liên kết vòng:

Tác vụ getnode:
Cấp phát một biến động làm cho nút một danh sách liên kết vòng:

NODEPTR getnode(void)
{
      NODEPTR p;
   p = (NODEPTR) malloc(sizeof(struct node));
   return (p);
};

Tác vụ freenode:
Giải phóng biến động đã cấp phát trước đó.

void freenode(NODEPTR p)
{
      free(p);
}

Tác vụ initialize:
Khởi động danh sách liên kết vòng:

void initialize(NODEPTR *plist)
{
     *plist = NULL;
}

Tác vụ empty:
Kiểm tra danh sách liên kết vòng có rỗng không.

int empty(NODEPTR *plist)
{
       return(*plist == NULL ? true : false);
}

Tác vụ listsize:
Đếm số nút có trong danh sách liên kết vòng:

int listsize(NODEPTR *plist)
{
     NODEPTR p;
   int i;
   if(empty(plist))
       return (0);
   p = (*plist->next);
   i = 1;
   while(p != *plist)
   {
        i++;
      p = p->next;
   }
   return (i);
}

Tác vụ nodepointer:
Trả về con trỏ nút thứ i (i = 0,1,2,....) trong danh sách liên kết vòng

NODEPTR nodepointer(NODEPTR *plist, int i)
{
      NODEPTR p;
      int vitri;
      if(i < 0 || i >= listsize(plist))
           return(null);
      p = (*plist)->next; //p chi nut dau dslk vong
      for(vitri = 0;vitri < i;vitri++)
          p = p->next;
      return(p);
}

Tác vụ push:
Thêm một nút vào đầu danh sách liên kết vòng.

void push(NODEPTR *plist, int x)
{
      NODEPTR p;
   p = getnode();
   p->info = x;
   if(empty(plist) == true)
       *plist = p;
   else
       p->next = (*plist)->next;
   (*plist)->next = p;
};

Tác vụ insend:
Thêm nút vào cuối danh sách liên kết vòng.

void insend(NODEPTR *plist, int x)
{
    NODEPTR p;
    p = getnode();
    p->info = x;
    if(empty(plist) == true)
        p->next = p;
    else
    {
         p->next = (*plist)->next;
      (*plist)->next = p;
    }
    *plist = p;
};

Tác vụ pop:
Xóa nút ở đầu danh sách liên kết vòng.

int pop(NODEPTR *plist)
{
      NODEPTR p;
   int x;
   if(empty(plist))
       printf("Danh sach bi rong");
   else
   {
        p = (*plist)->next; // p la nut can xoa
      x = p->info;
      if(p == *plist) // truong hop ds chi co mot nut
          *plist = NULL;
      else
          (*plist)->next = p->next;
      freenode(p);
      return (x);
   }
};

Tác vụ dellast:
Xóa nút ở cuối danh sách liên kết vòng.

int dellast(NODEPTR *plist)
{
     NODEPTR p;
   int x;
   if(empty(plist))  // truong hop danh sach bi rong
       printf("Danh sach bi rong");
   else
   {
        if((*plist)->next == plist) // truong hop cho co mot nut
           {
              p = *plist;
               x = p->info;
             *plist = NULL;
              freenode(p);
              return(x);
         }
         p = *plist;    // p la nut can xoa
         x = p->info;
         *plist = nodepointer(plist, listsize(plist) - 2);
         (*plist)->next = p->next;
         freenode(p);
         return (x);
   }
}

Tác vụ traverse:
Duyệt danh sách liên kết vòng từ nút đầu đến nút cuối.

void traverse(NODEPTR *plist)
{
     NODEPTR p;
   if(*plist == NULL)
       printf("Danh sach rong")
   else
   {
        p = (*plist)->next; //p chi nut dau
      printf("%d", p->info);
      p = p->next;        //p chi nut thu hai
      while(p != (*plist)->next)
      {
           printf("%d",p->info);
         p = p->next;
      }
   }
}