#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERROR -1
#define OK 1
#define BUFFSIZE 2048
typedef struct node{
char a[80];//存储书号
struct node *next;//指向下一个结点的指针
}Lnode, *linklist;//存储书号的链表
typedef struct {
char *ch;
int length;//字符个数
} heapstring;//字符串的堆方式定义
typedef struct {
char item[100][80];//定义一个字符数组存储各个单词
int last;//单词的个数
}wordlisttype;//单词列表
typedef struct{
heapstring key;//以堆方式存放的关键字
linklist bnolist;//书号链表
}idxtermtype;//关键字元素
typedef struct{
idxtermtype item[1000];//关键字数组
int last; //关键字的个数
}idxlisttype;//关键字倒排表
typedef int status;
status init(heapstring &t)//初始化堆字符串
{
t.ch=(char *)malloc(sizeof(char));
return 1;
}
status strassign(heapstring &t,char *chars)//将字符串存放到堆方式表示的字符串中
{
int len,j;
init(t);
if(t.ch) free(t.ch);
len=strlen(chars);
if(chars[len-1]==10) len=len-1;//去掉从文件中读入一行字符的换行标记（其ASCII为10），此标记不存入字符串中
if(!len) {t.ch=NULL;t.length =0;}
else
if(!(t.ch=(char *)malloc(len*sizeof(char))))
return ERROR;
else
{
for (j=0;j<len;j++) t.ch[j]=chars[j];
t.length =len;
}
return OK;
}
void outputstring(heapstring t)//输出以堆方式表示的字符串
{
int i;
for (i=0;i<t.length ;i++)
printf("%c",t.ch[i]);
}
status extractword(heapstring t,wordlisttype &wd)// 从字符串堆t中分离出单词符号存放到单词表wd中
{
int num=0,i=0,len=t.length,label=-1,j=0 ;
char p,q;
i=0;num=0;
p=' ';q=t.ch[i];
while(i<len)
{
if(p==' '&&q!=' ')//p,q为两相邻字符，空格+非空格表示一个单词的开始，label=1
{
num++;label=1;j=0;//num为单词的个数
}
else if(p!=' '&&q==' ') label=0;//p,q为两相邻字符，非空格+空格表示一个单词的结束，label=0
if(label==1) //wd.item[num-1][j++]=q;//存储单词的字符
{
if(q>='0' && q<='9')
wd.item[num-1][j++]=q;
else if (q>='A' && q<='Z')
wd.item[num-1][j++]=q+32;
else
wd.item[num-1][j++]=q;
}
else if(label==0) wd.item[num-1][j++]=' ';
p=q;q=t.ch[++i];
}
wd.item[num-1][j]=' ';
printf("
-----num=%d
",num);//输出分离的单词，可省略
for(i=0;i<num;i++)
printf("%s
",wd.item[i]);
wd.last=num;
return 1;
}
int strcompare(heapstring key,heapstring word) //key>word return 1; key<word return -1; key=word return 0
{
int i,flag;
printf("
");outputstring(key);printf(" # ");outputstring(word);
for(i=0;i<key.length && i<word.length ;i++)
if (key.ch[i]!=word.ch[i]) break;
if(key.length==word.length && i==word.length)//字符串相等
flag=0;
else if(i<key.length && i<word.length)//字符串不相等
{
if (key.ch [i]>word.ch [i])
flag=1;
else flag=-1;
}
else if(i<key.length)
flag=1;
else flag=-1;
printf(" @@@@@@ %d",flag);
return flag;
}
void getword(int i,heapstring &word,wordlisttype wd)//从词表wd中分离出第i个单词，并相许到字符串堆word中
{
strassign(word,wd.item [i]);
}
void heapstringcopy(heapstring &obj,heapstring soure)//以堆方式表示的字符串的复制，源为soure，目标为obj
{
int i;
obj.ch =(char *)malloc(soure.length *sizeof(char));
for (i=0;i<soure.length ;i++)
obj.ch[i]=soure.ch [i];
obj.length =soure.length ;
}
int locateidxlist(idxlisttype idxlist,heapstring word)
{
//在idxlist中查找word的位置，返回相等或第一个大于该字符串的元素的下标(0..idxlist.last)
int i;
for(i=0;i<idxlist.last;i++)
if(strcompare(idxlist.item[i].key ,word)>=0)
break;
return i;
}
void write_idxlist_i(idxlisttype &idxlist,heapstring word,char bno[],int i)
{ //将单词word和书号bno写入到idxlist的第i个元素中
linklist p;
//outputstring(word);
heapstringcopy(idxlist.item[i].key,word);
//printf(" %d--- ",i);
p=(linklist)malloc(sizeof(Lnode));
strcpy(p->a,bno);
p->next =NULL;
idxlist.item[i].bnolist =p;
idxlist.last++;
}
int locate_ins(idxlisttype &idxlist,heapstring word,char bno[])//将单词word和书号插入到idxlist中
{
int i=0,m,j;
linklist p,q,r;
m=locateidxlist(idxlist,word);
printf("
position=%d
",m);
if(idxlist.last ==0 || m==idxlist.last )//idxlist没有元素或待插入的元素位于有序表的最后，直接插入
write_idxlist_i(idxlist,word,bno,m);
else
if(strcompare(idxlist.item[m].key ,word)==0)//相等则只增加书号索引,插入bno，使bno递增排列
{
p=(linklist)malloc(sizeof(Lnode));//生成插入结点p
strcpy(p->a,bno);
q=idxlist.item[m].bnolist;
r=NULL;
while(q && strcmp(q->a,bno)<0)
{
r=q;q=q->next;
}
if(r==NULL)//p插入到q的前面
{
p->next =q;
idxlist.item[m].bnolist =p;
}
else//p插入到r的后面
{
p->next =q;
r->next =p;
}
}
else//先移动，再插入
{
for(j=idxlist.last-1;j>=m;--j)
{
idxlist.item[j+1].bnolist =idxlist.item[j].bnolist ;
heapstringcopy(idxlist.item[j+1].key,idxlist.item[j].key);
}
write_idxlist_i(idxlist,word,bno,m);//插入到第m位置
}
return 1;
}
status insidxlist(idxlisttype &idxlist,wordlisttype wd)//将一行书的各单词插入到idxlist中
{
int i;
heapstring word;
char bookno[80];
strcpy(bookno,wd.item [0]);
// printf("bookno=%s
",bookno);
for(i=1;i<wd.last;i++)
{
getword(i,word,wd);
locate_ins(idxlist,word,bookno);
}
return 1;
}
void outputidxlist(idxlisttype idxlist)//将idxlist中的内容输出
{
int i;
linklist p;
printf("
The idxlist is:
");
for(i=0;i<idxlist.last;i++)
{
outputstring(idxlist.item [i].key );
p=idxlist.item[i].bnolist ;
while (p!=NULL)
{
printf(" %s ",p->a);//getchar();
p=p->next ;
}
printf("
");
}
}
void outputidxlistfile(idxlisttype idxlist,FILE *fp)//将idxlist中的内容输出到文件
{
int i;
linklist p;
fprintf(fp,"
The idxlist is:
");
for(i=0;i<idxlist.last;i++)
{
for (int j=0;j<idxlist.item [i].key.length ;j++)//将单词写入文件
fprintf(fp,"%c",idxlist.item [i].key.ch[j]);
p=idxlist.item[i].bnolist ;
while (p!=NULL)//将书号写入文件
{
fprintf(fp," %s ",p->a);//getchar();
p=p->next ;
}
fprintf(fp,"
");
}
}
main()
{
heapstring str;
idxlisttype idxlist;
idxlist.last=0;
wordlisttype wd;
FILE *file1= NULL;
FILE *file2= NULL;
char buf[BUFFSIZE];
if((file1 = fopen("wordin.txt", "r")) == NULL)//输入数据文件
{
printf("fopen 'wordin.txt' error
");
return 0;
}
if((file2 = fopen("wordout.txt", "w")) == NULL)//输出数据文件
{
printf("fopen 'wordout.txt' error
");
return 0;
}
while(fgets(buf, BUFFSIZE, file1))
{
//fputs(buf,file2);//测试写入情况
//printf("%s",buf);
strassign(str,buf);
outputstring(str);
extractword(str,wd);
insidxlist(idxlist,wd);
getchar();
}
outputidxlist(idxlist);
outputidxlistfile(idxlist,file2);
exit(0);
}