Java学习-Day10

字符串匹配

一、总述

String 是 Java 常用的类, 这里重新实现下部分功能. 对于 String 这个类有着非常多的方法, 本节内容就主要只实现字符串匹配子串和截取子串.

字符串匹配子串在 String 的原生方法里面是没有的, 但是可以通过其他方法组合实现.

二、字符串匹配子串

描述

匹配过程中有两个字符串, 一个叫做模式串, 一个叫做子串. 我们所需要做的就是查看模式串中是否有子串, 然后返回第一次出现子串的位置.

输入

一个字符串

输出

输入字符串第一次出现的位置, 若模式串中无子串则返回 -1

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 *********************
 * Locate the position of a substring.
 * 
 * @param paraString The given substring.
 * @return The first position. -1 for no matching.
 *********************
 */
public int locate(MyString paraMyString) {
	boolean tempMatch = false;
	for (int i = 0; i < length - paraMyString.length + 1; i++) {
		// Initialize.
		tempMatch = true;
		for (int j = 0; j < paraMyString.length; j++) {
			if (data[i + j] != paraMyString.data[j]) {
				tempMatch = false;
				break;
			} // Of if
		} // Of for j

		if (tempMatch) {
			return i;
		} // Of if
	} // Of for i
	return -1;
}// Of locate

三、截取字符串

描述

获取当前字符串第几位, 长度为几的字符子串. 需要注意的是, 要对截取位置和长度进行是否越界的判断.

输入

一个整数表示截取子串开始位置, 一个整数表示截取子串的长度.

输出

根据输入所截取到的字符子串.

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 *********************
 * Get a substring
 * 
 * @param paraString        The given substring.
 * @param paraStartPosition The start position in the original string.
 * @param paraLength        The length of the new string.
 * @return The first position. -1 for no matching.
 *********************
 */
public MyString substring(int paraStartPosition, int paraLength) {
	if (paraStartPosition + paraLength > length) {
		System.out.println("The bound is exceeded.");
		return null;
	} // Of if

	MyString resultMyString = new MyString();
	resultMyString.length = paraLength;
	for (int i = 0; i < paraLength; i++) {
		resultMyString.data[i] = data[paraStartPosition + i];
	} // Of for i

	return resultMyString;
}// Of substring

四、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package datastructure;

/**
 * My string. String is a class provided by the language, so I use another name.
 * It is essentially a sequential list with char type elements.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com.
 */
public class MyString {
	/**
	 * The maximal length.
	 */
	public static final int MAX_LENGTH = 10;

	/**
	 * The actual length.
	 */
	int length;

	/**
	 * The data.
	 */
	char[] data;

	/**
	 *********************
	 * Construct an empty char array.
	 *********************
	 */
	public MyString() {
		length = 0;
		data = new char[MAX_LENGTH];
	}// Of the first constructor

	/**
	 *********************
	 * Construct using a system defined string.
	 * 
	 * @param paraString The given string. Its length should not exceed MAX_LENGTH -
	 *                   1.
	 *********************
	 */
	public MyString(String paraString) {
		data = new char[MAX_LENGTH];
		length = paraString.length();

		// Copy data.
		for (int i = 0; i < length; i++) {
			data[i] = paraString.charAt(i);
		} // Of for i
	}// Of the second constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	@Override
	public String toString() {
		String resultString = "";

		for (int i = 0; i < length; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Locate the position of a substring.
	 * 
	 * @param paraString The given substring.
	 * @return The first position. -1 for no matching.
	 *********************
	 */
	public int locate(MyString paraMyString) {
		boolean tempMatch = false;
		for (int i = 0; i < length - paraMyString.length + 1; i++) {
			// Initialize.
			tempMatch = true;
			for (int j = 0; j < paraMyString.length; j++) {
				if (data[i + j] != paraMyString.data[j]) {
					tempMatch = false;
					break;
				} // Of if
			} // Of for j

			if (tempMatch) {
				return i;
			} // Of if
		} // Of for i
		return -1;
	}// Of locate

	/**
	 *********************
	 * Get a substring
	 * 
	 * @param paraString        The given substring.
	 * @param paraStartPosition The start position in the original string.
	 * @param paraLength        The length of the new string.
	 * @return The first position. -1 for no matching.
	 *********************
	 */
	public MyString substring(int paraStartPosition, int paraLength) {
		if (paraStartPosition + paraLength > length) {
			System.out.println("The bound is exceeded.");
			return null;
		} // Of if

		MyString resultMyString = new MyString();
		resultMyString.length = paraLength;
		for (int i = 0; i < paraLength; i++) {
			resultMyString.data[i] = data[paraStartPosition + i];
		} // Of for i

		return resultMyString;
	}// Of substring

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		MyString tempFirstString = new MyString("I like ik.");
		MyString tempSecondString = new MyString("ik");
		int tempPosition = tempFirstString.locate(tempSecondString);
		System.out.println("The position of \"" + tempSecondString + "\" in \"" + tempFirstString + "\" is: " + tempPosition);

		MyString tempThirdString = new MyString("ki");
		tempPosition = tempFirstString.locate(tempThirdString);
		System.out.println("The position of \"" + tempThirdString + "\" in \"" + tempFirstString + "\" is: " + tempPosition);

		tempThirdString = tempFirstString.substring(1, 2);
		System.out.println("The substring is: \"" + tempThirdString + "\"");

		tempThirdString = tempFirstString.substring(5, 5);
		System.out.println("The substring is: \"" + tempThirdString + "\"");

		tempThirdString = tempFirstString.substring(5, 6);
		System.out.println("The substring is: \"" + tempThirdString + "\"");
	}// Of main
} // Of class MyString

五、运行截图

小结

一、面向对象与面向过程相比, 有哪些优势?

面向对象的方法是对于类而言的, 更具有逻辑性和符合现实世界, 这个也有点封装的意思在里面. 但面向对象的其他特点在这些代码练习中并没有体现出来. 也就是面向对象的继承和多态. 最终的目标就是实现代码的复用.

二、比较顺序表和链表的异同.

顺序表和链表都是线性表的一种, 唯一不同的就是存储方式的不同. 简单来说就是连续和离散的差别.

当然因为存储方式的不同, 在内部具体实现的时间复杂度就不一样.

顺序表在添加和删除时平均都需要移动大量的数, 而链表则只需要对一个节点做出修改. 在查找方面两者都需要遍历, 要是顺序表遵循大小排序倒是可以用二分法降低查找的时间复杂度.

三、分析顺序表和链表的优缺点. 顺序表的初始内存是固定的, 如果数据量过多就需要新申请一段内容, 把之前的数据拷贝过去. 如果一次删除过多数据, 多出来的空间会造成浪费. 这样的唯一好处是可以直接取得某位的数组值.

链表的有点正是改进了顺序表的缺点, 而链表的缺点被顺序表改正.

四、分析调试程序常见的问题及解决方案.

考虑不完全所有需要测试的数据, 测试代码在主要文件内, 看起来冗余. 提出单元测试的方法, 对测试代码新建一个文件并通过注解标明.

五、分析链队列与循环队列的优缺点. 链队列不用管理资源的分配与回收但, 循环队列则需要管理

唯一能区分优劣的点就是在链队列向操作系统申请内存和释放时会产生的部分时间开销.

六、之前建立的两个队列, 其区别仅在于基础数据不同, 一个是 int, 一个是 char. 按这种思路, 对于不同的基础数据类型, 都需要重写一个类, 这样合理吗? 你想怎么样?

当然不合理啊, 对于这种情况可以使用Java的范式接受所有类型的值. 就算要重写一个类也应该用继承的方式来写两个不同的类.