【正文】 t[M]。void main( ){int i,j,k。 y[0]=568731。 for(i=1。i801。i++){y[i]= (15625*y[i1]+22221)% m。 x[i]= 1000* y[i]/m。}for(i=0。iM。i++)t[i]= 1。 /* 因x[i]是非負(fù)數(shù)，所以初始化Hash表時(shí)t[i]全置為1*/for(i=1。i801。i++) {j= x[i]。 for(k=0。kMamp。amp。t[(j+k)%M]=0。k++)。 j=(j+k)%M。 if(t[j]0) t[j]= x[i]。 }}2） 拉鏈法 include define M 1000 define m 2 31typedef struct node{int key。 struct node* link。 }NODE。int x[801]。long int y[801]。NODE *t[M]。void main( ){int i。 NODE * p,*q,*r 。 y[0]=568731。 for(i=1。i801。i++){y[i]= (15625*y[i1]+22221)% m。 x[i]= 1000* y[i]/m。}for(i=0。iM。i++)t[i]= NULL。for(i=1。i801。i++){p=t[x[i]]。 q=NULL。 while(p!=NULL) {q=p。p=plink。}r=(NODE*)malloc(sizeof(NODE))。rkey= x[i]。rlink=NULL。if(q= =NULL) t[x[i]]=r。else qlink=r。}} 1_21求廣義表的深度。我們規(guī)定空的廣義表的深度為0，而一般的有 0 若s?是一個(gè)原子depth(s)= { 1+max(depth(a0),… depth(an1)) 若s是廣義表（a0,a1,…an1）編寫一個(gè)求解廣義表s的深度的C函數(shù)。解答： 有題目給出的深度的公式，很容易想到運(yùn)用遞歸來實(shí)現(xiàn)所要求的功能。這里在主函數(shù)中簡單的采用直接構(gòu)造各種類型的廣義表法，為了測(cè)試算深度函數(shù)的有效性。includestruct node{ int tag。 union{struct node *dlink。 char data。 }dd。 struct node *link。}。typedef struct node NODE。int depth(NODE *p){ int max,t。 if(p==NULL)return(0)。 if((ptag)==0)max=1。 else max=depth(p)+1。 t=depth(plink)。 return(tmax?t:max)。}main(){ NODE *head,*p。 int d,i。 char k=39。a39。 head=NULL。 /*(1)*/ d=depth(head)。 printf(the depth is:%d\n,d)。 head=(NODE *)malloc(sizeof(NODE))。 /*(2)*/ headtag=0。 head=k。 headlink=NULL。 p=head。 for(i=1。i4。i++){ plink=(NODE*)malloc(sizeof(NODE))。 p=plink。 ptag=0。 p=k+i。 plink=NULL。 } d=depth(head)。 printf(the depth is:%d\n,d)。 k=39。e39。 /*(3)*/ p=head。 for(i=1。i4。i++){ ptag=1。 p=(NODE*)malloc(sizeof(NODE))。 p=p。 ptag=0。 p=k。 plink=NULL。 }d=depth(head)。printf(the depth is:%d\n,d)。}在主函數(shù)中構(gòu)造了三種結(jié)構(gòu)各異的廣義表。（1） 空的廣義表，得到的深度為0。（2） 0,a,0,b0,c0,d，^ 得到的深度為1。（3） 1，↘，》0,b0,c0,d^ 得到的深度為4。 1,↘,^ 1,↘^ 0,e,^2_1假設(shè)s和t分別是具有m個(gè)和n個(gè)字符的順序存貯的串。試編寫一個(gè)在s和t中尋找最大公共子串的C函數(shù)。解答： 該題的本質(zhì)即為模式匹配，實(shí)際上是把t中所有可能長度的子串與s進(jìn)行模式匹配，從最長長度n開始，若匹配成功就直接輸出當(dāng)前子串，否則長度自減1后重新開始匹配。直到長度減為0，此時(shí)則說明沒有公共子串。下面的C函數(shù)利用了書中列出的幾個(gè)函數(shù)實(shí)現(xiàn)了題目所要求的功能。includeincludedefine MAXN 100char t[MAXN],s[MAXN]。int flink[MAXN]。int m,n。int strsub(char s1[],int i,int j,char s2[]){ int m,k。 if(i0||i=(m=strlen(s1))) return(1)。 if(j0||im) return(1)。 for(k=0。kj。k) s2[k]=s1[i]。 s2[k]=39。\039。 return(0)。}void faillink(char p[],int flink[],int m){int j,k。flink[0]=1。j=1。while(jm){ k=flink[j1]。 while(k!=1amp。amp。p[k]!=p[j1]) k=flink[k]。 flink[j]=k。 j。}}int kmp_match(char t[],char p[],int flink[],int n,int m){ int i,j。 i=0。 j=0。 while(in) { while(j!=1amp。amp。p[j]!=t[i]) j=flink[j]。 if(j==m1)return(im)。 i。 j。 }return (1)。}void search_max(char s[],char t[],int m,int n){ char temp[MAXN]。 int i,j,k。 i=n。 while(i0) { k=0。 while(k1n){ strsub(t,k,i,temp)。 faillink(temp,flink,i)。 if(kmp_match(s,temp,flink,m,i)!=1) { printf(The max match is:\n)。 for(j=0。ji。j) printf(%c ,temp[j])。 return。 } k。 } i。}printf(No match found!\n)。}main(){ printf(Input the length of S39。s string:\n)。 scanf(%d,amp。m)。 printf(Please input the S39。s string:\n)。 scanf(%s,s)。 printf(Input the length of T39。s string:\n)。 scanf(%d,amp。n)。 printf(Please input the T39。s string:\n)。 scanf(%s,t)。 search_max(s,t,m,n)。}運(yùn)行示例：Input the length of S’s string:8↙Please input the S’s string:adgabcde↙Input the length of T’s string:6↙Please input the T’s string:fabcdg↙最后輸出：a b c d2_2 假設(shè)所使用的串采用鏈接存儲(chǔ)結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)可存放M（M=4）個(gè)字符。試編寫一個(gè)實(shí)現(xiàn)STRINS（S1，I，S2）的C函數(shù)。為了減少移動(dòng)字符的次數(shù)，結(jié)點(diǎn)中允許使用無效的特殊字符，但一個(gè)結(jié)點(diǎn)至少含有一個(gè)有效的字符。存儲(chǔ)法：struct node { char data[4]。 struct node *link。 }。 typedef struct node NODE。算法步驟：1． 通過 i/4 算出 所在的結(jié)點(diǎn)2． 通過k= i %4 算出i 在該結(jié)點(diǎn)中的位置3． 開設(shè)一新結(jié)點(diǎn)，把該結(jié)點(diǎn)中k 后的字符賦給新結(jié)點(diǎn)4． 把該結(jié)點(diǎn)中賦過的字符及新結(jié)點(diǎn)中未賦過值的都置成無效字符‘*’，5． 使新結(jié)點(diǎn)指向該結(jié)點(diǎn)的后繼，該結(jié)點(diǎn)指向 s2首結(jié)點(diǎn)，并把 s2的末結(jié)點(diǎn)中的‘\0’置成’‘*’，末結(jié)點(diǎn)指向新結(jié)點(diǎn)。void strins(NODE *s1, int i, NODE *s2){ int j, k, l, m。 NODE *p, *q, *r。 j=i/4。 k=i%4。 p=s1。 for(l=0。 l !=j。 l++)p=plink。 q=(NODE *)malloc(sizeof(NODE))。 for(m=k。m4amp。amp。pdata[m]!=39。\039。m++) { qdata[mk]=pdata[m]。 pdata[m]=39。*39。 /* 39。*39。is invalid char */ } if(pdata[m]==39。\039。)qdata[mk]=39。\039。 else for(l=k。l4。l++)qdata[l]=39。*39。 r=s2。 while(rlink!=NULL)r=rlink。 for(m=0。 rdata[m]!=’\0’。 m++)。 rdata[m]=’*’。 while( m4) rdata[++m]=’*’。 qlink=plink。 plink=s2。 rlink=q。}若S1=“ABCDEFGHI”；S2=“JKLMNOP”；I=6；則調(diào)用后得 “ABCDEF**JKLMNOP*GHI2_3，編一個(gè)實(shí)現(xiàn)STRDEL（S，I，J）的C函數(shù)。算法步驟：1． 計(jì)算出S中結(jié)點(diǎn)的個(gè)數(shù)L2． 通過I/4 計(jì)算出其在S中的哪個(gè)結(jié)點(diǎn)3． 通過I%4算出其在該結(jié)點(diǎn)中的位置4． 若（I+J1）/4 L 則置該位置為‘*’；否則，將I位所在結(jié)點(diǎn)中的所在位及其后均置為‘*’；并將（ I+J1）/4位所在結(jié)點(diǎn)中的所在位及其前均置為‘*’；5． 最后使 I位所在結(jié)點(diǎn)指向（ I+J1）/4位所在結(jié)點(diǎn)void strdel(NODE *s, int I，int j){ int k,l,m,h。 NODE *p, *q。 k=i/4。 h=i%4。 q=p=s。 l=0。 while(plink!=NULL) { p=plink。 l++。 } for(m=0。m!=k。m++)p=plink。 if((i+j1)/4l)pdata[h]=39。\039。 else { for(m=0。m!=(i+j1)/4。m++)q=qlink。 for(m=h。m4。m++)pdata[m]=39。*39。 for(m=(i+j1)%4。m=0。m)qdata[m]=39。*39。 /* 39。*39。 is invalid char */ plink=q。 }} 若S=“ABCDEFGHIJKLMNO”，I=3, j=10則調(diào)用后結(jié)果為 “ABC* ***LMNO”3_1編寫一個(gè)二分插入排序的C程序一：數(shù)據(jù)結(jié)構(gòu) 用一個(gè)數(shù)組a來存儲(chǔ)數(shù)據(jù)元素，線性存儲(chǔ)可以方便存儲(chǔ)。二：具體分析 使用二分查找來代替線性查找來進(jìn)行插入操作可以顯著提高效率，因此，編寫了一個(gè)bi_search函數(shù)來進(jìn)行查找