数据结构第四章串：定长顺序串

//数据结构 第四章串 定长顺序串
//2021.8.14
//by Walnut from NWU
/*
* 串：子串，主串，串相等，字符串，
* 三种实现方式：定长顺序串，堆串，块链串
* 操作：串生成，串插入，串删除，串拷贝，判空，串比较，串长度，串清空，串拼接，串切片，寻找字串位置，串替换，串销毁
*/
#include<iostream>
#include<stack>
#include<cmath>
#define MAXSIZE 15
using namespace std;

typedef struct SString {//串结构体声明
    char ch[MAXSIZE];//串存储空间
    int len;//串长度
};

void StrAssign(SString* s, char chars[], int n) {//串生成，将chars转化为串，设定长度为n，超过n或超过最大串长的部分将舍去
    if (MAXSIZE < n)
        n = MAXSIZE;
    for (int i = 0; i < n; i++) {
        s->ch[i] = chars[i];
    }
    s->len = n;
}

bool StrInsert(SString* s, char ch, int n) {//串插入，将ch插入第n个元素处，需要后部分元素后移，若超出串长则舍去多余部分
    if (n<1 || n>s->len)//判断输入是否合法
        return false;
    if (s->len == MAXSIZE)//若串已满，舍去最后一个
        s->len--;
    for (int i = s->len; i >= n; i--) {//插入部分后面元素后移
        s->ch[i] = s->ch[i - 1];
    }
    s->len++;
    s->ch[n - 1] = ch;//插入元素
    return true;
}

bool StrDelete(SString* s, int pos, int len) {//串删除，在pos位置开始删除长度为len的子串
    if (pos<1 || pos>s->len)//判断合法性
        return false;
    if (len > s->len - pos)//若删除子串长度过大，则将pos后所有元素删除，例如串为abcde，删除4开始的100长子串，相当于删除4开始2长子串
        len = s->len - pos;
    for (int i = pos + len - 1, j = pos - 1; i < s->len; i++, j++) {//i指向需要前移的第一个元素，j指向删除位置
        s->ch[j] = s->ch[i];
    }
    s->len = s->len - len;//串长度改变
}

void StrCopy(SString* s, SString t) {//串拷贝
    s->len = t.len;
    for (int i = 0; i < t.len; i++) {
        s->ch[i] = t.ch[i];
    }
}

bool StrEmpty(SString s) {//判空
    if (s.len == 0)
        return true;
    return false;
}

bool StrCompare(SString s, SString t) {//串比较，相同返回true，不同false
    if (s.len != t.len)
        return false;
    for (int i = 0; i < s.len; i++) {
        if (s.ch[i] != t.ch[i])
            return false;
    }
    return true;
}

int StrLength(SString s) {//获取串长度
    return s.len;
}

void StrClear(SString* s) {//串清空
    s->len = 0;
}

void StrCat(SString* s, SString t) {//串拼接，超出最大长度部分将舍去
    if (s->len == MAXSIZE)
        return;
    for (int i = s->len, j = 0; j < t.len && i < MAXSIZE; i++, j++) {
        s->ch[i] = t.ch[j];
    }
    if (t.len < MAXSIZE - s->len)
        s->len = s->len + t.len;
    else
        s->len = MAXSIZE;
}

bool SubString(SString* sub, SString s, int pos, int len) {//串切片，将s从pos起len长的串存入sub中
    if (pos<1 || pos>s.len)//判断合法性
        return false;
    if (len > MAXSIZE - s.len)//len过长
        len = MAXSIZE - s.len;
    for (int i = 0, j = pos - 1; i < len; i++, j++) {//依次存入sub中
        sub->ch[i] = s.ch[j];
    }
    sub->len = len;//设定sub串长度
}

void coutSString(SString s) {//串输出
    cout << "String: ";
    for (int i = 0; i < s.len; i++) {
        cout << s.ch[i];
    }
    cout << endl;
}

int main() {
    SString s;
    char chars[5] = { 'a','b','c','d','e' };
    StrAssign(&s, chars, 5);//串创建
    coutSString(s);
    StrInsert(&s, 'z', 2);//串插入
    coutSString(s);
    StrDelete(&s, 4, 100);//串删除
    coutSString(s);

    SString ss;
    StrCopy(&ss, s);//串拷贝
    coutSString(ss);
    StrInsert(&ss, 'm', 2);//串插入
    coutSString(ss);
    cout << StrCompare(s, ss) << endl;//串比较
    coutSString(s);
    coutSString(ss);
    StrCat(&s, ss);//串拼接
    coutSString(s);

    SubString(&ss, s, 2, 5);//串切片
    coutSString(ss);
    return 0;
}