数据结构课程设计字典序(源代码)

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#defineNULL0#defineERROR-1#definestack_in_size100#definestackincrement10structTreeNode/*树结点*/{ charch; intnumber;/*以该字符为结束的单词出现的个数*/ structTreeNode*pt[26];/*指向后继的字母的26个指针*/};structTreeNode*root;typedefstructTreeNode*Link_TreeNode;structMAX_TEN/*存放出现频率最高的十个单词数据结构*/{ charSTRING[35]; intcount;/*字符串出现的次数*/ intxiabao;/*字符数组位置的下标*/};structMAX_TENMAX[10];structMAX_TENMIN;structDocumentNode/*文件结点*/{ charch;/*存放某个单词的一个字符*/ intnumber;/*以该字符为结束的单词出现的个数*/ structDocumentNode*pt[26];/*指向后继的字母的26个指针*/ structLocationn*next;/*连接以该字符为结束的单词所在的位置*/};typedefstructDocumentNode*Link_DocumentNode;Link_DocumentNodeROOT[301];/*300个根节点指针,零号单元不用*/structLocationn/*单词在文件中的位置*/{ intnum; structLocationn*next;};structWORD/*单词链表结构*/{ charstrr[35]; structWORD*next;};typedefstruct{ char*base; char*top; intstacksize;}SQSTACK;SQSTACKS,T;SQSTACKCreat()/*创建空栈*/{ SQSTACKs; s.base=(char*)malloc(stack_in_size*sizeof(char)); s.top=s.base; s.stacksize=stack_in_size; returns;}/*全局变量栈*/charpop(SQSTACK&s)/*出栈*/{ chare; if(s.top==s.base)returnERROR; e=*(--s.top); returne;}voidpush(SQSTACK&s,chare)/*入栈*/{ if(s.top-s.base>=s.stacksize) { s.base=(char*)realloc(s.base, (s.stacksize+stackincrement)*sizeof(char)); s.top=s.base+s.stacksize; s.stacksize+=stackincrement; } *s.top=e; s.top=s.top+1;}intisempty(SQSTACKs)/*判断栈是否为空*/{ if(s.base==s.top) return1; else return0;}Link_TreeNodecreat()/*创建树结点，并返回指向该节点的指针*/{ inti; Link_TreeNodept; pt=(Link_TreeNode)malloc(sizeof(TreeNode)); pt->number=0; for(i=0;i<26;i++) pt->pt[i]=NULL; returnpt;}voidCREAT_DicTree()/*创建字典树*/{ root=creat(); Link_TreeNodeq; FILE*fp; char*p; intctmp; intjieshu; charstr[35];/*存放从文件中读入的单词*/ if((fp=fopen("vocabulary.txt","r"))==NULL) printf("cannotopenvocabulary.txt\n"); while(1) { jieshu=fscanf(fp,"%s",str);/*从文件中读入字符串*/ q=root; if(jieshu==-1) break; else { p=str; while(*p!='\0') { ctmp=*p-97; if(q->pt[ctmp]!=NULL) q=q->pt[ctmp]; else { q->pt[ctmp]=creat(); q=q->pt[ctmp]; q->ch=*p; } p++; if(*p=='\0') { q->number++; break; } } } }}intSearch(charstr[],Link_TreeNoderoot)/*在字典树中搜索字符串str，并返回其出现的次数不存在时返回次数为0*/{ intcount,ctmp; char*p; p=str; Link_TreeNodeq; q=root; while(*p!='\0') { ctmp=*p-97; if(q->pt[ctmp]==NULL) {count=0;/*不存在时count置为0*/ break; } else { q=q->pt[ctmp]; p++; if(*p=='\0') count=q->number; } } returncount;}Link_TreeNodeGet_Last_Link(charstr[]){ intk; char*p; Link_TreeNodeq=root; p=str; T.top=T.base; S=Creat(); while(*p!='\0')/*前缀存入栈S中*/ { push(S,*p); p++;} p=str; while(*p!='\0'){ k=*p-97; if(q->pt[k]==NULL) { q=q->pt[k]; break; } else {q=q->pt[k];/*指针q指向的结点中字符为当前*p的字符值*/ p++; }} returnq;}boolOutPrint(Link_TreeNodep,FILE*fp)/*递归将指针p所指的结点的指针数组所指向的所有单词写入文件中*/{ intk; chartemp; Link_TreeNodeq; for(k=0;k<26;)/*扫描26个指针*/ { if(p->pt[k]==NULL) k++; else { q=p->pt[k]; push(S,q->ch); if(q->number>0)/*输出该单词*/ { while(!isempty(S)) { temp=pop(S); push(T,temp);/*将栈S中的元素全部弹入T栈中*/ } charshuzu[35]; chartempp[2]; shuzu[0]='\0'; while(!isempty(T))/*逐个将T栈中元素弹入S栈中*/ { tempp[0]=pop(T); tempp[1]='\0'; strcat(shuzu,tempp); push(S,tempp[0]); } fprintf(fp,"%s\n",shuzu);/*将出现的该单词写入文件中*/ } OutPrint(q,fp);/*递归调用*/ pop(S);k++; } } if(k==26) returntrue;/*没有后继指针*/}voidRECHANGE_MIN(chartepp[],intcunt)/*数组中保存的十个最大的单词*/{ strcpy(MAX[MIN.xiabao].STRING,tepp); MAX[MIN.xiabao].count=cunt; intk; MIN=MAX[0]; for(k=1;k<10;k++) { if(MIN.count>MAX[k].count) MIN=MAX[k]; }}boolGOT_MAX_TEN(Link_TreeNodep)/*递归得到指针p所指的结点的指针数组所指向的所有单词中出现次数最高的十个单词*/{ intk; chartemp; Link_TreeNodeq; for(k=0;k<26;)/*扫描26个指针*/ { if(p->pt[k]==NULL) k++; else { q=p->pt[k]; push(S,q->ch); if(q->number>0) { if(q->number>MIN.count) { while(!isempty(S)) { temp=pop(S); push(T,temp); } charshuzu[35]; chartempp[2]; shuzu[0]='\0'; while(!isempty(T)) { tempp[0]=pop(T); tempp[1]='\0'; strcat(shuzu,tempp); push(S,tempp[0]); } RECHANGE_MIN(shuzu,q->number); } } GOT_MAX_TEN(q); pop(S);k++; } } if(k==26) returntrue;}Link_DocumentNodeCREAT()/*创建一个文件型的数据结构结点，并返回指向该节点的指针*/{ inti; Link_DocumentNodep; p=(Link_DocumentNode)malloc(sizeof(structDocumentNode)); p->number=0; for(i=0;i<26;i++) { p->pt[i]=NULL; } p->next=NULL;/*文件初始化*/ returnp;}voidCREAT_DocumentTree()/*读入文件，创建文件树*/{ Link_DocumentNodeq; structLocationn*LL; FILE*fp; char*p; intctmp; intjieshu; intLocation;/*定位单词在文章中的位置*/ intk; charstr[35];/*存放从文件中读入的单词*/ if((fp=fopen("Document.txt","r"))==NULL) printf("cannotopenDocument.txt\n"); while(1) { jieshu=fscanf(fp,"%s",str); if(jieshu==-1) break;/*文件中单词已读完*/ if(!strcmp(str,"Document")) { fscanf(fp,"%d",&k); ROOT[k]=CREAT(); Location=1; fscanf(fp,"%s",str); } q=ROOT[k]; p=str; while(*p!='\0')/*处理每个单词*/ { ctmp=*p-97; if(q->pt[ctmp]!=NULL) q=q->pt[ctmp]; else { q->pt[ctmp]=CREAT(); q=q->pt[ctmp]; q->ch=*p; } p++; if(*p=='\0') { q->number++; if(q->next==NULL) { LL=(structLocationn*)malloc(sizeof(structLocationn)); LL->num=Location; q->next=LL; LL->next=NULL; Location++; break; } else { LL=q->next; while(LL->next!=NULL) LL=LL->next; LL->next=(structLocationn*)malloc(sizeof(structLocationn)); LL=LL->next; LL->next=NULL; LL->num=Location; Location++; break; } } } }}intSearch_Doc(charstr[],Link_DocumentNoderoot)/*在文件树中搜索字符串str，不存在时返回次数为0，存在返回其出现的次数*/{ intcount,ctmp; char*p; p=str; Link_DocumentNodeq; q=root; while(*p!='\0')/*逐个扫描该字符串中的每个字符*/ { ctmp=*p-97; if(q->pt[ctmp]==NULL) {count=0; break; } else { q=q->pt[ctmp]; p++; if(*p=='\0') count=q->number; } } returncount;}voidSORT_MAX_Ten()/*对出现频率最高的十个单词从大到小排序*/{ inti,j,temp; structMAX_TENctmp; for(i=0;i<9;i++)/*选择排序*/ { temp=i; for(j=i+1;j<10;j++) if(MAX[temp].count<MAX[j].count) temp=j; if(temp!=i) {ctmp=MAX[temp]; MAX[temp]=MAX[i]; MAX[i]=ctmp;}}}structWORD*Creat_two_word_link(charstr1[],charstr2[]){ structWORD*head,*tempary,*pt; tempary=head=NULL; charttmp[35]; char*p,*q; intcount; for(count=1;count<=2;count++) {/*扫描两个单词*/ if(count==1) p=str1; else { p=str2; } q=ttmp; while(*p!='\0') { *q=*p; p++; q++; } *q='\0'; pt=(structWORD*)malloc(sizeof(structWORD)); strcpy(pt->strr,ttmp); if(head==NULL)/*扫描第一个单词的情况*/ { head=pt; tempary=head; } else/*扫描第二个单词的情况*/ { tempary->next=pt; tempary=pt; } } tempary->next=NULL;returnhead;} structWORD*Creat_multi_word_link(intlength,FILE*fp){ charttmp[35]; charstring[35];/*存放读入是的字符串*/ intcount; char*p; char*q; structWORD*head,*pt,*tempary; tempary=head=NULL;/*对指针进行初始化*/ for(count=1;count<=length;count++) { fscanf(fp,"%s",string); p=string; q=ttmp; while(*p!='\0') { *q=*p; p++; q++; } *q='\0'; pt=(structWORD*)malloc(sizeof(structWORD)); strcpy(pt->strr,ttmp); if(head==NULL) { head=pt; tempary=head; } else { tempary->next=pt; tempary=pt; } } tempary->next=NULL; returnhead;} voidSearch_Match_Word(structWORD*head,intlength,FILE*fp){ Link_DocumentNodeq; intcircle; intctmp; structWORD*point; structLocationn*list1; structLocationn*list2; list1=(structLocationn*)malloc(sizeof(structLocationn));list2=(structLocationn*)malloc(sizeof(structLocationn)); list2->next=NULL; structLocationn*pt1; structLocationn*pt2; structLocationn*pt3; inti; char*p; for(circle=0;circle<=300;) {nextcircle: circle++; if(circle>300) break;/*文件树扫描结束*/ for(i=1,point=head->next;i<=length;i++) {/*逐个扫描从文件中读入的n个字符串*/ p=point->strr;/*指向当前扫描的该字符串的首地址*/ q=ROOT[circle];/*q指向第circle个文件数*/ while(*p!='\0') { ctmp=*p-97; if(q->pt[ctmp]==NULL) gotonextcircle; else {/*存在时继续在文件树中扫描直到该单词的结尾*/ q=q->pt[ctmp]; } p++; if(*p=='\0') { if(i==1) list1->next=q->next; else { pt1=list1->next; while(pt1!=NULL) { pt2=q->next; while(pt2!=NULL) { if(pt1->num+1!=pt2->num) pt2=pt2->next; else { pt3=list2; while(pt3->next!=NULL) pt3=pt3->next; pt3->next=(structLocationn*)malloc(sizeof(structLocationn)); pt3=pt3->next; pt3->num=pt2->num; pt3->next=NULL; pt2=pt2->next; } } pt1=pt1->next; }//while list1->next=list2->next; if(list1->next==NULL) gotonextcircle; list2->next=NULL; }//else } } point=point->next;/*扫描该字符串的下一个单词*/ } if(list1->next!=NULL) { fprintf(fp,"%d",circle); } list2->next=NULL; }//circle }voidOPEN_SearchWordInVocabulary()/*生成SearchWordInVocabulary_Result.txt*/{FILE*fp1;FILE*fp2;charstr[35];intcount;/*存放查找该单词时出现的次数*/intk=1;intjieshu;/*结束判断的标志*/if((fp1=fopen("SearchWordInVocabulary.txt","r"))==NULL) printf("cannotopenSearchWordInVocabulary.txt\n");if((fp2=fopen("SearchWordInVocabulary_Result.txt","w"))==NULL) printf("cannotwriteSearchWordInVocabulary_Result.txt\n");jieshu=fscanf(fp1,"%s",str);/*文件读取结束的标志*/while(jieshu!=-1){ fprintf(fp2,"%s%d:\n","CASE",k); k++;count=Search(str,root);if(count==0) fprintf(fp2,"%s\n","NO"); else fprintf(fp2,"%d\n",count); jieshu=fscanf(fp1,"%s",str);}fclose(fp1);fclose(fp2);}voidOPEN_TotPrefixWord()/*生成TotPrefixWord_Result.txt*/{ FILE*fp1; FILE*fp2; charstr[35]; intcount; intk=1; intjieshu; Link_TreeNodep_link; if((fp1=fopen("TotPrefixWord.txt","r"))==NULL) printf("cannotopenSearchWordInVocabulary.txt\n"); if((fp2=fopen("TotPrefixWord_Result.txt","w"))==NULL) printf("cannotwriteSearchWordInVocabulary_Result.txt\n"); jieshu=fscanf(fp1,"%s",str);/*读入一个单词*/ while(jieshu!=-1) { fprintf(fp2,"%s%d:\n","CASE",k); k++; p_link=Get_Last_Link(str);/*找到在单词树中指向该单词最后一个字符的指针*/ if(p_link!=NULL) { fprintf(fp2,"%s\n",str); OutPrint(p_link,fp2); }jieshu=fscanf(fp1,"%s",str);/*从文件中读入下一个单词*/ } fclose(fp1);fclose(fp2);}voidOPEN_PrefixFrequence()/*生成PrefixFrequence_Result.txt*/{ FILE*fp1; FILE*fp2; charstr[35]; intcount; intk=1; inti; intjieshu; Link_TreeNodep_link; if((fp1=fopen("PrefixFrequence.txt","r"))==NULL) printf("cannotopenSearchWordInVocabulary.txt\n"); if((fp2=fopen("PrefixFrequence_Result.txt","w"))==NULL) printf("cannotwriteSearchWordInVocabulary_Result.txt\n"); jieshu=fscanf(fp1,"%s",str);/*从文件中读入一个该单词*/ while(jieshu!=-1) { fprintf(fp2,"%s%d:\n","CASE",k); k++; p_link=Get_Last_Link(str); if(p_link!=NULL) { for(i=0;i<10;i++) { MAX[i].xiabao=i; MAX[i].count=0; } MIN=MAX[0]; GOT_MAX_TEN(p_link);SORT_MAX_Ten(); if(p_link->number>0) { for(i=0;i<10;i++) { if(MAX[i].count==0) { strcpy(MAX[i].STRING,str); MAX[i].count=p_link->number; break; } } }SORT_MAX_Ten(); for(i=0;i<10;i++) { if(MAX[i].count>0) { fprintf(fp2,"%s%d\n",MAX[i].STRING,MAX[i].count); } } }jieshu=fscanf(fp1,"%s",str); } fclose(fp1);