数据结构（12.2）串之定长顺序串

雨点打透心脏的1/2处 2023-06-30 08:58 15阅读 0赞

### 数据结构（12.2）串之定长顺序串 ###

*   *   *  前言
         *  定长顺序串的初始化
         *  定长顺序串的赋值
         *  定长顺序串的比较
         *  定长顺序串的连接
         *  定长顺序串的插入与删除
         *  定长顺序串的定位
         *  定长顺序串的替换
         *  全部代码
         *   *  SString.h
             *  SString.c
             *  Main.c

### 前言 ###

定长顺序串是串顺序存储结构的一种，顺序存储结构意味着它所占的内存空间是一块连续的，而定长意味着空间大小在串创建之初就确定了，无法动态分配内存，如果有超过的部分只能舍去。在这里我们使用尾部加“ \\0 ”的方法来表示串结束，因此实际要开辟的空间是 MAXSTRLEN + 1。

### 定长顺序串的初始化 ###

我们使用数组来保存串，因此直接定义一个字符数组作为串。

#define u_char unsigned char
    typedef u_char SString[MAXSTRLEN+1];

串的初始化就是将这个字符数组初始化为空串，在数组首位添加" \\0 "即可

void InitString(SString s){ 
        s[0] = '\0';
    }

### 定长顺序串的赋值 ###

在这里赋值的意思是，我们有一个char \*类型的字符串，将它转化为我们自定义的SString类型，就是给SString进行赋值。

因此赋值包括三个步骤：

1.计算出char \*类型的字符串的长度

2.判断长度是否超出定义的最大长度，如果超出则需要截断超出的部分

3.依次取出char \*中的每一个字符，然后保存到SString数组中

void StrAssign(SString s,char *str){ 
        //1.求要赋值的字符串的长度
        int len = (int)strlen(str);
        
        //2.比较是否超出最大长度
        if (len > MAXSTRLEN) { 
            //超出，只能赋值到最大长度的位置
            len = MAXSTRLEN;
        }
        
        //3.依次赋值
        for (int i = 0; i < len; i ++) { 
            s[i] = str[i];
        }
        //标记字符串结束
        s[len] = '\0';
    }

在最后不要忘记添加“ \\0 ”表示字符串结束

### 定长顺序串的比较 ###

比较的意思是，将两个字符串对应位置的字符的ASCII码依次进行比较，假如一致则继续比较，不一致则直接输出结果。例如字符串abc和字符串acb，先将a与a比，一样则b与c比，因为c的ASCII码比b大，认为acb大于abc，输出结果。只有每个字符都相等时，才意味着两个字符串相等。

因为是直接比较ASCII码，我们也可以这样设计：定义result等于0，然后依次取出字符直接相减，假如a字符大于b字符，则结果大于0；若小于则小于0，一致则等于0。在大于或小于0时直接退出循环，等于0时则继续取下一个字符，直到两个字符串都结束为止。

int StrCompare(SString s,SString t){ 
        int result = 0;
        //判断字符串是否结束
        while (*s != '\0' || *t != '\0') { 
            result = *s - *t;
            if (result != 0) { 
              //如果有结果则直接退出循环
                break;
            }
            s ++;
            t ++;
        }
        return result;
    }

### 定长顺序串的连接 ###

连接是指将串s2接到串s1的尾部，用串t来保存。由于是定长顺序串，需要考虑到串t能否装得下的问题。

一共有三种情况：

1.s1和s2都装得下，直接装即可

2.只装得下s1和s2的一部分，s2需要截断

3.只装得下s1(s1的长度等于MAXSTRLEN)，只存s1即可

需要针对不同的情况进行不同处理。

void StrConcar(SString t,SString s1,SString s2){ 
        int len1 = StrLength(s1);
        int len2 = StrLength(s2);
        
        if (len1 + len2 <= MAXSTRLEN) { 
            //装得下两个子串->直接装入
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            for (int j = 0; j < len2; j ++) { 
                t[len1+j] = s2[j];
            }
            t[len1+len2] = '\0';
        }else if(len1 < MAXSTRLEN){ 
            //只装得下s1和部分s2->s2需要截断
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            for (int j = 0; j < MAXSTRLEN - len1; j ++) { 
                t[len1+j] = s2[j];
            }
            //最后一个位置设为'\0'表示结束
            t[MAXSTRLEN] = '\0';
        }else{ 
            //只装得下s1
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            t[MAXSTRLEN] = '\0';
        }
    }

当然还有另一种写法：先将s1存入t中，然后判断t剩余空间的情况，如果能存下s2则直接存入，否则将s2截断后存入。

### 定长顺序串的插入与删除 ###

定长顺序串的插入指的是，将串t从pos的位置插入到串s中。这同样要考虑s串能否装得下的问题，假如装不下则需要截断串t，然后从pos位置起的字符往后挪t\_len（实际能插入的长度）位，再将t插入。

![img\_1][img_1]

删除指的是，在串s中从pos的位置开始删除长度为len的子串。首先需要判断是否越界的问题，然后直接从pos位置起将len长度后的字符直接往前挪即可。

![img\_2][img_2]

### 定长顺序串的定位 ###

定位指的是，在串s中从pos位置起寻找子串t，如果找到则返回其第一个字符在s串的位置。这个方法返回的是第一个子串t的位置，假如后续还有其他子串t是无法找到的。

这其中涉及到字符串的匹配算法，比较复杂，为了实现的方便我们直接使用BF算法：从pos位置起遍历串s，与串t的首个字符开始比较，假如一致则串s和串t都移到下一位，继续比较下一个字符。当有不一致时，串t需要回溯到起始位置，而串s要回溯到与串t开始相等的位置，并且移到下一位，继续和串t的首个字符比较。

int StrIndex(SString s,SString t,int pos){ 
        //标记s串的位置
        int i = pos;
        //标记t串的位置
        int j = 0;
        
        while (s[i]!='\0' && t[j]!='\0') { 
            //判断两个字符是否相等
            if (s[i] == t[j]) { 
                //相等，找到下一个位置
                i ++;
                j ++;
            }else{ 
                //不相等,s串回溯到与t串开始相等的位置，并且挪到下一位
                i = i-j+1;
                //t串回溯到起始位置
                j = 0;
            }
        }
        
        if (t[j] == '\0') { 
            return i-j;
        }
        return -1;
    }

### 定长顺序串的替换 ###

替换指的是使用串v替换在串s中出现的所有子串t。

因为在之前已经实现过定位、插入和删除的方法，在这里我们直接调用即可。思路是：首先调用定位方法，找到子串t在串s中的位置pos，然后调用删除方法删除从pos位置起长度为t\_len的字符串，最后调用插入方法从pos位置起插入串v。

需要注意的是，因为子串可能不止出现一次，因此需要循环调用定位的方法，当定位失败（不存在子串）或者位置已经超出串s的长度时才能退出循环。

void StrReplace(SString s,SString t,SString v){ 
        int s_len = StrLength(s);
        int t_len = StrLength(t);
        int v_len = StrLength(v);
        
        int index = -1;
        int pos = 0;
        
        while (pos < s_len) { 
            //开始匹配
            index = StrIndex(s, t, pos);
            if (index == -1) { 
                //不存在子串
                return;
            }
            //存在
            //1.先删除t串
            StrDelete(s, index, t_len);
            //2.插入v串
            StrInsert(s, index, v);
            
            pos = index + v_len;
        }
    }

### 全部代码 ###

#### SString.h ####

#ifndef SString_h
    #define SString_h
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXSTRLEN 20
    #define u_char unsigned char
    
    typedef u_char SString[MAXSTRLEN+1];
    
    //初始化
    void InitString(SString s);
    //赋值
    void StrAssign(SString s,char *str);
    //展示
    void PrintString(SString s);
    //拷贝(将t串拷贝到s串来
    void StrCopy(SString s,SString t);
    //判空:0->非空 !0->空
    int StrEmpty(SString s);
    //比较(若s>t 返回值>0 s==t 返回值==0 s<t 返回值<0
    //依次取出对应位置的字符，以ASCII码值进行比较
    int StrCompare(SString s,SString t);
    //求长度
    int StrLength(SString s);
    //链接
    void StrConcar(SString t,SString s1,SString s2);
    void StrConcar2(SString t,SString s1,SString s2);
    //求子串(在s串中从pos位置开始求长度为len的子串，并保存到sub串中
    void SubString(SString s,SString sub,int pos,int len);
    //插入(将t串从pos位置起插入到s串中
    void StrInsert(SString s,int pos,SString t);
    //删除(在s串中从pos位置开始删除长度为len的子串
    void StrDelete(SString s,int pos,int len);
    //清除
    void StrClear(SString s);
    //定位(在s串中寻找子串t,如果找到则返回第一个字符在s串的位置，用pos返回
    int StrIndex(SString s,SString t,int pos);
    //替换(用v替换在s中出现的所有子串t
    void StrReplace(SString s,SString t,SString v);
    
    #endif /* SString_h */

#### SString.c ####

#include "SString.h"
    //初始化->初始化为空串
    void InitString(SString s){ 
        s[0] = '\0';
    }
    
    //赋值
    void StrAssign(SString s,char *str){ 
        //求要赋值的字符串的长度
        int len = (int)strlen(str);
        
        //比较是否超出最大长度
        if (len > MAXSTRLEN) { 
            //超出，只能赋值到最大长度的位置
            len = MAXSTRLEN;
        }
        
        //依次赋值
        for (int i = 0; i < len; i ++) { 
            s[i] = str[i];
        }
        //标记字符串结束
        s[len] = '\0';
    }
    //展示
    void PrintString(SString s){ 
        printf("%s\n",s);
    }
    //拷贝(将t串拷贝到s串来
    void StrCopy(SString s,SString t){ 
        //获取t串长度
        int len = StrLength(t);
        for (int i = 0; i < len; i ++) { 
            s[i] = t[i];
        }
        s[len] = '\0';
    }
    //判空:0->非空 !0->空
    int StrEmpty(SString s){ 
        return s[0] == '\0';
    }
    //比较(若s>t 返回值>0 s==t 返回值==0 s<t 返回值<0 以ASCII码值进行比较
    int StrCompare(SString s,SString t){ 
        int result = 0;
        while (*s != '\0' || *t != '\0') { 
            result = *s - *t;
            if (result != 0) { 
                break;
            }
            s ++;
            t ++;
        }
        return result;
    }
    //求长度
    int StrLength(SString s){ 
        int len = 0;
        while (*s != '\0') { 
            len ++;
            s ++;
        }
        return len;
    }
    //链接
    void StrConcar(SString t,SString s1,SString s2){ 
        int len1 = StrLength(s1);
        int len2 = StrLength(s2);
        
        if (len1 + len2 <= MAXSTRLEN) { 
            //装得下两个子串->直接装入
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            for (int j = 0; j < len2; j ++) { 
                t[len1+j] = s2[j];
            }
            t[len1+len2] = '\0';
        }else if(len1 < MAXSTRLEN){ 
            //只装得下s1和部分s2->s2需要截断
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            for (int j = 0; j < MAXSTRLEN - len1; j ++) { 
                t[len1+j] = s2[j];
            }
            //最后一个位置设为'\0'表示结束
            t[MAXSTRLEN] = '\0';
        }else{ 
            //只装得下s1
            for (int i = 0; i < len1; i ++) { 
                t[i] = s1[i];
            }
            t[MAXSTRLEN] = '\0';
        }
    
    }
    void StrConcar2(SString t,SString s1,SString s2){ 
        int len1 = StrLength(s1);
        int len2 = StrLength(s2);
        
        //先将s1装入
        for (int i = 0; i < len1; i ++) { 
            t[i] = s1[i];
        }
        
        //判断t剩余的空间情况
        if (MAXSTRLEN-len1 > 0) { 
            //还未满
            //判断是否能把整个s2装下
            if (len1+len2 <= MAXSTRLEN) { 
                //是
                for (int j = 0; j < len2; j ++) { 
                    t[len1+j] = s2[j];
                }
                t[len1+len2] = '\0';
            }else{ 
                //否，s2需要截断
                for (int j = 0; j < MAXSTRLEN - len1; j ++) { 
                    t[len1+j] = s2[j];
                }
                //最后一个位置设为'\0'表示结束
                t[MAXSTRLEN] = '\0';
            }
        }
    }
    //求子串(在s串中从pos位置开始求长度为len的子串，并保存到sub串中
    void SubString(SString s,SString sub,int pos,int len){ 
        //判断位置是否合法
        int s_len = StrLength(s);
        if (pos<0 || pos>= s_len || len<0 || len>s_len || pos+len>s_len) { 
            printf("要截取的位置或长度不合法\n");
            return;
        }
        
        for (int i = 0; i < len; i ++) { 
            sub[i] = s[pos+i];
        }
        sub[len] = '\0';
        
    }
    //插入(将t串从pos位置起插入到s串中
    void StrInsert(SString s,int pos,SString t){ 
        int s_len = StrLength(s);
        int t_len = StrLength(t);
        
        //长度不足->只能插入t串的一部分
        if (s_len+t_len > MAXSTRLEN) { 
            t_len = MAXSTRLEN-s_len;
        }
        //将原来pos位置的字符挪到pos+t_len上
        for (int i = s_len-1; i>=pos; i --) { 
            s[i+t_len] = s[i];
        }
        //将t串插入到pos位置上
        int j = pos;
        for (int i = 0; i < t_len; i++) { 
            s[j+i] = t[i];
        }
        s[s_len+t_len] = '\0';    
    }
    //删除(在s串中从pos位置开始删除长度为len的子串
    void StrDelete(SString s,int pos,int len){ 
        int s_len = StrLength(s);
        if (pos < 0 || pos > s_len || len < 0 || len > s_len) { 
            printf("要删除的位置或长度非法\n");
            return;
        }
        for (int i = pos; i < s_len; i ++) { 
            s[i] = s[i+len];
        }
        s[s_len - len] = '\0';
    }
    //清除
    void StrClear(SString s){ 
        s[0] = '\0';
    }
    
    //定位(在s串中从pos位置起寻找子串t,如果找到则返回第一个字符在s串的位置
    int StrIndex(SString s,SString t,int pos){ 
        //标记s串的位置
        int i = pos;
        //标记t串的位置
        int j = 0;
        
        while (s[i]!='\0' && t[j]!='\0') { 
            //判断两个字符是否相等
            if (s[i] == t[j]) { 
                //相等，找到下一个位置
                i ++;
                j ++;
            }else{ 
                //不相等,s串回溯到与t串开始相等的位置，并且挪到下一位
                i = i-j+1;
                //t串回溯到起始位置
                j = 0;
            }
        }
        
        if (t[j] == '\0') { 
            return i-j;
        }
        return -1;
    }
    
    //替换(用v替换在s中出现的所有子串t
    void StrReplace(SString s,SString t,SString v){ 
        int s_len = StrLength(s);
        int t_len = StrLength(t);
        int v_len = StrLength(v);
        
        int index = -1;
        int pos = 0;
        
        while (pos < s_len) { 
            //开始匹配
            index = StrIndex(s, t, pos);
            if (index == -1) { 
                //不存在子串
                return;
            }
            //存在
            //1.先删除t串
            StrDelete(s, index, t_len);
            //2.插入v串
            StrInsert(s, index, v);
            
            pos = index + v_len;
        }
    }

#### Main.c ####

#include "SString.h"
    
    int main(int argc, const char * argv[]) { 
        
        SString s;
        InitString(s);
        SString t;
        InitString(t);
        
        //赋值
        char *str = "abcd";
        StrAssign(s, str);
        char *str2 = "xyz";
        StrAssign(t, str2);
        
        //比较
        int result = StrCompare(s,t);
        printf("compare:%d\n",result);
        
        //拷贝
        //StrCopy(t,s);
        //PrintString(t);
        
        //连接
        SString y;
        InitString(y);
        StrConcar2(y,s,t);
        PrintString(y);
        
        //求子串
        SString sub;
        InitString(sub);
        SubString(y, sub, 2, 3);
        PrintString(sub);
        
        //插入
        StrInsert(s, 1, t);
        PrintString(s);
        
        //删除
        StrDelete(s, 1, 2);
        PrintString(s);
        
        //定位
        SString s1;
        InitString(s1);
        StrAssign(s1, "ababcababcab");
        
        SString s2;
        InitString(s2);
        StrAssign(s2, "abc");
        
        result = StrIndex(s1, s2, 0);
        printf("index:%d\n",result);
        
        //替换
        SString s3;
        InitString(s3);
        StrAssign(s3, "xy");
        
        StrReplace(s1, s2, s3);
        PrintString(s1);
        
        return 0;
    }

[img_1]: https://img-blog.csdnimg.cn/20200116135114728.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70
[img_2]: https://img-blog.csdnimg.cn/2020011613513552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjY0MzIxNg==,size_16,color_FFFFFF,t_70