Java学习-Day6

总述

在《数据结构》中, 使用“抽象数据类型”来描述不同的数据结构. 在《面向对象程序设计》中, 用对象来存储数据及其上的操作. 我认为, 它们的本质都是相同的，都是把具体的事物抽象化. 但数据结构更注重事物之间的联系, 面向对象则更注重本身属性。

一、对象

数据及其上操作的总和.

例如, 我是一个对象, 具有身高、体重、年龄、跑步速度等数据; 同时，我具有吃饭、睡觉、送快递等功能.

从计算机的发展来看.

第一阶段以操作 (函数) 为中心, 一个计算导弹轨迹的函数, 根据不同输入获得不同输出. 这属于面向过程.

第二阶段以数据为中心, 即数据存放于数据库, 使用不同的算法来处理它. 这属于面向数据.

第三阶段认为数据及其上的操作是统一不可分的, 这就到了面向对象.

二、类

前面已经使用过 int i; 这类代码, int 就是类型, i 是一个具体的整数变量. 同理, 对象就是属于某种类的变量. 也可以用集合的方式来理解: 类是集合, 对象是其中的元素; int 是指所有整数的集合, i 是其中的一个元素.

三、包

包并非程序设计必须的东西, 其作用仅仅是将类进行合理的组织. 但是, 在计算机界, 往往这种可有可无的东西才是最重要的. 如文档、注释、编码规范. 可有可无是针对程序的运行而言, 其核心是计算机; 而重要是针对程序的易读性、可维护性而言, 其核心是程序员.

四、编码规范

常量用 final 修饰. 这里故意把 MAX_LENGTH 设置得比较少, 方便调拭后面的越界检查代码.

用 new 生成新的对象.

有一个成员变量叫做 length. 程序里还有用 length 表示一个整数数组的长度. 实际上, 同一个变量名可以被不同的类所使用.

toString 这个方法很特殊, 它覆盖了 Object 类的相应方法. 可以看到, 在 println 里面使用 tempFirstList 时, 由于是用另一个字符串与其相加, 系统会自动调用 tempFirstList.toString().

顺序表

把逻辑上相邻的结点储存在物理位置上的相邻储存单元中, 结点的逻辑关系由储存单元的邻接关系来体现.

通俗来讲, 顺序表就是把线性表中的所有元素按照其逻辑顺序, 依次储存到从指定的储存位置开始的一块连续的储存空间中.

第一个元素的储存位置就是指定的储存位置, 第 i+1 个元素的储存位置在第 i 个元素后面.

顺序表（一）

示例要求

1.编写顺序表的两个构造函数. 一个参数为空, 另一个参数为 int 数组并用其初始化顺序表.

2.重写顺序表的 toString 方法

具体代码

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
package datastructure.list;

/**
 * SequentialList
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */

public class SequentialList {
	/**
	 * The maximal length of the list. It is a constant.
	 */
	private static final int MAX_LENGTH = 10;

	/**
	 * The actual length not exceeding MAX_LENGTH. Attention: length is not only
	 * the member variable of Sequential list, but also the member variable of
	 * Array. In fact, a name can be the member variable of different classes.
	 */
	int length;

	/**
	 * The data stored in an array.
	 */
	int[] data;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public SequentialList() {
		length = 0;
		data = new int[MAX_LENGTH];
	}// Of the first constructor

	/**
	 *********************
	 * Construct a sequential list using an array.
	 * 
	 * @param paraArray
	 *            The given array. Its length should not exceed MAX_LENGTH. For
	 *            simplicity now we do not check it.
	 *********************
	 */
	public SequentialList(int[] paraArray) {
		this.data = new int[MAX_LENGTH];
		this.length = paraArray.length;

		// Copy data.
		for (int i = 0; i < paraArray.length; i++) {
			this.data[i] = paraArray[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 = "";

		if (this.length == 0) {
			return "empty";
		} // Of if

		for (int i = 0; i < this.length - 1; i++) {
			resultString += data[i] + ", ";
		} // Of for i

		resultString += data[this.length - 1];

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty.
	 *********************
	 */
	public void reset() {
		this.length = 0;
	}// Of reset

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args
	 *            Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int[] tempArray = { 1, 4, 6, 9 };
		SequentialList tempFirstList = new SequentialList(tempArray);
		System.out.println("Initialized, the list is: " + tempFirstList.toString());
		System.out.println("Again, the list is: " + tempFirstList);

		tempFirstList.reset();
		System.out.println("After reset, the list is: " + tempFirstList);
	}// Of main

}// Of class SequentialList

运行截图

注意事项

尽量保证类中变量为私有, 提高其安全性.

当类中变量名可能出现重复时尽量使用 this 关键字进行指明.

在重写函数的时候需要在函数名上一行写上 @Override 用以注明.

顺序表（二）

一、示例要求

在顺序表（一）的基础上进行修改.

二、查找元素

描述

查找给定数值元素的位置. 找不到就返回 -1.

输入

一个整数, 如下所示 

1
4

输出

若顺序表中存在该输入整数则返回第一次出现时的下标, 若不存在则返回 -1

方法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 *********************
 * Find the index of the given value. If it appears in multiple positions,
 * simply return the first one.
 * 
 * @param paraValue The given value.
 * @return The position. -1 for not found.
 *********************
 */
public int indexOf(int paraValue) {
	int tempPosition = -1;

	for (int i = 0; i < length; i++) {
		if (data[i] == paraValue) {
			tempPosition = i;
			break;
		} // Of if
	} // Of for i

	return tempPosition;
}// Of indexOf

三、增加元素

描述

在给定位置增加元素. 如果顺序表已满, 或位置不在已有位置范围之内, 就拒绝增加. 该位置可以是在最后一个元素之后一个.

输入

两个整数一个表示插入位置, 另一个表示需要插入的元素. 

1
2
1 ==> paraPosition
4 ==> paraValue

输出

返回一个布尔值, 增加成功返回 true , 增加失败返回 false.

方法代码

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
/**
	 *********************
	 * Insert a value to a position. If the list is already full, do nothing.
	 * 
	 * @param paraPosition The given position.
	 * @param paraValue    The given value.
	 * @return Success or not.
	 *********************
	 */
	public boolean insert(int paraPosition, int paraValue) {
		if (length == MAX_LENGTH) {
			System.out.println("List full.");
			return false;
		} // Of if

		if ((paraPosition < 0) || (paraPosition > length)) {
			System.out.println("The position " + paraPosition + " is out of bounds.");
			return false;
		} // Of if

		// From tail to head. The last one is moved to a new position. Because length <
		// MAX_LENGTH, no exceeding occurs.
		for (int i = length; i > paraPosition; i--) {
			data[i] = data[i - 1];
		} // Of for i

		data[paraPosition] = paraValue;
		length++;

		return true;
	}// Of insert

四、删除元素

描述

删除给定位置的元素. 要处理给定位置不合法的情况. 该位置必须是已经有数据的.

输入

一个整数表示删除位置

输出

返回一个布尔值, 删除成功返回 true , 删除失败返回 false.

方法代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 *********************
 * Delete a value at a position.
 * 
 * @param paraPosition The given position.
 * @return Success or not.
 *********************
 */
public boolean delete(int paraPosition) {
	if ((paraPosition < 0) || (paraPosition >= length)) {
		System.out.println("The position " + paraPosition + " is out of bounds.");
		return false;
	} // Of if

	// From head to tail.
	for (int i = paraPosition; i < length - 1; i++) {
		data[i] = data[i + 1];
	} // Of for i

	length--;

	return true;
}// Of delete

五、完整代码

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
package datastructure.list;

/**
 * SequentialList
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */

public class SequentialList {
	/**
	 * The maximal length of the list. It is a constant.
	 */
	private static final int MAX_LENGTH = 10;

	/**
	 * The actual length not exceeding MAX_LENGTH. Attention: length is not only the
	 * member variable of Sequential list, but also the member variable of Array. In
	 * fact, a name can be the member variable of different classes.
	 */
	int length;

	/**
	 * The data stored in an array.
	 */
	int[] data;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public SequentialList() {
		length = 0;
		data = new int[MAX_LENGTH];
	}// Of the first constructor

	/**
	 *********************
	 * Construct a sequential list using an array.
	 * 
	 * @param paraArray The given array. Its length should not exceed MAX_LENGTH.
	 *                  For simplicity now we do not check it.
	 *********************
	 */
	public SequentialList(int[] paraArray) {
		this.data = new int[MAX_LENGTH];
		this.length = paraArray.length;

		// Copy data.
		for (int i = 0; i < paraArray.length; i++) {
			this.data[i] = paraArray[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 = "";

		if (this.length == 0) {
			return "empty";
		} // Of if

		for (int i = 0; i < this.length - 1; i++) {
			resultString += data[i] + ", ";
		} // Of for i

		resultString += data[this.length - 1];

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty.
	 *********************
	 */
	public void reset() {
		this.length = 0;
	}// Of reset

	/**
	 *********************
	 * Find the index of the given value. If it appears in multiple positions,
	 * simply return the first one.
	 * 
	 * @param paraValue The given value.
	 * @return The position. -1 for not found.
	 *********************
	 */
	public int indexOf(int paraValue) {
		int tempPosition = -1;

		for (int i = 0; i < length; i++) {
			if (data[i] == paraValue) {
				tempPosition = i;
				break;
			} // Of if
		} // Of for i

		return tempPosition;
	}// Of indexOf

	/**
	 *********************
	 * Insert a value to a position. If the list is already full, do nothing.
	 * 
	 * @param paraPosition The given position.
	 * @param paraValue    The given value.
	 * @return Success or not.
	 *********************
	 */
	public boolean insert(int paraPosition, int paraValue) {
		if (length == MAX_LENGTH) {
			System.out.println("List full.");
			return false;
		} // Of if

		if ((paraPosition < 0) || (paraPosition > length)) {
			System.out.println("The position " + paraPosition + " is out of bounds.");
			return false;
		} // Of if

		// From tail to head. The last one is moved to a new position. Because length <
		// MAX_LENGTH, no exceeding occurs.
		for (int i = length; i > paraPosition; i--) {
			data[i] = data[i - 1];
		} // Of for i

		data[paraPosition] = paraValue;
		length++;

		return true;
	}// Of insert

	/**
	 *********************
	 * Delete a value at a position.
	 * 
	 * @param paraPosition The given position.
	 * @return Success or not.
	 *********************
	 */
	public boolean delete(int paraPosition) {
		if ((paraPosition < 0) || (paraPosition >= length)) {
			System.out.println("The position " + paraPosition + " is out of bounds.");
			return false;
		} // Of if

		// From head to tail.
		for (int i = paraPosition; i < length - 1; i++) {
			data[i] = data[i + 1];
		} // Of for i

		length--;

		return true;
	}// Of delete

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		int[] tempArray = { 1, 4, 6, 9 };
		SequentialList tempFirstList = new SequentialList(tempArray);
		System.out.println("After initialization, the list is: " + tempFirstList.toString());
		System.out.println("Again, the list is: " + tempFirstList);

		int tempValue = 4;
		int tempPosition = tempFirstList.indexOf(tempValue);
		System.out.println("The position of " + tempValue + " is " + tempPosition);

		tempValue = 5;
		tempPosition = tempFirstList.indexOf(tempValue);
		System.out.println("The position of " + tempValue + " is " + tempPosition);

		tempPosition = 2;
		tempValue = 5;
		tempFirstList.insert(tempPosition, tempValue);
		System.out.println(
				"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);

		tempPosition = 8;
		tempValue = 10;
		tempFirstList.insert(tempPosition, tempValue);
		System.out.println(
				"After inserting " + tempValue + " to position " + tempPosition + ", the list is: " + tempFirstList);

		tempPosition = 3;
		tempFirstList.delete(tempPosition);
		System.out.println("After deleting data at position " + tempPosition + ", the list is: " + tempFirstList);

		for (int i = 0; i < 8; i++) {
			tempFirstList.insert(i, i);
			System.out.println("After inserting " + i + " to position " + i + ", the list is: " + tempFirstList);
		} // Of for i

		tempFirstList.reset();
		System.out.println("After reset, the list is: " + tempFirstList);

	}// Of main

}// Of class SequentialList

六、运行截图

总结

函数 要求同样的输入参数获得同样的输出结果, 但 方法 所依赖的数据既包括参数列表中给出的，也依赖于对象的成员变量.

程序员的世界无非就是增删改查.