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;
}
}
}