pat1022Digital Library (30)

NO IMAGE

題意分析:

(1)給出若干條書籍資訊:按照書名、作者、關鍵字、出版商、出版年份的格式列出;再給出若干條檢索記錄,這些檢索記錄是圍繞書名、作者、關鍵字、出版社以及年份,來按順序列出查詢的書的ID,考察的是排序和查詢。

(2)將書的資訊包裝成結構體,在這些結構體當中,比較容易檢索的包括書名、作者、出版社、出版年份;而對於關鍵字來說,由於每本書最多會有5個關鍵字,書的數目比較大時,如果將關鍵字向量或陣列維護在結構體當中,每次都分別檢索,檢索的效率就可又能降低;因此聰明的大家也可能想到了將關鍵字分離出來,單獨處理,按關鍵字的檢索使用map效率會很高,而同一個關鍵字有可能會檢索到多本書籍,所以map按關鍵字檢索到的應該是一個書籍ID的向量

(3)也可以將書籍的各資訊分開儲存到map當中,但是這樣又引來另外一個問題,那就是需要對每一項查詢記錄結果排序,額外增加了負擔;這裡就體現出了包裝結構體的優勢:只需要排序一次

可能坑點:

(1)將關鍵字也維護在結構體當中,導致檢索超時

#include <iostream>
#include <algorithm>
#include <string.h>
#include <sstream>
#include <map>
#include <vector>
#include <stdio.h>
using namespace std;
struct bookInfo
{
string ID;
string title;
string author;
string publisher;
string year;
};
bookInfo book[10001];
map<string,vector<string> >keymap;
bool cmp(bookInfo a,bookInfo b)
{
return a.ID<b.ID;
}
int main()
{
int N,i=0;
cin>>N;
string keyword,temp;
while(i<N)
{
cin>>book[i].ID;
getchar();
getline(cin,book[i].title,'\n');
getline(cin,book[i].author,'\n');
getline(cin,keyword,'\n');
istringstream is(keyword);
while(is>>temp)keymap[temp].push_back(book[i].ID);
getline(cin,book[i].publisher,'\n');
getline(cin,book[i].year,'\n');
i  ;
}
sort(&book[0],&book[N],cmp);
int M;
cin>>M;
int j=0;
int index;
string query;
int flag;
while(j<M)
{
flag=0;
scanf("%d: ",&index);
getline(cin,query,'\n');
cout<<index<<": "<<query<<endl;
if(index==1)
{
for(int k=0;k<N;k  )
{
if(book[k].title==query)
{
flag=1;
cout<<book[k].ID<<endl;
}
}
}
else if(index==2)
{
for(int k=0;k<N;k  )
{
if(book[k].author==query)
{
flag=1;
cout<<book[k].ID<<endl;
}
}
}
else if(index==3)
{
sort(keymap[query].begin(),keymap[query].end());
if(keymap[query].size()>0)
{
flag=1;
vector<string >::iterator iter=keymap[query].begin();
for(;iter!=keymap[query].end();iter  )
{
cout<<*iter<<endl;
}
}
}
else if(index==4)
{
for(int k=0;k<N;k  )
{
if(book[k].publisher==query)
{
flag=1;
cout<<book[k].ID<<endl;
}
}
}
else
{
for(int k=0;k<N;k  )
{
if(book[k].year==query)
{
flag=1;
cout<<book[k].ID<<endl;
}
}
}
if(flag==0)cout<<"Not Found"<<endl;
j  ;
}
return 0;
}