数据结构--串的实现

﹏ヽ暗。殇╰゛Y 2021-08-13 13:45 367阅读 0赞

### 串 ###

*  串定义：S=“s0 S1 … Sn-1”
 *  子串：“at” 是 “data” 的子串
 *  串比较：两个串可以比较收否相等，也可比较大小。

串的顺序存储结构：  
![在这里插入图片描述][20200118135732769.png]

串的链式存储结构  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]

### 串的抽象数据类型 ###

package pers.zhang.string;
    
    /** * @author zhang * @date 2020/1/18 - 13:19 * * 串的抽象数据类型 */
    public interface SString { 
    
        //返回字符串的长度
        int length();
    
        //返回第i（i>=0）个字符
        char charAt(int i);
    
        //返回当前串与str串连接生成的新串
        SString concat(SString str);
    
        //返回串中字符序号从begin到end-1的子串
        SString substring(int begin, int end);
    
        //返回pattern串在主串中的第一次匹配位置
        int indexOf(SString pattern);
    }

### 串的顺序存储实现 ###

package pers.zhang.string;
    
    /** * @author zhang * @date 2020/1/18 - 13:23 * * 串的实现 */
    public class MyString implements Comparable<MyString>, java.io.Serializable{ 
    
        //字符数组，私有最终变量，只能赋值一次
        private final char[] value;
    
        //构造一个空串
        public MyString() { 
            this.value = new char[0];
        }
    
        //由字符串常量构造串对象
        public MyString(String original){ 
            this.value = original.toCharArray();
        }
    
        //以value数组中从begin开始的count个字符构造串对象
        public MyString(char[] value, int begin, int count){ 
            this.value = new char[count];
            for(int i = begin; i < begin + count; i++)
                this.value[i] = value[i];
        }
    
        //以value数组中字符构造串对象
        public MyString(char[] value){ 
            this(value, 0, value.length);
        }
    
        //拷贝构造
        public MyString(MyString str){ 
            this(str.value);
        }
    
        //比较当前串与str串的大小，返回两者差值，实现Comparable接口
        @Override
        public int compareTo(MyString str) { 
            for(int i = 0; i < this.value.length && i < str.value.length; i++)
                if(this.value[i] != str.value[i])
                    return this.value[i] - str.value[i];//返回两串第一个不同字符的差值
            return this.value.length - str.value.length;//前缀子串，返回两串长度的差值
        }
    
        //返回字符串长度
        public int length() { 
            return this.value.length;
        }
    
        //返回第i（i>=0）个字符
        public char charAt(int i) { 
            if(i < 0 || i >= this.value.length)
                throw new StringIndexOutOfBoundsException(i);
            return this.value[i];
        }
    
        //返回当前串与指定串str连接生成的新串，不改变当前串
        public MyString concat(MyString str) { 
            if(str.length() == 0)//连接空串，返回当前串
                return this;
            char[] buffer = new char[this.value.length + str.length()];
            int i;
            for(i = 0; i < this.value.length; i++)
                buffer[i] = this.value[i];
            for(int j = 0; j < str.value.length; j++)
                buffer[i + j] = str.value[j];
            return new MyString(buffer);
        }
    
        //返回串中序号从begin至end-1的子串
        public MyString substring(int begin, int end) { 
            if(begin < 0)
                begin = 0;
            if(end > this.value.length)
                end = this.value.length;
            if(begin == 0 && end == this.value.length)
                return this;
            if(begin > end)
                throw new StringIndexOutOfBoundsException(end - begin);
            char[] buffer = new char[end - begin];
            for (int i = 0; i < buffer.length; i++)
                buffer[i] = this.value[i + begin];
            return new MyString(buffer);
        }
    
        //返回串中序号从begin至串尾的子串
        public MyString substring(int begin){ 
            return substring(begin, this.value.length);
        }
    
    
        @Override
        public String toString(){ 
            return new String(this.value);
        }
    
        //比较当前串是否与obj引用的串相等 ，覆盖Object类的equals(obj)方法
        public boolean equals(Object obj){ 
            if (this == obj)//同一对象
                return true;
            if (obj instanceof MyString)//同类对象
            { 
                MyString str = (MyString)obj;
                if (this.value.length == str.value.length){ //比较长度
                    for (int i=0; i<this.value.length; i++)//逐个比较
                        if (this.value[i]!=str.value[i])
                            return false;
                    return true;
                }
            }
            return false;
        }
    
        //返回ch字符在当前串中首次出现的序号
        public int indexOf(char ch){ 
            for (int i = 0; i < this.value.length; i++)
                if (this.value[i] == ch)
                    return i;
            return -1;
        }
    
        //串的模式匹配，Brute-Force算法
        //返回模式串pattern在当前串this（目标串target）中从begin开始的首次匹配位置，匹配失败时返回-1
        int count=0;//记载比较次数
        public int indexOf(MyString pattern, int begin){ 
            if (pattern.length() > 0 && this.length() >= pattern.length()){ //当目标串比模式串长时进行比较
                int i = begin, j = 0;                              //i、j分别为目标串和模式串当前字符的下标
                count = 0;
                while (i < this.length()){ 
                    if (this.charAt(i) == pattern.charAt(j)){      //若当前两字符相等，则继续比较后续字符
                        i++;
                        j++;
                    }else{                                        //否则i、j回溯，进行下一次匹配
                        i = i - j + 1;                               //目标串下标i退回到下一个待匹配子串首字符
                        j = 0;                                   //模式串下标j退回到0
                    }
                    count++;
                    if (j == pattern.length())                   //一次匹配结束，匹配成功
                        return i-j;                            //返回匹配的子串序号
                }
            }
            return -1;                                         //匹配失败时返回-1
        }
    
        //返回模式串pattern在当前串中的首次匹配位置，匹配失败时返回-1
        public int indexOf(MyString pattern){ 
            return this.indexOf(pattern, 0);
        }
    
        //返回将当前串中首个与pattern匹配的子串替换成replacement的字符串
        public MyString replaceFirst(MyString pattern, MyString replacement){ 
            int i = this.indexOf(pattern,0);                     //返回匹配子串的序号，从0开始查找
            if (i == -1)
                return this;                                   //匹配失败时返回当前串
            return this.substring(0,i).concat(replacement).concat(this.substring(i+pattern.length()));//连接3个串
        }
    
        //返回将当前串中所有与pattern匹配的子串全部替换成replacement的字符串
        public MyString replaceAll(MyString pattern, MyString replacement){ 
            MyString temp = new MyString(this);                //拷贝构造方法，复制当前串
            int i = this.indexOf(pattern,0);
            while (i != -1){ 
                temp = temp.substring(0,i).concat(replacement).concat(temp.substring(i+pattern.length()));
                i=temp.indexOf(pattern, i+replacement.length());//从下一个字符开始再次查找匹配子串
    // i=temp.indexOf(pattern, i+1); //错
            }
            return temp;
        }
    
        //将串中的大写字母全部转换成对应的小写字母
        public MyString toLowerCase(){ 
            char temp[] = new char[this.value.length];
            for (int i = 0; i < this.value.length; i++)
                if (this.value[i] >= 'A' && this.value[i] <= 'Z')  //大写字母
                    temp[i] = (char)(this.value[i] + 'a' - 'A');     //转换成对应小写字母
            return new MyString(temp);
        }
    
        //将串中的小写字母全部转换成对应的大写字母
        public MyString toUpperCase(){ 
            char temp[] = new char[this.value.length];
            for (int i = 0; i < this.value.length; i++)
                if (this.value[i] >= 'a' && this.value[i] <= 'z')  //小写字母
                    temp[i] = (char)(this.value[i] - ('a'-'A'));   //转换成对应大写字母
            return new MyString(temp);
        }
    
        //返回字符数组
        public char[] toCharArray(){ 
            char[] temp = new char[this.value.length];
            for (int i = 0; i < temp.length; i++)                  //复制数组
                temp[i] = this.value[i];
            return temp;
        }
    
        //判断prefix是否前缀子串
        public boolean startsWith(MyString prefix){ 
            if (this.value.length < prefix.value.length)
                return false;
            for (int i = 0; i < prefix.value.length; i++)
                if (this.value[i] != prefix.value[i])
                    return false;
            return true;
        }
    
        //判断suffix是否后缀子串
        public boolean endsWith(MyString suffix){ 
            int j = suffix.value.length-1;
            for (int i = this.value.length - 1; i >= 0 && j >= 0; i--,j--)
                if (this.value[i] != suffix.value[j])
                    return false;
            return j == -1;
        }
    
        //比较当前串与str串是否相等，忽略字母大小写
        public boolean equalsIgnoreCase(MyString str){ 
            if (this == str)
                return true;
            if (this.value.length == str.value.length){ 
                for (int i = 0; i < this.value.length; i++){ 
                    int c1 = this.value[i];
                    if (c1 >= 'a' && c1 <= 'z')
                        c1 -= 'a'-'A';
                    int c2 = str.value[i];
                    if (c2 >= 'a' && c2 <= 'z')
                        c2 -= 'a'-'A';
                    if (c1 != c2)
                        return false;
                }
                return true;
            }
            return false;
        }
    
        //比较两个串大小，忽略字母大小写
        public int compareToIgnoreCase(MyString str){ 
            for (int i = 0; i < this.value.length && i < str.value.length; i++){ 
                int c1 = this.value[i];
                if (c1 >= 'a' && c1 <= 'z')
                    c1 -= 'a'-'A';
                int c2 = str.value[i];
                if (c2 >= 'a' && c2 <= 'z')
                    c2 -= 'a'-'A';
                if (c1 != c2)
                    return this.value[i] - str.value[i];
            }
            return this.value.length - str.value.length;
        }
    
        //返回删除所有空格后的字符串
        public MyString trim(){ 
            char temp[] = new char[this.value.length];
            int j = 0;
            for (int i = 0; i < this.value.length; i++)
                if (this.value[i] != ' ')
                    temp[j++] = this.value[i];
            return new MyString(temp,0,j);                     //以temp数组中从0开始的j个字符构造串对象
        }
    }

### 测试 ###

package pers.zhang.string;
    
    /** * @author zhang * @date 2020/1/18 - 13:59 */
    public class MyString_ex { 
        public static void main(String args[])
        { 
            //1. String类声明
    /* MyString s1 = new MyString(); //构造一个空串 MyString s2 = new MyString("xyz"); //以java.lang.String字符串常量构造串对象 char[] letters={'a','b','c','d'}; //字符数组，只能在声明时赋值，不能赋值为"abcd" MyString s3 = new MyString(letters); //以字符数组构造串对象 letters[0]='y'; //数组元素改了，对串没影响 MyString s4 = new MyString(s3); //拷贝构造方法 System.out.println("s1=\""+s1.toString()+"\""); System.out.println("s2=\""+s2.toString()+"\""); System.out.println("s3=\""+s3.toString()+"\""); System.out.println("s4=\""+s4.toString()+"\""); MyString s5=s2; //对象引用赋值 System.out.println("\""+s5.toString()+"\"==\""+s2.toString()+"\"? "+(s5==s2)); System.out.println("\""+s3.toString()+"\"==\""+s4.toString()+"\"? "+(s3==s4)); System.out.println("\""+s3.toString()+"\".equals(\""+s4.toString()+"\")? "+s3.equals(s4)); System.out.println("\""+s3.toString()+"\".compareTo(\""+s4.toString()+"\")? "+s3.compareTo(s4)); System.out.println("\""+s2.toString()+"\".equals(\""+s3.toString()+"\")? "+s2.equals(s3)); System.out.println("\""+s2.toString()+"\".compareTo(\""+s3.toString()+"\")? "+s2.compareTo(s3)); //2. 连接串 MyString s1=new MyString("abcd"), s2=new MyString("xyz"); System.out.println("s1.concat(s2)=\""+s1.concat(s2).toString()+"\""); //s1.concat(s2)="abcdxyz" //3. 求子串 MyString s=new MyString("abcdefgh"); System.out.println(s.substring(2,5).toString()); //cde // MyString target=new MyString("ababdabcd"); //目标串 // MyString pattern=new MyString("abc"); //模式串 // MyString target=new MyString("aabaaa"), pattern=new MyString("aab"); //最好情况， // MyString target=new MyString("aaaaa"), pattern=new MyString("aab"); //最坏情况，匹配不成功， MyString target=new MyString("aaaab"), pattern=new MyString("aab"); //最坏情况，匹配成功 System.out.println("\""+target+"\".indexOf(\""+pattern+"\")="+target.indexOf(pattern)); System.out.println("BF.count="+target.count); MyString target=new MyString("ababdabcdabcabc"); //目标串， MyString pattern=new MyString("abc"); //模式串 MyString replacement=new MyString("xy"); //替换串 */
            MyString target=new MyString("aaaa");              //目标串，
            MyString pattern=new MyString("a");                //模式串
            MyString replacement=new MyString("ab");           //替换串
    
            System.out.println("\""+target+"\".replaceFirst(\""+pattern+"\", \""+replacement+"\")="+
                    target.replaceFirst(pattern,replacement));
            System.out.println("\""+target+"\".replaceAll(\""+pattern+"\", \""+replacement+"\")="+
                    target.replaceAll(pattern,replacement));
    
    /* System.out.println("\""+s3.toString()+"\".startsWith(\""+s2.toString()+"\")? "+s3.startsWith(s6)); System.out.println("\""+s3.toString()+"\".endsWith(\""+s2.toString()+"\")? "+s3.endsWith(s2)); System.out.println("\""+s2.toString()+"\".equalsIgnoreCase(\"XYZ\")? "+ s2.equalsIgnoreCase(new MyString("XYZ"))); System.out.println("\""+s4.toString()+"\".compareToIgnoreCase(\"ABCDEF\")? "+ s4.compareToIgnoreCase(new MyString("ABCDEF"))); */
        }
    }
    /* 程序运行结果如下： s1="" s2="xyz" s3="abcd" s4="abcd" "xyz"=="xyz"? true "abcd"=="abcd"? false "abcd".equals("abcd")? true "abcd".compareTo("abcd")? 0 "xyz".equals("abcd")? false "xyz".compareTo("abcd")? 23 "abcdxyz".startsWith("xyz")? true "abcdxyz".endsWith("xyz")? true "xyz".equalsIgnoreCase("XYZ")? true "abcd".compareToIgnoreCase("ABCDEF")? -2 朴素的模式匹配（Brute-Force）算法 "ababdabcd".indexOf_BF("abc")=5 BF.count=12 "aabaaa".indexOf("aab")=0 //最好情况， BF.count=3 "aaaaaa".indexOf("aab")=-1 //最坏情况 BF.count=14 //比较m*(n-m+1)次，O(n*m) "aaaaa".indexOf("aab")=-1 //最坏情况，匹配不成功 BF.count=11 "aaaab".indexOf("aab")=2 //最坏情况，匹配成功 BF.count=9 //替换子串 "ababdabcdabcabc".replaceFirst("abc", "xy")=ababdxydabcabc "ababdabcdabcabc".replaceAll("abc", "xy")=ababdxydxyxy //替换子串 "aaaa".replaceFirst("a", "ab")=abaaa "aaaa".replaceAll("a", "ab")=abababab **/

[20200118135732769.png]: /images/20210813/12da92d0e0364e579c797ad3924c9af0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbGRfX19wbGF5_size_16_color_FFFFFF_t_70]: /images/20210813/9de7961b2ca0446ca62b082780836a4e.png