串的存储结构

串的顺序存储：【默认使用方案四】

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

#define MAXIEN 255  //预定义最大串长为255

//静态数组实现(定长顺序存储)
typedef struct{
    char ch[MAXIEN];  //每个分量存储一个字符
    int length;  //串的实际长度
}SString;

//动态数组实现(堆分配存储)
typedef struct{
    char *ch;  //按串长分配存储区，ch指向串的基地址
    int length;  //串的长度
}HString;

//初始化动态数组
void Init(HString *S){
    
    S->ch=(char *)malloc(MAXIEN * sizeof(char));  //用完需要手动free
    S->length=0;
}

int main(){
    
    HString S;
    Init(&S);

}

串的基本操作实现：

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

#define MAXIEN 255  //预定义最大串长为255

//静态数组实现(定长顺序存储)
typedef struct{
    char ch[MAXIEN];  //每个分量存储一个字符
    int length;  //串的实际长度
}SString;

//基本操作的实现
//1.求子串：用Sub返回串S的第pos个字符起长度为len的子串
bool SubString(SString *Sub,SString *S,int pos,int len){
    //子串范围越界
    if(pos+len-1 > S->length){
        return false;
    }
    for(int i=pos-1;i<pos+len-1;i++){
        Sub->ch[i-pos+1]=S->ch[i];
    }
    Sub->length=len;
    return true;
}

//2.比较操作：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0
int StrCompare(SString *S,SString *T){
    for(int i=1;i<=S->length && i<=T->length;i++){
        if(S->ch[i] != T->ch[i]){
            return S->ch[i]-T->ch[i];
        }
    }
    //扫描过的所有字符都相同，则长度长的串更大
    return S->length-T->length;
}

//求串长，返回串S的元素个数[未完成代码]
int StrLength(SString *S){
    return 0;
}

//3.定位操作，若主串S中存在与串T值相同的子串，则返回它在主串S中第一次出现的位置，否则函数值为0
int Index(SString *S,SString *T){
    int i=1,n=StrLength(S),m=StrLength(T);
    SString sub;  //用于暂存字符串
    while(i<=n-m+1){
        SubString(&sub, S, i, m);
        if(StrCompare(&sub, T) != 0){
            ++i;
        }else{
            return i;  //返回子串在主串中的位置
        }
    }
    return 0;  //S中不存在与T相等的子串
}

int main(){
    SString S={"hello world!",12};
    
    SString Sub={"",0};  //初始化时清空数组
    if(SubString(&Sub, &S, 3, 5)){
        printf("%s\n",Sub.ch);
    }
}

串的链式存储：