Một số hàm trong danh sách liên kết vòng

Danh sách liên kết vòng: Là một danh sách liên kết đơn (hoặc đôi) mà phần tử cuối danh sách, thay vì mang giá trị NULL, trỏ tới phần tử đầu danh sách .Đối với danh sách vòng, có thể xuất phát từ một phần tử bất kỳ để duyệt toàn bộ danh sách.
Sau đây là một số hàm trong danh sách liên kết vòng:

Khởi tạo cấu trúc 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;
Tạo 1 nút cho danh sách
NODEPTR getnode(void)
{
      NODEPTR p;
   p = (NODEPTR) malloc(sizeof(struct node));
   return (p);
};
Giải phóng biến đã cấp phát
void freenode(NODEPTR p)
{
      free(p);
}
Khởi động danh sách
void initialize(NODEPTR *plist)
{
     *plist = NULL;
}
Kiểm tra danh sách rỗng
int empty(NODEPTR *plist)
{
       return(*plist == NULL ? true : false);
}
Đếm các nút có trong danh sách
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);
}
Trả về vị trí con trỏ của nút trong danh sách (i=0,1,2....)
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);
}
Thêm 1 nút vào đầu danh sách
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;
};
Thêm 1 nút vào cuối danh sách
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;
};
xóa nút đầu danh sách
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);
   }
};

Xóa nút cuối danh sách
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);
   } 
}
Duyệt từ đầu đến cuối danh sách
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;
      }
   }
}