【正文】 panext=Cnext。 pa=r。 // 保留后繼結(jié)點的指針 pbnext=Cnext。 pb=r。//釋放B表頭結(jié)點} // 算法結(jié)束 9 void deleteprior(linklist *L)// 長度大于1的單循環(huán)鏈表，既無頭結(jié)點，也無頭指針，本算法刪除*s 的前驅(qū)結(jié)點{ linklist *p=snext,*pre=s。 p=pnext。 free(p)。2本算法//將A表分成 // 三個帶頭結(jié)點的循環(huán)單鏈表A、B和C，分別含有字母、數(shù)字和其它符號的同一類字符，利用原表空間。// p為工作指針，指向A表的當前元素，r為當前元素的后繼指針,使表避免斷開。 B=(linklist *)malloc(sizeof(linklist))。 // 準備循環(huán)鏈表的頭結(jié)點 C=(linklist *)malloc(sizeof(linklist))。 // 準備循環(huán)鏈表的頭結(jié)點 while(p) { r=pnext。amp。amp。 Anext=p。amp。 Bnext=p。 Cnext=p。 // 恢復(fù)后繼結(jié)點的指針 }//while} // 算法結(jié)束 2{ linklist *p=Lnext,*q。 while (p amp。 pdata !=x) p=pnext。 if (!p) return (“不存在值為x的結(jié)點”)。 // 令元素值為x的結(jié)點的freq域加1 。 // 將p結(jié)點從鏈表上摘下。q=pprior。amp。 pnext=qnext。// 將p結(jié)點插入 pprior=q。 1 2 3 4 2 1 3 4 3 2 1 4 4 3 2 11 2 4 3 2 1 4 3 3 2 4 1 1 3 2 4 2 3 1 4 3 4 2 11 3 4 2 2 3 4 1 1 4 3 2 2 4 3 1 設(shè)入棧序列元素數(shù)為n，則可能的出棧序列數(shù)為C2nn=(1/n+1)*(2n!/(n!)2) 證明：由jk和pjpk 說明pj在pk之前出棧，即在k未進棧之前pj已出棧，之后k進棧，然后pk出棧；由jk和pjpk 說明pj在pk之后出棧，即pj被pk 壓在下面，后進先出。也就是說，若有1，2，3順序入棧，不可能有3，1，2的出棧序列。 linklist *p=headnext。 p=pnext。// 奇數(shù)個結(jié)點時跳過中心結(jié)點 while (p amp。 pdata==pop(s)) p=pnext。//初始化棧s scanf(“%c”,amp。 while (ch!=’’) //’’是表達式輸入結(jié)束符號switch (ch) { case ’(’: push(s,ch)。 case ’)’: if (empty(s)) {printf(“括號不配對”)。} pop(s)。 else printf(“括號配對”)。typedef struct // 兩棧共享一向量空間 { ElemType v[m]。// 棧滿 else {switch (i) {case 0: sv[++(stop)]=x。 case 1: sv[(stop)]=x。 default: printf(“棧編號輸入錯誤”)。 } return(1)。if (i!=0 amp。 i!=1) return(0)。//?？誩lse x=sv[stop]。 case 1: if(stop[1]==m) return(0)。 break。return(0)。 // 退棧成功 }} // 算法結(jié)束 switch (i) {case 0: if(stop[0]==1) return(0)。 break。//?？誩lse x=sv[stop]。 default: printf(“棧編號輸入錯誤”)。 } return(x)。3．6void Ackerman(int m,int n) // Ackerman 函數(shù)的遞歸算法 { if (m==0) return(n+1)。amp。else return(Ackerman(m1,Ackerman(m,n1))} // 算法結(jié)束 //申請空間，不判斷空間溢出qnext=q。} // 算法結(jié)束 (2) linklist *enqueue(linklist *q，ElemType x)// q是以帶頭結(jié)點的循環(huán)鏈表表示的隊列的尾指針，本算法將元素x入隊{ s=(linklist *)malloc(sizeof(linklist))。 // 將元素結(jié)點s入隊列 qnext=s。 // 修改隊尾指針 return (q)。 // 判斷隊列是否為空 else {linklist *s=qnextnext。 // 若隊列中只一個元素，置空隊列else qnextnext=snext。 // 釋放出隊結(jié)點 }return (q)。算法并未返回出隊元素 // 循環(huán)隊列占m個存儲單元 int front,rear。 int queuelength(sequeue *cq) // cq為循環(huán)隊列，本算法計算其長度 { return (cqrear cqfront + m) % m。 typedef struct{ElemType sequ[m]。 // rear指向隊尾元素,quelen為元素個數(shù)}sequeue。} // 算法結(jié)束 (2) sequeue *enqueue(sequeue *cq，ElemType x)// cq是如上定義的循環(huán)隊列，本算法將元素x入隊{if (cqquelen==m) return(0)。 // 計算插入元素位置 cqsequ[cqrear]=x。 // 修改隊列長度 }return (cq)。 // 隊空 else { int front=(cqrear cqquelen + 1+m) % m。 // 修改隊列長度 return (cqsequ[front])。在以下習題解答中，假定使用如下類型定義：define MAXSIZE 1024typedef struct{ char data[MAXSIZE]。 // curlen表示終端結(jié)點在向量中的位置 }seqstring。typedef struct node{char data。 n=length(t)。 while(i=mn+1) if(strcmp(substr(s,i,n),t)==0) break。if(i=mn+1) return(i)。//s串中無子串t}//算法index結(jié)束 設(shè)A=” ”, B=”mule”, C=”old”, D=”my” 則：（a） （a） strcat（A,B）=”mule”（b） （b） strcat(B,A)=”mule”（c） （c） strcat(strcat(D,C),B)=”myoldmule”（d） （d） substr(B,3,2)=”le”（e） （e） substr(C,1,0)=” ”（f） （f） char search(linkstring *X, linkstring *Y)// X和Y是用帶頭結(jié)點的結(jié)點大小為1的單鏈表表示的串，本算法查找X中 第一個不在Y中出現(xiàn)的字符。{ linkstring *p, *q,*pre。 q=Ynext。 while (p amp。 q) { ch=pdata。amp。 // 和Y中字符比較 if (!q) return(ch)。 // 上一字符在Y中存在， p=pre。 q=Ynext。 // X中字符在Y中均存在 }// 算法結(jié)束 while (sch[i]!=’\0’ amp。 tch[i]!=’\0’) if (sch[i]tch[i]) return(1)。 else i++。amp。else if (sch[i]==’\0’amp。 tch[i]!=0) return(1)。}// 算法結(jié)束 linkstring *invert(linkstring *S, linkstring *T)// S和T是用帶頭結(jié)點的結(jié)點大小為1的單鏈表表示的串，S是主串，T是// 模式串。如模式匹// 配成功，則將S中的子串（T串）逆置。 pre=S。 tp=Tnext。amp。 tp=tpnext。 sp=prenext。}if (tp!=null) return (null)。 // tp是逆置的工作指針，現(xiàn)在指向待逆置的第一個字符prenext=sp。 tpnext=prenext。 tp=r } }}// 算法結(jié)束 第五章 多維數(shù)組和廣義表（參考答案） A[2][3][2][3]A0000 , A0001 , A0002 A0010 , A0011 , A0012 A0100 , A0101 , A0102 A0110 , A0111 , A0112 A0200 , A0201 , A0202 A0210 , A0211 , A0212 將第一維的0變?yōu)?后，可列出另外18個元素。 設(shè)各維上下號為c1…d1，c2…d2，c3…d3，每個元素占l個單元。 // a是m行n列的二維數(shù)組,本算法求所有馬鞍點 // b是一維數(shù)組,存放一行中可能的馬鞍點的列值,k記相等值個數(shù) // c是一維數(shù)組,存放某列可能馬鞍點的行值,kk記相等值個數(shù) {for(i=0。i++) {min=a[i,0]。 k=1。jn。 min=a[i][j]。}// 重新確定最小值 else if (a[i][j]==min) {b[k+1]=j。} // 有相等的最小值 for (jj=0。k++) // 第i 行有k個相等的最小值 {j=b[jj]。 kk=0。amp。 if(kk=m)printf(“馬鞍點 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j])。for (i=0。i++) {row[i]=a[i][0]。jn。 // 重新確定最小值 }for (j=0。j++) {col[j]=a[0,j]。im。 // 重新確定最大值 }for (i=0。i++) for (j=1。j++)if(row[i]==col[j])printf(“馬鞍點 i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j])。 // a是m行n列的二維數(shù)組,本算法求所有馬鞍點 { int max[]=0,min[]=0。im。 im。 jn。 // 重新確定第j列最大值的行號if (A[i][j]A[i][min[i]]) min[i]=j。im。 // a[i][j]是否是馬鞍點 if( max[j]==i) printf(“馬鞍點 A[%d][%d]=%d”,i,j,a[i][j])。在（3）種情況下，要看結(jié)果是否為0，C矩陣只有非零元素。cb=Bnext。amp。pb=cbright。//A表在該行無非0元素； else if(pb==cb)cb=cbnext//B表在該行無非0元素； else if(pbcolpacol)//B的非0元素插入A中； {j=pbcol。pre=pt// 取到表頭指針； while(ptdown_colpbcol) {pre=pt。} predown=ptdown。pt=chb[i]。//取B表行表頭指針 while(ptrightrowpbrow {pre=pt。}