neatprint.cpp

漂亮打印

// NeatPrint.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <string>
#include <stdio.h>

using namespace std;
#define MAXLINE = 500;

int neatPrint(FILE* fout, string *str, int lineLen);
int extraSpace(int *, int, int, int, int);
int _tmain(int argc, _TCHAR* argv[])
{
	FILE *fout = fopen("test.txt","wt");
	if(!fout)
	{
		exit (1);
	}
	string source = "Historically, Jeep's reputation as a go-anywhere vehicle dates back to the Second World War when the original Jeeps, \
supplied by the Willys company, carried Allied forces through the Pacific and Europe. \
The Macquarie Dictionary of Motoring says the mane Jeep stemmed from the United States Army's \
decision to call the vehicle GP, for General Purpose vehicle. The name was eventually corrupted to \
'jeep,' from the pronunciation of the letters GP, and became a trademark owned by the Willy company. \
Jeep became part of Chrysler in 1988 and the company has since spent a lot of money to revitalize \
the Jeep production facilities, and to increase the number and style of models available. \
Chrysler says the Jeep's wartime reputation and rugged image undoubtedly helped it to carve out a new role in \
peacetime as a recreational vehicle. It says the Jeep created the original market for recreational, \
off-road vehicles using the powerful four-wheel drive traction (known commercially as 4 WD) \
for which the army jeep was famous.";
	

	neatPrint(fout, &source, 50);
	
	fclose(fout);
	return 0;
}

int neatPrint(FILE* fout, string *str, int lineLen)
{
	int strLen = (int)str->length();
	int wordNo = 0;
	const char* space = " ";
	int spaceFind = (int)str->find(space);
	//单词总数
	while(spaceFind != string::npos)
	{
		wordNo++;
		spaceFind = (int)str->find(space, spaceFind+1);
	}
	wordNo++;
	//每个单词的长度
	int* lenArray = new int[wordNo];
	int* wordPos = new int[wordNo];
	wordPos[0] = 0;
	int lastSpace = 0;
	int indexWord = 0;
	spaceFind = 0;
	while(true)
	{
		spaceFind = (int)str->find(space, spaceFind+1);
		if(spaceFind != string::npos)
		{
			lenArray[indexWord++]=spaceFind-lastSpace;
			lastSpace = spaceFind+1;
		}
		else
			break;
		wordPos[indexWord] = lastSpace;
	}
	lenArray[indexWord]=strLen - lastSpace;
	
	//打印从0到i个个单词所需要的最少的空格数立方和
	int* cost = new int[wordNo];
	int* trace = new int[wordNo];
	//memset(cost, -1, wordNo * sizeof(int)/sizeof(char));
	for(int i = 0; i<wordNo; i++)
	{
		if(i == wordNo-1)
		{
			int x = 0;
		}
		if(i==0)
			cost[i] = extraSpace(lenArray, i, i, lineLen, wordNo);
		else
			cost[i] = cost[i-1]+ extraSpace(lenArray, i, i, lineLen, wordNo);
		int j = i-1;
		//i所在的行打印的第一个单词的索引
		trace[i] = i;
		int ls = extraSpace(lenArray, j,i, lineLen, wordNo);
		while (ls>=0)
		{
			if(cost[i]>cost[j]+ls)
			{
				cost[i]=cost[j]+ls;
				trace[i] = j;
			}
			ls = extraSpace(lenArray, --j,i, lineLen, wordNo);
		}
	}
	string strOut = "";
	int pivot = trace[wordNo - 1];
	int lastPivot = strLen;
	while(true)
	{
		//if(pivot == trace[wordNo - 1])//如果是最后一行
		strOut = str->substr(wordPos[pivot],lastPivot-wordPos[pivot])+strOut;
		lastPivot = wordPos[pivot]-1;
		if (pivot!=0)
			strOut = "\n"+strOut;
		else
			break;
		pivot = trace[pivot -1 ];
	}
	fwrite(strOut.c_str(), sizeof(char), strOut.length(), fout);
	delete [] lenArray;
	delete [] cost;
	delete [] wordPos;
	delete [] trace;

	return 0;
}

int extraSpace(int *l, int i, int j, int len, int wordNo)
{
	if(i<0||j<i)return -1;
	int v = len;
	int p = i;
	while (p<=j)
	{
		v -= (*(l+p));
		if(p!=j)
			v--;
		p++;
	}
	if (v<0) return -1;
	if (j == wordNo-1)
		return 0;
	return v*v*v;
}