[线性表](4)循环链表
循环链接(circular linked list)是另一种形式的链式存储结构,它的特点是表中最后一个结点的指针域指向头结点。整个链表形成一个环。
由此,从表中任一结点出发均可找到表中其他结点,如下图所示:
类似的,还可以有多重链的循环链表。
循环链表的操作和线性表基本一致,差别仅在于算法中的循环条件不是p或者p->next为NULL,而是他们是否等于头结点
循环链表中有带头结点和不带头结点之分,不带头节点就是头指针一直指向第一个节点。
主要算法下:声明链表
typedef struct List
{
int data;
struct List* next;
}CList;
尾插
void Malloc_CL()
{
node = (CList*)malloc(sizeof(CList));
scanf("%d", &node->data);
if (head == NULL)
{
head = node;
node->next = head;
}
else
{
p = head;
while (p->next != head)
{
p = p->next;
}
node->next = p->next;
p->next = node;
}
}
头插:
void Malloc_CL()
{
node = (CList*)malloc(sizeof(CList));
scanf("%d", &node->data);
if (head == NULL)
{
head = node;
node->next = head;
}
else
{
p = head;
while (p->next != head)
{
p = p->next;
}
node->next = head;
p->next = node;
head = node;
}
}
尾删:
void Delete_CL()
{
p = head;
s = head;
while (s->next != head)
{
p = s;
s = s->next;
}
free(s);
p->next = head;
}
头删:
void Delete_CL()
{
p = head;
s = head;
while (s->next != head)
{
s = s->next;
}
s->next = p->next;
head = p->next;
free(p);
}
遍历:
p = head;
do
{
printf("%d ", p->data);
p = p->next;
} while (p != head);
带头结点:初始化
void MalloHead()
{
head = (CList*)malloc(sizeof(CList));
head->next = head;
}
尾插:
void Malloc_CL()
{
node = (CList*)malloc(sizeof(CList));
scanf("%d", &node->data);
p = head;
while (p->next != head)
{
p = p->next;
}
node->next = head;
p->next = node;
}
头插:
void Malloc_CL()
{
node = (CList*)malloc(sizeof(CList));
scanf("%d", &node->data);
p = head;
node->next = p->next;
p->next = node;
}
尾删:
void Delete_CL()
{
p = head;
s = head->next;
while (s->next != head)
{
p = s;
s = s->next;
}
p->next = head;
free(s);
}
头删
void Delete_CL()
{
p = head->next;
head->next = p->next;
free(p);
}
遍历
p = head->next;
while (p != head)
{
printf("%d ", p->data);
p = p->next;
}
可以看到,循环单链和单链表的操作大致一样。但有的时候,若在循环链表中设立尾指针而不设头指针,可以简化某些操作,如下图所示:链接两表,只需要将A表尾链接到B表头,将B表尾链接到A表头即可
链接前
链接后
只需要修改两个指针域即可