一.查找的算法

---

1.顺序查找

1 int Search_Seq( SeqList L, ElemType elem )2 {3     L.elem[0] = elem;4     for ( int i = L.length; L.elem[0].key != L.elem[i].key; i-- );5     return i;6 }

2.折半查找(二分查找)

1 int Binary_Search( SeqList L, ElemType elem ) 2 { 3     int low = 1, high = L.length; 4     while (low <= high) 5     { 6         int mid = ( low + high ) / 2; 7         if ( elem.key == L.elem[mid].key ) 8             return mid; 9         else if ( elem.key < L.elem[mid].key )10             high = mid - 1;11         else12             low = mid + 1;13     }14     return 0;15 }

3.折半查找(二分查找)递归

1 int Binary_search_RC( SeqList L, ElemType elem, int low, int high )2 {3     if ( low > high ) return 0;4     int mid = ( low + high ) / 2;5     if ( elem.key == L.elem[mid] ) return mid;6     else if ( elem.key < L.elem[mid] )  high = mid - 1;7     else low = mid + 1;8     return Binary_search_RC( L, elem, low, high );9 }

二.字符串匹配

---

 

1.简单的模式匹配算法(朴素模式匹配算法)

1 int Index( SString S, SString T ) 2 { 3     int i = 1, j = 1; 4     while ( i <= S[0] && j <= T[0] ) 5     { 6         if ( S[i] == T[j] ) { i++; j++; } 7         else { i = i - j + 2; j = 1; } 8     } 9     if ( j > T[0] ) return i - T[0];10     return 0;11 }

2.KMP算法

算法需要先求出模式串的next值:

1 void get_next( SString T, int next[] ) 2 { 3     int i = 1, j = 0; 4     next[1] = 0; 5     while (i<=T[0]) 6     { 7         if (j==0||T[i]==T[j] ) 8         { 9             i++; j++; next[i] = j;10         }11         else j = next[j];12     }13 }

也可求出改进后的nextval值:

1 void get_nextval( SString T, int nextval[] ) 2 { 3     int i = 1, j = 0; 4     nextval[1] = 0; 5     while ( i <= T[0] ) 6     { 7         if ( j == 0 || T[i] == T[j] ) 8         { 9             i++, j++;10             if ( T[i] == T[j] )11                 nextval[i] = nextval[j];12             else13                 nextval[i] = j;14         }15         else j = nextval[j];16     }17 }

以下是KMP算法:

1 int KMP( SString S, SString T, int next[], int pos ) 2 { 3     int i = pos, j = 1; 4     while ( i<=S[0]&&j<=T[0] ) 5     { 6         if ( j == 0 || S[i] == T[j] ) { i++; j++; } 7         else j = next[j]; 8     } 9     if ( j > T[0] ) return i - T[0];10     return 0;11 }