蓝桥杯2014年第五届真题-分糖果 （C语言代码）循环链表求解 过程有点繁琐 思路不难

作了个大死...想用循环链表的方式求解，写了挺久的。。

就当复习一下链表的操作吧！代码量有点长

参考代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node
{
	int num; 			//糖果数量
	struct Node* pNext;
	
}NODE, *PNODE;

//创建一个长度为N的循环链表
PNODE creat_list(int N)
{
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	if (pHead == NULL)
	{
		perror("malloc error!");
		return NULL;
	}
	//pHead->num   = -1; //头结点不存放有效数据
	pHead->pNext = NULL;
	
	PNODE pTail = pHead;
	PNODE pNew  = NULL;
	
	int i;
	for (i = 0; i < N; i++)
	{
		pNew = (PNODE)malloc(sizeof(NODE));
		if (pNew == NULL)
		{
			perror("malloc error!");
			return NULL;
		}
		scanf("%d", &(pNew->num));
		pNew->pNext = NULL;
		
		pTail->pNext = pNew;
		pNew->pNext  = NULL;
		
		pTail = pNew;
	}
	pTail->pNext = pHead->pNext; //尾结点指向首结点，形成循环链表
	
	return pHead;
}

//遍历链表
void traverse_list(PNODE pHead)
{
	PNODE pFir = pHead->pNext;
	
	PNODE pTmp = pHead->pNext;
	while (pTmp->pNext != pFir)
	{
		printf("%d->", pTmp->num);
		pTmp = pTmp->pNext;
	}
	printf("%d\n", pTmp->num);
}

//判断链表结点的num是否全相等，相等返回1，不全相等返回-1
int allequal(PNODE pHead, int N)
{
	PNODE pCur = pHead->pNext;
	int val = pCur->num;
	
	int i;
	for (i = 1; i < N; i++)
	{
		pCur = pCur->pNext;
		
		if (pCur->num != val)
			return -1;
	}
	
	return 1;
}

//关键步骤，注意用临时变量存放结点中num的初值
void process(PNODE pHead, int N)
{
	PNODE pFir = pHead->pNext;
	
	PNODE pCur = pHead->pNext;
	int tmp1, tmp2;
	tmp1 = pCur->num;
	int i;
	for (i = 1; i < N; i++)
	{
		pCur = pCur->pNext;
		tmp2 = pCur->num;
		pCur->num = (tmp2 / 2) + (tmp1 / 2);
		tmp1 = tmp2;
	}
	
	pFir->num = (pFir->num / 2) + (tmp2 / 2); //首结点的值也要修改
}

//给不是偶数结点的增加一个糖果，返回增加的数量
int feedcandy(PNODE pHead, int N)
{
	PNODE pCur = pHead->pNext;
	
	int candynum = 0;
	int i;
	for (i = 0; i < N; i++)
	{
		if (pCur->num % 2 != 0) 
		{
			pCur->num += 1;
			candynum++;
		}
		pCur = pCur->pNext;
	}
	
	return candynum;
}

int main(void)
{
	int N;
	scanf("%d", &N);
	
	PNODE pHead = creat_list(N);
	//traverse_list(pHead);
	//int tmp = allequal(pHead, N);
	//printf("%d... \n", tmp);
	
	//process(pHead, N);
	//traverse_list(pHead);
	
	//feedcandy(pHead, N);
	//traverse_list(pHead);

	int candysum = 0;
	int candynumper = 0;	
	
	while (allequal(pHead, N) == -1) //不全相等时继续循环
	{
		process(pHead, N);
		candynumper = feedcandy(pHead, N);
		//printf("%d\n", candynumper);
		candysum += candynumper;
	}
	printf("%d\n", candysum);
	
	return 0;
}

有什么疑问可以留言~