编程珠玑第十五章

一、单词1>.将几百本书作为输入，通过一个程序，使得输出为书中包含实现方法：可以使用C++标准模板库中的sets2>.接着上面的问题，统计每个出现的单词的个数实现1：使用C++标准模板库中的map将整数计数与每个单实现方法2：用C语言实现，采用哈希表的数据结构数据结#defineNHASH //中有29131个单词，采用29131最近的质数作为哈希表的typedefstruct{char*word;intcount;structhashpHash实现源码如代码1中所示 temp->word=(char*)malloc(sizeof(char)*(strlen(p)+ strcpy(temp-temp->word=strdup(p);//这样代码优没增加一个没有的单词就要malloc一次，而调用malloc会申请的空间，这样就造成了内存空间的浪费，而且速度也使用，等使用完了之后，再申请。源码如代码2所示问题：找出一个长字符串中最长的重复子字符如”canidoforyouyycanidoforyou”,的最长重复子字符串为：canidoforyou如”aaabbbbbccc”的最长重复子字符串解决方法用两个循环不断的查解决方法2：把全部字符放到数组c中，然后申请一个指针数组，每个指针序后查找相邻数组的指针指向的字符串里面重复的字符printf("%.*s\n",maxlen,a[maxi只输出a[maxi字符串中前maxlen个字符源码见代码4所示一．基于字k个字母的随6二．基于单以得到更加令人感的文本；{{0阶、17k阶随机文本2源源代码#include<stdio.h>#include<stdlib.h>#include#defineNHASH //中有29131个单词，采用29131最近的质数作为哈希表的typedefstructchar*word;intcount;structhashpHashunsignedintHash(char*p);voidinword(char*p);int{intcharbuf[100];pHashp;for(i=0;i<NHASH;i++)//先初始化，为后面判断做准备,试了，bin[i]={}for(i=0;i<{

if(bin[i]!={for(p=bin[i];p!=NULL;p=p-{printf("%s %d\n",p->word,p-}}}return}{unsignedinth=1;pHashtemp;h=for(temp=bin[h];temp!=NULL;temp=temp-{if(strcmp(p,temp->word)==}} 下面的一定要放到for外temp=(structhash*)malloc(sizeof(structtemp->word=(char*)malloc(sizeof(char)*(strlen(p)+1));//因为结构体中定义的是char*wordstructhash时没有申请大小，word使用的时候必须自己申请内存空间temp->count=1;temp->next=bin[h];bin[h]=temp;}unsignedintHash(char{unsignedinth=0;for(;*p{h=h*MULT+}h=return}代码2：#include<stdio.h>#include#include#defineN_MAX#defineS_MAX#defineNHASH //中有29131个单词，采用29131最近的质数作为哈希表的typedefstruct{char*word;intcount;structhashpHashbin[NHASH];intnmalloc_size=0;intsmalloc_size=structhash*nmalloc_address;char*smalloc_address;structhash*nmalloc(void);char*smalloc(intn);unsignedintHash(char*p);voidinword(char*p);int{intcharbuf[100];pHashp;for(i=0;i<NHASH;i++)//先初始化，为后面判断做准备,试了，bin[i]={}for(i=0;i<{

if(bin[i]!={for(p=bin[i];p!=NULL;p=p-{printf("%s %d\n",p->word,p-}}}return}{unsignedinth=1;pHashtemp;h=for(temp=bin[h];temp!=NULL;temp=temp-{if(strcmp(p,temp->word)=={}} 下面的一定要放到for外 temp=(structhash*)malloc(sizeof(struct//temp->word=(char*)malloc(sizeof(char)*(strlen(p)+1));//因为结构体中定义的是char*wordstructhash时没有申请大小，word使用的时候必须自己申请内存空间temp=temp->word=temp->count=1;temp->next=bin[h];bin[h]=temp;}unsignedintHash(char{unsignedinth=0;for(;*p{h=h*MULT+}h=return}structhash*{{}

nmalloc_address=(structnmalloc_size=nmalloc_size--return}char*smalloc(int{if(smalloc_size<{smalloc_address=(char*)malloc(S_MAX);smalloc_size=S_MAX;}smalloc_size-=n;smalloc_address+=n;return(smalloc_address-}代码#include<stdlib.h>#include<string.h>#include<stdio.h>intcomlen(char*p,char*q)//返回两个参数共同部分的 inti=while(*p&&(*p++==*q++))return}int{inti,j,maxi,maxj;intmaxlen=-1;intthislen;char{{ { printf("maxi=%d,maxj=}}}for(i=maxi;i<maxi+maxlen;++i打印出该字符串return0;}代码#include<stdlib.h>#include<string.h>#include<stdio.h>intpstrcmp(char**p,char{returnstrcmp(*p,*q);}//只能比较字符串,两个字符串自左向右逐个字符相比（按ASCII值大小相比较，直到出现不同的字符intcomlen(char*p,char*q)//返回两个参数共同部分的 inti=while(*p&&(*p++==*q++))return}#defineM1#defineMAXNcharc[MAXN],*a[MAXN];//a为指针数组，每个数组都是一个int inti,ch,n=0,maxi,maxlen=-1;while((ch=getchar())!='\n'){a[n]=&c[n];c[n++]=ch;}c[n]=qsort(a,nsizeof(char*pstrcmp);//快速排序for(i=0;i<n-M;i++)if(comlen(a[i],a[i+M])>maxlen){//比较相邻字符串相个maxlen=comlen(a[i],a[i+M]);maxi=i;}printf("%.*s\n",maxlen,a[maxi]);return0;}代码/*Copyright(C)2000Lucent/*Modifiedfrommarkov.cin'ProgrammingPearls'byJonBentley/*markovlet.c--generateletter-levelrandomtextfrominputtextAlg:StoretextinanarrayoninputScancompletetextforeachoutputcharacter(Randomlyselectonematchingk-gram)#include<stdio.h>char int intc,i,eqsofar,max,n=0,k=5;char*p,*nextp,*q;while((c=getchar())!={x[n++]=}x[n]=p=x;for(max=2000;max>0;max--{eqsofar=for(q=x;q<x+n-k+1;{for(i=0;i<k&&*(p+i)==*(q+i);;if(i=={if(rand()%++eqsofar=={nextp=}}}c=*(nextp+k);if(c==0){}p=nextp+1;}return}代码6：#include<stdio.h>#include#include<string.h>#include<time.h>charinputchars[ char*word[800000];intnword=0;intk=2;intwordncmp(char*p,char*{intn=for(;*p==*q;p++,{if(*p==0&&--n==0)return0;}return*p-}intsortcmp(char**p,char{}char*skip(char*p,int for(;n>0;{if(*p==n--}return}int{inti,wordsleft=10000,l,m,u;char*phrase,*p;word[0]=inputchars;//这个很重要，因为word是指针，不能直接赋值，而inputchar是数组，申请了空间的，可以直接赋值，而这句话的意word指向数组inputchar的首地址，这样就可以赋值了，相当于所有的输入都到inputchar中了while(scanf("%s",word[nword])!={word[nword+1]=word[nword]+strlen(word[nword])+1;}for(i=0;i<k;word[nword][i0;//word数组后面加k个空字符，这样比较函数wordncmp就不会允许到最后了。for(i=0;i<k;i++)//输出排序之前k个单词,这很重要，k 的关键printf("%s\n",qsort(word,nword,sizeof(word[0]),sortcmp);//调用数组的地址变换了，不再与inputchars对应了for(i=0;i<nword;i++)//输出排序之后的所有单词 phrase=forwordsleft0wordsleftwordsleft是最多输出单词的{l=-u=whilel+1u找到和phrase一样的单词{m=(l+u)/if(wordncmp(word[m],phrase)<0)l=m;u=}//在与word【u】邻近的一样的单词中等概率的选一个出来，前提是该单词也是k连for(i=0;wordncmp(phrase,word[u+i])==0;{if(rand()%(i+1)=={p=}}//即如果输入aabbaakkaaccaaffaaddaaee，则，i最多只能输出1，p=word[u]，不可能出现p=word[u+1]的情况，因为首先输出的是aabbaa中任意选一个（前提aa之后也要有bb，