05、数据结构和算法 - 实战：线性表（3）

循环链表

将单链表中终端节点的指针端由空指针改为指向头节点，就使整个单链表形成一个环。头尾相接。

主要差异在于空链表的判断条件，由判断head->next是否为NULL，变成head->next是否为head。

终端结点用尾指针rear表示，开始结点为rear->next->next。

主要操作包括：初始化部分，插入部分，删除部分和返回结点所在位置。

初始化循环链表

void ds_init(node **pNode) //双重指针，指向指针的指针
{
   
     
	int item;
	node *temp;
	node *target;
	printf("输入结点的值，输入0完成初始化\n");

	while(1)
	{
   
     
		scanf("%d",&item);
		fflush(stdin);
		if(item == 0)
			return;
		if((*pNode)== NULL)
		{
   
     
			//循环链表中只有一个结点
			*pNode = (node*)malloc(sizeof (struct CLinkList));
			//分配空间失败，错误退出
			if(!(*pNode))
				exit(0);
			(*pNode)->data = item;
			(*pNode)->data = *pNode;
			//循环链表，pNode为假设的第一个结点
		}
		else
		{
   
     
			//找到next指向第一个结点的结点
			for(target = (*pNode); target->next != (*pNode); target = target->next);
			//生成新结点
			temp = (node*)malloc(sizeof(struct CLinkList));
			if(!temp)
				exit(0);
			temp->data = item;
			temp->next = *pNode;
			target->next = temp;
		}
	}
}

插入元素

//定义链表存储结构
typedef struct CLinkList
{
   
     
int data;
struct CLinkList *next;
}node;

/*插入结点，参数（链表第一个结点，插入的位置）*/
void ds_insert(node **pNode, int i)
{
   
     
	node *temp;
	node *target;
	node *p;
	int item;
	int j=1;
	printf("输入要插入结点的值：");
	scanf(%d,&item);

	if(i == 1)
	{
   
     
		//新插入的结点作为第一个结点
		temp = (node*)malloc(sizeof(struct CLinkList));

		if(!temp)
			//分配失败，错误退出
			exit(0);
		temp->data = item;
		//寻找最后一个结点
		for(target = (*pNode) ; target->next !=(*pNode); target = target->next);
		
		temp->next = (*pNode);
		target->next = temp;
		*pNode = temp;
	}
	else
	{
   
     
		target = *pNode;
		for(;j< ( i - 1); ++j)
			target = target->next;
		temp = (node *)malloc(sizeof(struct CLinkList));

		if(!temp)
			exit(0);
		temp->data = item;
		p=target->next;
		target->next = temp;
		temp->next = p;
	}
}

删除元素

/*删除结点*/
void ds_delete(node **pNode, int i)
{
   
     
	node *target;
	node *temp;
	int j = 1;

	if(i== 1)
	{
   
     
	/*删除第一个结点，找到最后一个结点*/
		for(target = (*pNode) ; target->next !=(*pNode); target = target->next);
		
		temp = *pNode;
		*pNode = (*pNode)->next;
		target->next = *pNode;
		free(temp);
	}
	else
	{
   
     
		target = *pNode;
		for(; j < i-1; ++j)
			target = target->next;
		temp = target->next;
		target->next = temp->next;
		free(temp)
	}
}

返回结点位置

int ds_search(node *pNode, int elem)
{
   
     
	node *target;
	int i = 1;
	for(target = pNode; target->data !=elem && target->next !=pNode ; ++i)
		target = target->next;
	if(target->next == pNode)
		return 0; //表中不存在该元素
	else
		return i;
}