程序员实用算法
看过《程序员实用算法》的前辈看过来啊。请指点指点小弟啊。按照书上的源码抄袭了一遍。可是为什么就不能正确的运行呢？？？这让我狠是纠结啊。和书本上的代码比对了N遍了，都没有发觉有任何的笔误啊。可就是不正确。请教前辈啊，这段代码是怎么回事啊。谁能够帮忙调试出正确的结果啊。我头都大了啊。如果没有看过这书的大牛也可以帮忙看下啊。提供个书的下载地址啦。http://ishare.iask.sina.com.cn/f/13043320.html?from=dl
各位大大们，小弟先在此谢过啦。如果觉得分不够，解决问题后继续追加。上代码。
#include "stdafx.h"#define DRIVER 1#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXCHAR 256/*linked list of keyword to search for.*/struct kword{ unsigned char *word; struct kword *next;};//#define MAXCHAR 256//max number of states we have room forstatic int MaxState;/*First level of matching.Possible value:(1) EMPTY_SLOT -2(2) a character(3) MULTI_WAY -1*/static int *MatchArray;#define EMPTY_SLOT -2#define MULTI_WAY -1union GotoTable{ int GotoState; int *BranchTable;}static *GotoArrary;#define FAIL_STATE -1static struct kword **OutArrary;static int *FailArrary;static int HighState;static void AddStateTrans(int ,int ,int);static void ComputeFail(void);static void Enter(unsigned char*);static void FindFail(int ,int ,int);static void QueueAdd(int* nQueue,int qbeg,int newer);void MsrchInit(struct kword *klist){ int i; struct kword *ktemp; //compute maximum number of possible states MaxState = 1; for (ktemp=klist;ktemp != NULL;ktemp=ktemp->next) { MaxState += strlen((char*)ktemp->word); } //allocate memory for arrays MatchArray = (int *) malloc(sizeof(int)*MaxState); GotoArrary = (union GotoTable *) malloc(sizeof(union GotoTable)*MaxState); OutArrary = (struct kword **)malloc(sizeof(struct kword*)*MaxState); FailArrary = (int *)malloc(sizeof(int)*MaxState); //initialize states array for (i=0;i<MaxState;++i) { MatchArray[i] = EMPTY_SLOT; OutArrary[i] = NULL; } //initialize state_array[0] HighState = 0; AddStateTrans(0,'a',FAIL_STATE); //force a multiway table AddStateTrans(0,'b',FAIL_STATE); //step through keywords for (;klist != NULL;klist = klist->next) { Enter(klist->word); } //setup return to zero transitions for state[0] for (i=0;i<MAXCHAR;++i) { if (GotoArrary[0].BranchTable[i]==FAIL_STATE) { GotoArrary[0].BranchTable[i]=0; } } //compute failure array ComputeFail();}/*add transition from oldState --> NewState for MatchChar*/static void AddStateTrans(int oldState,int MatchChar,int NewState){ int i,*temp; //is this slot empty ?? if (MatchArray[oldState] == EMPTY_SLOT) { MatchArray[oldState]=MatchChar; GotoArrary[oldState].GotoState = NewState; } //is there already a multi-way table ? else { if (MatchArray[oldState]==MULTI_WAY) { GotoArrary[oldState].BranchTable[MatchChar] = NewState; } else {//need to convert to multi-way table temp = (int*) malloc(sizeof(int)*MAXCHAR); for (i=0;i<MAXCHAR;++i) { temp[i]=FAIL_STATE; } temp[MatchArray[oldState]] = GotoArrary[oldState].GotoState; temp[MatchChar] = NewState; MatchArray[oldState] = MULTI_WAY; GotoArrary[oldState].BranchTable = temp; } }}/*add keyword to list of words our machine recognizes*/static void Enter(unsigned char *keyword){ int state , k; char* save; struct kword *ktemp; state = 0; save =(char*) keyword; /* first , see whether we can place this word on top of an existing one */ for (;*keyword != '\0';keyword++) { if (MatchArray[state] == *keyword) { state = GotoArrary[state].GotoState; } else if (MatchArray[state]==MULTI_WAY) { if((k=GotoArrary[state].BranchTable[*keyword]) == FAIL_STATE) break; else state = k; } else break; } //now add new state as needed for ( ; *keyword !='\0';keyword++) { HighState += 1; if (HighState >= MaxState) { fputs("INTERNAL ERROR: too many states\n",stderr); exit(EXIT_FAILURE); } AddStateTrans(state,*keyword,HighState); state = HighState; } // now add this keyword to output list for final state ktemp = (struct kword *)malloc(sizeof(struct kword)); ktemp->word =(unsigned char*) save; ktemp->next = OutArrary[state]; OutArrary[state] = ktemp;}/* build FailArray and update GotoArray*/static void ComputeFail(){ int *Queue,qbeg,r,s; int i; Queue = (int *)malloc(sizeof(int)*MaxState); qbeg = 0; Queue[0] = 0; /* scan first level and setup initial values for FailArray */ for (i=0;i<MAXCHAR;++i) if ((s = GotoArrary[0].BranchTable[i])!=0) { FailArrary[s] =0; QueueAdd(Queue,qbeg,s); } /* now scan lower levels */ while(Queue[qbeg] !=0) { /* pull off state from front of Queue and advance qbeg */ r = Queue[qbeg]; qbeg = r; //now investigate this state if (MatchArray[r] == EMPTY_SLOT) continue; else if (MatchArray[r] == MULTI_WAY) { for(i=0;i<MAXCHAR;++i) if((s=GotoArrary[r].BranchTable[i]) != FAIL_STATE) { QueueAdd(Queue,qbeg,s); FindFail(FailArrary[r],s,i); } } else { QueueAdd(Queue,qbeg,GotoArrary[r].GotoState); FindFail(FailArrary[r],GotoArrary[r].GotoState,MatchArray[r]); } } free(Queue);}/*--------------------*Actually compute failure transition. We know that 'a'*would normally cause us to go from state s1 to s2.*To compute the faulure value, we backtrack in search* of other places 'a' might go.*---------------------*/static void FindFail(int s1, int s2,int a){ int on_fail; struct kword *ktemp,kdummy,*out_copy,*kscan; for (;;s1= FailArrary[s1]) if(MatchArray[s1]==a) { if((on_fail = GotoArrary[s1].GotoState) != FAIL_STATE) break; } else if(MatchArray[s1] != EMPTY_SLOT) if((on_fail = GotoArrary[s1].BranchTable[a]) != FAIL_STATE) break; FailArrary[s2] = on_fail; if(OutArrary[on_fail]==NULL) out_copy = NULL; else { kscan = OutArrary[on_fail]; out_copy = (struct kword*)malloc(sizeof(struct kword)); out_copy->word = kscan->word; out_copy->next = NULL; for (kscan=kscan->next;kscan!=NULL;kscan = kscan->next) { ktemp = (struct kword*)malloc(sizeof(struct kword)); ktemp->word = kscan->word; ktemp->next = out_copy->next; out_copy->next = ktemp; } } if ((kdummy.next=OutArrary[s2])!=NULL) { ktemp = &kdummy; for(;ktemp->next->next != NULL;ktemp = kdummy.next) ; ktemp->next->next = out_copy; } else OutArrary[s2] = out_copy;}/************************************************************************//* add newer to the end of Queue *//************************************************************************/static void QueueAdd(int* nQueue,int qbeg,int newer){ int q; q = nQueue[qbeg]; if(q==0) nQueue[qbeg] = newer; else { for(;nQueue[q]!=0;q= nQueue[q]) ; nQueue[q] = newer; } nQueue[newer] = 0;}/************************************************************************//* do the actual search *//************************************************************************/void MsrchGo(int (*MsrchData)(),void (*MsrchSignal)(char *)){ int state,c,g,m; struct kword *kscan; state = 0; while((c=MsrchData())!=EOF) { for(;;) { /************************************************************************/ /* we cheat slightly in the interest of speed/simplicity.The machine will*/ /* spend most of its time in state==0 , and this state is always a MULTI_WAY */ /* table .Since this is a simple test , we make it first and try to save the */ /* calcalation of an array index */ /************************************************************************/ if(state==0 || (m = MatchArray[state])==MULTI_WAY) g = GotoArrary[state].BranchTable[c]; else { if(m==c) g = GotoArrary[state].GotoState; else g = FAIL_STATE; } if(g != FAIL_STATE) break; state = FailArrary[state]; } state = g; if((kscan = OutArrary[state])!=NULL) for(;kscan!=NULL;kscan=kscan->next) MsrchSignal((char*)kscan->word); }}/************************************************************************//* At the end of program , we should free the memory we malloc. *//************************************************************************/void MsrchEnd(){ int i; struct kword *kscan; for(i=0;i<MaxState;++i) if(MatchArray[i]==MULTI_WAY) free(GotoArrary[i].BranchTable); free(MatchArray); free(GotoArrary); free(FailArrary); for (i=0;i<MaxState;++i) if(OutArrary[i]!=NULL) for(kscan=OutArrary[i];kscan!=NULL;kscan=kscan->next) free(kscan); free(OutArrary);}
//将c:\\tmp文件夹下的所有文件的内容全部放到用malloc分配的内存中#include <stdio.h>#include <stdlib.h>#include <string.h>#include <io.h>struct FB { char fn[256]; size_t fl; char *b; struct FB *next; struct FB *prev;} *fh,*fb,*ft;char ln[256];char fpn[256];FILE *af;FILE *f;int L,n;int main() { system("dir /b /a-d c:\\tmp\\*.* >c:\\allfn.txt"); af=fopen("c:\\allfn.txt","r"); if (NULL==af) { printf("Can not open file c:\\allfn.txt!\n"); return 1; } fh=NULL; fb=NULL; n=0; while (1) { if (NULL==fgets(ln,256,af)) break; L=strlen(ln); if ('\n'==ln[L-1]) ln[L-1]=0; printf("read %s\n",ln); strcpy(fpn,"c:\\tmp\\"); strcat(fpn,ln); ft=(struct FB *)malloc(sizeof(struct FB)); if (NULL==ft) { printf("Can not malloc ft!\n"); fclose(af); return 2;//之前的malloc在main退出后由操作系统自动free } printf("ft[%d]==%p\n",n,ft); strcpy(ft->fn,fpn); f=fopen(fpn,"rb"); if (NULL==f) { printf("Can not open file %s!\n",fpn); fclose(af); return 3;//之前的malloc在main退出后由操作系统自动free } ft->fl=_filelength(fileno(f)); ft->b=malloc(ft->fl); if (NULL==ft->b) { printf("Can not malloc ft->b!\n"); fclose(f); fclose(af); return 4;//之前的malloc在main退出后由操作系统自动free } printf("ft[%d]->b==%p\n",n,ft->b); if (ft->fl!=fread(ft->b,1,ft->fl,f)) { printf("fread error!\n"); fclose(f); fclose(af); return 5;//之前的malloc在main退出后由操作系统自动free } fclose(f); ft->next=NULL; if (NULL==fh) { ft->prev=NULL; fh=ft; } else { fb->next=ft; ft->prev=fb; } fb=ft; n++; } fclose(af); printf("-----list-----\n"); for (ft=fh;NULL!=ft;ft=ft->next) { printf("%8d %s\n",ft->fl,ft->fn); if (NULL!=ft) fb=ft; } printf("-----free-----\n"); n--; if (NULL!=fh) { for (ft=fb->prev;NULL!=ft;ft=ft->prev) { if (NULL!=ft->next->b) { printf("ft[%d]->b==%p\n",n,ft->next->b); free(ft->next->b); } if (NULL!=ft->next) { printf("ft[%d]==%p\n",n,ft->next); free(ft->next); } n--; } if (NULL!=fh->b) { printf("ft[0]->b==%p\n",fh->b); free(fh->b); } printf("ft[0]==%p\n",fh); free(fh); } return 0;}//C:\tmp\tmp\Debug>dir /a-d c:\tmp// 驱动器 C 中的卷是 C_HD5_1// 卷的序列号是 1817-D526//// c:\tmp 的目录////找不到文件////C:\tmp\tmp\Debug>tmp//找不到文件//-----list-----//-----free-----////C:\tmp\tmp\Debug>dir /a-d c:\tmp// 驱动器 C 中的卷是 C_HD5_1// 卷的序列号是 1817-D526//// c:\tmp 的目录////2011-06-30 18:04 44,840 my_c.rar//2011-06-30 17:18 1,036 err.frm//2011-06-30 14:32 14,243 出租.txt//2011-06-28 12:08 23,681 MSDN98书签.txt// 4 个文件 83,800 字节// 0 个目录 17,041,870,848 可用字节////C:\tmp\tmp\Debug>tmp//read my_c.rar//ft[0]==00421800//ft[0]->b==00520068//read err.frm//ft[1]==00421670//ft[1]->b==0052AFC0//read 出租.txt//ft[2]==00421530//ft[2]->b==00378F28//read MSDN98书签.txt//ft[3]==004213F0//ft[3]->b==0052B3F8//-----list-----// 44840 c:\tmp\my_c.rar// 1036 c:\tmp\err.frm// 14243 c:\tmp\出租.txt// 23681 c:\tmp\MSDN98书签.txt//-----free-----//ft[3]->b==0052B3F8//ft[3]==004213F0//ft[2]->b==00378F28//ft[2]==00421530//ft[1]->b==0052AFC0//ft[1]==00421670//ft[0]->b==00520068//ft[0]==00421800////C:\tmp\tmp\Debug>
[解决办法]
调试技巧可是很关键的，试试自己动手。
[解决办法]
路过啊。貌似这么长的代码没有人愿意帮忙调试啊
[解决办法]
你是不是没有这个包含命令（#include "stdafx.h"）中的"stdafx.h"用户定义的头文件啊？你确定自己定义了吗？
[解决办法]
你这代码都没抄全啊 95页的代码漏了吧
MsrchGo()中传了两个关键的函数:RetrieveChar和FoundWord
在95页也给出了
[解决办法]
#include "stdafx.h" 这行可以删除的，如果你创建的是空工程的话
同意5楼。完整代码 VS2010 + Win7 下调试通过的
main函数里有行代码需略改一下：
ktemp->word = (unsigned char *)argv[i - 1]; // char* cannot be assigned to an entity of type unsigned char*