数据结构学习笔记2——链表练习

数据结构学习笔记2——链表练习

链表数据结构定义：

typedef struct student
{//以学生信息作为链表节点
	int num;
	float score;
	struct student* pnext;
}*pstu, stu;

• 链表逆置
  链表逆置思路：1原地逆转，2定义一个新链表，将旧链表以头插法放入新链表
  法2思路图：
  

链表逆置函数实现如下：

pstu list_reverse(pstu phead)
{//法1原地逆转
	pstu ptemp, ppre;
	ppre = NULL;
	ptemp = phead;
	if (NULL == phead)
	{
		printf("Link list is empty\n");
	}
	else
	{
		while (phead)
		{
			ptemp = ptemp->pnext;//指向下一个要剪切的链表节点。链表循环连接操作
			phead->pnext = ppre;//链表头节点指向ppre。
			ppre = phead;//头节点的值赋给ppre，头插
			phead = ptemp;//phead指向下一个要剪切的头节点。
		}
	}
	return ppre;
	
}
pstu list_reverse2(pstu phead)
{//法2
	pstu ptemp = (pstu)calloc(1, sizeof(stu));
	pstu pcur,pnew;
	pcur = phead;
	if (NULL == phead)
	{
		printf("Link list is empty\n");
	}
	while (pcur&&pcur->pnext)
	{
		pnew = (pstu)calloc(1, sizeof(stu));
		ptemp->num = pcur->num;//ptemp作为新链表的尾节点
		pcur = pcur->pnext;
		pnew->num = pcur->num;//pnew从旧链表取值
		pnew->pnext = ptemp;//pnew头插ptemp
		ptemp = pnew;
	}
	return ptemp;
}

链表逆置的使用主函数如下：

int main()
{
	pstu phead, ptail;
	pstu pnow = (pstu)calloc(1, sizeof(stu));
	phead = NULL;
	ptail = NULL;
	phead = list_sort_insert(phead, ptail);//参见上一篇文章链表的增删查改
	list_print(phead);
	pnow = list_reverse2(phead);
	list_print(pnow);
	return 0;
}

• 链表的合并
  思路：将两个链表放入一个新的链表当中
  链表合并函数实现如下：

pstu mergelist(pstu phead1, pstu phead2)
{
	pstu pcur = NULL, ppre = NULL, head = NULL;
	if (NULL==phead1)
	{
		return (head = phead2);
	}
	else if(NULL==phead2)
	{
		return (head = phead1);
	}
	head = phead1->num < phead2->num ? phead1 : phead2;
	ppre = head;
	while (phead1!=NULL&&phead2!=NULL)
	{//将链表1和链表2都合并到链表3
		if (phead1->num < phead2->num)
		{
			pcur = phead1;//学号101赋给pcur
			phead1 = phead1->pNext;//phead1指向学号103
			ppre->pNext = pcur;//ppre为链表3
			ppre = pcur;//尾插链表3
			pcur->pNext = NULL;//清空链表3尾部
		}
		else
		{
			pcur = phead2;
			phead2 = phead2->pNext;
			ppre->pNext = pcur;
			ppre = pcur;
			pcur->pNext = NULL;
		}	
	}
	if (NULL == phead1)
	{//遍历完链表1
		ppre->pNext = phead2;
		return head;
	}
	else if (NULL == phead2)
	{//遍历完链表2
		ppre->pNext = phead1;
		return head;
	}
}

• 链表是否相交
  思路：分别求出链表1和2的长度，让较长的链表先走（假如长度相差1，则较长的链表先走1步），之后再链表1链表2一同走。注意：链表相交最后一个节点必然相同。
  

判断链表相交函数实现如下：

void list_cross(pstu phead1, pstu phead2)
{
	pstu pcur1, pcur2, ptemp;
	pcur1 = phead1;
	pcur2 = phead2;
	int len1, len2;
	len1 = len2 = 0;
	if (NULL == phead1 || NULL == phead2)
	{
		printf("条件不足，链表不相交\n");
	}
	//分别计算两个链表的长度
	for (; pcur1->pnext!=NULL; pcur1 = pcur1->pnext)
	{//遍历链表1
		len1++;
	}
	for ( ;pcur2->pnext!=NULL ; pcur2=pcur2->pnext)
	{//遍历链表2
		len2++;
	}
	int diff;
	diff = abs(len1 - len2);
	if (pcur1->num != pcur2->num)
	{//最后一个节点不相同
		printf("链表不相交\n");
	}else if (len1 < len2)
	{
		pcur1 = phead1;//较短的链表赋给pcur1
		ptemp = phead2;//较长的链表赋给ptemp
	}
	else if (len1 > len2)
	{
		pcur1 = phead2;
		ptemp = phead1;
	}
	for (int i = 0; i < diff; i++)
	{//ptemp先走，让ptemp和pcur1平齐
		ptemp = ptemp->pnext;
	}
	while (pcur1!=ptemp)
	{
		pcur1 = pcur1->pnext;
		ptemp = ptemp->pnext;
	}
	if (!pcur1 && !ptemp)
	{//如果链表1和链表2都走到尾部代表链表相交。
		printf("链表相交\n");
	}
}

• 链表是否有环
  
  思路：让刘备(pcur)先走两步，关羽（ppre）走一步，刘备每走两步，关羽走一步，当最终刘备撞上关羽时，链表有环
  判断链表是否有环函数实现如下：

bool circle(pstu phead)
{
	pstu pcur,ppre;
	pcur = phead;
	ppre = pcur;
	while (pcur)
	{
		pcur = pcur->pnext->pnext;//刘备走两步
		ppre = ppre->pnext;//关羽走一步
		if (pcur == ppre)
		{//刘备撞见关羽
			printf("链表有环\n");
			return true;
		}
		else if(!pcur||!pcur->pnext)
		{
			printf("链表无环\n");
			return false;
		}
		
	}
}
//主函数如下
int main()
{
	pstu phead, ptail;
	pstu pcur;
	phead = NULL;
	ptail = NULL;
	list_tail_insert(&phead, &ptail);
	list_print(phead);
	//链表建环
	ptail->pnext = phead->pnext->pnext;
	circle(phead);
	return 0;
}

• 删除单链表中的重复数
  思路：遍历链表，刘备(pcur)走两步，关羽(ppre)走一步，刘备拿到的锦囊(pcur->num)和关羽拿到的锦囊(pcur->num)一样时，则丢弃一个锦囊（断链）。
  删除单链表中重复数的函数实现如下：

pstu list_delete_repeat(pstu phead)
{//利用刘备pcur和关羽ppre遍历链表，当找到相同的武器num时，则删除
	pstu ppre, pcur;
	pcur = phead;
	ppre = pcur;
	if (NULL==phead)
	{
		printf("Link List is empty\n");
	}
	else
	{
		while (pcur)
		{
			pcur = pcur->pnext;
			if (NULL == pcur)
			{
				break;
			}else if (pcur->num == ppre->num)
			{
				ppre->pnext = pcur->pnext;//断链
				pcur = pcur->pnext;
			}
			ppre = pcur;
		}
		pcur = NULL;
	}
	return phead;
}

• 寻找链表节点
  1寻找链表倒数第4个节点
  函数实现如下：

void find_node4(pstu phead)
{
	//找出链表的倒数第四个节点
	//思路：刘备pcur先走4步，此后刘备每走1步，关羽ppre也走1步,刘备走到终点，则关羽就是倒四个节点。
	pstu ppre, pcur;
	pcur = phead;
	ppre = phead;
	int cnt = 0;
	while (pcur&&pcur->pnext)
	{
		while (cnt < 3)
		{
			pcur = pcur->pnext;
			cnt++;
		}
		ppre = ppre->pnext;
		pcur = pcur->pnext;
	}
	printf("倒数第四个节点是%d\n", ppre->num);
	//return ppre;//需要倒数第四个节点的指针则使用本句
}

2寻找链表的中间节点
函数实现如下：

void find_mid(pstu phead)
{
	//(2)找出链表的中间节点
	//思路：刘备pcur每走2步，关羽ppre走1步，当刘备走到终点，关羽正好在中间节点。
	int cnt = 0;
	pstu pcur, ppre;
	pcur = phead;
	ppre = pcur;
	if (NULL == phead)
	{
		printf("Link list is empty\n");
	}
	while (pcur&&pcur->pnext)
	{
		while (cnt < 2)
		{
			pcur = pcur->pnext;
			cnt++;
		}
		ppre = ppre->pnext;
		cnt = 0;
	}
	printf("中间节点是：%d", ppre->num);
	//return ppre;//需要中间节点的地址则使用本句
}

• 拆分一个链表,将链表中的奇数构成链表1，偶数构成链表2
  
  链表拆分后：pcur1则为1-3-5-7，pcur2则为2-4-6-8
  链表拆分函数实现如下：

void list_detach(pstu phead)
{
	pstu ppre1, pcur1, ppre2, pcur2;//ppre1和ppre2作为分身用于遍历链表
	//pcur1,pcur2作为返回值用于打印
	pcur1 = phead, ppre1 = pcur1;
	pcur2 = phead->pnext, ppre2 = pcur2;
	while (ppre1&&ppre2)
	{
		pstu ptemp;
		ppre1->pnext = ppre2->pnext;//1->3，和2断链
		ppre1 = ppre1->pnext;//1->3
		ptemp = ppre2->pnext;//ptemp作为小兵先走向3
		if (!ptemp)
		{//小兵指向NULL时
			ppre2->pnext = NULL;
			break;
		}
		else
		{//小兵指向数值时
			ppre2->pnext = ptemp->pnext;
			ppre2 = ppre2->pnext;
		}
	}
	list_print(pcur1);
	list_print(pcur2);
}
//主函数
int main()
{
	pstu phead, ptail;
	phead = NULL;
	ptail = NULL;
	phead=list_sort_insert(phead, ptail);
	list_print(phead);
	list_detach(phead);
	return 0;
}