吐了,一开始看错题意了,导致代码很多冗余(不过话说两个文件只要后十六位相同就是同一文件很明显不合理啊)
思路:
1、将所有字符串读入一个数组(这里也可以一段一段读入分开处理,不过我不知道这样输入该怎么处理)
2、定义ij为0,遍历数组(注意这里遍历时j先跑,遇到\就停下让i=j,遇到\n时ij之间就是包括页数的文件)
3、将其截取为文件名只有后十六位的形式
4、定义散列式(这里我是把他们的ascii码加上对哈希表求余数)
5、定义哈希表(这里写211个是为了保证a/n在0.5到0.8的范围内)
6、定义插入函数(这里的冲突解决办法选择的是平方法)
7、定义位置数组(顺序存放放进哈希表中的文件的所在哈希表的位置)
8、将3截取的文件插入哈希表中,如果哈希表中没有就直接插入并返回位置,如果哈希表中有就返回位置+1000(这里加1000是为了求次数)
9、全部放入后取位置数组中的最后八个
10、定义次数(小于1000就是1次,每多1000就多一次)
12、遍历输出
#include<stdio.h>
#include<string.h>
int kvalue(char*file, int start, int end){
int all = 0;
for(; start<=end; start++){
all+=file[start];
}
return all%211;
}
int insert(char**hash, int k, char*file){
int cnum=0;
while(hash[k][0]!='\0'){
if(strcmp(hash[k], file)!=0){
if(++cnum%2==1){
k=k+(cnum+1)/2*(cnum+1)/2;
k%=211;
}
else{
k=k-cnum/2*cnum/2;
k%=211;
}
}
else{
int kk=1000+k;
return kk;
}
}
hash[k]=file;
return k;
}
void print_file(char*file, int times){
int file_len = 0;
int all_len = 0;
for(;file[file_len]!=' '; file_len++);
for(;file[all_len]!='\0'; all_len++);
if(file_len<=16){
for(int x=0; x<all_len; x++){
printf("%c", file[x]);
}
}
else{
for(int x=file_len-16; x<all_len; x++){
printf("%c", file[x]);
}
}
printf(" %d\n", times);
}
int main(){
int sort_len=0;
int sort_file[100];
memset(sort_file, -1, sizeof(int)*100);
char** hash = (char**)malloc(sizeof(int*) * 211);
int i;
for (i = 0; i < 211; i++) {
hash[i] = (char*)malloc(sizeof(char) * 100);
memset(hash[i], 0, sizeof(char)*100);
}
char file[10000]={0};
char*loc=file;
while(~scanf("%c", loc))loc++;
int lenth = (loc-file)/sizeof(char);
int j=0;
for(i=0; i<lenth; i=j){
for(j=i+1; file[j]!='\\' && file[j]!='\n' && file[j]!='\0'; j++){
if(file[j+1]=='\n'){//此时i+1和j(闭合)之间就是该字符串
int len=j-i;
char*one_file=(char*)malloc(sizeof(char)*(len+1));
int bias=0;
int file_len=0;
int x = i+1;
for(;file[x]!=' '; x++)file_len++;
int k, lo;
if(file_len<=16){
for(int z=i+1; z<=j; z++){
one_file[bias]=file[z];
bias++;
}
k=kvalue(one_file, 0, len-1);
lo=insert(hash, k, one_file);
}
else{
for(int z=i+1+file_len-16; z<=j; z++){
one_file[bias]=file[z];
bias++;
}
k=kvalue(one_file, 0, len-1);
lo=insert(hash, k, one_file);
}
if(lo<1000){
sort_file[sort_len]=lo;
sort_len++;
}
else{
for(int x=0; x<100; x++){
if(sort_file[x]%1000==lo%1000){
sort_file[x]=(sort_file[x]/1000+lo/1000)*1000+lo%1000;
break;
}
}
}
}
}
}
int start = 0;
if(sort_len>8)start = sort_len-8;//[start,sort_len)之间就是最后八个
for(; start<sort_len; start++){
int times = sort_file[start]/1000+1;
int seq = sort_file[start]%1000;
print_file(hash[seq], times);
}
return 0;
}