main.cpp

我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:递归,分治,动态规划,回溯法,AO算法等,除此之外还用到比较多的数学知识,我做了一部分,还有一些暂时还没做出来,大家也帮

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

  72. (NOI'95.1_2)　在一个园形操场的四周摆放 N 堆石子(N≤100)， 现要将石子
有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆
的石子数，记为该次合并的得分。
　　编一程序，由文件读入堆数 N 及每堆的石子数(≤20)，
　　① 选择一种合并石子的方案, 使得做N-1次合并, 得分的总和最小;
    ② 选择一种合并石子的方案, 使得做N-1次合并, 得分的总和最大.
    例如, 图 2-1 所示的4堆石子,每堆的石子数(从最上面的一堆数起, 顺时针数)
依次为4  5  9  4. 则 3 次合并得分总和最小的方案为图2-2,得分总和最大的方案
为图 2-3.
    (加图)
　　输入数据:
    文件名由键盘输入，该文件内容为;
    第一行为石子堆数 N;
    第二行为每堆的石子数, 每两个数之间用一个空格符分隔
    输出数据:
    输出文件名为 OUTPUT.TXT
　　第 1 至 N-1 行为得分最小的合并过程. 每行包含两个数, 表示应该合并的两
 堆石子的数目, 小数在前, 大数在后, 第 N 行为合并成一堆后的最小得分总和;
 第 N+1 行为空行, 第 N+2 至 2N+1 行为得分最大合并过程(格式同前). 第 2N+2
 行为最大得分总和.

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


#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(FILE *fp, int n)
{
	int i;
	int data;
	TreeNode *tempTreeNode;
	LinkNode *tempLinkNode;

	for(i=0; i<n; i++)
	{
		fscanf(fp,"%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;
			tail->pNext = head;//尾节点指向头节点
		}
		else 
		{
			tail->pNext = tempLinkNode;
			tail = tail->pNext;
			tail->pNext = head;//尾节点指向头节点
		}
	}
}

//插入元素
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)
	{
		if(head == tail)
		{
			head = tail = NULL;
		}
		else
		{
			head = head->pNext;
			tail->pNext = head;
		}
		free(pLinkNode);
	}
	else 
	{
		p = tail;
		q = head;
		while(q != tail)
		{
			if(q == pLinkNode)
			{
				p->pNext = q->pNext;
				free(pLinkNode);
				break;
			}
			p = q;
			q = q->pNext;
		}
		if(q == tail)
		{
			tail = p;
			p->pNext = q->pNext;
			free(pLinkNode);
		}
	}
}

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

	while(head != tail)
	{
		p = tail;
		q = head;
		min = p;
		min_sum = min->pTreeNode->data + min->pNext->pTreeNode->data;
		do
		{		
			if(q->pTreeNode->data + p->pTreeNode->data < 
				min_sum)
			{
				min = p;
				min_sum = min->pTreeNode->data + min->pNext->pTreeNode->data;
			}
			p = q;
			q = q->pNext;
		}while(q != head);
		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;
}

int CalcMax()
{
	int sum = 0;
	int max_sum;
	LinkNode *p,*q,*max,*pnew;

	while(head != tail)
	{
		p = tail;
		q = head;
		max = p;
		max_sum = max->pTreeNode->data + max->pNext->pTreeNode->data;
		do
		{		
			if(q->pTreeNode->data + p->pTreeNode->data > 
				max_sum)
			{
				max = p;
				max_sum = max->pTreeNode->data + max->pNext->pTreeNode->data;
			}
			p = q;
			q = q->pNext;
		}while(q != head);
		sum += max_sum;
		pnew = InsertAfter(max->pNext,max_sum);
		pnew->pTreeNode->left = max->pTreeNode;
		pnew->pTreeNode->right = max->pNext->pTreeNode;
		DeleteLinkNode(max->pNext);
		DeleteLinkNode(max);
	}
	root = head->pTreeNode;
	DeleteLinkNode(head);

	return sum;
}

//打印结果


void main()
{
	int n;
	FILE *fp,*fpw;
	int rs;

	fp = fopen("input.txt","r");
	if(!fp)
	{
		printf("fail to open the file input.txt!\n");
		return;
	}
	fscanf(fp,"%d",&n);
	printf("石子堆数N: %d\n", n);
	
//	fpw = fopen("output.txt","w");
	CreateLink(fp,n);
	rs = CalcMin();
	printf("min = %d\n",rs);

	fseek(fp,0,SEEK_SET);
	fscanf(fp,"%d",&n);
	CreateLink(fp,n);
	rs = CalcMax();
	printf("max = %d\n",rs);

	fclose(fp);

}