找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ JAVA开发技术 ] 【守望者 j2se】String结构模拟

2014-10-12 15:13| 发布者: zhouy | 查看: 1268 | 收藏

摘要: 我们开始模拟一下大家最熟悉的String数据结构的模拟,这个相信做java的没有不熟悉的吧.那我们开始1.操作接口 public interface IString { public void clear(); //将一个已经存在的串置成空串 public boolean ...

我们开始模拟一下大家最熟悉的String数据结构的模拟,这个相信做java的没有不熟悉的吧.那我们开始

1.操作接口

  public interface IString {
   
     public void clear();          //将一个已经存在的串置成空串
     public boolean isEmpty();    //判断当前串是否为空,为空则返回true,否则返回false
     public int length();         //返回字符串的长度
     public char charAt(int index);   //返回串中序号为index的字符
     public IString substring(int begin, int end); //返回串中字符序号从begin至end-1的子串
     public IString insert(int offset, IString str);  //在当前串的第offset个字符之前插入串str
     public IString delete(int begin, int end);   //删除当前串中从序号begin开始到序号end-1为止的子串
     public IString concat(IString str);  //添加指定串str到当前串尾
     //将当前串与目标串str进行比较,若当前串大于str,则返回一个正整数,若当前串等于str,则返回0,若当前串小于str,则返回一个负整数。
     public int compareTo(IString str);
     //若当前串中存在和str相同的子串,则返回模式串str在主串中从第start字符开始的第一次出现位置,否则返回-1
     public int indexOf(IString str,int start);

}


2.实现操作(顺序串的实现)

public class SeqString  implements  IString{
   
    private char[] strvalue;            //字符数组,存放串值
     private int curlen;                //当前串的长度
     //构造方法1,构造一个空串
     public SeqString() {
         strvalue = new char[0];
         curlen = 0;
     }


     //构造方法2,以字符串常量构造串对象
     public SeqString(String str) {
         if (str != null) {
             char[] tempchararray = str.toCharArray();
             strvalue = tempchararray;
             curlen = tempchararray.length;
         } 
     }


     //构造方法3,以字符数组构造串对象
     public SeqString(char[] value) {
         this.strvalue = new char[value.length];
         for (int i = 0; i < value.length; i++) { //复制数组
             this.strvalue = value;
         }
         curlen = value.length;
     }

     //将一个已经存在的串置成空串
     public void clear() {
         this.curlen = 0;
     }

     //判断当前串是否为空,为空则返回true,否则返回false
     public boolean isEmpty() {
         return curlen == 0;
     }
     //返回字符串长度
     public int length() {
         return curlen;    //区别: strvalue.length是数组容量
     }



     //返回字符串中序号为index的字符
     public char charAt(int index) {
         if ((index < 0) || (index >= curlen)) {
             throw new StringIndexOutOfBoundsException(index);
         }
         return strvalue[index];
     }



     //将字符串中序号为index的字符设置为ch
     public void setCharAt(int index, char ch) {
         if ((index < 0) || (index >= curlen)) {
             throw new StringIndexOutOfBoundsException(index);
         }
         strvalue[index] = ch;
     }
     public void allocate(int newCapacity) //扩充容量,参数指定最小容量
     {
         char[] temp = strvalue;                           //复制数组
         strvalue = new char[newCapacity];
         for (int i = 0; i < temp.length; i++) {
             strvalue = temp;
         }
     }



     //返回串中序号从begin至end-1的子串
     public IString substring(int begin, int end) {
         if (begin < 0) {
             throw new StringIndexOutOfBoundsException("起始位置不能小于0");
         }
         if (end > curlen) {
             throw new StringIndexOutOfBoundsException("结束位置不能大于串的当前长度:" + curlen);
         }
         if (begin > end) {
             throw new StringIndexOutOfBoundsException("开始位置不能大于结束位置");
         }
         if (begin == 0 && end == curlen) {
             return this;
         } else {
             char[] buffer = new char[end - begin];
             for (int i = 0; i < buffer.length; i++) //复制子串
             {
                 buffer = this.strvalue[i + begin];
             }
             return new SeqString(buffer);
         }
     }
     //返回串中序号从begin至串尾的子串
     public IString substring(int begin) {
         return substring(begin,strvalue.length);
     }



     //在当前串的第offset个字符之前插入串str,0<=offset<=curlen
     public IString insert(int offset, IString str) {
         if ((offset < 0) || (offset > this.curlen)) {
             throw new StringIndexOutOfBoundsException("插入位置不合法");
         }
         int len = str.length();
         int newCount = this.curlen + len;
         if (newCount > strvalue.length) {
             allocate(newCount);             // 插入空间不足,需扩充容量
         }
         for (int i = this.curlen - 1; i >= offset; i--) {
             strvalue[len + i] = strvalue;    //从offset开始向后移动len个字符
         }
         for (int i = 0; i < len; i++) //复制字符串str
         {
             strvalue[offset + i] = str.charAt(i);
         }
         this.curlen = newCount;
         return this;
     }



     //删除从begin到end-1的子串, 0≤begin≤length()-1,1≤end≤length()。
     public IString delete(int begin, int end) {
         if (begin < 0) {
             throw new StringIndexOutOfBoundsException("起始位置不能小于0");
         }
         if (end > curlen) {
             throw new StringIndexOutOfBoundsException("结束位置不能大于串的当前长度:" + curlen);
         }
         if (begin > end) {
             throw new StringIndexOutOfBoundsException("开始位置不能大于结束位置");
         }
         for (int i = 0; i < curlen - end; i++) //从end开始至串尾的子串向前移动到从begin开始的位置
         {
             strvalue[begin + i] = strvalue[end + i];
         }
         curlen = curlen - (end - begin);  //当前串长度减去end-begin
         return this;
     }



     //添加指定串str到当前串尾
     public IString concat(IString str) {
         return insert(curlen, str);
     }



     //将字符c连接到到当前串尾
     public IString concat(char c) {
         int newCount = curlen + 1;
         if (newCount > strvalue.length) {
             allocate(newCount);
         }
         strvalue[curlen++] = c;
         return this;
     }
     //比较串
     public int compareTo(IString str) {
         return compareTo((SeqString) str);
     }
     public int compareTo(SeqString str) {  //比较串
         //若当前对象的串值大于str的串值,则函数返回一个正整数
         //若当前对象的串值等于str的串值,则函数返回0
         //若当前对象的串值小于str的串值,则函数返回一个负整数
         int len1 = curlen;
         int len2 = str.curlen;
         int n = Math.min(len1, len2);
         //char s1[] = strvalue;
         //char s2[] = str.strvalue;
         //int k = 0;
         //while (k < n) {
         //    char ch1 = s1[k];
         //    char ch2 = s2[k];
         //    if (ch1 != ch2) {
         //        return ch1 - ch2;  //返回第一个不相等字符的数值差
         //    }
        //     k++;
         //}
         for (int k=0;k<n;k++)
              if (strvalue[k]!=str.strvalue[k])
                  return(strvalue[k]-str.strvalue[k]);
         return len1 - len2;   //返回两个字符串长度的数值差
     }
     public String toString() {
         return new String(strvalue, 0, curlen);   //以字符数组strvalue构造串
     }
     // 模式匹配的Brute-Force 算法
     //返回模式串t在主串中从start开始的第一次匹配位置,匹配失败时返回-1。
     public int index_BF(SeqString t, int start) {
         if (this != null && t != null && t.length() > 0 && this.length() >= t.length()) {  //当主串比模式串长时进行比较
             int slen, tlen, i = start, j = 0;    //i表示主串中某个子串的序号
             slen = this.length();
             tlen = t.length();
             while ((i < slen) && (j < tlen)) {
                 if (this.charAt(i) == t.charAt(j)) //j为模式串当前字符的下标
                 {
                     i++;
                     j++;
                 } //继续比较后续字符
                 else {
                     i = i - j + 1;        //继续比较主串中的下一个子串
                     j = 0;                //模式串下标退回到0
                 }
             }
             if (j >= t.length()) //一次匹配结束,匹配成功
             {
                 return i - tlen;         //返回子串序号
             } else {
                 return -1;
             }
         }
         return -1;                     //匹配失败时返回-1
     }
     //若当前串中存在和str相同的子串,则返回模式串str在主串中从第start字符开始的第一次出现位置,否则返回-1
     public int indexOf(IString t, int start) {
         return index_KMP(t, start);
     }


     //KMP模式匹配算法
     public int index_KMP(IString T, int start) {
         //在当前主串中从start开始查找模式串T
         //若找到,则返回模式串T在主串中的首次匹配位置,否则返回-1
         int[] next = getNext(T);     //计算模式串的next[]函数值
         int i = start;               //主串指针
         int j = 0;                   //模式串指针
         //对两串从左到右逐个比较字符
         while (i < this.length() && j < T.length()) {
             //若对应字符匹配
             if (j == -1 || this.charAt(i) == T.charAt(j)) { // j==-1表示S!=T[0]
                 i++;
                 j++;         //则转到下一对字符
             } else //当S不等于T[j]时
             {
                 j = next[j];        //模式串右移
             }
         }
         if (j < T.length()) {
             return -1;                  //匹配失败
         } else {
             return (i - T.length());    //匹配成功
         }
     }
    


//计算模式串T的next[]函数值
    private int[] getNext(IString T) {
         int[] next = new int[T.length()];  //next[]数组
         int j = 1;    //主串指针
         int k = 0;   //模式串指针
         next[0] = -1;
         if (T.length()>1)
            next[1] = 0;
         while (j < T.length() - 1) {
             if (T.charAt(j) == T.charAt(k)) {  //匹配
                 next[j + 1] = k + 1;
                 j++;
                 k++;
             } else if (k == 0) {  //失配
                 next[j + 1] = 0;
                 j++;
             } else {
                 k = next[k];
             }
         }
         return (next);
     }
     

//计算模式串T的nextval[]函数值
     private int[] getNextVal(IString T) {
         int[] nextval = new int[T.length()];  //nextval[]数组
         int j = 0;
         int k = -1;
         nextval[0] = -1;
         while (j < T.length() - 1) {
             if (k == -1 || T.charAt(j) == T.charAt(k)) {
                 j++;
                 k++;
                 if (T.charAt(j) != T.charAt(k)) {
                     nextval[j] = k;
                 } else {
                     nextval[j] = nextval[k];
                 }
             } else {
                 k = nextval[k];
             }
         }
         return (nextval);
     }
}

小结:还有能不能用链表实现呢?当然这样不是很好,但是可以锻炼思维和动手能力

推荐阅读

【守望者  j2se】ConcurrentHashMap原理分析
【守望者 j2se】ConcurrentHashMap原
集合是编程中最常用的数据结构。而谈到并发,几乎总是离不开集合这类高级数据
【守望者  j2se】双向链表模拟
【守望者 j2se】双向链表模拟
我们熟悉了java单向链表的模拟,现在我就必须开始双向链表的模拟的.1.基础结构
【守望者 高并发】现有高并发WEB服务器 lighttpd Apache Nginx比较
【守望者 高并发】现有高并发WEB服务器
lighttpd网络服务器基于的Lighttpd的网络服务器具有这样的特点:占用内存资源
【守望者 高并发】C10K/C500K与I/O框架
【守望者 高并发】C10K/C500K与I/O框架
C10K、C/500K问题C10K 的意思是10000并发请求,C500K意思是500 000并发请求,
【守望者  j2se】虚拟机各部分内存溢出情况
【守望者 j2se】虚拟机各部分内存溢出
通过简单的小例子程序,演示java虚拟机各部分内存溢出情况:(1).java堆溢出:
【守望者  JMM】理解volatile内存语义
【守望者 JMM】理解volatile内存语义
理解volatile变量对写多线程程序还是很有帮助的,这样就会避免一上来就是syn这
【守望者 高并发】使用CAS实现高效并发处理
【守望者 高并发】使用CAS实现高效并发
守望者:在并发处理应用中,一般使用锁的方式来解决竞争问题,但锁的效率比较
【守望者  j2se】吃透 java I/O 工作机制-1
【守望者 j2se】吃透 java I/O 工作机
I/O 问题可以说是当今互联网 Web 应用中所面临的主要问题之一,因为当前在这
【守望者 大数据】Mahout学习路线图
【守望者 大数据】Mahout学习路线图
Hadoop家族产品,常用的项目包括Hadoop, Hive, Pig, HBase, Sqoop, Mahout, Z
【守望者 j2se】ConcurrentMap之putIfAbsent(key,value)用法讨论
【守望者 j2se】ConcurrentMap之putIfA
先看一段代码:public class Locale { private final static MapString, Lo
【守望者  javascript】判断IE浏览器世界上最短的代码
【守望者 javascript】判断IE浏览器世
最短的IE判定var ie=!-分析以前最短的IE判定借助于IE不支持垂直制表符的特性
【守望者 大数据】机器学习已成为大数据的基石
【守望者 大数据】机器学习已成为大数
机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、
【守望者  j2se】多线程与并发知识点总结
【守望者 j2se】多线程与并发知识点总
对于多线程和并发编程这个比较大的技术模块,我们会整理一些帖子方便知识点的
【守望者  j2se】二叉树模拟
【守望者 j2se】二叉树模拟
接着我们就要写一个比较复杂的数据结构的,但是这个数据结构是很重要的,假如
【守望者 SRS  】SRS 源代码分析笔记(0.9.194)-分析服务器对端口的监听 ...
【守望者 SRS 】SRS 源代码分析笔记(
第一部分 分析服务器对端口的监听 端口监听与初始化(一)全局变量_srs_confi

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved