广州番禺Python, Java小班周末班培训
薯条老师的线下Python小班办得很好，学员的平均就业薪资有11K。线下小班培训的课程有Python爬虫，Python后端开发，Python办公自动化，Python大数据分析，Python量化投资，Java中高级后端开发。授课详情请点击：http://chipscoco.com/?cate=6
10.3.1 无处不在的结构
在生活中细心观察，我们会发现许多事物都具有结构性的特征。下图是一颗树的外部结构：
所谓结构，简言之即组成部分，以上图的树结构为例，它由树根，树干，树枝，树叶所组成。树有其结构，我们人体有它的结构，一台计算机有它的结构，数据也有它的结构，只要读者留心观察，会发现结构是无处不在的。
10.3.2 数据结构初认识
数据结构是一门既基础又重要的课程，读者务必在以后的进阶学习中继续深入地学习这门课程。我们现在来看下数据结构的定义：
数据结构是指数据成员相互之间所存在的一种或多种特定关系的数据元素的集合。
概念乍看起来很复杂，我们先对复杂的概念进行分解:
(1) 所谓的数据结构指的是数据元素的集合，读者可以把数据结构看成是容纳数据对象的容器。
(2) 在这个数据集合或容器中，数据元素相互之间存在一种或多种特定的关系。
(3) 数据元素之间的关系主要是线性的和非线性的关系。
对复杂的概念进行分解，再逐个突破，是一种很有效的学习方法。根据数据元素之间的线性或非线性的关系，又可将数据结构分为线性结构和非线性结构。
10.3.3 线性结构
先看图，以直观地理解线性结构的含义，下图分别为图1，图2：
图1，图2都是线性结构，这是逻辑上的线性结构，两图的区别在于图1在逻辑上是连续的一条线，在计算机地址空间中对应的是一块连续的内存，图二在逻辑上也是一条线，但在计算机中却不一定是连续存储的，图二中的圆形节点对应的是计算机中的一块内存，箭头对应的是下一个内存块的地址，内存块之间以内存地址进行逻辑上的连接。
所谓内存地址，就是内存块的编号。通过该编号，就可以找到下一个内存块。
所谓逻辑上的连接，意指并不存在物理的连接媒介，它与物理连接有本质的区别，物理连接是实打实的点对点的连接，通俗地说就是看得见，摸得着的。如网线通过网口与电脑之间的连接，就是物理上的连接。图1在计算机中是顺序存储结构，图2是链式存储结构，二者都是线性结构。区别为前者在计算机内存空间中是连续存储的，读者可以把它理解为内存块紧挨着一个内存块，如下图所示：
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
而链式存储，通常为非连续存储，对于初学者来说，这些概念会有点难以理解，这涉及到数据结构这门课程的知识，初学者现在仅需做的是，能在脑海中想象出这种线性的逻辑结构。
10.3.4 非线性结构
非线性结构，直观地看，就是这种数据结构在逻辑上不是一条直线，它是曲的，折的，分叉的，我们看图：
上图中的结构即是非线性结构的一种，它看起来是不是与本节一开始的那棵树很像？其实，它就是棵树，只不过是棵倒长的树，这种树形的结构在数据结构里面叫二叉树，所谓二叉，是指每个节点最多有两个子节点，如编号为1的节点，其子节点是2和3，编号为2的节点，它的子节点是4和5。更有三叉树，多叉树等等，都是一样的原理。
还有比树结构更复杂的非线性结构，比如图结构等，读者如果有兴趣，可以自行学习数据结构这门课程。
10.3.5 为什么要学习数据结构
编程的核心是处理数据，在处理数据的过程中，如何更快地对数据进行处理，就需要了解数据结构，在数据结构的基础上，设计出相应的算法，以加快数据的处理过程。
笔者举一个经典的折半查找的例子：在顺序存储结构中，我们可以预先对数据集合中的数据进行排序，以加快数据的查找过程。下图是排序前的一维数组，如果要找到9这个元素，那么需要从数组的第一个元素开始，一个一个的往下查找，最慢需要查找9次。
1 | 3 | 2 | 7 | 6 | 5 | 4 | 8 | 9 |
由于事先不知道数组包含了哪些元素，所以只能从数组的第一个元素开始逐个查找。为加快元素的查找过程，我们可以先对数组进行升序排序，排序后的一维数组如下表所示：
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
对数组排序以后，我们先从中间位置开始查找，中间位置的元素为5,由于数组为升序，且查找的元素9大于5，所以只能往右半区间查找(左半区间的元素肯定都小于9，所以无需再查)。不断重复这样的过程，最慢只需查找3次就可以找到元素9，显著地提升了查找性能。
先对数组进行排序，升序或降序都可以，然后每次与一半区间中的中间位置的元素进行比较，这即是经典的二分查找算法。
先对数据集合进行排序等预处理操作，那么即使数据集合中包含百万，甚至千万、亿万个元素，使用二分查找算法最慢也只需几十次就可以确认元素是否在数据集合中。
10.3.6 冒泡排序算法
上节讲到了先对数据集合进行排序，然后利用二分查找算法来提升查找性能。在本节内容中，笔者向大家介绍数据结构中最经典的排序算法之一：冒泡排序算法。利用冒泡排序，我们可以将数组中的值从无序变成有序。
冒泡排序原理：
冒泡排序，其排序过程跟海水的冒泡过程很相似，故名冒泡排序。冒泡排序的原理很简单，海水在冒泡的过程中是由小气泡逐渐变成大气泡的，小气泡变成大气泡的过程，我们可以将其理解为气泡与相邻气泡的交换过程。如果相邻位置处前面的气泡比自己小，那么就相互交换位置，否则就不进行交换。我们看图，下表所示为一组无序的气泡，编号值表示气泡的大小：
9 | 2 | 5 | 1 | 3 | 4 | 6 | 8 | 7 |
笔者简单演示气泡交换的过程，我们先看第一步：
在第一步交换中，气泡9比气泡2要大，所以气泡9被交换到了气泡2的位置，气泡2被交换到了气泡9的位置。接着来看第二步：
此时气泡9再与气泡5进行比较，同样地，气泡9比气泡5大，所以这次它们又互相交换位置。在这样的相邻气泡的比较过程中，气泡9最终被交换到了尾部的位置：
最大的气泡9被交换到了尾部位置以后，我们再从剩下的8个气泡中重复这样的交换过程。
n个元素两两进行比较，最多只需比较n-1次，就可以找出最大或最小的值。
在上面的冒泡排序算法中，10个元素两两进行比较，比较了9次，才把最大的气泡交换到了尾部位置。在剩下的8个元素中，继续重复两两比较的过程，比较7次后就可以将8个中的最大值放到倒数第二个位置。不断重复这样的过程，就可以实现冒泡排序。下图所示为数组[3,2,1]的冒泡排序过程：
代码实例-实现冒泡排序：
import java.util.Arrays;
/**
* @description: Sort类提供了冒泡排序的算法实现
*/
class Sort {
public static void bubbleSort(int[] array) {
/*
(1) length个元素需要比较length-1次才能找出最大值或最小值
(2) 每次找出数据集合中的最大值或最小值，将其放到对应位置
(3) length个元素需要比较length-1趟才能实现排序
*/
// 外层循环的length-1表示比较的趟数，在初始情况下，一共需要length-1趟
for(int outerIndex=0; outerIndex < array.length-1; ++outerIndex) {
// 内层循环的array.length-1-outerIndex表示每趟比较的次数
for(int innerIndex=0; innerIndex < array.length-1-outerIndex; ++innerIndex){
if (array[innerIndex] > array[innerIndex+1]) {
// 如果相邻元素小于当前元素，就两两交换
int tmp = array[innerIndex];
array[innerIndex] = array[innerIndex+1];
array[innerIndex+1] = tmp;
}
}
}
}
}
public class HelloJava{
public static void main(String[] args) {
// 定义一个长度为7的一维数组
int[] numbers = {5, 2, 1, 4, 7, 9, 11};
// 执行bubbleSort算法对数组进行排序
Sort.bubbleSort(numbers);
// 通过toString方法将数组转换为字符串，方便输出
System.out.println(Arrays.toString(numbers));
}
}10.3.7 二分查找算法
二分查找算法的逻辑比较简单，在有序(升序或降序)的数据集合中，每次与中间位置的元素进行比较，如果相等就返回该元素的索引，如果不相等，就根据数据集合是升序还是降序，来选择另一半区间。代码实例-实现二分查找算法：
import java.util.Arrays;
/**
* @description: Sort类提供了冒泡排序的算法实现
*/
class Sort {
public static void bubbleSort(int[] array) {
/*
(1) length个元素需要比较length-1次才能找出最大值或最小值
(2) 每次找出数据集合中的最大值或最小值，将其放到对应位置
(3) length个元素需要比较length-1趟才能实现排序
*/
// 外层循环的length-1表示比较的趟数，在初始情况下，一共需要length-1趟
for(int outerIndex=0; outerIndex < array.length-1; ++outerIndex) {
// 内层循环的array.length-1-outerIndex表示每趟比较的次数
for(int innerIndex=0; innerIndex < array.length-1-outerIndex; ++innerIndex){
if (array[innerIndex] > array[innerIndex+1]) {
// 如果相邻元素小于当前元素，就两两交换
int tmp = array[innerIndex];
array[innerIndex] = array[innerIndex+1];
array[innerIndex+1] = tmp;
}
}
}
}
}
/**
* @description: Search类提供了二分查找的算法实现
*/
class Search {
public static int binarySearch(int[] array, int val){
int pos = -1;
// left表示区间的最左边位置
int left = 0;
int mid;
// right表示区间的最右边位置
int right = array.length-1;
while (left <=right){
/*
(1) 每次与中间位置的元素进行比较
(2) 中间位置即(left+right)/2,由于left+right可能溢出，所以才写成right/2-left/2+left
表达式(left+right)/2与表达式right/2-left/2+left是等价的
*/
mid = (right-left)/2 + left;
if (array[mid] == val) {
// 如果与中间位置元素相等，就保存索引值，并退出循环
pos = mid;
break;
}
else if(array[mid] > val){
// 如果小于中间位置元素，则在升序的数组中，往左半区间查找
right = mid-1;
}
else {
// 如果小于中间位置元素，则在升序的数组中，往右半区间查找
left = mid+1;
}
}
return pos;
}
}
public class HelloJava{
public static void main(String[] args) {
// 定义一个长度为7的一维数组
int[] numbers = {5, 2, 1, 4, 7, 9, 11};
// 执行bubbleSort算法对数组进行排序
Sort.bubbleSort(numbers);
int val = 12;
System.out.println(Arrays.toString(numbers));
// 调用二分查找算法来查找元素
System.out.println(Search.binarySearch(numbers, val));
}
}10.2.7 最具实力的小班培训
来这里参加Python和Java小班培训的学员大部分都找到了很好的工作，平均月薪有11K，学得好的同学，拿到的会更高。由于是小班教学，所以薯条老师有精力把每位学员都教好。打算参加线下小班培训的同学，必须遵守薯条老师的学习安排，认真做作业和项目。把知识学好，学扎实，那么找到一份高薪的工作就是很简单的一件事。
(1) Python后端工程师高薪就业班，月薪11K-18K，免费领取课程大纲
(2) Python爬虫工程师高薪就业班，年薪十五万，免费领取课程大纲
(3) Java后端开发工程师高薪就业班，月薪11K-20K, 免费领取课程大纲
(4) Python大数据分析，量化投资就业班，月薪12K-25K,免费领取课程大纲
扫码免费领取学习资料：
