Java学习-Day7

链表

一、总述

链表是由多个相同的节点链接形成的, 在C语言中用结构体来表示, 在Java中则用一个类来表示.

C语言中使用指针直接访问节点, 访问的同时实际对内存也有了读写的属性, 不稍加注意就会出现错误. 而在Java中就不会出现这种情况.

链表与顺序表在插入、删除时的不同: 前者不移动元素, 只改变引用 (指针).

二、链表初始化

描述

生成的是一个带有头节点的单链表

具体代码

1
2
3
4
5
6
7
8
/**
 *********************
 * Construct an empty linked list.
 *********************
 */
public LinkedList() {
	header = new Node(0);
}// Of the first constructor

三、查找元素

描述

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

输入

一个整数, 如下所示 

1
4

输出

若链表中存在该输入整数则返回第一次出现时的链表中的序号, 若不存在则返回 -1. 如下所示 

1
2
3
input 3
head -> 1 -> 3 -> 4 -> null
return 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 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 locate(int paraValue) {
	int tempPosition = -1;

	Node tempNode = header.next;
	int tempCurrentPosition = 0;
	while (tempNode != null) {
		if (tempNode.data == paraValue) {
			tempPosition = tempCurrentPosition;
			break;
		} // Of if

		tempNode = tempNode.next;
		tempCurrentPosition++;
	} // Of while

	return tempPosition;
}// Of locate

四、插入元素

描述

在给定位置增加元素. 如果位置不在已有位置范围之内, 就拒绝增加.

输入

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

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) {
	Node tempNode = header;
	Node tempNewNode;

	for (int i = 0; i < paraPosition; i++) {
		if (tempNode.next == null) {
			System.out.println("The position " + paraPosition + " is illegal.");
			return false;
		} // Of if

		tempNode = tempNode.next;
	} // Of for i

	// Construct a new node.
	tempNewNode = new Node(paraValue);

	// Now link them.
	tempNewNode.next = tempNode.next;
	tempNode.next = tempNewNode;

	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
24
25
26
27
28
29
/**
 *********************
 * Delete a value at a position.
 * 
 * @param paraPosition The given position.
 * @return Success or not.
 *********************
 */
public boolean delete(int paraPosition) {
	if (header.next == null) {
		System.out.println("Cannot delete element from an empty list.");
		return false;
	} // Of if

	Node tempNode = header;

	for (int i = 0; i < paraPosition; i++) {
		if (tempNode.next.next == null) {
			System.out.println("The position " + paraPosition + " is illegal.");
			return false;
		} // Of if

		tempNode = tempNode.next;
	} // Of for i

	tempNode.next = tempNode.next.next;

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

/**
 * Linked List
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class LinkedList {
	/**
	 * An inner class.
	 */
	class Node {
		/**
		 * The data.
		 */
		int data;

		/**
		 * The reference to the next node.
		 */
		Node next;

		/**
		 ******************* 
		 * The constructor
		 * 
		 * @param paraValue The data.
		 ******************* 
		 */
		public Node(int paraValue) {
			data = paraValue;
			next = null;
		}// Of the constructor
	}// Of class Node

	/**
	 * The header node. The data is never used.
	 */
	Node header;

	/**
	 *********************
	 * Construct an empty linked list.
	 *********************
	 */
	public LinkedList() {
		header = new Node(0);
	}// Of the first constructor

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

		if (header.next == null) {
			return "empty";
		} // Of if

		Node tempNode = header.next;
		while (tempNode != null) {
			resultString += tempNode.data + ", ";
			tempNode = tempNode.next;
		} // Of while

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Reset to empty. Free the space through garbage collection.
	 *********************
	 */
	public void reset() {
		header.next = null;
	}// Of reset

	/**
	 *********************
	 * Locate 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 locate(int paraValue) {
		int tempPosition = -1;

		Node tempNode = header.next;
		int tempCurrentPosition = 0;
		while (tempNode != null) {
			if (tempNode.data == paraValue) {
				tempPosition = tempCurrentPosition;
				break;
			} // Of if

			tempNode = tempNode.next;
			tempCurrentPosition++;
		} // Of while

		return tempPosition;
	}// Of locate

	/**
	 *********************
	 * 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) {
		Node tempNode = header;
		Node tempNewNode;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		// Construct a new node.
		tempNewNode = new Node(paraValue);

		// Now link them.
		tempNewNode.next = tempNode.next;
		tempNode.next = tempNewNode;

		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 (header.next == null) {
			System.out.println("Cannot delete element from an empty list.");
			return false;
		} // Of if

		Node tempNode = header;

		for (int i = 0; i < paraPosition; i++) {
			if (tempNode.next.next == null) {
				System.out.println("The position " + paraPosition + " is illegal.");
				return false;
			} // Of if

			tempNode = tempNode.next;
		} // Of for i

		tempNode.next = tempNode.next.next;

		return true;
	}// Of delete

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		LinkedList tempFirstList = new LinkedList();
		System.out.println("Initialized, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.insert(0, i);
		} // Of for i
		System.out.println("Inserted, the list is: " + tempFirstList.toString());

		tempFirstList.insert(6, 9);

		tempFirstList.delete(4);

		tempFirstList.delete(2);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		tempFirstList.delete(0);
		System.out.println("Deleted, the list is: " + tempFirstList.toString());

		for (int i = 0; i < 5; i++) {
			tempFirstList.delete(0);
			System.out.println("Looped delete, the list is: " + tempFirstList.toString());
		} // Of for i
	}// Of main

}// Of class LinkedList

七、运行截图

栈

一、总述

栈作为一种数据结构不仅仅出现在当前需求中. 在计算机底层也少不了栈的使用. 通常编程中栈的增长方向是从下往上, 在计算机底层中栈的增长是从上往下.

两者都有一个共同的特点那就是栈需要遵守的属性是后进先出, 入栈（push）和出栈（pop）操作只能在栈顶执行.

二、入栈

描述

向栈中添加一个元素.

输入

一个整数

输出

返回一个布尔值, 入栈成功返回 true , 入栈失败返回 false.

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 *********************
 * Push an element.
 * 
 * @param paraChar The given char.
 * @return Success or not.
 *********************
 */
public boolean push(char paraChar) {
	if (depth == MAX_DEPTH) {
		System.out.println("Stack full.");
		return false;
	} // Of if

	data[depth] = paraChar;
	depth++;

	return true;
}// Of push

三、出栈

描述

从栈顶去除一个元素.

输入

无

输出

返回一个char值为之前的栈顶元素, 若栈为空则返回 '\0'

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 *********************
 * Pop an element.
 * 
 * @return The popped char.
 *********************
 */
public char pop() {
	if (depth == 0) {
		System.out.println("Nothing to pop.");
		return '\0';
	} // Of if

	char resultChar = data[depth - 1];
	depth--;

	return resultChar;
}// Of pop

四、完整代码

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

/**
 * Char stack. I do not use Stack because it is already defined in Java.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class CharStack {
	/**
	 * The depth.
	 */
	private static final int MAX_DEPTH = 10;

	/**
	 * The actual depth.
	 */
	int depth;

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

	/**
	 *********************
	 * Construct an empty char stack.
	 *********************
	 */
	public CharStack() {
		depth = 0;
		data = new char[MAX_DEPTH];
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	@Override
	public String toString() {
		String resultString = "";
		for (int i = 0; i < depth; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Push an element.
	 * 
	 * @param paraChar The given char.
	 * @return Success or not.
	 *********************
	 */
	public boolean push(char paraChar) {
		if (depth == MAX_DEPTH) {
			System.out.println("Stack full.");
			return false;
		} // Of if

		data[depth] = paraChar;
		depth++;

		return true;
	}// Of push

	/**
	 *********************
	 * Pop an element.
	 * 
	 * @return The popped char.
	 *********************
	 */
	public char pop() {
		if (depth == 0) {
			System.out.println("Nothing to pop.");
			return '\0';
		} // Of if

		char resultChar = data[depth - 1];
		depth--;

		return resultChar;
	}// Of pop

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		CharStack tempStack = new CharStack();
		for (char ch = 'a'; ch < 'm'; ch++) {
			tempStack.push(ch);
			System.out.println("The current stack is: " + tempStack);
		} // Of for ch

		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = tempStack.pop();
			System.out.println("Poped: " + tempChar);
			System.out.println("The current stack is: " + tempStack);
		} // Of for i
	}// Of main
}// Of CharStack

五、运行截图

总结

无论是链表还是栈, 都不过是对数据的特定存储和处理. 不同的数据结构为的是解决不同的问题.

结合之前的内容无非就是增删改查. 根据之前学习C语言的经验, 对于栈的函数应该还可以增加获取当前栈顶元素而不需要出栈, 或者查找栈中元素.

仔细想想栈就是一个特殊一点的数组罢了.