{
t.tail->next=s.head;
t.tail=s.tail; //把s连接在t的后面 } else {
q=p->next;
r=(Chunk*)malloc(sizeof(Chunk)); //将包含字符c的节点p分裂为两个 for(j=0;j r->ch[j]=p->ch[j]; p->ch[j]='#'; //p的后半部分和r的前半部分的字符改为无效字符'#' } p->next=s.head; s.tail->next=r; r->next=q; //把串s插入到结点p和r之间 }//else t.curlen+=s.curlen; //修改串长 s.curlen=0; }//LString_Concat int Find_Char(Chunk *p,char c)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0 { for(i=0;i int LString_Palindrome(LString L)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0 { InitStack(S); p=S.head;i=0;k=1; //i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++) { if(k<=S.curlen/2) Push(S,p->ch[i]); //将前半段的字符入串 else if(k>(S.curlen+1)/2) { Pop(S,c); //将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c) return 0; //失配 } if(++i==CHUNKSIZE) //转到下一个元素,当为块中最后一个元素时,转到下一块 { p=p->next; i=0; } }//for return 1; //成功匹配 }//LString_Palindrome 4.24 void HString_Concat(HString s1,HString s2,HString &t)//将堆结构表示的串s1和s2连接为新串t { if(t.ch) free(t.ch); t.ch=malloc((s1.length+s2.length)*sizeof(char)); for(i=1;i<=s1.length;i++) t.ch[i-1]=s1.ch[i-1]; for(j=1;j<=s2.length;j++,i++) t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length; }//HString_Concat 4.25 int HString_Replace(HString &S,HString T,HString V)//堆结构串上的置换操作,返回置换次数 { for(n=0,i=0;i<=S.length-T.length;i++) { for(j=i,k=0;k { if(T.length==V.length) for(l=1;l<=T.length;l++) //新子串长度与原子串相同时:直接替换 S.ch[i+l-1]=V.ch[l-1]; else if(T.length for(l=S.length-1;l>=i+T.length;l--) S.ch[l+V.length-T.length]=S.ch[l]; for(l=0;l else //新子串长度小于原子串时:先将后部左移 { for(l=i+V.length;l S.length+=V.length-T.length; i+=V.length;n++; }//if }//for return n; }//HString_Replace 4.26 Status HString_Insert(HString &S,int pos,HString T)//把T插入堆结构表示的串S的第pos个字符之前 { if(pos<1) return ERROR; if(pos>S.length) pos=S.length+1;//当插入位置大于串长时,看作添加在串尾 S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char)); for(i=S.length-1;i>=pos-1;i--) S.ch[i+T.length]=S.ch[i]; //后移为插入字符串让出位置 for(i=0;i S.ch[pos+i-1]=T.ch[pos]; //插入串T S.length+=T.length; return OK; }//HString_Insert 4.27 int Index_New(Stringtype s,Stringtype t)//改进的定位算法 { i=1;j=1; while(i<=s[0]&&j<=t[0]) { if((j!=1&&s[i]==t[j])||(j==1&&s[i]==t[j]&&s[i+t[0]-1]==t[t[0]])) { //当j==1即匹配模式串的第一个字符时,需同时匹配其最后一个 i=i+j-2; j=1; } else { i++;j++; } }//while if(j>t[0]) return i-t[0]; }//Index_New 4.28 void LGet_next(LString &T)//链串上的get_next算法 { p=T->succ;p->next=T;q=T; while(p->succ) { if(q==T||p->data==q->data) { p=p->succ;q=q->succ; p->next=q; } else q=q->next; }//while }//LGet_next 4.29 LStrNode * LIndex_KMP(LString S,LString T,LStrNode *pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针 { p=pos;q=T->succ; while(p&&q) { if(q==T||p->chdata==q->chdata) { p=p->succ; q=q->succ; } else q=q->next; }//while if(!q) { for(i=1;i<=Strlen(T);i++) p=p->next; return p; } //发现匹配后,要往回找子串的头 return NULL; }//LIndex_KMP 4.30 void Get_LRepSub(Stringtype S)//求S的最长重复子串的位置和长度 { for(maxlen=0,i=1;i for(k=0,j=1;j<=S[0]-i;j++)//j为串S2的当前指针,此时串S1的当前指针为i+j,两指针同步移动 { if(S[j]==S[j+i]) k++; //用k记录连续相同的字符数 else k=0; //失配时k归零 if(k>maxlen) //发现了比以前发现的更长的重复子串 { lrs1=j-k+1;lrs2=mrs1+i;maxlen=k; //作记录 } }//for }//for if(maxlen) { printf(\ printf(\ } else printf(\}//Get_LRepSub 分析:i代表\错位值\本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明\重复子串\是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2). 4.31 void Get_LPubSub(Stringtype S,Stringtype T)//求串S和串T的最长公共子串位置和长度 { if(S[0]>=T[0]) { StrAssign(A,S);StrAssign(B,T); } else { StrAssign(A,T);StrAssign(B,S); } //为简化设计,令S和T中较长的那个为A,较短的那个为B for(maxlen=0,i=1-B[0];i if(i<0) //i为B相对于A的错位值,向左为负,左端对齐为0,向右为正 { jmin=1;jmax=i+B[0]; }//B有一部分在A左端的左边 else if(i>A[0]-B[0]) { jmin=i;jmax=A[0]; }//B有一部分在A右端的右边 else { jmin=i;jmax=i+B[0]; }//B在A左右两端之间. //以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax. for(k=0,j=jmin;j<=jmax;j++) { if(A[j]==B[j-i]) k++; else k=0; if(k>maxlen) { lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for if(maxlen) { if(S[0]>=T[0]) { lpsS=lps1;lpsT=lps2; } else { lpsS=lps2;lpsT=lps1; } //将A,B上的位置映射回S,T上的位置 printf(\ printf(\ }//if else printf(\}//Get_LPubSub 分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。 第五章 数组和广义表 5.18 void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间 { for(i=1;i<=k;i++) if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p for(i=0;i j=i;l=(i+k)%n;temp=A[i]; while(l!=i) { A[j]=temp; temp=A[l]; A[l]=A[j]; j=l;l=(j+k)%n; }// 循环右移一步 A[i]=temp; }//for }//RSh 分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个\循环链\上面.举例如下: n=15,k=6,则p=3. 第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. 第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1]. 第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2]. 恰好使所有元素都右移一次. 虽然未经数学证明,但作者相信上述规律应该是正确的. 5.19 void Get_Saddle(int A[m][n])//求矩阵A中的马鞍点 { for(i=0;i for(min=A[i][0],j=0;j if(A[i][j] if(A[i][j]==min) //判断这个(些)最小值是否鞍点 { for(flag=1,k=0;k }//Get_Saddle 5.20 本题难度极大,故仅探讨一下思路.这一题的难点在于,在多项式的元数m未知的情况下,如何按照降幂次序输出各项.可以考虑采取类似于层序遍历的思想,从最高次的项开始,依次对其每一元的次数减一,入一个队列.附设访问标志visited以避免重复. 5.21 void TSMatrix_Add(TSMatrix A,TSMatrix B,TSMatrix &C)//三元组表示的稀疏矩阵加法 { C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; for(x=1;x<=A.mu;x++) //对矩阵的每一行进行加法 { while(A.data[pa].i while(A.data[pa].i==x&&B.data[pb].i==x)//行列值都相等的元素 { if(A.data[pa].j==B.data[pb].j) { ce=A.data[pa].e+B.data[pb].e; if(ce) //和不为0 { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=ce; pa++;pb++;pc++; } }//if else if(A.data[pa].j>B.data[pb].j) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x) //插入A中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } while(B.data[pb]==x) //插入B中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc; }//TSMatrix_Add 5.22