(25)王道数据结构-串的存储结构

存储结构

顺序存储

静态数组

#define MAXLEN 255  //预定义最大串长为255
typedef struct {    
    char ch[MAXLEN];//每个分量存储一个字符
    int length;     //串的实际长度
}SString;

动态数组

#define MAXLEN 255
typedef struct {    
    char *ch;       //按串长度分配存储区，ch指向串的基地址
    int length;     //串的实际长度
}HString;  
HString S;
S.ch = (char *)malloc(MAXLEN *sizeof(char));
S.length = 0;

链式存储

方式一:

typedef struct StringNode {
    char ch;    //每个节点存1个字符
    struct StringNode * next;
}StringNode, *String;

存储密度低，每个字符1B，每个指针4B

方式二:

typedef struct StringNode {
    char ch[4];    //每个节点存多个字符
    struct StringNode * next;
}StringNode, *String;

存储密度提高了

基本操作

#include<stdio.h>
#include<string.h>
#define MAXLEN 255  //预定义最大串长为255
typedef struct {    
    char ch[MAXLEN];//每个分量存储一个字符
    int length;     //串的实际长度
}SString;
bool StrAssing(SString *T, char ch[]);
bool SubString(SString *sub, SString S, int pos, int len);
int StrCompare(SString S, SString T);
int StrLength(SString T);
int Index(SString S, SString T);
int main(void) {
    SString S, sub;
    char ch[] = "This is String Demo Code";
    StrAssing(&S, ch);
    SubString(&sub, S, 2, 5);
    printf("sub=%s\n", sub.ch);
    
    int len = StrCompare(S, sub);
    printf("len=%d\n", len);
    
    int index = Index(S, sub);
    printf("index=%d\n", index);
    return 0;
}

//赋值操作
bool StrAssing(SString *T, char str[]) {
    //清空原始内容
    memset(T->ch, 0, MAXLEN);
    T->length = 0;
    //重新赋值为chars
    strcpy(T->ch, str);
    T->length = (int)strlen(str);
    printf("len=%d\n",strlen(T->ch));
}

//求子串
bool SubString(SString *sub, SString S, int pos, int len) {
    //子串范围越界
    if (pos + len - 1 > S.length) {
        return false;
    }
    //清空T中的原始内容
    memset(sub->ch, 0, MAXLEN);
    sub->length = 0;
    strncpy(sub->ch, S.ch + pos, len);
    //重新设置串的长度
    sub->length=len;
    return true;
}

bool subString(SString &sub, SString S, int pos, int len) {
    //子串范围越界
    if (pos + len - 1 > S.length) {
        return false;
    }
    for (int i = pos; i < pos + len; i++) {
        sub.ch[i-pos+1] = S.ch[i];
    }
    sub.length = len;
    return true;
}

//比较操作
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;
}

//定位操作
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 StrLength(SString T) {
    return T.length;
}