Java学习（Day 6）

学习来源：日撸 Java 三百行（11-20天，线性数据结构）_闵帆的博客-CSDN博客

总述

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

一、对象

数据及其上操作的总和.

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

从计算机的发展来看.

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

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

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

二、类

前面已经使用过 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 方法

具体代码

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.

输入

一个整数, 如下所示

4

输出

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

方法代码

	/**
	 *********************
	 * 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 ==> paraPosition
4 ==> paraValue

输出

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

方法代码

/**
	 *********************
	 * 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.

方法代码

	/**
	 *********************
	 * 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

五、完整代码

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

六、运行截图

总结

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

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