数据结构---串（赋值，求子串，比较，定位）

#define MaxLen 255
typedef struct{
    char ch[MaxLen];//静态数组,系统自动回收
    int length;
}SString;
typedef struct{
    char *ch;
    int length;
}HString;
HString S;
S.ch=(char*)malloc(MaxLen*sizeof(char));//在堆区分配存储空间,所以需要free手动回收
S.length=0;

typedef struct StringNode{
    char ch;//一个字符占一个字节
    struct StringNode *next;//占4个字节/8个字节
}StringNode,*String;
//以上定义的结构体类型存储密度低,可以采用以下方案定义结构体
typedef struct StringNode{
    char *ch;//或一个结点存放更多字符
    struct StringNode *next;
}StringNode,*String;

void StrAssign(const StringNode* str, char** S) {
    int len = 0;
    const StringNode* currentNode = str;
   
    // 计算字符串长度
    while (currentNode != NULL && currentNode->ch != '\0') {
        len++;
        currentNode = currentNode->next;
    }
   
    *S = (char*)malloc((len + 1) * sizeof(char)); // 分配空间，要考虑'\0'所以长度加1
   
    int i = 0;
//将 currentNode 指向 str，我们可以从链表的头部开始逐个访问节点，并依次处理每个节点的字符
    currentNode = str;
    // 复制字符到新的字符串里
    while (currentNode != NULL && currentNode->ch != '\0') {
        (*S)[i] = currentNode->ch;
        i++;
        currentNode = currentNode->next;
    }
   
    (*S)[i] = '\0'; // 在新的字符串末尾添加'\0'表示结束
}

void StrAssign(SString S, SString& sub) {
    int length = 0;
    while (S.ch[length] != '\0') {
        sub.ch[length] = S.ch[length];
        length++;
    }
    sub.ch[length] = '\0';
}

void StrCopy(StringNode* str, const char* chars) {
    int len = strlen(chars);
    int i;
    for (i = 0; i < len; i++) {
        str->ch = chars[i];
        if (i < len - 1) {
            str->next = (StringNode*)malloc(sizeof(StringNode));
            // 若字符串还没有复制完毕则手动扩展空间
            str->next->ch = '\0'; // 将下一个节点的 ch 字段设置为空字符
            str = str->next;
        }
    }
    str->next = NULL;
}

void StrCopy(SString S, SString& sub) {
    int length = 0;
    while (S.ch[length] != '\0') {
        sub.ch[length] = S.ch[length];
        length++;
    }
    sub.ch[length] = '\0';
}

链式表
bool StrEmpty(String str)
{
    if(str->ch[0]=='\0')
        return true;
    else
        return false;
}
顺序表
bool StrEmpty(SString S) {
    if (S.ch[0] == '\0')
        return true;
    else
        return false;
}

void StrClear(StringNode* str)
{
    while(str!=NULL){
        free(str);
        str=str->next;
    }
}

void Concat(StringNode* str, char* s1, char* s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    // 创建一个新的结点用于存储连接后的字符串
    StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
    newNode->ch = (char*)malloc((len1 + len2 + 1) * sizeof(char)); // 加1是为了存放字符串结束符 '\0'
    newNode->next = NULL;
    // 连接字符串并保存到新结点的ch字段
    strcpy(newNode->ch, s1);
    strcat(newNode->ch, s2);
    // 找到链表末尾并将新结点连接到其后
    while (str->next != NULL) {
        str = str->next;
    }
    str->next = newNode;
}

void Concat(SString& sub, SString S, SString T) {
    int i = 0;
    // 复制字符串 S 到 sub
    while (S.ch[i] != '\0') {
        sub.ch[i] = S.ch[i];
        i++;
    }
    // 复制字符串 T 到 sub
    int j = 0;
    while (T.ch[j] != '\0') {
        sub.ch[i] = T.ch[j];
        i++;
        j++;
    }
    sub.ch[i] = '\0'; // 添加字符串结束符
}

void Insert(StringNode** str, char ch) {
    StringNode* newNode = (StringNode*)malloc(sizeof(StringNode));
    newNode->ch = ch;
    newNode->next = NULL;
    if (*str == NULL) {
        *str = newNode;
        return;
    }
    StringNode* currentNode = *str;
    while (currentNode != NULL) {
        currentNode = currentNode->next;
    }
    currentNode->next = newNode;
}
StringNode* SubString(StringNode* str, int pos, int len) {
    StringNode* subStr = NULL;
    StringNode* currentNode = str;
    int currentPos = 0;
    while (currentNode != NULL && currentPos < pos + len) {
        if (currentPos >= pos) {
            Insert(&subStr, currentNode->ch);
        }
        currentNode = currentNode->next;
        currentPos++;
    }
    return subStr;
}

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 getListLength(StringNode* head) {
    int length = 0;
    ListNode* current = head;
    while (current != nullptr) {
        length++;
        current = current->next;
    }
    return length;
}
int compareLinkedListLength(StringNode* list1, StringNode* list2) {
    int length1 = getListLength(list1);
    int length2 = getListLength(list2);
    if (length1 > length2) {
        return 1;
    } else if (length1 < length2) {
        return -1;
    } else {
        return 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;
}

ListNode* locateNode(StringNode* head, int position) {
    if (position <= 0 || head == nullptr) {
        return nullptr;
    }
    ListNode* current = head;
    int count = 1;
    while (current != nullptr && count < position) {
        current = current->next;
        count++;
    }
    return current;
}

#define MaxLen 255
typedef struct {
    char ch[MaxLen]; // 静态数组,系统自动回收
    int length;
} SString;
void SubString(SString& sub, SString S, int start, int length) {
    int i;
    for (i = 0; i < length; ++i) {
        sub.ch[i] = S.ch[start + i];
    }
    sub.ch[length] = '\0'; // 添加字符串结束符
    sub.length = length;
}
int StrCompare(SString S, SString T) {
    int i = 0;
    while (S.ch[i] != '\0' && T.ch[i] != '\0') {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
        i++;
    }
    return S.length - T.length;
}
int Index(SString S, SString T) {
    int i = 1, n = S.length, m = T.length; // n, m 分别为字符串 S 和 T 的长度
    SString sub;
    while (i <= n - m + 1) {//确保了字符串 T 在字符串 S 中进行匹配时不会越界
//假设 n = 10，m = 3，那么 n - m + 1 = 8
//在循环中，当 i = 9 或 i = 10 时，剩余的字符串 S 的长度已经小于 T 的长度，无法再进行匹配
        SubString(sub, S, i, m);
        if (StrCompare(sub, T) != 0)
            ++i;
        else
            return i;
    }
    return 0;
}