main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 184 行

/**************************************************************************************

  45. (数列的最小代价) 给定一个正整数序列，例如：4,1,2,3, 不改变数的位置把
 它们相加， 并且由括号来标记每一次加法所得到的和。例如：((4+1)+(2+3))=
 ((5)+(5))=10. 除去原数4、1、2、3之外，其余都为中间结果，如：5,5,10, 将中
 间结果相加，得到：5+5+10=20, 数 20 称为此数列的一个代价。对于另一种算法:
 (4+((1+2)+3))=(4+((3+3))=(4+(6))=10, 得到数列的另一个代价为：3+6+10=19.
 若给出 N 个数的数列，求出此数列的最小代价。

  贪心算法求解

  *************************************************************************************/

#include <stdio.h>
#include <malloc.h>

typedef struct tagTreeNode
{
	int data;
	tagTreeNode *left;
	tagTreeNode *right;
} TreeNode;

typedef struct tagLinkNode
{
	TreeNode *pTreeNode;
	tagLinkNode *pNext;
} LinkNode;

LinkNode *head = NULL;
LinkNode *tail = NULL;
TreeNode *root = NULL;

//创建一个链表,保存数列
void CreateLink(int n)
{
	int i;
	int data;
	TreeNode *tempTreeNode;
	LinkNode *tempLinkNode;

	for(i=0; i<n; i++)
	{
		scanf("%d",&data);
		tempTreeNode = (TreeNode*)malloc(sizeof(TreeNode));
		tempTreeNode->data = data;
		tempTreeNode->left = NULL;
		tempTreeNode->right = NULL;
		tempLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
		tempLinkNode->pTreeNode = tempTreeNode;
		tempLinkNode->pNext = NULL;
		if(!head)
			head = tail = tempLinkNode;
		else 
		{
			tail->pNext = tempLinkNode;
			tail = tail->pNext;
		}
	}
}

//插入元素
LinkNode* InsertAfter(LinkNode *pLinkNode,int data)
{
	TreeNode *tempTreeNode;
	LinkNode *tempLinkNode = NULL;

	if(pLinkNode)
	{
		tempTreeNode = (TreeNode*)malloc(sizeof(TreeNode));
		tempTreeNode->data = data;
		tempTreeNode->left = NULL;
		tempTreeNode->right = NULL;
		tempLinkNode = (LinkNode*)malloc(sizeof(LinkNode));
		tempLinkNode->pTreeNode = tempTreeNode;
		tempLinkNode->pNext = NULL;
		
		tempLinkNode->pNext = pLinkNode->pNext;
		pLinkNode->pNext = tempLinkNode;
		if(pLinkNode == tail)
			tail = tempLinkNode;
	}

	return tempLinkNode;
}

//删除元素
void DeleteLinkNode(LinkNode *pLinkNode)
{
	LinkNode *p,*q;
	if(pLinkNode == head)
	{
		head = head->pNext;
		if(head == NULL)
			tail = NULL;
		free(pLinkNode);
	}
	else 
	{
		p = NULL;
		q = head;
		while(q)
		{
			p = q;
			q = q->pNext;
			if(q == pLinkNode)
			{
				p->pNext = q->pNext;
				free(pLinkNode);
				break;
			}
		}
	}
}

//计算
int Calc()
{
	int sum = 0;
	int min_sum;
	LinkNode *p,*q,*min,*pnew;

	while(head != tail)
	{
		p = NULL;
		q = head;
		min = q;
		min_sum = min->pTreeNode->data + min->pNext->pTreeNode->data;
		while(q)
		{
			p = q;
			q = q->pNext;
			
			if(q)
			{
				if(q->pTreeNode->data + p->pTreeNode->data < 
					min_sum)
				{
					min = p;
					min_sum = min->pTreeNode->data + min->pNext->pTreeNode->data;
				}
			}
		}
		sum += min_sum;
		pnew = InsertAfter(min->pNext,min_sum);
		pnew->pTreeNode->left = min->pTreeNode;
		pnew->pTreeNode->right = min->pNext->pTreeNode;
		DeleteLinkNode(min->pNext);
		DeleteLinkNode(min);
	}
	root = head->pTreeNode;
	DeleteLinkNode(head);
	
	return sum;
}

//打印结果
void PrintTree(TreeNode *ptree)
{
	if((!ptree->left) && (!ptree->right))
	{
		printf("%d",ptree->data);
	}
	else
	{
		printf("(");
		PrintTree(ptree->left);
		printf("+");
		PrintTree(ptree->right);
		printf(")");
	}
}

void main()
{
	int n,sum;

	printf("请输入数列元素的个数N: ");
	scanf("%d",&n);
	CreateLink(n);
	sum = Calc();
	printf("min = %d \n", sum);
	PrintTree(root);
}