本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解查找，代码均为自己实现。

查找（Searching）是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

顺序表查找

​ 顺序查找又叫线性查找，是最基本的查找技术，它的查找过程是：从表中第一个（或最后一个）记录开始，逐个记性记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class OrderSearch {
	public int orderSearch(int[] array ,int key){
		for ( int i = 0 ;i < array.length ; i++){
			if(array[i] == key){
				return i;
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array = new int[]{1,3,5,2,9,7};
		OrderSearch OrderSearch = new OrderSearch();
		System.out.println(OrderSearch.orderSearch(array,9));
	}
}

垃圾收集器与内存分配策略

Java技术体系中所提倡的自动内存管理最终可以归结为自动化地解决了两个问题：给对象分配内存以及回收分配给对象的内存。

​ Java内存运行时区域的各个部分，其中程序计数器、 虚拟机栈、 本地方法栈3个区域随线程而生，随线程而灭；栈中的栈帧随着方法的进入和退出而有条不紊地执行着出栈和入栈操作。 每一个栈帧中分配多少内存基本上是在类结构确定下来时就已知的，因此这几个区域的内存分配和回收都具备确定性，在这几个区域内就不需要过多考虑回收的问题，因为方法结束或者线程结束时，内存自然就跟随着回收了。 而Java堆和方法区则不一样，一个接口中的多个实现类需要的内存可能不一样，一个方法中的多个分支需要的内存也可能不一样，我们只有在程序处于运行期间时才能知道会创建哪些对象，这部分内存的分配和回收都是动态的，垃圾收集器所关注的是这部分内存。

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解图，代码均为自己实现。

图

图（Graph）是由定点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

线性表中将数据元素称为元素，树中将数据元素称为结点，图中将数据元素称为顶点。

线性表中可以没有数据元素，称为空表。树中可以没有结点，称为空树。在图结构中，不允许没有顶点。在定义中，顶点集合有穷非空。

线性表中，相邻数据元素之间有线性关系。树结构中，相邻两层结点之间有层次关系。在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系有边来表示。边集可以为空。

各种图的相关概念

无向边：若顶点vi到vj之间的边没有方向，则称这条边为无向边（Edge），用无序偶对(vi , vj)来表示。

无向图：若图中任意两个顶点之间的边都是无向边，则称该图为无向图。

有向边：若从顶点vi到vj的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶对来表示，vi 称为弧尾（Tail），vj 称为弧头（Head）。

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解树，代码均为自己实现。

树

树（Tree）是n（n>=0）个结点的有限集。 n=0又称为空树。在任意一课非空的树中：有且仅有一个特定的称为跟（Root）的结点；当n>1时，其余结点可分为m（m>0）个互不相交的有限集，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树是一种一对多的数据结构。

需要注意的是：当n>0时根结点是惟一的，不可能存在多个根结点。 ​m>0时，子树的个数没有限制，但它们一定是互不相交的。如果相交，就不符合树的定义。

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解串，代码均为自己实现。

串

串（string）是由零个或多个字符组成的有限序列，又名字符串。

串的存储结构

​ 串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。 用“\0”来表示串的终结，不计入串长度，但是计入数组长度。 两个长度不同的串不可能相等。

​ 串的链式存储结构要考虑一个结点是存放一个字符（会造成很大的空间浪费）还是多个字符。除了链接串与串的操作有一定方便外，总的来说不如顺序存储量或，性能也不如顺序存储结构好。

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解栈和队列，代码均为自己实现。

栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。（类似弹夹中的子弹）
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。（类似等待客服电话排队）

栈的抽象数据类型

栈本身也是一种线性表，除了删除和添加改名为pop(弹)和push(压)，抽象功能没有特别的地方。为了方便实现我们还是自定义栈的接口

，另外注意一点是java的sdk继承vector实现的stack，相关操作使用synchronized，具有安全性。