數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)字典序(源代碼)

#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>#defineNULL0#defineERROR-1#definestack_in_size100#definestackincrement10structTreeNode/*樹結(jié)點(diǎn)*/{ charch; intnumber;/*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/ structTreeNode*pt[26];/*指向后繼的字母的26個(gè)指針*/};structTreeNode*root;typedefstructTreeNode*Link_TreeNode;structMAX_TEN/*存放出現(xiàn)頻率最高的十個(gè)單詞數(shù)據(jù)結(jié)構(gòu)*/{ charSTRING[35]; intcount;/*字符串出現(xiàn)的次數(shù)*/ intxiabao;/*字符數(shù)組位置的下標(biāo)*/};structMAX_TENMAX[10];structMAX_TENMIN;structDocumentNode/*文件結(jié)點(diǎn)*/{ charch;/*存放某個(gè)單詞的一個(gè)字符*/ intnumber;/*以該字符為結(jié)束的單詞出現(xiàn)的個(gè)數(shù)*/ structDocumentNode*pt[26];/*指向后繼的字母的26個(gè)指針*/ structLocationn*next;/*連接以該字符為結(jié)束的單詞所在的位置*/};typedefstructDocumentNode*Link_DocumentNode;Link_DocumentNodeROOT[301];/*300個(gè)根節(jié)點(diǎn)指針,零號(hào)單元不用*/structLocationn/*單詞在文件中的位置*/{ intnum; structLocationn*next;};structWORD/*單詞鏈表結(jié)構(gòu)*/{ charstrr[35]; structWORD*next;};typedefstruct{ char*base; char*top; intstacksize;}SQSTACK;SQSTACKS,T;SQSTACKCreat()/*創(chuàng)建空棧*/{ 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()/*創(chuàng)建樹結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/{ 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()/*創(chuàng)建字典樹*/{ 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，并返回其出現(xiàn)的次數(shù)不存在時(shí)返回次數(shù)為0*/{ intcount,ctmp; char*p; p=str; Link_TreeNodeq; q=root; while(*p!='\0') { ctmp=*p-97; if(q->pt[ctmp]==NULL) {count=0;/*不存在時(shí)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指向的結(jié)點(diǎn)中字符為當(dāng)前*p的字符值*/ p++; }} returnq;}boolOutPrint(Link_TreeNodep,FILE*fp)/*遞歸將指針p所指的結(jié)點(diǎn)的指針數(shù)組所指向的所有單詞寫入文件中*/{ intk; chartemp; Link_TreeNodeq; for(k=0;k<26;)/*掃描26個(gè)指針*/ { 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))/*逐個(gè)將T棧中元素彈入S棧中*/ { tempp[0]=pop(T); tempp[1]='\0'; strcat(shuzu,tempp); push(S,tempp[0]); } fprintf(fp,"%s\n",shuzu);/*將出現(xiàn)的該單詞寫入文件中*/ } OutPrint(q,fp);/*遞歸調(diào)用*/ pop(S);k++; } } if(k==26) returntrue;/*沒(méi)有后繼指針*/}voidRECHANGE_MIN(chartepp[],intcunt)/*數(shù)組中保存的十個(gè)最大的單詞*/{ 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所指的結(jié)點(diǎn)的指針數(shù)組所指向的所有單詞中出現(xiàn)次數(shù)最高的十個(gè)單詞*/{ intk; chartemp; Link_TreeNodeq; for(k=0;k<26;)/*掃描26個(gè)指針*/ { 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()/*創(chuàng)建一個(gè)文件型的數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)，并返回指向該節(jié)點(diǎn)的指針*/{ 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()/*讀入文件，創(chuàng)建文件樹*/{ 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')/*處理每個(gè)單詞*/ { 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，不存在時(shí)返回次數(shù)為0，存在返回其出現(xiàn)的次數(shù)*/{ intcount,ctmp; char*p; p=str; Link_DocumentNodeq; q=root; while(*p!='\0')/*逐個(gè)掃描該字符串中的每個(gè)字符*/ { 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()/*對(duì)出現(xiàn)頻率最高的十個(gè)單詞從大到小排序*/{ 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++) {/*掃描兩個(gè)單詞*/ 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)/*掃描第一個(gè)單詞的情況*/ { head=pt; tempary=head; } else/*掃描第二個(gè)單詞的情況*/ { 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;/*對(duì)指針進(jìn)行初始化*/ 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;/*文件樹掃描結(jié)束*/ for(i=1,point=head->next;i<=length;i++) {/*逐個(gè)掃描從文件中讀入的n個(gè)字符串*/ p=point->strr;/*指向當(dāng)前掃描的該字符串的首地址*/ q=ROOT[circle];/*q指向第circle個(gè)文件數(shù)*/ while(*p!='\0') { ctmp=*p-97; if(q->pt[ctmp]==NULL) gotonextcircle; else {/*存在時(shí)繼續(xù)在文件樹中掃描直到該單詞的結(jié)尾*/ 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;/*掃描該字符串的下一個(gè)單詞*/ } if(list1->next!=NULL) { fprintf(fp,"%d",circle); } list2->next=NULL; }//circle }voidOPEN_SearchWordInVocabulary()/*生成SearchWordInVocabulary_Result.txt*/{FILE*fp1;FILE*fp2;charstr[35];intcount;/*存放查找該單詞時(shí)出現(xiàn)的次數(shù)*/intk=1;intjieshu;/*結(jié)束判斷的標(biāo)志*/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);/*文件讀取結(jié)束的標(biāo)志*/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);/*讀入一個(gè)單詞*/ while(jieshu!=-1) { fprintf(fp2,"%s%d:\n","CASE",k); k++; p_link=Get_Last_Link(str);/*找到在單詞樹中指向該單詞最后一個(gè)字符的指針*/ if(p_link!=NULL) { fprintf(fp2,"%s\n",str); OutPrint(p_link,fp2); }jieshu=fscanf(fp1,"%s",str);/*從文件中讀入下一個(gè)單詞*/ } 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);/*從文件中讀入一個(gè)該單詞*/ 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);