专栏首页从流域到海域《数据结构》 定长顺序串常用操作代码集合

《数据结构》 定长顺序串常用操作代码集合

代码来自老师上课使用的ppt或者课本

/*定长顺序串*/
#define MAXLEN 40
typedef struct {
    char ch[MAXLEN];
    int len;
} SString
/*插入函数*/
/*在串S中下标为pos的字符之前插入串t*/
int StrInsert(SString *S, int pos, SString t) {
    int i;
    if(pos < 0 || pos > S->len) return ERROR;
    if(S->len + t.len <= MAXLEN) {    //插入后串长小于MAXLEN,正常插入
        for (i = S->len - 1; i >= pos; i--) {
            S->ch[i + t.len] = S->ch[i];
        }   //从后向前后移元素,从下标S->len-1到pos结束,为t腾出位置
        for (i = 0; i < t.len; i++) {
            S->ch[pos + i] = t.ch[i];    //插入t
        }
        S->len = S->len + t.len;
    }
    else if(pos + t.len <= MAXLEN) {    //插入后串长大于MAXLEN,S部分被舍弃
        for(i = MAXLEN - t.len -1; i >= pos; i-- ) {
            S->ch[i + t.len] = S->ch[i];
        }   //从后向前右移元素,被舍去的元素不移动
        for(i = 0; i < t; i++) {
            S->[pos + i] = t.ch[i];
        }
        S->len = MAXLEN;
    }
    else {      //插入后串长大于MAXLEN,S移动的元素全部被舍弃,t部分被舍弃
        for(i = 0; i < MAXLEN - pos; i++) {
            S->ch[pos + i] = t.ch[i];
        }
        S->len = MAXLEN;
    }
    return OK;
}
/*删除函数*/
/*在串S中删除从下标pos起len个字符*/
/*S->len-1表示最后一个下标,S->len-1-pos表示从最后一个下标到下标pos间的元素个数*/
int StrDelete(SString *S, int pos, int len) {
    int i;
    if(pos < 0 || len < 1 || pos > (S->len - len)) {
        return ERROR;    //从pos起最多删除S->len-1-pos+1 个字符
    }
    for(i = pos +len; i < len; i++) {
        S->ch[i - len] = ch[i];
    }
    S->len = S->len - len;
    return OK;
}
/*串复制函数*/
/*将串t的值复制到串S中*/
void StrCopy(SString *S, SString t) {
    int i;
    for(i = 0; i < t.len; i++) {
        S->ch[i] = t.ch[i];
    }
    S->len = t.len;
}
/*判空函数*/
int StrEmpty(SString S) {
    if (S.len == 0) return 1;
    else return 0;
    /*return!(s.len)*/
}
/*串比较函数*/
/*比较规则与字符串的比较相同*/
int StrCompare(SString S, SString t) {
    int i;
    for(i = 0; i < S.len && i < t.len; i++) {
        if(S.ch[i] != t.ch[i]) {
            return(S.ch[i] - t.ch[i]);
        }
    }
    return(S.len - t.len);    /*包含三种情况*/
}
/*求串长函数*/
int StrLength(SString) {
    return(S.len);
}
/*清空函数*/
void StrClear(SString *S) {
    S->len = 0;
}
/*连接函数*/
/*将串连接在串S的后面,*/
int StrCat(SString *S, SString t) {
    int i,flag;
    if(S->len + t.len <= MAXLEN) {    /*连接后串长小于MAXLEN,正常插入*/
        for(i = S->len; i < S->len + t.len; i++) {
            S->ch[i] = t.ch[i - S->len];
        }
        S->len += t.len;
        flag = 1;
    }
    else if(S->len < MAXLEN) {    /*连接后串长大于MAXLEN,t部分被舍去*/
        for (i = S->len; i < MAXLEN; i++) {
            S->ch[i] = t.ch[i - S->len];
        }
        S->len = MAXLEN;
    }
    else {
        flag = 0;
    }
    return flag;     //flag = 0表示非正常连接,t部分被舍弃或全部被舍弃
}
/*求字串函数*/
/*将串S中下标pos起len个字符串复制到sub中*/
int SubString(SString *sub, SString S, int pos, int len) {
    int i;
    if(pos < 0 || pos >S.len - 1 || len <1 || len > S.len - pos) {
        sub->len = 0;
        return OK;
    }
    else {
        for(i = 0; i < len; i++) {
            sub->ch[i] = S.ch[pos + i];
        }
        sub->len = len;
        return OK;
    }
}
/*定位函数即Brute-Force算法*/
/*求主串S的pos位置起,串t第一次出现的位置,成功返回位置序号,失败返回-1*/
int StrIndex(SString S, int pos, SString t) {
    int, i, start;
    if(t.len == 0) {    //t为空串时,是任意串的匹配
        return -1;
    }
    start = pos; i = start; j = 0;    //主串从pos开始,t从头开始
    while(i < S.len && j < t.len) {
        if(S.ch[i] = t.ch[j]) {
            i++; j++;
        }
        else {
            start++;     /*当前对应字符不等时回溯*/
            i = start;
            j = 0;      /*回溯,主串起始位置+1,t从头开始*/
    }
    if(j > t.len) {
        return start;     /*匹配成功,返回匹配起始位置*/
    }
    else return -1;     /*匹配不成功,返回-1*/
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Batch Norm

    Bactch Normalization通过标准化让激活函数分布在线性区间,结果就是加大了梯度,让模型更大胆的进行梯度下降。

    Steve Wang
  • 普利姆(prim)算法和克鲁斯卡尔(kruskal)算法

    连通网的最小生成树算法: 1.普里姆算法——”加点法”。 假设N=(V,{E})是连通网,TE为最小生成树的边集合。 (1)初始U={u0}(...

    Steve Wang
  • Java面试高频面试题汇总 锁专题

    广义上可重入锁,也叫做递归锁,指的是同一线程,外层函数获得锁之后,内层函数仍有获得该锁的代码,但不受影响。Java的ReentrantLock和synchron...

    Steve Wang
  • 【LeetCode02】找出不含重复字符的 最长子串 的长度

    这道题,一开始最直接的想法就是暴力法,直接穷举所有的子串,然后选择无重复的子串中最长的那个。

    Sam Gor
  • 基础练习 高精度加法

      由于a和b都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。   定义一个数组A,A[0]用于存储a的个位,A[1]...

    刘开心_1266679
  • 【 BowWow and the Timetable CodeForces - 1204A 】【思维】

    题目链接 可以发现 十进制4 对应 二进制100 十进制16 对应 二进制10000 十进制64 对应 二进制1000000 可以发现每多两个零,4的...

    _DIY
  • HBUOJ 回音排版

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【POJ 1035】Spell checker

      每个单词,如果字典里存在,输出”该单词 is correct“;如果字典里不存在,但是可以通过删除、添加、替换一个字母得到字典里存在的单词,那就输出 “该单...

    饶文津
  • 归并排序算法 顶

    合并排序算法就是把多个有序数据表合并成一个有序数据表。如果参与合并的只有两个有序表,则称为二路合并。

    算法之名
  • [剑指offer] 把数组排成最小的数

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    尾尾部落

扫码关注云+社区

领取腾讯云代金券