概述

字符串的应用已经非常广泛，如信息检索、文字编辑、自然语言的翻译等都离不开字符串。在各种高级语言的程序设计中都会有字符串类型，虽然各种语言的表现方式各自不同，但其实现原理基本相同。熟悉java语言的人定会感受到String类的强大和实用性，但是其是如何实现的呢？这就是下面所要讲的内容。

从逻辑关系上来看，串是一各特殊的线性表。它与一般线性表的区别是：一般线性表的操作通常以表内的数据元素为操作对象，而串的操作则主要将串作为一个整体加以操作。

（1）求字符串的长度

（2）求指定索引处的 char 值

（3）指定字符在此字符串中第一次出现处的索引

（4）指定字符串在此字符串中第一次出现处的索引

（5）求子串

（6）插入字符串

（7）删除子串

（8）替换子串

（9）连接字符串

（10）字符串比较

串的接口定义

根据串的主要操作，对串的抽象数据类型定义Str接口如下：

package string;public interface Str extends Comparable{	/**	 * 求字符串的升长度	 * @return	 */	public int length();	/**	 * 返回指定索引处的 char 值	 * @param index char值的索引	 * @return 此字符串指定索引处的 char 值。第一个 char 值在索引 0 处。 	 */	public char charAt(int index);	/**	 *  返回指定字符在此字符串中第一次出现处的索引	 * @param c 一个字符（Unicode 代码点）	 * @return 在该对象表示的字符序列中第一次出现该字符的索引，如果未出现该字符，则返回 -1	 */	public int indexOf(char c);	/**	 * 	 * @param c 一个字符（Unicode 代码点）	 * @param from 开始搜索的索引	 * @return 在此对象表示的字符序列中第一次出现的大于或等于 fromIndex 的字符的索引，如果未出现该字符，则返回 -1	 */	public int indexOf(char c, int from);	/**	 * 返回第一次出现的指定子字符串在此字符串中的索引	 * @param str 任意字符串	 * @return 返回第一次出现的指定子字符串在此字符串中的索引；如果它不作为一个子字符串出现，则返回 -1	 */	public int indexOf(Str str);	/**	 * 从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引	 * @param str 要搜索的子字符串	 * @param from 开始搜索的索引位置	 * @return 从指定的索引处开始，返回第一次出现的指定子字符串在此字符串中的索引	 */	public int indexOf(Str str, int from);	/**	 * 求子串	 * @param strartIndex 开始处的索引（包括）	 * @return  返回一个从beginIndex到末尾的新字符串，它是此字符串的一个子字符串	 */	public Str substring(int strartIndex);	/**	 *  求子串	 * @param beginIndex 开始处的索引（包括）	 * @param endIndex 结束处的索引（不包括）	 * @return 返回一个从beginIndex到endIndex-1的新字符串，它是此字符串的一个子字符串	 */	public Str substring(int beginIndex, int endIndex);	/**	 * 插入字符串	 * @param posit	 * @param str	 * @return	 */	public Str insert(int posit, Str str);	/**	 * 删除子串	 * @return	 */	public Str delete(int begin, int end);	/**	 * 替换子串	 * @param target 要被替换的子串	 * @param replacement 要替换的子串	 * @return	 */	public Str replace(Str target, Str replacement);	/**	 * 替换子串	 * @param target 要被替换的子串	 * @param replacement 要替换的子串	 * @param from 开始查找的位置	 * @return	 */	public Str replace(Str target, Str replacement, int from);	/**	 * 连接字符串	 * @param str	 * @return	 */	public Str concat(Str str);	/**	 * 转化成数组	 * @return	 */	public char[] toCharArray();}

串的存储结构有顺序结构、链式结构和堆结构，下面主要对顺序串作一介绍。

对于串操作而言有两种方式：一种是操作后当前串的值不变，操作的结果是产生一个新的串对象；另一种操作结果体现在当前串上，同时也返加该当前串本身。

串值可变的顺序串

package string;public class ArrayStr implements Str {	private int len;	private char[] s;		public ArrayStr() {		len = 0;		//s = new char[0];	}		public ArrayStr(char[] ch) {		len = ch.length;		s = ch;	}		public ArrayStr(Str s) {		len = s.length();		for(int i=0; i
    
      len) {			throw new StringIndexOutOfBoundsException(index);		}		return s[index];	}	@Override	public int compareTo(Object o) {		Str s2 = (Str)o;		int n = Math.min(len, s2.length());		int i = 0;		while(i
     
       len) {			throw new StringIndexOutOfBoundsException(pos);		} else {			Str s2 = this.substring(pos);			delete(pos, len);			concat(str);			concat(s2);		}		return this;	}	@Override	public int length() {		return len;	}		@Override	public Str replace(Str target, Str replacement) {		return replace(target, replacement, 0);	}			@Override	public Str replace(Str target, Str replacement, int from) {		int tLen = target.length();		int rLen = replacement.length();		int pos, k = 0;		while(k
     
    

测试串操作

package string;public class Test {	public static void main(String[] args) {		Str s = new ArrayStr("data structure!");		Str s2 = new ArrayStr("hello world");		System.out.println("len:" + s.length());		System.out.println(s.compareTo(s2));		System.out.println(s.charAt(5));		System.out.println(s.indexOf(new ArrayStr("ture"),3));		System.out.println(s.indexOf('t',3));		System.out.println(s.delete(2, 5));		System.out.println(s.length());		System.out.println(s.concat(s2));		System.out.println(s.substring(12, s.length()));		System.out.println(s);		System.out.println(s.delete(0, 12));		System.out.println(s.replace(new ArrayStr("world"), new ArrayStr("animal ")));		System.out.println(s.length());		System.out.println(s.insert(13, new ArrayStr("world")));	}}

串值不变的顺序串

@Override	public Str insert(int posit, Str str) {		if(posit < 0 || posit > len)			throw new StringIndexOutOfBoundsException(posit);		else if(posit != 0) {			Str s1 = this.substring(0, posit);			Str s2 = this.substring(posit);			Str res1 = s1.concat(str);			Str res2 = res1.concat(s2);			return res2;		}else {			return str.concat(this);		}	}	@Override	public Str delete(int begin, int end) {		if(begin < 0 || begin > end || end > len)			throw new StringIndexOutOfBoundsException();		else if(begin == 0 && end == len)			return new ArrayStr();		else {			Str s1 = this.substring(0, begin);			Str s2 = this.substring(end);			return s1.concat(s2);		}	}	@Override	public Str replace(Str target, Str replacement) {		return replace(target, replacement, 0);	}	@Override	public Str replace(Str target, Str replacement, int from) {		int pos, tLen, rLen, k = from;		tLen = target.length();		rLen = replacement.length();		Str strx = new ArrayStr(s);		while(k