www.pudn.com > datastructor.rar > SString.c

#include  
#include  
 
#define MAX     50 
typedef unsigned char SString[MAX+1]; 
typedef enum {ERROR = -2,OVERLOW,FALSE, TRUE, OK} Status; 
 
Status StrAssign(SString T, const char* chars) { 
    //生成一个其值等于串chars的串T      
    int i; 
    T[0] = strlen(chars); 
    for(i = 1; i <= T[0]; ++i) { 
        T[i] = chars[i-1]; 
    } 
    return OK; 
} 
 
Status Concat(SString T, const SString S1, const SString S2) { 
    //用T返回由S1和S2联接而成的新串      
    int i;  Status uncut; 
     
    if(S1[0] + S2[0] <= MAX) { 
        for(i = 1; i <= S1[0]; i++){ 
            T[i] = S1[i]; 
        } 
        for(i = S1[0]+1; i <= S1[0]+S2[0]; i++){ 
            T[i] = S2[i-S1[0]]; 
        } 
        T[0] = S1[0] + S2[0];   uncut = TRUE; 
    } 
    else if(S1[0] < MAX) { 
        for(i = 1; i <= S1[0]; i++){ 
            T[i] = S1[i]; 
        } 
        for(i = S1[0]+1; i <= MAX; i++){ 
            T[i] = S2[i-S1[0]]; 
        } 
        T[0] = MAX;   uncut = FALSE; 
    } 
    else { 
        for(i = 0; i <= MAX; i++){ 
            T[i] = S1[i]; 
        } 
        uncut = FALSE;     
    }         
    return uncut;  
} 
 
Status SubString(SString Sub, const SString S, int pos, int len) { 
    //用Sub返回串S的第pos个字符起长度为len的子串 
    //其中，1 <= pos <= Stringth(s)且O <= len <= StringLength(S)-pos+1      
    int i; 
    if(pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1) 
        return ERROR; 
    for(i = 1; i <= len; i++){ 
        Sub[i] = S[pos+i-1]; 
    }        
    Sub[0] = len; 
    return OK; 
}                                                                   
 
int Index(const SString S, const SString T, int pos) { 
    //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0 
    //其中，T非空，1 <= pos <= StrLength(S) 
    int i = pos, j = 1; 
    while(i <= S[0] && j <= T[0]) { 
        if(S[i] == T[j]) { ++i; ++j; } //继续比较后继字符  
        else{ i = i-j+2; j = 1; }      //指针后退重新开始匹配  
    } 
    if(j > T[0]) return i-T[0]; 
    else return 0; 
} 
 
//KMP算法 
void get_next(SString T, int next[]) { 
    //求模式串T的next函数值并存入数组next  
    int i = 1, j = 0; 
    next[1] = 0; 
    while(i < T[0]){ 
        if(j==0 || T[i]==T[j]){ 
            ++i; ++j; next[i] = j; 
        } 
        else j = next[j]; 
    } 
} 
 
int Index_KMP(SString S, SString T, int pos, int next[]) { 
    //利用模式串T的next函数求T在主串中第pos个字符之后的位置的  
    //KMP算法。其中，T非空，1<=pos<=StrLength(S)。  
    int i = pos, j= 1; 
    while(i <= S[0] && j <= T[0]){ 
        if(j == 0 || S[i] == T[j]){ ++i; ++j; } 
        else j = next[j]; 
    } 
    if(j > T[0]) return i-T[0]; 
    else return 0; 
}         
 
//以下为测试程序                                  
void output(const SString S){ 
    //输出串S  
        int i; 
 
        for(i= 1; i<= S[0]; i++) 
                printf("%c", S[i]); 
        printf("\n"); 
} 
 
int main() 
{ 
        SString S1, S2, S3, S4; 
        //int compare; 
 
        StrAssign(S1, "ababcabcacbab"); 
        output(S1); 
        printf("The length of S1: %d\n", S1[0]); 
         
        StrAssign(S2, "abcac"); 
        output(S2); 
        printf("The length of S2: %d\n", S2[0]); 
        /* 
        printf("\nCompare S1 to S2:\n"); 
        compare = StrCompare(&S1, &S2); 
        if(compare > 0) printf("S1 > S2.\n"); 
        else if(compare == 0) printf("S1 = S2.\n"); 
        else printf("S1 < S2\n"); 
        */ 
        printf("\nConnect String S1 to S2:\n"); 
        Concat(S3, S1, S2); 
        output(S3); 
        printf("The length of S3: %d\n", S3[0]); 
        //printf("%d\n", strlen(S3.ch));    
         
        printf("\nSubset of String:\n"); //子集 
        SubString(S4, S1, 1, 5); 
        output(S4); 
        /* 
        printf("\nClear String S3:\n"); 
        ClearString(&S3); 
        printf("Length: %d\n", S3.length); 
 
        free(S1.ch); 
        free(S2.ch); 
        if(S3.ch) { free(S3.ch);printf("Free S3.\n"); } 
        free(S4.ch); 
        */ 
        printf("\nIndex String:\n"); 
        printf("%d\n", Index(S3, S2, 1)); 
         
        int next[10]; 
        get_next(S2, next); 
        printf("\nIndex using KMP:\n"); 
        printf("%d\n", Index_KMP(S1, S2, 1, next)); 
          
        system("pause"); 
        return 0; 
}