Spiga

串(一):串

2012-04-13 18:29:13

一、串概述

  串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表,其特殊性在于串中的数据元素是一个个的字符。
  串中字符的个数,称为串的长度。
  不含任何字符的串称为空串,它的长度n=0,记为s=""。
  串中任意个连续的字符组成的子序列称为该串的子串(Substring)。包含子串的串相应地称为主串。
  子串的第一个字符在主串中的位置叫子串的位置。例如: 串s1="David Ruff",它的长度是10,串s2="Ruff"的长度是4,s2是s1的子串,s2的位置是6。

二、串的操作

1.串比较:Compare(s)
2.求子串:SubString(int index, int len)
3.求串的长度:GetLength()
4.串连接:Concat(s)
5.串定位:IndexOf(s,startpos)
6.串插入:Insert(index, s)
7.串删除:Delete(index, len)

三、串的顺序表示

  串的静态存储结构即顺序存储结构是用一组地址连续的存储单元存储串的字符序列。可用高级语言的字符数组来实现。
  不同的语言在用数组存放字符串时,其处理方式可能有所不同。
  对串进行操作:
1.创建顺序串
  步骤:
    a.如果给定的参数是字符数组的话,将创建一个一样大的数组,并将参数数组中的每个字符拷贝到字符串的存储空间里,即新创建的数组里。
    b.如果给定的参数是SeqString类的实例的话,就将参数串所在存储空间的每个字符拷贝到新创建字符串的数组空间中。
2.求子串:SubString(int index, int len)
  步骤:
    a.首先确定index和len的合法性,index应限定在0≤index≤主串长度-1的范围内,len应限定在0<len≤主串长度-index的范围内,如果不合法的,将null返回主调程序。
    b.创建一个新的字符串,并为新字符串申请的数组空间,空间大小为子串的长度len一样的大小。
    c.在主串的index位置开始,将主串len个字符拷贝到子串的数组空间中。
    d.将子串返回主调程序。

3.串比较:Compare(SeqString s)
  步骤:
    a.依次将较短字符串中的每个字符与较长字串的每个字符比较,当被比较的两个字符不相等时,终止比较。
    b.如果比较在中途退出,需进一步判断主串与字符串S在退出比较时所比较字符的大小,如果主串的字符小,返回-1,否则返回1
    c.如果比较是正常退出,则需进一步判断两个字符串的长度是否相等,如相等,返回0,否则如果主串的长度大于S的长度,返回1,否则返回-1。

4.串连接:Concat(s)
  步骤:
    a.申请一块连续的可以存储两个字符串的空间。
    b.将主串中的每个字符逐个拷贝到连续空间的前部分。
    c.将字符串s逐个拷贝到主串的后面。
    d.将新生成的字符串返回给使用者。

5.串定位:IndexOf(SeqString s, int startpos)
  步骤:
    a.获取从主串startpos位置开始到主串最后一个字符的子串。
    b.将主串从startpos开始的子串中的每个字符与s中的每个字符比较,若相等则继续比较后续字符,否则从主串中子串的下一个位置开始比较。依此类推。
    c.若存在模式串中的每个字符依次和主串中一个连续的字符序列相等,则匹配成功,返回模式串s第一个字符在主串中的位置,否则返回-1。

6.串插入:Insert(int index, SeqString s)
  步骤:
    a.找到主串的位置index。如果位置符合条件,则该操作返回一个新串,新串的长度是主串的长度与串s的长度之和,否则返回一个空串。
    b.新串的第1部分是该串的开始字符到第index之间的字符,第2部分是串s,第3部分是主串从index位置字符到串串的结束位置处的字符。

7.串删除:Delete(int index, int len)
  步骤:
    a.找到主串的位置index。如果位置符合条件,则该操作返回一个新串,新串的长度是主串的长度减去串s的长度,否则返回一个空串。
    b.新串的前部分是原串的开始到第index个位置之间的字符,后部分是原串从第index+len位置到原串结束的字符。

四、串的实现

  基本运算在串上的实现如下:

public class SeqString
{
	private char[] data; 
	 
	public char this[int index]
	{
		get
		{
			return data[index];
		}
		set
		{
			data[index] = value;
		}
	}

	public SeqString(char[] arr)
	{
		data = new char[arr.Length];
		for (int i = 0; i < arr.Length; i++)
		{
			data[i] = arr[i];
		}
	}

	public SeqString(SeqString s)
	{
		int len = s.GetLength();
		data = new char[len];
		for (int i = 0; i < len; i++)
		{
			data[i] = s[i];
		}
	}

	private SeqString(int len)
	{
		data = new char[len];
	}
	 
	public int GetLength()
	{
		return data.Length;
	}
	 
	public int Compare(SeqString s)
	{
		int len = ((this.GetLength() <= s.GetLength()) ? this.GetLength() : s.GetLength());
		int i = 0;
		for (i = 0; i < len; i++)
		{
			if (this[i] != s[i])
			{
				break;
			}
		}
		if (i < len)
		{
			if (this[i] < s[i])
			{
				return -1;
			}
			else
			{
				return 1;
			}
		}
		else if (this.GetLength() == s.GetLength())
			return 0;
		else if (this.GetLength() < s.GetLength())
			return -1;
		else
			return 1;
	}

	public SeqString SubString(int index, int len)
	{
		if ((index < 0) || (index > this.GetLength() - 1) || (len <= 0) || (len > this.GetLength() - index))
			throw new Exception("位置或长度的错误");

		SeqString s = new SeqString(len);
		for (int i = 0; i < len; i++)
		{
			s[i] = this[i + index];
		}
		return s;
	}
	 
	public SeqString Concat(SeqString s)
	{
		SeqString s1 = new SeqString(this.GetLength() + s.GetLength());
		for (int i = 0; i < this.GetLength(); i++)
		{
			s1.data[i] = this[i];
		}
		for (int j = 0; j < s.GetLength(); j++)
		{
			s1.data[this.GetLength() + j] = s[j];
		}
		return s1;
	}

	public int IndexOf(SeqString s, int startpos)
	{
		SeqString sub;
		sub = this.SubString(startpos, this.GetLength() - startpos);
		if (sub.GetLength() < s.GetLength())
		{
			return -1;
		}
		int i = 0, j = 0, v;
		while (i < sub.GetLength() && j < s.GetLength())
		{
			if (sub.data[i] == s.data[j])
			{
				i++;
				j++;
			}
			else
			{
				i = i - j + 1;
				j = 0;
			}
		}
		if (j == s.GetLength()) 
			v = i - s.GetLength() + startpos;
		else 
			v = -1;
		return v;

	}
	 
	public SeqString Insert(int index, SeqString s)
	{
		int len = s.GetLength();
		int len2 = len + this.GetLength();
		SeqString s1 = new SeqString(len2);
		if (index < 0 || index > this.GetLength() - 1)
			throw new Exception("位置或长度的错误");

		for (int i = 0; i < index; i++)
		{
			s1[i] = this[i];
		}
		for (int i = index; i < index + len; i++)
		{
			s1[i] = s[i - index];
		}
		for (int i = index + len; i < len2; i++)
		{
			s1[i] = this[i - len];
		}
		return s1;
	}
	 
	public SeqString Delete(int index, int len)
	{
		if ((index < 0) || (index > this.GetLength() - 1) || (len < 0) || (len > this.GetLength() - index))
			throw new Exception("位置或长度的错误");

		SeqString s = new SeqString(this.GetLength() - len);
		int j = 0;
		for (int i = 0; i < index; i++)
		{
			s[j++] = this[i];
		}
		for (int i = index + len; i < this.GetLength(); i++)
		{
			s[j++] = this[i];
		}
		return s;
	}

	public override string ToString()
	{
		return new String(data);
	}
}