数据结构—带头结点的单循环链表

1.基本操作

• 循环链表的特点是最后一个元素的指针域指向头结点。

• 因此对于循环链表的初始化（设表的头结点是L， 不再是L->next=NULL，而是L->next=L。循环链表为空时，头结点的下一个结点依然是头结点本身。因此但虚幻链表的初始化如下：

//初始化 
int InitList(LinkList &L)
{
	L=new LNode;
	L->next=L;   //非循环链表的初始化是头指针的指针域置空 L->next=NULL 
	return 1;
}

• 从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链表做不到；
• 循环链表中没有明显的尾端，如何避免死循环？
• 循环条件：
  • p!=NULL  -—>  p!=L                    
  • p->next!=NULL ——>  p->next!=L
• 所以根据循环链表的特点，判断循环链表是否为空时，只需判断头结点的下一个结点是否是头结点即可：

//判断链表是否为空
int ListEmpty(LinkList L)
{
	if(L->next==L)
	{
		return 1;//空 
	}
	else
	{
		return 0;//非空 
	}
}

• 从头检查每一个结点，若当前结点不是头结点，则链表长度加1，由此可计算链表的长度：

//获取链表长度
int ListLength(LinkList L)
{
	int length=0;
	LNode *p;
	p=L->next;
	while(p!=L)
	{	//当p不是头结点时，链表长度加1 
		p=p->next;
		length++;
	}
	return length;
} 

• 遍历链表

//遍历链表
void TraveList(LinkList L)
{
	LNode *p;
	p=L->next;
	printf("遍历链表:\n");
	while(p!=L)
        {      //当p不是头结点时，输出元素值 
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
} 

• 使用头插法和尾插法创建单循环链表的方法和创建一般单链表的操作一样，区别在于建立空链表的语句不同。一般单链表是L->next=NULL，而单循环链表是L->next=L。
• 头插法

//头插法创建单循环链表
void CreateList1(LinkList &L,int n)
{
	//创建长度为n的单循环链表 
	L=new LNode;
	L->next=L;
	printf("请输入链表元素值:\n");
	for(int i=n;i>0;--i)
        {
		printf("请输入第%d个元素的值:",i);
		LNode *p;
		p=new LNode;//生成新结点
		scanf("%d",&p->data);
		p->next=L->next;;
		L->next=p; 
	}
} 

• 尾插法

//尾插法创建单循环链表
void CreateList2(LinkList &L,int n)
{
	L=new LNode;
	L->next=L;
	struct LNode *r;
	r=L;
	for(int i=0;i<n;i++)
    {
		printf("请输入第%d个元素的值:",i+1);
		LNode *p;
		p=new LNode;
		scanf("%d",&p->data);
		p->next=L;
		r->next=p;
		r=p;
	}
} 

• 单循环链表的删除操作和一般单链表的操作时一样的。要注意的是单循环链表的插入操作：

//单循环链表的插入操作
int ListInsert(LinkList &L,int location,int &e)
{
    //在L的location位置插入元素e
     LNode *p;
     p=L;
     int j=0;
     while(p->next!=L&&j<location-1)
     {
       //注意：由于p初始时指向头结点，所以循环的条件是 p->next!=L，而不是 p!=L 
         p=p->next;                      
         j++;
     }
     if(p==L||j>location-1)
     {
         return 0;
     }
     LNode *s;
     s=new LNode;
     s->data=e;
     s->next=p->next;
     p->next=s;
     return 1;
} 

• 删除操作

//单循环链表的删除操作
int ListDelete(LinkList &L,int location,int &e)
{
	//删除L中location位置的元素,并用e返回其值
	 LNode *p;
	 p=L;
	 int j=0;
	 while(p->next!=L&&j<location-1)
	 {
	 	p=p->next;
	 	j++;
	 }
	 if(p==L||j>location-1)
	 {
	 	return 0;
	 }
	 
	 LNode *q;
	 q=new LNode;
	 q=p->next;
	 p->next=q->next;
	 e=q->data;
	 delete q;
	 return 1;
} 

2.代码实现

• man.cpp

#include<iostream>

using namespace std;

//存储结构 
typedef struct LNode 
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

//初始化 
int InitList(LinkList &L) 
{
	L = new LNode;
	L->next = L;       //非循环链表的初始化是头指针的指针域置空 L->next=NULL 
	
	return 1;
}

// 判断链表是否为空
int ListEmpty(LinkList L)
{
	if (L->next == L)
	{
		return 1;   // 空 
	}
	else 
	{
		return 0;  // 非空 
	}
}

// 获取链表长度
int ListLength(LinkList L) 
{
	int length = 0;
	LNode *p;
	p = L->next;
	while (p != L)
	{                  //当p不是头结点时，链表长度加1 
		p = p->next;
		length++;
	}
	
	return length;
}

// 遍历链表
void TraveList(LinkList L) 
{
	LNode *p;
	p = L->next;
	
	printf("遍历链表:\n");
	while (p != L) 
	{                             //当p不是头结点时，输出元素值 
		printf("%d ", p->data);
		p = p->next;
	}
	
	printf("\n");
}

// 头插法创建单循环链表
void CreateList1(LinkList &L, int n) 
{
	//创建长度为n的单循环链表 
	L = new LNode;
	L->next = L;
	
	printf("请输入链表元素值:\n");
	for (int i = n; i > 0; --i)
	{
		printf("请输入第%d个元素的值:", i);
		struct LNode *p;
		p = new LNode;//生成新结点
		scanf("%d", &p->data);
		p->next = L->next;;
		L->next = p;
	}
}

// 尾插法创建单循环链表
void CreateList2(LinkList &L, int n) 
{
	L = new LNode;
	L->next = L;
	struct LNode *r;
	r = L;
	
	printf("请输入链表元素值:\n");
	for (int i = 0; i < n; i++) 
	{
		printf("请输入第%d个元素的值:", i + 1);
		LNode *p;
		p = new LNode;
		scanf("%d", &p->data);
		p->next = L;
		r->next = p;
		r = p;
	}
}

//单循环链表的插入操作
int ListInsert(LinkList &L, int location, int &e) 
{
	//在L的location位置插入元素e
	LNode *p;
	p = L;
	int j = 0;
	
	while (p->next != L && j < location - 1) 
	{
		//注意：由于p初始时指向头结点，所以训话的条件是 p->next!=L 
		//而不是 p!=L 
		p = p->next;
		j++;
	}
	if (p == L || j > location - 1) 
	{
		return 0;
	}

	LNode *s;
	s = new LNode;
	s->data = e;
	s->next = p->next;
	p->next = s;
	
	return 1;
}

//单循环链表的删除操作
int ListDelete(LinkList &L, int location, int &e) 
{
	//删除L中location位置的元素,并用e返回其值
	LNode *p;
	p = L;
	int j = 0;
	
	while (p->next != L && j < location - 1) 
	{
		p = p->next;
		j++;
	}
	if (p == L || j > location - 1) 
	{
		return 0;
	}
	
	LNode *q;
	//q = new LNode;
	q = p->next;
	p->next = q->next;
	e = q->data;
	
	delete q;
	
	return 1;
}

int main() 
{
	LinkList L;

	if (InitList(L)) 
	{
		printf("初始化成功!\n");
	}
	else 
	{
		printf("初始化失败!\n");
	}

	if (ListEmpty(L)) 
	{
		printf("当前链表为空.\n");
	}
	else 
	{
		printf("链表非空.\n");
	}

	printf("请输入链表长度:");
	int n;
	scanf("%d", &n);
	CreateList2(L, n);

	if (ListEmpty(L)) 
	{
		printf("当前链表为空.\n");
	}
	else 
	{
		printf("链表非空.\n");
	}

	printf("当前链表长度是:%d\n", ListLength(L));
	TraveList(L);

	printf("请输入插入位置和值:\n");
	int location, e;
	scanf("%d,%d", &location, &e);
	if (ListInsert(L, location, e)) 
	{
		printf("插入成功\n");
	}
	else 
	{
		printf("插入失败\n");
	}
	TraveList(L);

	printf("请输入删除元素的位置:\n");
	int e1, location1;
	scanf("%d", &location1);
	if (ListDelete(L, location1, e1)) 
	{
		printf("删除成功\n");
		printf("删除的元素值为:%d\n", e1);
	}
	else 
	{
		printf("删除失败\n");
	}
	TraveList(L);

	system("pause");

	return 0;
}

• 运行结果