单向循环链表

单向循环链表特点

• 尾结点的指针域指向头结点 rear->next==head
• 单向循环链表中没有NULL
• 可以在链表上多次往复循环
• 在插入、删除算法上遵循单向链表
• 从表中任意结点出发，能访问到所有结点
• 为了判断起始位置，一般要设置头结点，头结点的设置也可将空表与非空表结合起来

单向循环链表的创建

ElemSN * Greatlink(int a[])
{
	ElemSN *t,*p,*h;
	h=NULL;
	for(int i=0;i<N;i++)
	{
	p=(ElemSN*)malloc(sizeof(ElemSN));
	p->data=a[i];	
	if(!h){			//头结点 
		p->next=p;
		h=t=p;
	}
	else{
		p->next=h;
		t=t->next=p;
	}
	}
	return h;
}

单向循环链表的输出（！！！）

使用 do while语句，先输出一次

void Printlink(ElemSN*h)
{
	ElemSN *p=h;
	do{
		printf("%5d",p->data);
		p=p->next;
	}
	while(p!=h);
}

单向循环链表，删除关键字为KEY的结点（考虑有重复值）

我认为此题的难点在于：do while 循环，不同于以往的while 或 for循环
do while 先执行一次，再做判断，在循环链表中得到很好的应用

ElemSN*Delnode(ElemSN*h,int key)
{
	ElemSN *p,*q;
	int cnt=0;		//记录删除结点的个数
	p=h;
	q=NULL;
	do{
		if(p->data!=key){
			q=p;
			p=p->next;
		}
		else{
			if(p==h){
				for(q=h;q->next-h;q=q->next);	//不用分中间和头尾 
				h=h->next;
			}
			
			q->next=p->next;
			free(p);
			cnt++;
			p=h;
		}
	}while(p->next!=h);
	
	if(p->data==key){	//判断最后一个结点是否被删除
		q->next=h;
		free(p);
	}
	
	if(cnt==0)				//没有结点被删除，即没有找到关键字为KEY的结点
		return 0;
		
	return h;
 } 

应用：

约瑟夫环问题