【文章內容簡介】 }SqList。/*順序表的數(shù)據(jù)類型*/typedef struct LNode{ ElemType data。 struct LNode *next。}LNode,*LinkList。/*單鏈表的數(shù)據(jù)類型*/每一個抽象數(shù)據(jù)結構對應的算法如下void print_Sq(SqList L){ //打印順序表的全部元素。 int i。 int a[MaxSize]。 for(i=0。i。i++){ //從第0個元素開始， a[i]=[i]。 printf(%4d,a[i])。 } printf(\n)。}//print_Sq void print_Sq(SqList L){ //打印順序表的全部元素。 int i。 int a[MaxSize]。 for(i=0。i。i++){ //從第0個元素開始， a[i]=[i]。 printf(%4d,a[i])。 } printf(\n)。}//print_Sq void MergeList(SqList La,SqList Lb,SqList amp。Lc){ //已知線性表La和Lb中的數(shù)據(jù)元素按值非遞減排列 //歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列。 int ai,bj,i,j,k,La_len,Lb_len。 InitList_Sq(Lc)。 i=j=1。 k=0。 La_len=。 Lb_len=。 while((i=La_len)amp。amp。(j=Lb_len)){//當其中任意一個表沒有選擇完的時候 GetElem(La,i,ai)。 //調用GetElem()函數(shù)，獲取La的值，并賦給ai GetElem(Lb,j,bj)。 if(ai=bj){ //把其中小的插入到Lc中 ListInsert_Sq(Lc,++k,ai)。/*調用ListInsert_Sq把小的值插入到中*/ ++i。 /*i的值加1，指向下一個元素*/ } else{ ListInsert_Sq(Lc,++k,bj)。 ++j。 }//else }//while while(i=La_len){/*把La中剩余的元素賦給Lc*/ GetElem(La,i++,ai)。 ListInsert_Sq(Lc,++k,ai)。 } while(j=Lb_len){ /*把Lb中剩余的元素賦給Lc*/ GetElem(Lb,j++,bj)。 ListInsert_Sq(Lc,++k,bj)。 }//while}//MergeListStatus GetElem(SqList L,ElemType i,ElemType amp。e){ //把線性表L中的第i個元素傳遞給e if(i1||i){ //i的范圍有誤，要重新輸入 printf(范圍錯誤!\n)。 return 0。 } e=[i1]。 //吧線性表的第i個元素取出來。 return 1。 }//GetElemvoid unionSq(SqList amp。La,SqList Lb){ //將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中 ElemType La_len,Lb_len,i。 ElemType e。La_len=。 Lb_len=。for(i=1。i=Lb_len。i++){GetElem(Lb,i,e)。 //調用GetElem()函數(shù)，獲取Lb中的第i個值，并賦給e if(!LocateElem_Sq(La,e, pare))/*調用LocateElem_Sq函數(shù)，如果在La中找不到與e相等的函數(shù)， 就把e插入到La中，否則不進行插入*/ListInsert_Sq(La,++La_len,e)。}}//unionSqStatus LocateElem_Sq(SqList L,ElemType e,Status (*pare)(ElemType, ElemType)){ //在順序線性表中查找第一個與e值滿足pare關系的位序 //若找到則返回其在L中的位序，否者返回0 ElemType i=1。 ElemType *p=。 /*把L的首元素的地址給p*/ while(i=amp。amp。!(*pare)(*p++,e)) /*找到與e相等的元素，并且i在合法的值以內*/ ++i。 if(i=)/*i的值比元素個數(shù)少，是正常的查找*/ return i。 else return 0。 //查找不成功，返回0.}//LocateElem_SqStatus ListDelete_Sq(SqList amp。L,int i,ElemType amp。e){ //在順序線性表L中刪除第i個元素，并用e返回其值 //i的合法值為1=i=。 ElemType *p,*q。 if((i1)||(i)) return ERROR。/*輸入i的位置不合法，函數(shù)退出，返回0*/ p=amp。([i1])。 //把線性表的第i個值的地址給p e=*p。 //把的p所指元素值賦給e q=+。 /*q指向最后一個元素*/ for(++p。p=q。++p) *(p1)=*p。 /*從i開始，把所有的元素都向前移動*/ 。 /*順序表的長度減少1*/ return OK。 }//ListDelete_Sq Status pare(ElemType a1, ElemType a2){ //如果a1和a2相等，則返回1，否者返回0 if(a1==a2) return 1。 else return 0。}//listDelete_SqStatus ListInsert_Sq(SqList amp。L,int i,ElemType e){ //在順序表L中第i個位置之前插入新的元素e //i的合法值為1=i=+1 ElemType *newbase,*p,*q。if(i1||i+1){ //i值不合法 printf(范圍錯誤,請重新輸入\n)。 return ERROR。}if(=){//當前空間已滿，增加分配 newbase=(ElemType *)realloc(,(+LISTINCREMENT)*sizeof(ElemType))。 if(!newbase){ printf(空間已經(jīng)滿了，無法獲得新空間\n)。 exit(OVERFLOW)。} //存儲分配失敗 =newbase。 +=LISTINCREMENT。 //容量相應地增加 } q=amp。([i1])。 //q為插入位置 for(p=amp。([])。p=q。p) *(p+1)=*p。 //插入位置及之后的元素右移 *q=e。 ++。//表長增1 return OK。}//ListInsert_SqStatus InitList_Sq(SqList amp。L){//構造一個空的線性表 =(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 if(!) { printf(分配不了地址)。exit(OVERFLOW)。} =0。 //初始化沒有元素，順序表的長度為0 =LIST_INIT_SIZE。 //存儲空間初始化的空間 return OK。 }//InitList_Sqint Index_KMP(SString S,SString T,int amp。pos, int nextval[]){//利用模式串T的next函數(shù)求T在主串中第pos個字符之后// 的位置的KMP算法。其中，T非空，1=pos=StrLength(S) int i=pos。 int j=1,k=1。 while(i=S[0]amp。amp。j=T[0]){ //T為非空串。若主串中第pos個字符之后存在與T相等的子串 //則返回第一個這樣的子串在S中的位置，否則返回0 if(j==0||S[i]==T[j]){ /*兩個字符相等，則繼續(xù)向后匹配*/ ++i。++j。 } else { printf(第%d次在%d匹配失敗!\n,k,i)。 k++。 j=nextval[j]。 /*若匹配不成功，則把nextval賦給j從nextval開始匹配*/ }} if(jT[0]){ printf(最后匹配成功,在第%4d個位置\n,iT[0])。 return iT[0]。 //返回成功匹配的位置}else{ printf(最后匹配不成功!\n)。 return 0。}}//Index_KMPvoid get_nextval(SString T,int nextval[]){ //求模式串T的next函數(shù)修正值并存入數(shù)組nextval int i=1,j=0。 nextval[1]=0。 while(iT[0]){ if(j==0||T[i]==T[j]){ /*1的nextval是0*/ ++i。 /*i和j各加1*/ ++j。 if(T[i]!=T[j]) nextval[i]=j。 /*字符串不相等，就上一次的j賦給nextval*/ else nextval[i]=nextval[j]。 /*相等的話就把前一個nextval的值賦給這個*/ }//if else j=nextval[j]。/*若不相等的話，就可以吧nextval賦給j*/ }//while }//get_nextvalvoid get_next(SString T,int next[]){ //求模式串T的next函數(shù)值并存入數(shù)組next. int i=1,j。 next[1]=0。 /*1的next是0*/ j=0。 while(iT[0]){ if(j==0||T[i]==T[j]){ ++i。 ++j。 next[i]=j。/*前后相等或者j為0的時候，就把j賦給next*/ } else j=next[j]。 /*不相等就要返回，把next賦給j*/ }}//get_nextvoid MergeList_L(LinkList amp。La,LinkList amp。Lb,LinkList amp。Lc){ //已知單鏈表La和Lb的元素按值非遞減排列 //歸并La和Lb得到新單鏈表Lc，Lc的元素也按值非遞減排列LinkList pa,pb,pc。//定義三個指針，前兩個指向La和Lb的nextpa=Lanext。 /*后面的就指向La*/pb=Lbnext。Lc=pc=La。while(paamp。amp。pb){ if(padata=pbdata){ pcnext=pa。 /*pa指向的節(jié)點值小，就把該連到Lc中*/ pc=pa。 /*pc指最新連入的節(jié)點*/ pa=panext。 /*pa指向下一個節(jié)點*/ } else{pcnext=pb。/*pb指向的節(jié)點值小，就把該連到Lc中*/ pc=pb。 /*pc指最新連入的節(jié)點*/ pb=pbnext。/*pb指向下一個節(jié)點*/ }} pcnext=pa?pa:pb。 /*指向不為空的那個結點*/ free(Lb)。 /*釋放Lb的空間*/}//MergeList_void print_L(LinkList head){ LinkList p=headnext。 while(p!=NULL){ /*p不為空*/ printf(%5d,pdata )。 p=pnext。 /*p指向下一個結點*/ } printf(\n)。}//print_Lint ListLength_L(LinkList L){ LinkList p=L。 int i=0。 while(pnext!=NULL)/*當p不為空*/ { i++。 /*i加1*/ p=pnext。 }//while return (i)。}//ListLength_LStatus ListDelete_L(LinkList amp。L, int i, ElemType amp。e){ //在帶頭結點