[已解决]C++倒排索引表问题求解

Dogelike

3,实验要求
(1)输入格式说明:
输入首先给出正整数N(<=100)，为文件总数。随后按以下格式给出每个文件的内容:首先给出文件正文，最后在一行中只给出一个字符“#”,表示文件结束。在N个文件内容结束之后，给出查询总数M(<=104)，随后M行,每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到N编号。
(2)输出格式说明:
针对每一条查询，在一行中输出两文件的相似度,即两文件的公共词汇量占两文件总词汇量的百分比,精确到小数点后1位。注意这里的一个“单词”只包括仅由英文字母组成的、
长度不小于3、且不超过10的英文单词,长度超过10的只考虑前10个字母。单词间以任何非英文字母隔开。另外,大小写不同的同一单词被认为是相同的单词,例如“You”和“you”是同一个单词。
3)样例输入与输出:
输入
3
Aaa Bbb Ccc
#
Bbb Ccc Ddd
#
Aaa2 ccc Eee
is at Ddd@Fff
#
2
1 2
1 3
输出
50.0%
33.3%

下面是我自己写的代码：

1. #include <iostream>
   
2. #include <vector>
   
3. #include <string>
   
4. #include <iomanip>
   
5. #include <algorithm>
   
6. using namespace std;
   
7. 
   
8. struct Document
   
9. {
   
10.         int docID;
    
11.         vector<string> words;
    
12. };
    
13. 
    
14. class CompareFile
    
15. {
    
16. private:
    
17.     vector<Document> collection;
    
18.     int N,M;
    
19.     string s;
    
20. public:
    
21.         void input()
    
22.         {
    
23.             cin>>N;
    
24.             int i = 0;
    
25.             string temp;
    
26.             while(true)
    
27.         {
    
28.             getline(cin, temp);
    
29.             s = s + temp;
    
30.             if(temp[0] == '#') i++;
    
31.             if(i == N)
    
32.                 break;
    
33.         }
    
34.         for(i = 0; i < N; ++i)
    
35.         {
    
36.             collection[i].docID = i + 1;
    
37.         }
    
38.         }
    
39.         bool EqualWords(string s1,string s2)
    
40.         {
    
41.             string::size_type i;
    
42.             if(s1.size() != s2.size())
    
43.             return false;
    
44.         else
    
45.         {
    
46.             for(i = 0;i < s1.size(); ++i)
    
47.             {
    
48.                 if(s1[i] != s2[i] && s1[i] != s2[i] + 32 && s1[i] != s2[i] - 32)
    
49.                     return false;
    
50.             }
    
51.         }
    
52.         return true;
    
53.         }
    
54.     void indexDocument(int docID)
    
55.     {
    
56.         string::size_type n;
    
57.         int i;
    
58.         n = 0;
    
59.         for(i = 0; i < docID - 1; ++i)
    
60.         {
    
61.             n = s.find("#",n);
    
62.             n = n + 1;
    
63.         }
    
64.         string indexItem = "";
    
65.         while(s[n] != '#')
    
66.         {
    
67.             //读取单词，给索引项赋值
    
68.             while (isalpha(s[n]))
    
69.             {
    
70.                 indexItem += s[n];
    
71.                 n++;
    
72.             }
    
73.             if(indexItem.size() < 3)
    
74.                 continue;
    
75.             if(indexItem.size() >= 10)
    
76.                 indexItem = indexItem.substr(0,10);
    
77.             //把索引项加入词典
    
78.             collection[docID - 1].words.push_back(indexItem);
    
79.             //清空索引项，准备下一次
    
80.             indexItem = "";
    
81.             n++;
    
82.         }
    
83.     }
    
84.     void indexCollection()
    
85.     {
    
86.         //打开对应的文件并索引
    
87.         for (int i = 0; i < N; i++)
    
88.         {
    
89.             //索引单篇文档
    
90.             indexDocument(collection[i].docID);
    
91.         }
    
92.     }
    
93.     static bool cmp(string a, string b)
    
94.     {
    
95.         return a < b;//词项按照从小到大排序
    
96.     }
    
97.     void sortIndex(Document doc)
    
98.     {
    
99.         sort(doc.words.begin(), doc.words.end(), cmp);
    
100.     }
     
101.     void mergeIndex()
     
102.     {
     
103.         int j;
     
104.         for(j = 0; j < N; ++j)
     
105.         {
     
106.             sortIndex(collection[j]);
     
107.         }
     
108.         vector<string>::iterator it_cur;//创建迭代器
     
109.         vector<string>::iterator it_next;
     
110.         vector<Document>::iterator i = collection.begin();
     
111.         while(i != collection.end())
     
112.         {
     
113.             it_cur = (*i).words.begin();
     
114.             it_next = it_cur + 1;
     
115.             while (it_cur != (*i).words.end())
     
116.             {
     
117.                 if(it_cur + 1 != (*i).words.end()) it_next = it_cur + 1;
     
118.                 else break;
     
119.                 while(EqualWords((*it_cur),(*it_next)))
     
120.                 {//这个循环内处理掉所有与当前词项重复的词项
     
121.                     (*i).words.erase(it_next);//删除重复项
     
122.                     if (it_cur + 1 != (*i).words.end()) it_next = it_cur + 1;
     
123.                     else break;
     
124.                 }
     
125.                 it_cur++;
     
126.             }
     
127.             i++;
     
128.         }
     
129.     }
     
130.         void Compare(int docID1,int docID2)
     
131.     {
     
132.         int a = docID1 - 1 ,b = docID2 - 1;
     
133.         int Count = 0,sum;
     
134.         sum = collection[a].words.size() + collection[b].words.size();
     
135.         vector<string>::iterator it_cur1;//创建迭代器
     
136.         vector<string>::iterator it_cur2;
     
137.         it_cur1 = collection[a].words.begin();
     
138.         it_cur2 = collection[b].words.begin();
     
139.         while(it_cur1 != collection[a].words.end())
     
140.         {
     
141.             while(it_cur2 != collection[b].words.end())
     
142.             {
     
143.                 if(EqualWords((*it_cur1),(*it_cur2)))
     
144.                 {
     
145.                     Count++;
     
146.                     sum--;
     
147.                     break;
     
148.                 }
     
149.                 it_cur2++;
     
150.              }
     
151.              it_cur1++;
     
152.         }
     
153.         double r = Count/sum * 100;
     
154.         cout<<setiosflags(ios::fixed)<<setprecision(1)<<r<<"%"<<endl;
     
155.     }
     
156.     //~CompareFile();
     
157. };
     
158. 
     
159. int main()
     
160. {
     
161.     CompareFile t;
     
162.     t.input();
     
163.     t.indexCollection();
     
164.     t.mergeIndex();
     
165.     t.Compare(1,2);
     
166.     //for(int i = 0;i < N;++i)
     
167.     //   cout<<s[i];
     
168.     //int a,b;
     
169.     //cin>>a>>b;
     
170.     //t.Compare(s,a,b);
     
171.     return 0;
     
172. }

复制代码

不知道为啥运行没反应

最佳答案

月排行榜 / 总排行榜

jhq999

2021-11-17 16:16:29

1. #include <stdio.h>
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. 
   
7. 
   
8. #define STRINGMAXSIZE 64
   
9. int wordsum(string *instr,string *words=NULL,int count=0)//只输入一个参数时，返回字符串单词数量，否则分离出单词
   
10. {
    
11.         int i = 0;
    
12.         int start=0;
    
13.         if (NULL==words)
    
14.         {
    
15. 
    
16.                 for (i=0;instr->c_str()[i]; i++)
    
17.                 {
    
18.                         if (('a'>instr->c_str()[i]||'z'<instr->c_str()[i])&&('A'>instr->c_str()[i]||'Z'<instr->c_str()[i]))
    
19.                         {
    
20.                                 if (0x20!=instr->c_str()[i])
    
21.                                 {
    
22.                                         *instr=instr->replace(i,1," ");//把不是字母的都替换成空格
    
23. 
    
24.                                 }
    
25.                                 if (instr->substr(start,i-start).c_str()[0]&&(0x20!=instr->substr(start,i-start).c_str()[0]))//如果子字符串开头不是0和空格单词数量加一
    
26.                                 {
    
27.                                         count++;
    
28.                                 }
    
29.                                 start=i+1;
    
30.                         }
    
31.                 }
    
32.                 return count;
    
33.         }
    
34. 
    
35. 
    
36.         else if (count)//分离出单词
    
37.         {
    
38. 
    
39.                 for (i=0;instr->c_str()[i]; i++)
    
40.                 {
    
41.                         if (0x20==instr->c_str()[i])
    
42.                         {
    
43.                                 if (instr->substr(start,i-start).c_str()[0]&&0x20!=instr->substr(start,i-start).c_str()[0])
    
44.                                 {
    
45. 
    
46.                                
    
47.                                         words[--count]=instr->substr(start,i-start);
    
48.                                         if (words[count].length()>10)//大于10的单词取10个字符
    
49.                                         {
    
50.                                                 words[count]=words[count].substr(0,10);
    
51.                                         }
    
52.                                 }
    
53.                                 start=i+1;
    
54.                         }
    
55.                 }
    
56.         }
    
57. 
    
58. 
    
59.         return count;
    
60. }
    
61. double cmpword(string *words1,string *words2,int word1count,int word2count)
    
62. {
    
63.         double count=0;
    
64.         bool flag=0;
    
65.         for (int i = 0; i < word1count; i++)
    
66.         {
    
67.                 if (words1[i].length()<3)continue;//小于3丢掉
    
68.                
    
69.                 flag=0;
    
70.                 for (int j = 0; j <word2count; j++)
    
71.                 {
    
72.                         if (words2[j].length()<3)continue;//小于3丢掉
    
73.                         if (!_stricmp(words1[i].c_str(),words2[j].c_str()))//不区分大小写比对
    
74.                         {
    
75.                                 if (0==flag)
    
76.                                 {
    
77.                                         count++;
    
78.                                         flag=1;
    
79.                                 }
    
80.                                 count++;
    
81.                                 cout<<words1[i]<<endl;
    
82.                         }
    
83.                 }
    
84.         }
    
85.         return (count*100)/(double)(word1count+word2count);
    
86. }
    
87. int cmpstr(string *strs,int n,int (*team)[2],int m)
    
88. {
    
89.         int i=0,j=0,*wordcount=new int[n];
    
90.         string **word=new string*[n];
    
91.         for (i = 0; i < n; i++)
    
92.         {
    
93.                 wordcount[i]=wordsum(&strs[i]);
    
94.                 word[i]=new string[wordcount[i]];
    
95.                 wordsum(&strs[i],word[i],wordcount[i]);
    
96.         }
    
97. 
    
98.         for (i = 0; i < m; i++)
    
99.         {
    
100.                 //cout<<setprecision(1)<<cmpword(word[team[i][0]-1],word[team[i][1]-1],wordcount[team[i][0]-1],wordcount[team[i][1]-1])<<endl;
     
101.                 printf("%.1lf%%\n",cmpword(word[team[i][0]-1],word[team[i][1]-1],wordcount[team[i][0]-1],wordcount[team[i][1]-1]));
     
102.         }
     
103. 
     
104.         for (i = 0; i < n; i++)
     
105.         {
     
106.                 delete[] word[i];
     
107.         }
     
108.         delete[] wordcount;
     
109.         delete[] word;
     
110.         return 0;
     
111. }
     
112. int main()
     
113. {
     
114. 
     
115.         int i=0,j=0,m=0,n=0;
     
116.         cin>>n;
     
117.         fflush(stdin);
     
118.         string *strs=new string[n];
     
119.         for (i = 0; i <n; i++)
     
120.         {
     
121.                 strs[i].resize(STRINGMAXSIZE);
     
122.                 scanf("%[^#]",strs[i].data());
     
123.                 fflush(stdin);
     
124.         }
     
125.         cin>>m;
     
126.         fflush(stdin);
     
127.         int (*team)[2]=(int(*)[2])(new int[2*m*4]);
     
128.         for (i = 0; i < m; i++)
     
129.         {
     
130.                 cin>>team[i][0]>>team[i][1];
     
131.         }
     
132.         cmpstr(strs,n,team,m);
     
133.         delete[] team;
     
134.         delete[] strs;
     
135.         return 0;
     
136. }

复制代码

1. 3
   
2. Aaa Bbb Ccc ABCDEFGHIJ
   
3. #
   
4. Bbb Ccc Ddd
   
5. #
   
6. Aaa2  ccc Eee
   
7. is at Ddd@Fff
   
8. abcdefghijklmn
   
9. #
   
10. 3
    
11. 1 2
    
12. 1 3
    
13. 2 3
    
14. Ccc
    
15. Bbb
    
16. 57.1%
    
17. ABCDEFGHIJ
    
18. Ccc
    
19. Aaa
    
20. 50.0%
    
21. Ddd
    
22. Ccc
    
23. 36.4%
    

复制代码

跳转到最佳答案楼层

傻眼貓咪

这题很不错，有挑战性

Dogelike

傻眼貓咪 发表于 2021-11-15 21:27
这题很不错，有挑战性

做出来了吗哥

傻眼貓咪

Dogelike 发表于 2021-11-16 13:14
做出来了吗哥

抱歉，我试了，但是不能，可能需要其他大佬看看了

人造人

Dogelike 发表于 2021-11-16 13:14
做出来了吗哥

33.3% 是怎么算出来的？

jhq999

1. #include <stdio.h>
   
2. #include <iostream>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. 
   
7. 
   
8. #define STRINGMAXSIZE 64
   
9. int wordsum(string *instr,string *words=NULL,int count=0)//只输入一个参数时，返回字符串单词数量，否则分离出单词
   
10. {
    
11.         int i = 0;
    
12.         int start=0;
    
13.         if (NULL==words)
    
14.         {
    
15. 
    
16.                 for (i=0;instr->c_str()[i]; i++)
    
17.                 {
    
18.                         if (('a'>instr->c_str()[i]||'z'<instr->c_str()[i])&&('A'>instr->c_str()[i]||'Z'<instr->c_str()[i]))
    
19.                         {
    
20.                                 if (0x20!=instr->c_str()[i])
    
21.                                 {
    
22.                                         *instr=instr->replace(i,1," ");//把不是字母的都替换成空格
    
23. 
    
24.                                 }
    
25.                                 if (instr->substr(start,i-start).c_str()[0]&&(0x20!=instr->substr(start,i-start).c_str()[0]))//如果子字符串开头不是0和空格单词数量加一
    
26.                                 {
    
27.                                         count++;
    
28.                                 }
    
29.                                 start=i+1;
    
30.                         }
    
31.                 }
    
32.                 return count;
    
33.         }
    
34. 
    
35. 
    
36.         else if (count)//分离出单词
    
37.         {
    
38. 
    
39.                 for (i=0;instr->c_str()[i]; i++)
    
40.                 {
    
41.                         if (0x20==instr->c_str()[i])
    
42.                         {
    
43.                                 if (instr->substr(start,i-start).c_str()[0]&&0x20!=instr->substr(start,i-start).c_str()[0])
    
44.                                 {
    
45. 
    
46.                                
    
47.                                         words[--count]=instr->substr(start,i-start);
    
48.                                         if (words[count].length()>10)//大于10的单词取10个字符
    
49.                                         {
    
50.                                                 words[count]=words[count].substr(0,10);
    
51.                                         }
    
52.                                 }
    
53.                                 start=i+1;
    
54.                         }
    
55.                 }
    
56.         }
    
57. 
    
58. 
    
59.         return count;
    
60. }
    
61. double cmpword(string *words1,string *words2,int word1count,int word2count)
    
62. {
    
63.         double count=0;
    
64.         bool flag=0;
    
65.         for (int i = 0; i < word1count; i++)
    
66.         {
    
67.                 if (words1[i].length()<3)continue;//小于3丢掉
    
68.                
    
69.                 flag=0;
    
70.                 for (int j = 0; j <word2count; j++)
    
71.                 {
    
72.                         if (words2[j].length()<3)continue;//小于3丢掉
    
73.                         if (!_stricmp(words1[i].c_str(),words2[j].c_str()))//不区分大小写比对
    
74.                         {
    
75.                                 if (0==flag)
    
76.                                 {
    
77.                                         count++;
    
78.                                         flag=1;
    
79.                                 }
    
80.                                 count++;
    
81.                                 cout<<words1[i]<<endl;
    
82.                         }
    
83.                 }
    
84.         }
    
85.         return (count*100)/(double)(word1count+word2count);
    
86. }
    
87. int cmpstr(string *strs,int n,int (*team)[2],int m)
    
88. {
    
89.         int i=0,j=0,*wordcount=new int[n];
    
90.         string **word=new string*[n];
    
91.         for (i = 0; i < n; i++)
    
92.         {
    
93.                 wordcount[i]=wordsum(&strs[i]);
    
94.                 word[i]=new string[wordcount[i]];
    
95.                 wordsum(&strs[i],word[i],wordcount[i]);
    
96.         }
    
97. 
    
98.         for (i = 0; i < m; i++)
    
99.         {
    
100.                 //cout<<setprecision(1)<<cmpword(word[team[i][0]-1],word[team[i][1]-1],wordcount[team[i][0]-1],wordcount[team[i][1]-1])<<endl;
     
101.                 printf("%.1lf%%\n",cmpword(word[team[i][0]-1],word[team[i][1]-1],wordcount[team[i][0]-1],wordcount[team[i][1]-1]));
     
102.         }
     
103. 
     
104.         for (i = 0; i < n; i++)
     
105.         {
     
106.                 delete[] word[i];
     
107.         }
     
108.         delete[] wordcount;
     
109.         delete[] word;
     
110.         return 0;
     
111. }
     
112. int main()
     
113. {
     
114. 
     
115.         int i=0,j=0,m=0,n=0;
     
116.         cin>>n;
     
117.         fflush(stdin);
     
118.         string *strs=new string[n];
     
119.         for (i = 0; i <n; i++)
     
120.         {
     
121.                 strs[i].resize(STRINGMAXSIZE);
     
122.                 scanf("%[^#]",strs[i].data());
     
123.                 fflush(stdin);
     
124.         }
     
125.         cin>>m;
     
126.         fflush(stdin);
     
127.         int (*team)[2]=(int(*)[2])(new int[2*m*4]);
     
128.         for (i = 0; i < m; i++)
     
129.         {
     
130.                 cin>>team[i][0]>>team[i][1];
     
131.         }
     
132.         cmpstr(strs,n,team,m);
     
133.         delete[] team;
     
134.         delete[] strs;
     
135.         return 0;
     
136. }

复制代码

1. 3
   
2. Aaa Bbb Ccc ABCDEFGHIJ
   
3. #
   
4. Bbb Ccc Ddd
   
5. #
   
6. Aaa2  ccc Eee
   
7. is at Ddd@Fff
   
8. abcdefghijklmn
   
9. #
   
10. 3
    
11. 1 2
    
12. 1 3
    
13. 2 3
    
14. Ccc
    
15. Bbb
    
16. 57.1%
    
17. ABCDEFGHIJ
    
18. Ccc
    
19. Aaa
    
20. 50.0%
    
21. Ddd
    
22. Ccc
    
23. 36.4%
    

复制代码

Dogelike

人造人 发表于 2021-11-16 17:52
33.3% 是怎么算出来的？

一共有六个词（重复算一次），其中AAA,CCC重复，is和at长度不过二不算

Dogelike

jhq999 发表于 2021-11-17 16:16

牛哇大佬

人造人

Dogelike 发表于 2021-11-21 19:02
一共有六个词（重复算一次），其中AAA,CCC重复，is和at长度不过二不算

嗯，明白了

Dogelike

jhq999 发表于 2021-11-17 16:16

大佬你的程序应该词数记错了，输出结果和我放的不一样