数据的逻辑结构

单链表是递归结构

迭代是指从当前元素获得集合中的后继元素。

迭代功能由Tterable可迭代接口和Tterator迭代器接口实现。

栈和队列

是两种特殊的线性表，特殊之处在于插入和删除操作的位置受到限制。

栈：插入和删除只允许在线性表的一端进行，后进先出。

队列：插入和删除分别在线性表的两端进行，先进先出。

数组：

1.数组是随机存取结构，这是数组最大的优点。

2.数组一旦占用一片存储空间，这片存储空间的地址和长度就确定的，不能更改，因此数组只能进行赋值、取值两种随机存取操作，不能进行插入、删除操作。

3.解决数据溢出的办法是，申请一个更大容量的数组并进行数组元素的复制，这样扩充了顺序表等结构的容量。

广义表的特性：

1.线性结构

2.多层次结构，有深度

3.可共享

4.可递归

广义表的操作主要有：

建立一个广义表

判断广义表是否是空表

判断指定数据元素是否为原子

求广义表深度

遍历广义表

插入一个数据元素

删除一个数据元素

二叉树的三种次序遍历

先根次序：ABCDGEFH （中左右）

中根：DGBAECHF（左中右）

后根：GDBEHFCA（左右中）

树的遍历主要有先根遍历和后根遍历两种。

图的遍历一般有两种：深度优先搜索和广度优先搜索。

基于线性表的查找算法主要有：顺序查找、折半查找、分块查找，分别适用于线性表、有序顺序表、索引顺序表。

分块查找：将主表元素逻辑上分成若干块，分块特性为“块内无序，块间有序”，换而言之，每块中元素可无序存放，前一块中任意一个元素的关键字均小于后一块中所有元素的关键字。索引表保存每块元素的起始位置。

分块查找步骤：

（1）查找索引表：（可用顺序或折半）

（2）在一块中查找：（可用顺序或折半）

散列表

散列（hash）是一种按关键字编址的存储和检索方法。

散列函数

在数据元素的噶un尖子与该元素的存储位置之间建立一种关系，将这种关系称为散列函数（hash function）。

排序

常用：插入排序、交换排序、选择排序、归并排序。

插入排序算法有三种：直接插入排序、折半插入排序、希尔排序。

交换排序有两种：冒泡排序和快速排序。

冒泡排序：

  public  static void buttleSort(int [] table){

       boolean exchange =true;

      for(int i=1;i<table.length&&exchange;i++){

           exchange=false;

           for(int j=0;j<table.length-i;j++){

               if(table[j]>table[j+1]){

                   int temp=table[j];

                   table[j]=table[j+1];

                   table[j+1]=temp;

                   exchange=true;

               }

           }

       }

   }

快速排序

在数据序列中选择一个值作为比较 的基准值，每趟从数据库序列的两端开始比较交替进行，将小于基准值额元素交换到序列前端，将大于基准值的元素交换到序列后端，介于两者之间的位置则成为基准值的最终位置，同时，序列被划分为两个子序列，再用同样的方法分别对两个子序列进行排序。

选择排序

两种：直接选择排序和堆排序

直接选择排序：每次选一个最小放在前端，将剩下的依次选最小，放前端最小之后。

堆排序：是完全二叉树的应用。

归并排序：将两个已排序的子序列合并，形成一个排序数据序列，又称两路归并排序。