赵天泽

用户名：uq_99534628713

访问量：2964

签　名：

全体目光向我看齐，我宣布个事，我是个傻⚪

等　　级
排　　名	6822
经　　验	1375
参赛次数	2
文章发表	9
年　　龄	0
在职情况	学生
学　　校	sumhs
专　　业	大数据

　　自我简介：

已退站

TA的其他文章

蓝桥杯基础练习VIP-阶乘计算(C语言）
浏览：153

C语言解阶乘新问题，简单易理解，同时分享其他失败的思路
浏览：204

简单易懂的C语言动态规划算法（以及分享一下失败的递归算法）
浏览：455

你可能喜欢

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

链表解法，但会运行错误

　　作者: 赵天泽　　　　发表时间：2022-04-29 01:37:12 浏览：421　|　评论：0　

原题链接：蓝桥杯算法提高-能量项链

之前发表过一次动态规划算法，当时表示有时间会写一下链表做法，结果写了两天。思路很简单，但有很多细节的地方容易出错
不知道为什么会运行错误，在自己的运行环境下是没有问题的。
答案与动态规划做法多次比较，没有错误。
```c
#include<stdio.h>
#include<stdlib.h>
typedef struct list {
	int data1;//头标记
	int data2;//尾标记
	struct list *next;
}node;
int count;//表示现存的结点数

void insert(node* head, int data);//插入函数，将新结点插入到最后一位，并与头节点相连，形成循环
node* find_min(node* head);//查找最小的结点位置的前一位
node* delete_next(node* head, node* minnode);//将该结点的下一位删除，搭配find_min使用，可以删除最小的结点
void PrintList(node* head);//遍历并打印，与题目无关，用来观察运算过程
void create_neck(node* head,int* a, int n);//链表初始化

int main()
{
	int n,i, sum = 0;
	int a[100];
	node* head;
	head = (node*)malloc(sizeof(node));//头节点初始化
	head->next = head;//形成循环链表
	scanf("%d", &n);
	count = n;//n为最开始的结点数，不会再变，count表示现存结点数，会变化
	getchar();
	for (i = 0; i < n ; i++)
	{
		scanf("%d", &a[i]);
	}
	head->data1 = a[0];
	create_neck(head, a, n);
	node* minnode;
	for (i = 0; i < n-1; i++)
	{
		minnode = find_min(head);
//		printf("%d+%d*%d*%d=%d\n", sum, minnode->data1, minnode->data2, minnode->next->data2, sum + minnode->data1 * minnode->data2 * minnode->next->data2);
		sum = sum + minnode->data1 * minnode->data2 * minnode->next->data2;
		head=delete_next(head, minnode);
//		PrintList(head);
	}
	printf("%d", sum);
	return 0;
}

void insert(node* head, int data)
{
	node* newnode;
	newnode = (node*)malloc(sizeof(node));
	if(newnode!=NULL)
	newnode->data1 =data;
	node* temp = head;
	while(temp->next!=head)//用来找到最后的结点
	{
		temp = temp->next;
	}
	newnode->next =head;
	temp->next = newnode;
}

node* find_min(node* head)
{
	int i = 0;
	int min = 100, min_n;
	node* temp=head;
	node* minnode=NULL;
	for(i=0;i<count;i++)
	{
		if (temp->data2 < min)
		{
			minnode = temp;
			min = temp->data2;
		}
		else if (temp->data2 == min)//在过程中出现两个头标记相同的结点时，如果这两个结点不相连，则不影响结果；若相连，有可能影响结果，需要加一步判断。考虑过使用递归，将两个结点分别传递到下一级函数，算出最终结果后再比较，但觉得效率有点低，有点杀鸡用牛刀了，便作罢
		{
			if (temp->data1 * temp->data2 * temp->next->data2 > minnode->data1 * minnode->data2 * minnode->next->data2)//当两个结点的头标记相同时，若相连，可以选择出能量较大的消去方式，若不相连，则无影响
			{
				minnode = temp;
				min = temp->data2;
			}
		}
		temp = temp->next;
	}
	return minnode;
}

node* delete_next(node* head, node* minnode)
{
	node* freenode;
	freenode = minnode->next;
	minnode->next = freenode->next;
	minnode->data2 = freenode->data2;
	count--;//现存结点数减一
	if (freenode==head)//如果消除的点是头节点，需要让第二个结点成为头节点
		head = head->next;
	free(freenode);
	return head;
}

void PrintList(node* head)
{
	node* temp=head;
	for (int i = 0; i < count; i++)
	{
		printf("%d ",temp->data1);
		temp = temp->next;
	}
	printf("\n");
}

void create_neck(node* head,int* a, int n)
{
	node* temp=head;
	for (int i = 1; i < n; i++)
	{
		insert(head, a[i]);
	}
	for (int i = 0; i < n; i++)
	{
		temp->data2 = temp->next->data1;//为尾标记赋值
		temp = temp->next;
	}
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

求最大公约数-模板题

C二级辅导-同因查找（C语言代码）

链表解法，但会运行错误

评论区

精彩推荐

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-分段函数（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

数组输出（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

赵天泽

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C++代码）

求最大公约数-模板题

C二级辅导-同因查找 （C语言代码）

链表解法，但会运行错误

评论区

精彩推荐

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

数组输出 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

哥德巴赫曾猜测 （C语言代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （Java代码）

C二级辅导-同因查找（C语言代码）

　　评论区

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C二级辅导-分段函数（C语言代码）

数组输出（C语言代码）

哥德巴赫曾猜测（C语言代码）

C语言考试练习题_排列（C语言代码）