循环链表——单链表的改进之一

        对于单链表，由于每个结点只存储了向后的指针，到了尾标志就停止了向后链的操作，如此一来，链表中的结点就无法访问它的前驱（除非从头开始访问）。将单链表中终端结点的指针由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。其实循环链表和单链表的主要区别在于循环的判断条件上，由p->next是否为空改为p->next是否等于头结点，等于头结点则循环结束。

        在单链表中，我们可以通过头结点用O（1）的时间访问第一个结点，却需要通过O（n）的时间访问最后一个结点；在循环链表中，我们可以改造一下，使用指向终端的尾指针，用O（1）的时间访问头结点和终端节点。下图为循环链表示意图：

       循环链表中的大多数操作与单链表相同，但在合并操作中，循环链表因为存在尾指针就可以变得非常简单。所以我们重点来看合并操作。

代码预处理与循环链表定义

#include
#include
#include
typedef struct LNODE{
int data;
struct LNODE*next;
}LNode,*Linklist;

创建循环链表

void CreatCir(Linklist &L){
Linklist p, nail;
L = (LNode*)malloc(sizeof(LNode));
L->next = L;
nail = L;
p = (LNode*)malloc(sizeof(LNode));
printf("请输入循环链表元素,按Ctrl+Z结束：\n");
while ((scanf("%d", &(p->data))) != EOF){
p->next = L;
nail->next = p;
nail = p;
p = (LNode*)malloc(sizeof(LNode));
}
}

打印循环链表

void PrintCir(Linklist L){
Linklist p;
printf("建立的循环单链表为：\n");
p = L->next;
while (p!=L){
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}

合并操作

void Mergelist(Linklist &L1, Linklist &L2){
CreatCir(L2);
Linklist pA,pB,rear;
pA = L1->next;
pB = L2->next;
while (pA->next != L1)
pA = pA->next;//使pA指向L1最后一个结点
while (pB->next != L2)
pB = pB->next;//使pB指向L2最后一个结点
rear = pA->next;//保存pA的下一个结点，即L1头结点
pA->next = pB->next->next;//使L1的尾结点与L2的第一个结点相连
pB->next = rear;//使L2的尾结点与L1头结点相连
free(L2);//不再需要L2头结点，所以释放L2头结点
}

主函数调用

int main(){
Linklist list,listSec;
CreatCir(list);
PrintCir(list);
Mergelist(list, listSec);
PrintCir(list);
system("pause");
return 0;
}

        
本期循环链表到此结束，有关单链表的其他方面的改进请看下一期。谢谢大家！