概述

字符串的应用已经非常广泛，如信息检索、文字编辑、自然语言的翻译等都离不开字符串。在各种高级语言的程序设计中都会有字符串类型，虽然各种语言的表现方式各自不同，但其实现原理基本相同。熟悉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; i++) {
			this.s[i] = s.charAt(i);
		}
	}
	
	public ArrayStr(String str) {
		len = str.length();
		s = new char[len];
		for(int i=0; i<len; i++) {
			s[i] = str.charAt(i);
		}
	}

	@Override
	public char charAt(int index) {
		if(index <0 || index > 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<n) {
			char c1 = s[i], c2 = s2.charAt(i);
			if(c1 != c2) {
				return c1-c2;				
			}
			i++;
		}
		return len - s2.length();
	}

	@Override
	public Str concat(Str str) {
		int n = len + str.length();
		expand(n);
		for(int i=0; i<str.length(); i++) {
			s[i+len] = str.charAt(i);
		}
		len = n;
		return this;
	}

	@Override
	public Str delete(int begin, int end) {
		int n = end-begin;
		char[] c = new char[n];
		for(int i=end; i<len; i++) {
			s[i-n] = s[i];
		}
		len = len-n;
		return this;
	}

	private void expand(int size) {
		char c[] = new char[size];
		for(int i=0; i<len; i++) {
			c[i] = s[i];
		}
		s = c;
	}

	@Override
	public int indexOf(char c) {
		return indexOf(c, 0);
	}

	@Override
	public int indexOf(char c, int from) {
		int i = from;
		while(i<len) {
			if(c == s[i])
				return i;
			i++;
		}
		return -1;
	}

	@Override
	public int indexOf(Str str) {
		return indexOf(str, 0);
	}

	@Override
	public int indexOf(Str str, int from) {
		int i = from, j = 0;
		int sLen = str.length();
		while((i<len) && (j<sLen)) {
			if(s[i] == str.charAt(j)) {
				i++;
				j++;
			} else {
				i = i-j+1;
				j = 0;
			}
		}
		if(j == sLen)
			return i-sLen;
		else 
			return -1;
	}
	
	@Override
	public Str insert(int pos, Str str) {
		char c[] = null;
		if(pos < 0 || pos > 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<len) {
			pos = this.indexOf(target, from);
			if(-1 == pos) {
				break;
			} else {
				delete(pos, pos+tLen);
				insert(pos, replacement);
				k = pos + rLen;
			}
		}
		return this;
	}

	@Override
	public Str substring(int strartIndex) {
		return substring(strartIndex, len);
	}

	@Override
	public Str substring(int beginIndex, int endIndex) {
		int n = endIndex - beginIndex;
		char ss[] = new char[n];
		for(int i=0; i<n; i++) {
			ss[i] = s[i+beginIndex];
		}
		return new ArrayStr(ss);
	}

	@Override
	public char[] toCharArray() {
		return s;
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		for(int i=0; i<len; i++) {
			sb.append(s[i]);
		}
		return sb.toString();
	}
	
}

测试串操作

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<len) {
			pos = this.indexOf(target, k);
			if(pos == -1)
				break;
			else {
				strx = strx.delete(pos, pos+ tLen);
				strx = strx.insert(pos, replacement);
				k = pos + rLen;
			}
		}
		return strx;
	}

	@Override
	public Str concat(Str str) {
		int sLen = str.length();
		if(sLen == 0)
			return this;
		char buf[] = new char[len+sLen];
		for(int i=0; i<len; i++) {  
			buf[i] = s[i];
        }
		for(int i=0; i<sLen; i++) {
			buf[len+i] = str.charAt(i);
		}
		return new ArrayStr(buf);
	}