数据结构中一些示例代码的实现

发表于 | 更新于 | 分类于 ， | 阅读次数 次
字数统计 4,347 字

科学的研究方法（摘录至文明之光一书）

  1. 不盲从，不接受任何自己不清楚的真理。不管有什么权威的结论，只要没有经过自己的研究，都可以怀疑。
  2. 对于复杂的问题，尽量分解为多个简单的小问题来研究，一个一个地分开解决。
  3. 解决这些小问题时，应该按照先易后难的次序，逐步解决。
  4. 解决每个小问题之后，再综合起来。看看是否彻底解决了原来的问题。

内存溢出和内存泄露

内存溢出

内存溢出主要是指，要装的数据要超过容器本身了，这是则会导致溢出。类似与生活中的水桶、杯子等，容量是有限的，所以不能进行无限的填装。像Java中的OOM，就属于内存溢出。因为Java中GC的存在，所以并不会发生内存泄露。

内存泄露

上一章用到C语言制造链表，对于链表中结点的删除操作，会有一个free()函数的调用。free()函数的作用是释放内存空间。所谓的释放内存空间，是指把对内存地址的操作权限移交给操作系统。如果没有做free()这个操作，删除该结点时，会导致该结点在已经无法找到了，但却还拥有控制权限。操作系统在分配内存时，会认为当前内存地址有人还在使用，就不会分配给其他的应用程序，从而会导致内存空间，越用越少。

排序

排序的稳定性

所谓稳定性是指，如果序列中两个数据元素相等，即r[i]==r[j]，排序前r[i]在r[j]前，排序后r[i]仍然在r[j]前，则这个排序算法是稳定的，反之是不稳定的。

选择排序

其基本思想是从待排序的无序区中找出最小的元素，将该元素与该区中的第一个元素交换位置。该排序算法是不稳定的。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 上午9:27:32
 * @remark 
 * 选择排序：每一次在无序的序列中选出关键字最小的记录，依次存放在已排好序的记录序列最后。
 * 原始 数据：5 4 9 87 1 2 14 26
 * 	第一趟      1 5 4 9 87 2 14 26
 *  第二趟      1 2 5 4 9 87 14 26
 *  第三趟      1 2 4 5 9 87 14 26
 *  第四趟      1 2 4 5 9 87 14 26
 *  第五趟      1 2 4 5 9 87 14 26
 *  第六趟      1 2 4 5 9 14 87 26
 *  第七趟      1 2 4 5 9 14 26 87
 */
public class ChooseSort {
	public static void main(String[] args) {
		//统计运行次数
		int count = 0;
		int[] array = { 5, 4, 9, 87, 1, 2, 14, 26 };
		chooseSort(array, count);
	}
	
	/**
	 * 选择排序
	 * @param array
	 * @param count
	 */
	public static void chooseSort(int[] array, int count) {
		for (int i = 0; i < array.length; i++) {
			for (int j = i + 1; j < array.length; j++) {
				if(array[j] < array[i]){
					int temp = array[i];
					array[i] = array[j];
					array[j] = temp;
				}
				count++;
			}
		}
		System.out.println(Arrays.toString(array) + "--->ChooseSort：" + count);
	}
}

插入排序

其核心思想是把待排序区中的第一个元素拿出来，把位置给空出来。然后用该元素，跟有序区中的元素进行比较。假设是从小到大排序，则比该元素大的，往后移动一次。依次进行即可。把该元素插入到不能移动的元素后边的空间中。该排序算法是稳定的。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 上午9:57:20
 * @remark 插入排序：1、元素拿出来。2、符合条件的元素后移
 */
public class InsertSort {
	public static void main(String[] args) {
		// 统计运行次数
		int count = 0;
		int[] array = { 5, 4, 9, 87, 1, 2, 14, 26 };
		insertSort(array, count);
	}
	
	/**
	 * 插入排序
	 * @param array
	 * @param count
	 */
	public static void insertSort(int[] array, int count) {
		int pos = 0;
		for (int i = 2; i < array.length; i++) {
			// 待插入的位置
			pos = i;
			// 元素拿出来
			int temp = array[i];
			for (int j = i - 1; j >= 0 && array[j] > temp; j--) {
				// 符合条件的元素后移
				array[j + 1] = array[j];
				// 需要插入的位置
				pos = j;
				count++;
			}
			array[pos] = temp;
		}
		System.out.println(Arrays.toString(array) + "--->InsertSort：" + count);
	}
}

冒泡排序

其基本思想是通过相邻元素之间的比较和交换，来完成排序。有向上冒泡和向下下沉。该排序算法是稳定的。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 上午10:41:21
 * @remark 冒泡排序：相邻元素之间的比较交换。一种是向上冒泡，一种是向下下沉
 */
public class BubbleSort {
	public static void main(String[] args) {
		// 统计运行次数
		int count = 0;
		int[] array1 = { 5, 4, 9, 87, 1, 2, 14, 26 };
		int[] array2 = { 5, 4, 9, 87, 1, 2, 14, 26 };
		int[] array3 = { 5, 4, 9, 87, 1, 2, 14, 26 };
		int[] array4 = { 5, 4, 9, 87, 1, 2, 14, 26 };
		
		count = bubbleSort1(array1, 0);
		System.out.println(Arrays.toString(array1) + "--->bubbleSort1：" + count);
		
		count = bubbleSort2(array2, 0);
		System.out.println(Arrays.toString(array2) + "--->bubbleSort2：" + count);
		
		count = bubbleSort3(array3, 0);
		System.out.println(Arrays.toString(array3) + "--->bubbleSort3：" + count);
		
		count = bubbleSort4(array4, 0);
		System.out.println(Arrays.toString(array4) + "--->bubbleSort4：" + count);
		int[] array5 = { 1, 2, 4, 3, 5, 6, 7, 8 };
		count = bubbleSort4(array5, 0);
		System.out
				.println(Arrays.toString(array5) + "--->bubbleSort4：" + count);
	}
	/**
	 * 向上冒泡
	 * 
	 * @param array
	 * @param count
	 */
	public static int bubbleSort1(int[] array, int count) {
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = 1; j < array.length - i; j++) {
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
				count++;
			}
		}
		return count;
	}
	/**
	 * 向下下沉
	 * 
	 * @param array
	 * @param count
	 */
	public static int bubbleSort2(int[] array, int count) {
		for (int i = 0; i < array.length - 1; i++) {
			for (int j = array.length - 1; j > i; j--) {
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
				count++;
			}
		}
		return count;
	}
	/**
	 * 向上冒泡，优化
	 * 
	 * @param array
	 * @param count
	 */
	public static int bubbleSort3(int[] array, int count) {
		// 标记，true表示：元素还没有排好序
		boolean flag = true;
		for (int i = 0; i < array.length - 1 && flag; i++) {
			// 认为已经排好序
			flag = false;
			for (int j = 1; j < array.length - i; j++) {
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
					// 元素执行了交换，则说明数据还没有排好序
					flag = true;
				}
				count++;
			}
		}
		return count;
	}
	/**
	 * 向下下沉：优化
	 * 
	 * @param array
	 * @param count
	 */
	public static int bubbleSort4(int[] array, int count) {
		// 标记，true表示：元素还没有排好序
		boolean flag = true;
		for (int i = 0; i < array.length - 1 && flag; i++) {
			// 认为已经排好序
			flag = false;
			for (int j = array.length - 1; j > i; j--) {
				if (array[j] < array[j - 1]) {
					int temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
					// 元素执行了交换，则说明数据还没有排好序
					flag = true;
				}
				count++;
			}
		}
		return count;
	}
}

希尔排序

其核心思想是对数据进行分组，然后再对分组后的数据进行插入排序算法。该排序算法是不稳定的。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 下午3:23:48
 * @remark 希尔排序：对数据进行分组，然后再进行插入排序算法
 */
public class ShellSort {
	public static void main(String[] args) {
		// 统计运行次数
		int count = 0;
		int[] array = { 5, 4, 9, 87, 1, 2, 14, 26 };
		shellSort(array, count);
	}
	
	/**
	 * 希尔排序
	 * @param array
	 * @param count
	 */
	public static void shellSort(int[] array, int count) {
		int gap = array.length;
		int pos = 0;
		do {
			//业界统一实验 平均最好间隔情况
			gap = gap / 3 + 1;
			for (int i = gap; i < array.length; i += gap) {
				// 待插入的位置
				pos = i;
				// 元素拿出来
				int temp = array[i];
				for (int j = i - gap; j >= 0 && array[j] > temp; j -= gap) {
					// 符合条件的元素后移
					array[j + gap] = array[j];
					// 需要插入的位置
					pos = j;
					count++;
				}
				array[pos] = temp;
			}
		} while (gap > 1);
		System.out.println(Arrays.toString(array) + "--->ShellSort：" + count);
	}
}

快速排序

其基本思想是从待排序序列中找一个基准数，以基准数进行左右分区，其中一部分的所有数据都比另外一部分所以数据小，基准数排在两个分区序列中间。然后再按此方法对这两部分数据分别进行快速排序，递归进行，达到变成有序序列。该排序算法是不稳定的。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 下午4:30:56
 * @remark 快速排序：用一个PV值，跟PV值进行比较来分区，小的放左边，大的放右边。对分过区的，再找PV值进行分区，直到分区只有一个元素
 */
public class QuickSort {
	public static void main(String[] args) {
		int[] array = { 5, 4, 9, 87, 1, 2, 14, 26 };
		quickSort(array);
		System.out.println(Arrays.toString(array) + "--->QuickSort");
	}
	
	/**
	 * @param array
	 */
	public static void quickSort(int[] array) {
		qSort(array, 0, array.length - 1);
	}
	
	/**
	 * 
	 * @param array
	 * @param low
	 * @param hight
	 */
	public static void qSort(int[] array, int low, int hight) {
		if (low < hight) {
			int pivot = partition(array, low, hight);
			// 对左区间序列排序
			qSort(array, low, pivot - 1);
			// 对右区间序列排序
			qSort(array, pivot + 1, hight);
		}
	}
	
	/**
	 * 分区
	 * @param array
	 * @param low
	 * @param hight
	 * @return
	 */
	public static int partition(int[] array, int low, int hight) {
		// 用分区后的第一个元素作为PV值
		int pv = array[low];
		while (low < hight) {
			while (low < hight && array[hight] >= pv) {
				// 比基准数大，本来就在右边，所以hight向前移动
				hight--;
			}
			if (low < hight) {
				array[low] = array[hight];
				low++;
			}
			while (low < hight && array[low] <= pv) {
				// 比基准数小，本来就在左边，所以low向前移动
				low++;
			}
			if (low < hight) {
				array[hight] = array[low];
				hight--;
			}
		}
		//把拿出来的PV数，放回到low的位置
		array[low] = pv;
		return low;
	}
}

归并排序

其基本思想是使用辅助空间，首先是对待排序序列进行拆分，以递归的方式，拆成只剩下一个的时候，再两两进行归并操作，按指定的条件进行排序。再执行最后一次归并时，如果最后一次比较后，某个序列中有多余的元素，会直接插入到辅助空间后面。

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
package datastructure.part.sort;
import java.util.Arrays;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月27日 下午7:24:42
 * @remark 归并排序：两两归并
 */
public class MergeSort {
	
	public static void main(String[] args) {
		int[] array = { 5, 4, 9, 87, 1, 2, 14, 26 };
		mergeSort(array);
		System.out.println(Arrays.toString(array) + "--->MergeSort");
	}
	
	/**
	 * @param array
	 */
	public static void mergeSort(int[] array) {
		mSort(array, array, 0, array.length - 1, array.length);
	}
	
	/**
	 * 归并排序
	 * @param src：源数组
	 * @param des：目标数组
	 * @param low：最低位
	 * @param hight：最高位
	 * @param max：最大值
	 */
	public static void mSort(int[] src, int[] des, int low, int hight, int max) {
		if (low == hight) {
			// 只有一个元素，不需要归并
			des[low] = src[low];
		} else {
			// 如果多个元素，进行两路划分
			int[] space = new int[max];
			int mid = (low + hight) / 2;
			mSort(src, space, low, mid, max);
			mSort(src, space, mid + 1, hight, max);
			// 当剩下一个元素时，递归划分结束。开始进行merge归并操作
			merge(space, des, low, mid, hight);
		}
	}
	/**
	 * 两两合并
	 * @param src
	 * @param des
	 * @param low
	 * @param mid
	 * @param hight
	 */
	public static void merge(int[] src, int[] des, int low, int mid, int hight) {
		int i = low;
		int j = mid + 1;
		int k = low;
		// 将小的放到目的地中
		while (i <= mid && j <= hight) {
			if (src[i] < src[j]) {
				des[k++] = src[i++];
			} else {
				des[k++] = src[j++];
			}
		}
		// 若还剩几个尾部元素
		while (i <= mid) {
			des[k++] = src[i++];
		}
		// 若还剩几个尾部元素
		while (j <= hight) {
			des[k++] = src[j++];
		}
	}
}

查找

二分查找法

二分查找又称折半查找，效率较高，但有限制条件。只能对线性表的顺序存储结构并且元素有序进行查找。可采用递归、非递归方式。

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
package datastructure.part.sort;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月28日 下午3:18:58
 * @remark 二分查找法
 */
public class BinarySearch {
	public static void main(String[] args) {
		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8 };
		int index = binarySearch(array, 1, 0, array.length - 1);
		System.out.println("index：" + index);
		index = binarySearch(array, 1);
		System.out.println("index：" + index);
	}
	/**
	 * 非递归方式
	 * @param array
	 * @param keyword
	 * @return
	 */
	private static int binarySearch(int[] array, int keyword) {
		int low = 0;
		int hight = array.length - 1;
		int mid;
		while (low <= hight) {
			mid = (low + hight) / 2;
			if (keyword == array[mid]) {
				return mid;
			} else if (keyword < array[mid]) {
				hight = mid - 1;
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}
	/**
	 * 递归方式
	 * @param array
	 * @param keyword
	 * @param low
	 * @param hight
	 * @return
	 */
	private static int binarySearch(int[] array, int keyword, int low, int hight) {
		if (low <= hight) {
			int mid = (low + hight) / 2;
			if (keyword == array[mid]) {
				return mid;
			} else if (keyword > array[mid]) {
				return binarySearch(array, keyword, mid + 1, hight);
			} else {
				return binarySearch(array, keyword, low, mid - 1);
			}
		}
		return -1;
	}
}

二叉排序树

又称二叉查找树，其特点是如果右子树非空，右子树上所有结点的值均大于根节点的值。如果左子树非空，左子树上所有结点的值均小于根结点的值。左右子树又各是一棵二叉排序树。中序遍历即可获得一个有序序列。Java中的TreeSet，其实就是一个二叉排序树，根据左小右大来放置元素。

其他代码实现

顺序栈

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
package datastructure.part.one;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年2月8日 上午9:37:53
 * @remark 数组结构的顺序栈
 */
public class Stack<T> {
	private int maxSize; // 栈空间的大小
	private T[] stackArray;// 顺序栈，采用泛型确定栈空间的存放的数据类型
	private int top; // 栈顶指针
	public Stack(int size) {
		maxSize = size;
		stackArray = (T[]) new Object[maxSize];
		top = -1;
	}
	
	/**
	 * 入栈
	 * @param element
	 */
	public void push(T element) {
		stackArray[++top] = element;
		if (top > (maxSize - 1)){
			top = maxSize - 1;
		}
	}
	public void pretendedPush() {
		++top;
		if (top > (maxSize - 1)) {
			top = maxSize - 1;
		}
	}
	
	/**
	 * 出栈
	 * @return
	 */
	public T pop() {
		if (top == -1) {
			return null;
		} else {
			return stackArray[top--];
		}
	}
	
	/**
	 * 查看栈顶元素，但是不出栈
	 * @return
	 */
	public T peek() {
		return stackArray[top];
	}
	
	/**
	 * 判断栈是否空
	 * @return
	 */
	public boolean isEmpty() {
		return top == -1;
	}
	
	/**
	 * 判断栈是否满
	 * @return
	 */
	public boolean isFull() {
		return top == maxSize - 1;
	}
}

进制转换

借助栈空间，根据基数对原数取余数，把取到余数入栈，再对原数取整，循环该过程，直到取整的数为0时停止。最后再栈内元素全部出栈。

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
package datastructure.part.one;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年4月7日 上午9:17:33
 * @remark 进制转换
 */
public class BinaryConversion {
	public static void main(String[] args) {
		conversion(6, 2);
	}
	/**
	 * 进制转换的思想是，对一个原数不停的取余数
	 * @param number：原始数值
	 * @param decimalBinary：转换的进制，基数
	 */
	public static void conversion(int number, int decimalBinary) {
		// 初始化栈空间，栈的大小。取数值整除基数再加1
		Stack<Integer> stack = new Stack<Integer>(number / decimalBinary + 1);
		while (number != 0) {
			// 把余数放入栈中
			stack.push(number % decimalBinary);
			// 取整
			number = number / decimalBinary;
		}
		while (!stack.isEmpty()) {
			System.out.print(stack.pop());
		}
	}
}

判断回文数

回文的特点是：倒着写跟原来是一样的。代码的实现，用了三种方式。
第一种是判断非负整数是否是个回文数。采用的方式，是把原来的数值给回转过来，再跟原数值进行一次比较，相等则是回文数。

第二种是采用栈，对数值的长度进行劈叉，把前一半的数值一次入栈。然后再进行出栈，并与后一半数值进行比较，都相等则是回文数。该方式有一个BUG，当长度是奇数时，前一半数据的长度跟后一半数据的长度并不相等，会导致12321这种类型的数据，判断出来不是回文数。

第三种是获取数据的字节数组，采用头指针跟尾指针，每循环一次，拿头指针上的数据与尾指针上的数据进行比较，相等则头指针往前挪一位，尾指针往后挪一位。直到头指针小于等与尾指针，循环结束。

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
package datastructure.part.one;
/**
 * @description
 * @author Denghs
 * @version 1.0,2018年3月5日 下午4:52:12
 * @remark 判断回文数
 */
public class Symmetry {
	public static void main(String[] args) {
		System.out.println(symmetry(1221));
		System.out.println(symmetry("哈哈哈哈"));
		System.out.println(symmetry("456654"));
		System.out.println(symmetryStr("45654"));
	}
	/**
	 * 判断一个数值是否是回文数。回文的特点是：倒着写跟原来是一样的。
	 * 
	 * @param number
	 */
	public static boolean symmetry(int number) {
		int i = 0;
		int sum = 0;
		int record = number;// 保存原记录数
		while (true) {
			i = number % 10;
			sum = sum * 10 + i;
			number /= 10;
			if (number == 0)
				break;
		}
		// 判断倒过来写的数，是否跟原来的数是一样的。
		if (sum == record) {
			return true;
		} else {
			return false;
		}
	}
	/**
	 * 判断一个串是否是回文串。回文的特点是：倒着写跟原来是一样的。
	 * 使用栈的方式，进行比较。如果串的长度是一个奇数，会存在一个中间数没有对应的数进行比较。
	 * 则会返回false
	 * @param string
	 */
	public static boolean symmetry(String string) {
		// 获取串字符的长度
		char[] charArray = string.toCharArray();
		// 初始化栈
		Stack<Character> stack = new Stack<Character>(charArray.length / 2 + 1);
		for (int i = 0; i < charArray.length / 2; i++) {
			// 前一半的字符放入栈中
			stack.push(charArray[i]);
		}
		for (int j = charArray.length / 2; j < charArray.length; j++) {
			Character character = stack.pop();
			// 栈内已经没有元素了或者有字符不相同
			if (null == character || character != charArray[j]) {
				return false;
			}
		}
		return true;
	}
	/**
	 * 判断一个串是否是回文串。回文的特点是：倒着写跟原来是一样的。
	 * @param string
	 */
	public static boolean symmetryStr(String string) {
		char[] charArray = string.toCharArray();
		int start = 0;
		int end = charArray.length - 1;
		while (start <= end) {
			if (charArray[start] != charArray[end]) {
				return false;
			}
			start++;
			end--;
		}
		return true;
	}
}

汉诺塔问题


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
package datastructure.part.one;
import java.util.Scanner;
/**
 * @description 
 * @author Denghs
 * @version 1.0,2018年2月7日 上午9:37:53
 * @remark 汉诺塔问题
 */
public class HanNuoTa {
	
	public static void main(String[] args) {
		System.out.println("输入一个数字：");
		Scanner scanner = new Scanner(System.in);
		//操作数
		int number = scanner.nextInt();
		//三根柱子
		String poleA = "柱子A";
		String poleB = "柱子B";
		String poleC = "柱子C";
		//A柱子上的盘子，借助B柱子，移动到C柱子
		hanNuoTa(number, poleA, poleB, poleC);
		scanner.close();
	}
	/**
	 * @param number 盘子数
	 * @param poleA	盘子所在的柱子
	 * @param poleB 需要借力的柱子
	 * @param poleC	最终移动到的柱子
	 */
	private static void hanNuoTa(int number, String poleA, String poleB, String poleC) {
		/*
		如果是1个盘子
			直接将A柱子上的盘子从A移动到C
		否则
			先将A柱子上的n-1个盘子，借助C移动B
			直接将A柱子上的盘子从A移动到C
			最后将B柱子上的n-1个盘子，借助A移动C*/
		if(1 == number){
			System.out.println("将编号为-" + number + "的盘子，直接从柱子-" + poleA + "移动到柱子-" + poleC);
		}else{
			hanNuoTa(number-1, poleA, poleC, poleB);
			System.out.println("将编号为-" + number + "的盘子，直接从柱子-" + poleA + "移动到柱子-" + poleC);
			hanNuoTa(number-1, poleB, poleA, poleC);
		}
	}
	
}

谢谢你请我吃糖果

--------- 本文结束，感谢您的审阅 ---------
0%