05、数据结构与算法实战:线性表(3-循环链表)

学习笔记:数据结构与算法(五):线性表(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;
}

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: