文档章节

串操作

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 1868
阅读 6
收藏 0

概述

字符串的应用已经非常广泛,如信息检索、文字编辑、自然语言的翻译等都离不开字符串。在各种高级语言的程序设计中都会有字符串类型,虽然各种语言的表现方式各自不同,但其实现原理基本相同。熟悉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")));
	}
}

结果

len:15
-4
s
10
6
dastructure!
12
dastructure!hello world
hello world
dastructure!hello world
hello world
hello animal 
13
hello animal 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);
	}


本文转载自:http://blog.csdn.net/luoweifu/article/details/8644362

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
小蚂蚁学习数据结构(15)——串的认识

概念: 串(字符串):是由0个或多个字符组成的有限序列。 由双引号括起来 如: char str[] = "abcd"; 串相等的条件: 只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。 串的...

嗜学如命的小蚂蚁
2016/01/15
86
2
Android Intent通讯实例

//1.拨打电话 // 给移动客服10086拨打电话 Uri uri = Uri.parse("tel:10086"); Intent intent = new Intent(Intent.ACTION_DIAL, uri); startActivity(intent); //2.发送短信 // 给10086发送......

知亦行
01/28
0
0
数据结构与算法JavaScript (四) 串(BF)

串是由零个或多个字符组成的有限序列,又叫做字符串 串的逻辑结构和线性表很相似的,不同的是串针对是是字符集,所以在操作上与线性表还是有很大区别的。线性表更关注的是单个元素的操作CUR...

文艺小青年
2017/06/29
0
0
CRC校验程序设计

程序的宗旨:通过编写CRC的校验程序,加深对CRC原理的理解,同时学会将书本上的原理运用于实际,动手实践才能学得更快。 注:本文关于CRC原理那部分内容,来自网络搜集。 1. 需求分析 编写一...

乐搏学院
2016/12/07
43
0
Elixir学习笔记(二进制串、字符串和字符列表)

二进制串、字符串和字符列表 在“基本类型”一章中,介绍了字符串,以及使用函数检查它: 接下来学习和理解:二进制串(binaries)是个啥,它怎么和字符串(strings)扯上关系的。 以及用单引...

程序员小哥哥
2018/05/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

反编译9.png图片还原

本文链接:https://blog.csdn.net/a1140778530/article/details/10528507 经常反编译apk文件找资源,9.png的文件处理起来很麻烦。 最近使用Ant自动编译打包app时,从别处搜罗来的9.png文件导...

shzwork
16分钟前
4
0
Shell脚本应用 – for、while循环语句

一、for循环语句 在实际工作中,经常会遇到某项任务需要多次执行的情况,而每次执行时仅仅是处理的对象不一样,其他命令相同。例如:根据通讯录中的姓名列表创建系统账号等情况。 当面对各种...

linux-tao
17分钟前
5
0
RPA风潮下企业财务工作模式的变革

RPA(机器人流程自动化)在财务领域的应用,正给企业财务带来前所未有的改变。 前RPA时代,财务领域面临的痛点 在RPA机器人应用之前,企业财务工作进程的推进,主要通过财务人员人工操作或信...

UiBot
22分钟前
5
0
Hive之命令行修改表注释

最近遇到一个需求,在不重建表的情况下,修改表的注释,hive有没有类似关系型数据库的SQL命令来修改呢,找了下,亲测有效,如下List-1 List-1 hive>use your_schemahvie>ALTER TABLE tabl...

克虏伯
22分钟前
5
0
是什么,它的作用是什么

在HTML文档的首部往往会有这么一句话<!DOCTYPE html>,许多时候我们忽视了它的存在,它实际上是一个声明,告诉浏览器用哪种HTML版本的规范来解读HTML文档。 尽管我们不给出这句声明浏览器照样...

前端老手
28分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部