sstring.c

这是我的一些数据结构(C语言)源代码 比如LinkList

#include <stdio.h>
#include <stdlib.h>

#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;
}