1044-index generation.cpp

ZOJ1044 Index Generation.主要在于合理运用了qsort函数.

#include<vector>
#include<string>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct{
	string _entry;
	vector<unsigned int> _pages;
}_Entry;
typedef struct{
	string p_entry;
	vector<unsigned int> p_pages;
	vector<_Entry> s_entry;
}Entry;
Entry e[20];
string input,line,text,prim,seco;
unsigned int N;
string con(string a)
{
	string ret="";
	//for(int i=0;i<a.size();i++)
	for(size_t i=0;i<a.size();i++)
	{
		if(a[i]>='A' && a[i]<='Z')
			ret+=a[i]-'A'+'a';
		else
			ret+=a[i];
	}
	return ret;
}
int cmp(const void *a,const void *b)
{
	Entry *s=(Entry *)a,*t=(Entry *)b;
	string s1=con(s->p_entry),s2=con(t->p_entry);
	return s1.compare(s2);
}
/*
int cmp2(const void *a,const void *b)
{
	_Entry *s=(_Entry *)a,*t=(_Entry *)b;
	string s1=con(s->_entry),s2=con(t->_entry);
	return s1.compare(s2);
}
*/
/*
bool cmp2(_Entry a , _Entry b)
{
	string s1=con(a._entry),s2=con(b._entry);
	return s1.compare(s2);
}
*/
bool cmp2(const _Entry &a , const _Entry &b)
{
	string s1=con(a._entry),s2=con(b._entry);
	//return s1.compare(s2);
	return s1<s2;
}

/*
int cmp2(const _Entry *a,const _Entry *b)
{
	string s1=con(a->_entry),s2=con(b->_entry);
	return s1.compare(s2);
}
*/

int main()
{
	unsigned int page;
//	int i,j,k,p,q,cases=1;
	size_t i,j,k,p,q,cases=1;
	_Entry ee;
//	freopen("in.txt","r",stdin);
//  freopen("out.txt","w+",stdout);
	while(1)
	{
		getline(cin,line);
		if(line=="**")
			break;
		//cout<<line<<endl;
		if(line=="*")
		{
		//	cout<<input<<endl<<endl;
            page=1;
			N=0;
			for(i=0;input[i]!='\0';)
			{
				if(input[i]=='{')
				{
					text="";
					prim="";
					seco="";
					//过滤'{'的空格串
					for( i++ ; input[i]==' ' ; )
						i++;
					j=i;
					for( ; input[i]!='%' && input[i]!='$' && input[i]!='}' ; )
						i++;
					if(input[i]=='%' || input[i]=='$')
					{
						//过滤'%'或者'$'前的空格串
						for( p=i-1 ; input[p]==' ' ; )
							p--;
						for( k=j; k<=p ; k++ )
						{
							if(input[k]!='\n')
								text+=input[k];
						}
						if(input[i]=='%')
						{
							//继续
							//过滤'%'后的空格
							for( i++ ; input[i]==' '; )
								i++;
							j=i;
							for( ; input[i]!='$' && input[i]!='}' ; )
								i++;
							//过滤'$'或'}'前的空格
							for( p=i-1 ; input[p]==' ' ; )
								p--;
							for( k=j; k<=p ; k++ )
							{
								if(input[k]!='\n')
									prim+=input[k];
							}
							//
							if(input[i]=='$')
							{
								//过滤'$'后的空格
								for( i++ ; input[i]==' '; )
									i++;
								j=i;
								for( ; input[i]!='}' ;)
									i++;
								//过滤'}'前的空格
								for( p=i-1 ; input[p]==' ' ; )
									p--;
								for( k=j ; k<=p ; k++)
									if(input[k]!='\n')
										seco+=input[k];
							}
						}
						else
						{
							prim=text;
							//过滤'$'后的空格
							for( i++ ; input[i]==' '; )
								i++;
							j=i;
							for( ; input[i]!='}' ;)
								i++;
							//过滤'}'前的空格
							for( p=i-1 ; input[p]==' ' ; )
								p--;
							for( k=j ; k<=p ; k++)
								if(input[k]!='\n')
									seco+=input[k];						
						}

					}
					else if(input[i]=='}')
					{
						prim="";
						seco="";
						//过滤'}'前的空格
						for( p=i-1 ; input[p]==' ' ; )
							p--;
						for( k=j ; k<=p ; k++)
							if(input[k]!='\n')
								prim+=input[k];	
					}
				//  cout<<"text="<<text<<endl;
				//	cout<<"prim="<<prim<<endl;
				//	cout<<"seco="<<seco<<endl;
				//	cout<<"page="<<page<<endl;
				//	cout<<endl;
					/////////////////已经获得prim,seco,开始处理/////////////////
					for( q=0 ; q<N ;q++ )
					{
						if(e[q].p_entry == prim)
							break;
					}
					//主项已存在
					if(q<N)
					{
						//cout<<"The prim term has exsited"<<endl;
						//副项为空
						if(seco=="")
						{
							//试图把主项的页码加入
							j=e[q].p_pages.size()-1;
							if(e[q].p_pages[j]!=page)
								e[q].p_pages.push_back(page);
						}
						//副项不为空
						else
						{
							//看副项是否存在
							for(j=0;j<e[q].s_entry.size();j++)
							{
								if(seco==e[q].s_entry[j]._entry)
									break;
							}
							//副项存在
							if(j<e[q].s_entry.size())
							{
								k=e[q].s_entry[j]._pages.size()-1;
								if(page!=e[q].s_entry[j]._pages[k])
									e[q].s_entry[j]._pages.push_back(page);
							}
							//副项不存在
							else
							{
								ee._entry=seco;
								ee._pages.clear();
								ee._pages.push_back(page);
								e[q].s_entry.push_back(ee);
							}
						}
					}
					//主项不存在
					else
					{
						//cout<<"The prim term has not exsited"<<endl;
						e[N].p_entry=prim;
						//如果副项为空
						if(seco=="")
							e[N].p_pages.push_back(page);
						else
						{
						//	cout<<"The secondary term has exsited"<<endl;
							ee._entry=seco;
							ee._pages.clear();
							ee._pages.push_back(page);
							e[N].s_entry.push_back(ee);							
						}
						N++;
					}

				}
				else
				{
					if(input[i]=='&')
						page++;
					i++;
				}
			}
			//输出
			cout<<"DOCUMENT "<<cases<<endl;
			cases++;
		    //cout<<"排序开始"<<endl;
			qsort(e,N,sizeof(Entry),cmp);
			for(i=0;i<N;i++)
			//	qsort(e[i].s_entry.begin(),e[i].s_entry.size(),sizeof(_Entry),cmp2);
			    sort(e[i].s_entry.begin(),e[i].s_entry.end(),cmp2);
			//cout<<"排序结束"<<endl;
			for(i=0;i<N;i++)
			{
				cout<<e[i].p_entry;
				if(e[i].p_pages.empty())
					cout<<endl;
				else
				{
					for(j=0;j<e[i].p_pages.size();j++)
						cout<<", "<<e[i].p_pages[j];
					cout<<endl;
				}
				//
				e[i].p_pages.clear();
				if(!e[i].s_entry.empty())
				{
					for(j=0;j<e[i].s_entry.size();j++)
					{
						cout<<"+ "<<e[i].s_entry[j]._entry;
						for(k=0;k<e[i].s_entry[j]._pages.size();k++)
							cout<<", "<<e[i].s_entry[j]._pages[k];
						cout<<endl;
					}
				}
				e[i].s_entry.clear();
			}
			input="";
		}
		else
		{
			line+='\n';
			input+=line;
		}
	}
	return 0;
}