【正文】 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]是非負數(shù)，所以初始化Hash表時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?是一個原子depth(s)= { 1+max(depth(a0),… depth(an1)) 若s是廣義表（a0,a1,…an1）編寫一個求解廣義表s的深度的C函數(shù)。解答： 有題目給出的深度的公式，很容易想到運用遞歸來實現(xiàn)所要求的功能。這里在主函數(shù)中簡單的采用直接構造各種類型的廣義表法，為了測試算深度函數(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ù)中構造了三種結(jié)構各異的廣義表。（1） 空的廣義表，得到的深度為0。（2） 0,a,0,b0,c0,d，^ 得到的深度為1。（3） 1，↘，》0,b0,c0,d^ 得到的深度為4。 1,↘,^ 1,↘^ 0,e,^2_1假設s和t分別是具有m個和n個字符的順序存貯的串。試編寫一個在s和t中尋找最大公共子串的C函數(shù)。解答： 該題的本質(zhì)即為模式匹配，實際上是把t中所有可能長度的子串與s進行模式匹配，從最長長度n開始，若匹配成功就直接輸出當前子串，否則長度自減1后重新開始匹配。直到長度減為0，此時則說明沒有公共子串。下面的C函數(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)。}運行示例：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 假設所使用的串采用鏈接存儲結(jié)構，鏈表中每個結(jié)點可存放M（M=4）個字符。試編寫一個實現(xiàn)STRINS（S1，I，S2）的C函數(shù)。為了減少移動字符的次數(shù)，結(jié)點中允許使用無效的特殊字符，但一個結(jié)點至少含有一個有效的字符。存儲法：struct node { char data[4]。 struct node *link。 }。 typedef struct node NODE。算法步驟：1． 通過 i/4 算出 所在的結(jié)點2． 通過k= i %4 算出i 在該結(jié)點中的位置3． 開設一新結(jié)點，把該結(jié)點中k 后的字符賦給新結(jié)點4． 把該結(jié)點中賦過的字符及新結(jié)點中未賦過值的都置成無效字符‘*’，5． 使新結(jié)點指向該結(jié)點的后繼，該結(jié)點指向 s2首結(jié)點，并把 s2的末結(jié)點中的‘\0’置成’‘*’，末結(jié)點指向新結(jié)點。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，編一個實現(xiàn)STRDEL（S，I，J）的C函數(shù)。算法步驟：1． 計算出S中結(jié)點的個數(shù)L2． 通過I/4 計算出其在S中的哪個結(jié)點3． 通過I%4算出其在該結(jié)點中的位置4． 若（I+J1）/4 L 則置該位置為‘*’；否則，將I位所在結(jié)點中的所在位及其后均置為‘*’；并將（ I+J1）/4位所在結(jié)點中的所在位及其前均置為‘*’；5． 最后使 I位所在結(jié)點指向（ I+J1）/4位所在結(jié)點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編寫一個二分插入排序的C程序一：數(shù)據(jù)結(jié)構 用一個數(shù)組a來存儲數(shù)據(jù)元素，線性存儲可以方便存儲。二：具體分析 使用二分查找來代替線性查找來進行插入操作可以顯著提高效率，因此，編寫了一個bi_search函數(shù)來進行查找