wordin
001 dats struct
002 alogthrim and data struct
003 C language programing
004 the art of programing
005 data dimming
006 JAVA_EE programing
007 princple of database
008 princple of operating system
009 alogrithm design and analysis
010 Software Engineering
011 Software Engineering Stream
wordout
The idxlist is:
C 003
Engineering 010 011
JAVA_EE 006
Software 010 011
Stream 011
alogrithm 009
alogthrim 002
analysis 009
and 002 009
art 004
data 002 005
database 007
dats 001
design 009
dimming 005
language 003
of 004 007 008
operating 008
princple 007 008
programing 003 004 006
struct 001 002
system 008
the 004
#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++]='\0';
p=q;q=t.ch[++i];
}
wd.item[num-1][j]='\0';
printf("\n-----num=%d\n",num);//输出分离的单词，可省略
for(i=0;i<num;i++)
printf("%s\n",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("\n");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("\n\nposition=%d\n",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\n",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("\nThe idxlist is:\n");
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("\n");
}
}
void outputidxlistfile(idxlisttype idxlist,FILE *fp)//将idxlist中的内容输出到文件
{
int i;
linklist p;
fprintf(fp,"\nThe idxlist is:\n");
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,"\n");
}
}
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\n");
return 0;
}
if((file2 = fopen("wordout.txt", "w")) == NULL)//输出数据文件
{
printf("fopen 'wordout.txt' error\n");
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);
}