数据结构、算法与应用
一、绪论
二、线性表
三、树
四、图
4.1 图的基本概念
在图结构中，数据元素中间的关系可以是任意的，图中任意两个元素之间都可能相关。
图根据边的分类分为有向图和无向图，有向图的边是有向边，它就像公路的单行道一样，只能从一个方向到另一个方向。无向图的边是无向边，当然它就像双向车道一样可以互相到达，而且两个顶点是没有区别的。
当且仅当（u，v）是图的边，称顶点v和u是邻接的。边（u，v）关联于顶点u和v。对于无向图这种邻接和关联是对等的，而有向图是单向的，它仅仅从u到v。
权：在图的一些应用中，可能要为每条边赋予一个表示大小的值，这个值就称为权。例如从城市A到城市B存在一条公路，而可以使用权表示这条公路的距离。
路径：一个顶点序列i1，i2........ik是图的一条路径，当且仅当边（i1，i2）（i2，i3）.........(ik-1,ik)都在图中。如果除了第一个顶点和最后一个顶点之外，其余的顶点均不相同，那么这条路径称为简单路径。如果构成回路的路径是简单路径，则称此回路为简单回路。不带回路的图称为无环图。
连通图：设图G是无向图，当且仅当G的每一对顶点之间都有一条路径，则称G是连通图。
子图：如果图H的顶点和边的集合是图G的子集，那么称图H是图G的子图。
生成树：如果图H是图G的子图，且他们的顶点集合相同，并且H是没有环路的无向连通图（即一棵树），则称H是G的一棵生成树。
在具有n个顶点的无向图中，边数为e，则有
在具有n个顶点的有向图中，边数为e，则有
包含所有边的图为完全图，边数相对较少的为稀疏图，反之称为稠密图。
顶点的度(degree)：在无向图中，一个顶点v的度是依附于顶点v的边的条数，记作TD(v)。在有向图中，以顶点v为始点的有向边的条数称为顶点v的出度，记作OD(v)；以顶点v为终点的有向边的条数称为顶点v的入度，记作ID(v)。有向图中顶点v的度等于该顶点的入度与出度之和：TD(v)＝ID(v)十OD(v)。
连通图与连通分量：在无向图中，若从顶点vi到顶点vj有路径，则称顶点vi与vj是连通的。如果无向图中任意两个顶点都是连通的，则称此无向图是连通图。非连通图的极大连通子图（包括所有连通的顶点和这些顶点依附的所有的边）叫做连通分量。任何联通图的联通分量只有一个，即本身。而分联通图有多个连通分量。
强连通图与强连通分量(strongly connected digraph)：在有向图中，若对于顶点vi和vj，存在一条从vi到vj和从vj到vi的路径，则称顶点vi和顶点vj是强连通。如果有向图中任意两个顶点都是强连通的，则称此有向图为强连通图。非强连通图的极大强连通子图叫做强连通分量。
生成树(spanning tree)：一个连通图的生成树是它的极小连通子图，它包含图中全部n个顶点和仅使这n个顶点连通的n-1条边。如果一个有向图只有一个入度为零的顶点，且其它顶点的入度均为1，则称这个有向图为有向树。一个有向图的生成森林由若干棵有向树组成，生成森林含有图中所有的顶点，且只有足以构成若干棵互不相交的有向树的弧。
/**
* 边类型
* @author Roy wang
*
*/
class Edge implements Comparable{
public int start;
public int end;
public int weight;
public Edge(int start,int end,int weight) {
this.start=start;
this.end=end;
this.weight=weight;
}
@Override
public int compareTo(Object o) {
// TODO Auto-generated method stub
return weight-((Edge)o).weight;
}
}
/**
* 所有图的基类型
* @author Roy wang
*
*/
abstract class Graph{
public int vertexNum; //顶点数
public int edgeNum; //边数
int Mark[]; //标记是否被访问过
Graph(int vertexNum){
this.vertexNum=vertexNum;
edgeNum=0;
Mark=new int[vertexNum];
for(int i=0;i<vertexNum;i++) {
Mark[i]=0;
}
}
abstract Edge FirstEdge(int oneVertex);
abstract Edge NextEdge(Edge oneEdge);
int VerticesNum() {return vertexNum;}
int EdgesNum() {return edgeNum;}
boolean isEdge(Edge oneEdge) {
if(oneEdge.weight>0&&oneEdge.weight<Double.POSITIVE_INFINITY&&oneEdge.end>=0)
return true;
else {
return false;
}
}
int startVertex(Edge oneEdge) {
return oneEdge.start;
}
int endVertex(Edge oneEdge) {
return oneEdge.end;
}
int weight(Edge oneEdge) {
return oneEdge.weight;
}
abstract void setEdge(int start,int end,int weight);
abstract void delEdge(int start,int end);
}4.2 图的存储及基本操作
图的存贮结构应根据具体问题的要求来设计。常用的存贮结构有邻接矩阵、邻接表、邻接多重表和十字链表
4.2.1 图的邻接矩阵表示
在图的邻接矩阵表示中，除了记录每一个顶点信息的顶点表外，还有一个表示各个顶点之间关系的矩阵，称之为邻接矩阵。若设图G＝(V，E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组Arcs[n][n]，它的定义为：
对于网络(或带权图)，邻接矩阵定义如下：
邻接矩阵是指用矩阵来表示图。它是采用矩阵来描述图中顶点之间的关系(及弧或边的权)。
假设图中顶点数为n，则邻接矩阵定义为：
无向图的邻接矩阵是堆成的。使用邻接矩阵很容易获得顶点的度
public class AdjGraph extends Graph{
int [][]matrix;
public AdjGraph(int verticesNum) {
super(verticesNum);
int i,j;
matrix=new int[vertexNum][];
for(i=0;i<vertexNum;i++) {
matrix[i]=new int[vertexNum];
}
for(i=0;i<vertexNum;i++) {
for(j=0;j<vertexNum;j++) {
matrix[i][j]=0;
}
}
}
@Override
Edge FirstEdge(int oneVertex) {
// TODO Auto-generated method stub
Edge temp=new Edge();
for(int i=0;i<vertexNum;i++) {
if(matrix[oneVertex][i]!=0) {
temp.start=oneVertex;
temp.end=i;
temp.weight=matrix[oneVertex][i];
break;
}
}
return temp;
}
@Override
Edge NextEdge(Edge oneEdge) {
// TODO Auto-generated method stub
Edge temp=new Edge();
int oneVertex=temp.start=oneEdge.start;
for(int i=oneEdge.end+1;i<vertexNum;i++) {
if(matrix[oneVertex][i]!=0) {
temp.start=oneVertex;
temp.end=i;
temp.weight=matrix[oneVertex][i];
break;
}
}
return temp;
}
@Override
void setEdge(int start, int end, int weight) {
// TODO Auto-generated method stub
if(matrix[start][end]==0) {
edgeNum++;
}
matrix[start][end]=weight;
}
@Override
void delEdge(int start, int end) {
// TODO Auto-generated method stub
if(matrix[start][end]!=0) {
edgeNum--;
}
matrix[start][end]=0;
}
}4.2.2邻接表
链表中的结点称为边结点。包含三个域：邻接点的编号，边的信息，指向下一条关联边的边结点
存储无向图，顶点vi的度就是第i条链表中的边结点的数目。占用n+2e个存储单元
对于有向图，可以方便的计算出度，但是计算入度必须遍历整个邻接表。存储空间n+e
由于邻接表不便于找到入度。使用逆邻接表存储（差不多，就是指出变为指入）
/**
* 临界表边界点的数据定义
* @author Roy wang
*
*/
class listData{
public int vertex;
public int weight;
}
/**
* 边节点的数据定义
* @author Roy wang
*
*/
class ListNode{
public listData element;
ListNode next;
public ListNode(int vertex,int weight,ListNode next) {
element.vertex=vertex;
element.weight=weight;
this.next=next;
}
public ListNode() {}
}
/**
* 每个边关联的边表
* @author Roy wang
*
*/
class EdgeList{
public ListNode head=new ListNode();
}
/**
* 图的邻接表表示
* @author Roy wang
*
*/
class ListGraph extends Graph{
EdgeList[] graList;
public ListGraph(int verticesNum) {
super(verticesNum);
graList=new EdgeList[verticesNum];
}
@Override
Edge FirstEdge(int oneVertex) {
// TODO Auto-generated method stub
Edge tepEdge=new Edge();
tepEdge.start=oneVertex;
ListNode temp=graList[oneVertex].head;
while(temp.next!=null) {
tepEdge.end=temp.next.element.vertex;
tepEdge.weight=temp.next.element.weight;
}
return tepEdge;
}
@Override
Edge NextEdge(Edge oneEdge) {
// TODO Auto-generated method stub
Edge tepEdge=new Edge();
tepEdge.start=oneEdge.start;
ListNode temp=graList[tepEdge.start].head;
while(temp.next!=null&&temp.next.element.vertex<=oneEdge.end)
temp=temp.next;
if(temp.next!=null) {
tepEdge.end=temp.next.element.vertex;
tepEdge.weight=temp.next.element.weight;
}
return tepEdge;
}
@Override
void setEdge(int start, int end, int weight) {
// TODO Auto-generated method stub
ListNode temp=graList[start].head;
while(temp.next!=null&&temp.next.element.vertex<end)
temp=temp.next;
if(temp.next==null) {
temp.next=new ListNode(end,weight,null);
edgeNum++;
return;
}
if(temp.next.element.vertex==end) {
if(temp.next.element.vertex==end) {
temp.next.element.weight=weight;
return;
}
}
if(temp.next.element.vertex>end) {
if(temp.next.element.vertex==end) {
ListNode node=new ListNode(end,weight,null);
node.next=temp.next.next;
temp.next=node;
return;
}
}
}
@Override
void delEdge(int start, int end) {
// TODO Auto-generated method stub
ListNode temp=graList[start].head;
while(temp.next!=null&&temp.next.element.vertex<end)
temp=temp.next;
if(temp.next!=null) {
if(temp.next.element.vertex==end) {
temp.next=temp.next.next;
}
}
}
}
4.2.3 十字链表和邻接多重表
十字链表：有向图
邻接多重表：无向图
4.3 图的遍历
4.3.1 深度优先（DFS）
时间复杂度依赖存储结构 邻近矩阵：n2 邻接表：e +n
深度优先遍历得到的遍历序列可能不唯一
在搜索过程中，由于顶点v访问与其相邻且未被访问的顶点u时经过的边(v,u)称为前向边。深度优先搜索过程中的所有前向边和顶点组成为子图G是原图的一个生成树，也称为深度优先搜索生成树
递归实现
public void DFS(int v) {
Mark[v]=1;
visit(v);
for(Edge e=FirstEdge(v);isEdge(e);e=NextEdge(e)) {
if(Mark[endVertex(e)]==0) {
DFS(Mark[endVertex(e)]);
}
}
}
public void DFSTraverse()
{
for(int i=0;i<VerticesNum();i++) {
Mark[i]=0;
}
for(int i=0;i<VerticesNum();i++) {
if(Mark[i]==0) {
DFS(i);
}
}
}非递归实现
public void DFSNoReverse() {
int i,v,u;
Stack<Integer> s=new Stack<>();
for(i=0;i<VerticesNum();i++) {
Mark[i]=0;
}
for(i=0;i<VerticesNum();i++) {
if(Mark[i]==0) {
s.push(i);
visit(i);
Mark[i]=1;
while(!s.isEmpty()) {
v=s.pop();
for(Edge e=FirstEdge(v);isEdge(e);e=NextEdge(e)) {
u=endVertex(e);
if(Mark[u]==0) {
s.push(u);
visit(u);
Mark[u]=1;
}
}
}
}
}
}4.3.2 广度优先 （BFS）
public void BFS() {
Queue<Integer> s=new ArrayDeque<>();
for(int i=0;i<VerticesNum();i++) {
Mark[i]=0;
}
for(int v=0;v<VerticesNum();v++) {
if(Mark[v]==0) {
s.add(v);
visit(v);
Mark[v]=1;
while(!s.isEmpty()) {
v=s.poll();
for(Edge e=FirstEdge(v);isEdge(e);e=NextEdge(e)) {
int u=endVertex(e);
if(Mark[u]==0) {
s.add(u);
visit(u);
Mark[u]=1;
}
}
}
}
}
}4.4 最小生成树
对于带权无向图，代价最小的生成树称为最小生成树。通常使用构造方法实现最小生成树
3.1 普里姆（Prim）算法
时间复杂度O(n*n).与边无关，适用边数比较稠密的图
/**
* 从s顶点出发得到最小生成树
* @param G
* @param s
* @return
*/
Edge[] Prim(Graph G,int s) {
int i,j;
Edge[] MST;
int []nearest; //表示生成树中点到i点的最小权值
int []neighbor; //生成树中与i点最近的点编号
int n=G.VerticesNum();
nearest=new int[n];
neighbor=new int[n];
MST=new Edge[n-1];
for(i=0;i<n;i++) {
neighbor[i]=s;
nearest[i]=(int)Double.POSITIVE_INFINITY;
}
for(Edge e=G.FirstEdge(s);G.isEdge(e);e=G.NextEdge(e)) {
nearest[e.end]=e.weight;
}
neighbor[s]=-1;
for(i=1;i<n;i++) {
int min=(int)Double.POSITIVE_INFINITY;
int v=-1;
for(j=0;j<n;j++) {
if(nearest[j]<min&&neighbor[j]!=-1) {
min=nearest[j];
v=j;
}
}
if(v>=0) {
Edge e=new Edge(neighbor[v],v,nearest[v]);
MST[i]=e;
neighbor[v]=-1;
}
for(Edge e=G.FirstEdge(v);G.isEdge(e);e=G.NextEdge(e)) {
int u=e.end;
if(neighbor[u]!=-1&&nearest[u]>e.weight) {
neighbor[u]=v;
nearest[u]=e.weight;
}
}
}
return MST;
}3.2 克鲁斯卡尔（Kruskal）算法
时间复杂O(eloge).主要取决于边数。适用构造稀疏图的最小生成树
使用最小生成树
class UFSets{
private int n; //等价类中元素个数
private int[]root; //表示元素i所在等价类的代表元素符号
private int[]next; //表示在等价类i中，i的后面的元素编号
private int[]length; //length[i]表示i所代表的等价类的元素个数
public UFSets(int size) {
n=size;
for(int i=0;i<n;i++) { //每个元素自成一个等价类
root[i]=next[i]=i;
length[i]=1;
}
}
int Find(int v) {return root[v];}
void Union(int v,int u) {
if(root[u]==root[v]) {
return;
}else if(length[root[v]]<length[root[u]]) {
int rt=root[v];
length[root[u]]+=length[rt];
root[rt]=root[u];
for(int j=next[rt];j!=rt;j=next[j]) {
root[j]=root[u];
}
}else {
Union(u,v);
}
}
Edge Kruskal(Graph G) {
int n=G.VerticesNum();
UFSets set=new UFSets(n);
Edge[] MST=new Edge[n-1];
List<Edge> MinHeap=new ArrayList<>(G.EdgesNum());
Edge edge=new Edge();
for(int i=0;i<G.VerticesNum();i++) {
for(edge=G.FirstEdge(i);G.isEdge(edge);edge=G.NextEdge(edge)) {
if(G.startVertex(edge)<G.endVertex(edge))
MinHeap.add(edge);
}
}
int edgeNum=0;
while(edgeNum<n-1) {
if(!MinHeap.isEmpty()) {
Edge min=MinHeap.get(0);
for(Edge e:MinHeap) {
if(e.weight<min.weight) {
min=e;
}
}
MinHeap.remove(min);
if(set.Find(edge.start)!=set.Find(edge.end )) {
set.Union(edge.start, edge.end);
MST[edgeNum++]=edge;
}
}else {
return null;
}
}
return MST;
}
}四、最短路径 一般针对带权有向图
4.1 Dijkstra算法---->单源最短路径
D[i]表示当前所找到的从s到每个顶点的最短特殊长度
时间复杂度O(n*n).使用最小堆O(n*logn)
Path数组表示到达各个顶点的前驱结点
void Dijstra(Graph G,int s,int D[],int Path[]) {
int n=G.EdgesNum();
int i,j;
for(int i=0;i<n;i++) {
G.Mark[i]=0;
D[i]=(int)Double.POSITIVE_INFINITY;
Path[i]=-1;
}
G.Mark[s]=1;
D[s]=0;
Path[s]=s;
for(Edge e=G.FirstEdge(s);G.isEdge(e);e=G.NextEdge(e)) {
int endVertex=e.end;
if(G.Mark[endVertex]==0&&D[endVertex]>(D[s]+e.weight)) {
D[endVertex]=D[s]+e.weight;
Path[endVertex]=s;
}
}
for(i=0;i<n-1;i++) {
int min=D[0];
int k=0;
for(j=0;j<n;j++) {
if(G.Mark[j]==0&&min>D[j]) {
min=D[j];
k=j;
}
}
G.Mark[k]=1;
for(Edge e=G.FirstEdge(k);G.isEdge(e);e=G.NextEdge(e)) {
int endVertex=e.end;
if(G.Mark[endVertex]==0&&D[endVertex]>(D[k]+e.weight)) {
D[endVertex]=D[k]+e.weight;
Path[endVertex]=k;
}
}
}
}4.2 Floyd算法--->顶点对之间的最短路径
动态规划
时间复杂度O(n*n*n)
adj（k)矩阵。元素adjk[i,j]描述从Vi到Vj两点之间且中间顶点编号不大于k的最短路径长度
Pathk[i][j]表示从Vi到Vj两点之间且中间顶点编号不大于k的最短路径中vj的前驱结点编号
void Floyd(Graph G,int [][]Adj,int[][]Path) {
int i,j,v;
int n=G.VerticesNum();
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(i==j) {
Path[i][j]=i;
Adj[i][j]=0;
}else {
Adj[i][j]=(int)Double.POSITIVE_INFINITY;
Path[i][j]=i;
}
}
for(v=0;v<n;v++) {
for(Edge e=G.FirstEdge(v);G.isEdge(e);e=G.NextEdge(e)) {
Adj[e.start][e.end]=e.weight;
}
}
for(v=0;v<n;v++) {
for(i=0;i<n;i++) {
for(j=0;j<n;j++) {
if(Adj[i][j]>Adj[i][v]+Adj[v][j]) {
Adj[i][j]=Adj[i][v]+Adj[v][j];
Path[i][j]=v;
}
}
}
}
}
}五、拓扑排序
拓扑排序是对有向图中顶点进行的一种排序，根据排序结果可以判断有向图中是否存在环。
通过深度优先遍历可以确定图中有没有环
循环找到入度为0的结点。加入拓扑排序。更新其它结点的入度信息
如果vi是vj的前驱结点，在序列中vi必在vj之前，这样的排序为拓扑排序。拓扑排序可能不唯一。
六、关键路径
五、查找
为了提高在大规模数据中查找的效率，往往对数据的存储进行特殊处理。最常见的方法是建立索引和预排序
查找分为静态查找和动态查找。静态查找是在查找中不更改数据集中的元素。而动态查找指在查找不成功的时候要将查找的元素添加到数据集中，主要包括二叉搜索树、平衡二叉搜索树、B-树、B+树。
根据关键字的比较次数度量查找的效率
查找成功时的平均查找长度：如果要找的记录datai的概率为Pi，并且查找到datai需要经过Ci次比较
5.1 静态查找
5.1.1顺序查找
平均查找长度：
如果查找的关键字不在，要比较n+1次才能确定失败
插入的时间复杂度O(1),平均查找长度O(n)
public static int DirectResearch(List<Integer> list,int val) {
for(int i=0;i<list.size();i++) {
if(val==list.get(i)) {
return i;
}
}
return -1;
}5.1.2 折半查找
折半查找法的查找过程可以用二叉树描述，树中每个结点表示算法中参与比较的数据元素编号，这个二叉树被称为判定树
ASL=
log2(n+1)-1
折半查找只适用于顺序存储的有序表，而且向有序表中新增或删除数据操作比较复杂。
public static int BinaryResearch(List<Integer> list,int val) {
int left=0;
int right=list.size()-1;
int mid;
while(left<=right) {
mid=(left+right)/2;
if(list.get(mid)==val) {
return mid;
}
if(list.get(mid)<val) {
left=mid+1;
}
if(list.get(mid)>val) {
right=mid-1;
}
}
return -1;
}5.1.3 分块查找
分块查找分为两个阶段。第一阶段，根据索引表确定查找的记录所在的数据块。由于索引表按照关键字有序，因此可以用折半查找法。第二阶段，在已确定的数据块中用顺序查找法进行查找。
假如有n个记录，分成m块，每块m个记录
ASL=
package com;
import java.util.*;
/**
* @describe 分块查找
* @author Roy wang
*
*/
public class BlockSearch {
private int[] index; //建立索引
private ArrayList[] list;
/**
* 初始化索引
* @param args
*/
public BlockSearch(int[] index) {
if(null!=index&&index.length!=0) {
this.index=index;
this.list=new ArrayList[index.length];
for(int i=0;i<list.length;i++) {
list[i]=new ArrayList();
}
}
}
/**
* 插入
* @param value
*/
public void insert(int value) {
int i=binarySearch(value);
list[i].add(value);
}
/**
* 二分法查找
* @param value
* @return
*/
private int binarySearch(int value) {
int start=0,end=index.length,mid=-1;
while(start<=end) {
mid=(start+end)/2;
if(index[mid]>value) {
end=mid-1;
}else {
start=mid+1;
}
}
return start;
}
public boolean search(int data) {
int i=binarySearch(data);
for(int j=0;j<list[i].size();j++) {
if(data==(int)list[i].get(j)) {
return true;
}
}
return false;
}
public void printAll() {
for(int i=0;i<list.length;i++) {
System.out.println("ArrayList["+i+"]:");
for(int j=0;j<list[i].size();j++) {
System.out.println(list[i].get(j)+" ");
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int []index={10,20,30};
BlockSearch blocksearch=new BlockSearch(index);
blocksearch.insert(1);
blocksearch.insert(11);
blocksearch.insert(21);
blocksearch.insert(2);
blocksearch.insert(12);
blocksearch.insert(22);
blocksearch.insert(5);
blocksearch.insert(15);
blocksearch.insert(25);
blocksearch.printAll();
System.out.println("查找值15 结果"+blocksearch.search(15));
System.out.println("查找值29 结果"+blocksearch.search(29));
}
}
5.2 动态查找
在大规模数据查找中，大量信息存储在外存磁盘中，选择正确的数据结构可以显著降低查找磁盘中数据的时间。B-树和B+树就是两种常见的高效外存数据结构。
b树和b+树的区别。插入、删除什么的大同小异
5.3 散列
思想：在记录的关键字和存储位置之间建立一个确定的函数关系，使得每个关键字与结构中一个唯一的存储位置相对应。在查找时，首先对记录的关键字进行函数运算，把函数值当作该记录的存储位置。按照散列方法构造出来的表或结构称为散列表
散列方法的核心：由散列函数确定关键字与散列地址之间的对应关系，通过这种对应关系进行存储和查找。
由散列函数得到的散列地址相同的现象称为冲突，发生冲突的两个关键字称为散列函数的同义词。
在散列方法中，需要考虑两个问题：
1）构造使关键字均匀分布的散列函数，避免冲突
2）设计冲突解决方法，处理冲突。
影响散列函数的效率因素：散列函数是否均匀、处理冲突的方法以及装填因子。
5.3.1散列函数
- 散列函数定义域必须包括需要存储的所有关键字
- 散列函数计算出来的地址应能均匀分布在整个地址空间中
- 散列函数应是简单的，能在较短的时间内计算出结果
1）直接定址法 Hash(key)=a*key+b;
2）数字分析法 Hash(key)=key%p
3）除留余数法
4）平方取中法
5）基数地址法
6）折叠法
5.3.2冲突解决方法
散列地址不同的结点争夺同一个后继散列地址的现象称为一次聚集或堆积。
二次探查法可能难以包括散列表的所有存储位置。避免了一次聚集。但是仍然避免不了冲突的聚集。因为对散列到相同地址的关键字，采用的是同样的猴急探查序列。这成为冲突的二次聚集。
1）开放定址法，也称闭散列法（线性探查法、二次探查法、伪随机探查法、双散列法）
- 线性探查法（Hash(key)+1)%m;（Hash(key)+2)%m;（Hash(key)+3)%m;（Hash(key)+4)%m...（Hash(key)+m-1)%m;
- 二次探查法 d=Hash(key) d,(d+1^2)%m,(d-1^2)%m,(d+2^2)%m,(d-2^2)%m,(d+3^2)%m,(d-3^2)%m......
- 伪随机探查法
- 双散列法.避免二次冲突 Hi=(HashKey(key)+i*ReHash(key)%m, i=0,1,2,3,...m-1
2）链接法，也称开散列法、拉链法.散列表中的每个地址都是一个链表的表头，并关联着一个链表结构。不会出现冲突的聚集现象。
如果将整个散列表存储在磁盘中，拉链法就不合适。应为一个同义词链表中的元素可能存储在不同的磁盘中
3）桶定址法。桶定址法的基本思想是把记录分为若干个存储桶。每个存储桶包括一个或多个存储位置。如果桶满了，可以用开放定址法处理
5.3.3 散列查找例子
使用除留取余法散列函数。使用双散列探测法解决冲突
package com;
import java.util.*;
/**
* 没有使用泛型，使用int型变量作为关键字类型
* @author Roy wang
*
*/
public class hashtable {
/**
* 冲突解决
* @return
* @param k,i
*/
private int currentsize;
private int maxsize;
public Integer[] list;
public int probe(int k,int i) {
return k%maxsize+i;
}
int hash(int k) {
return k%maxsize;
}
public hashtable(int size) {
currentsize=0;
maxsize=size;
list=new Integer[maxsize];
}
public boolean hashInsert(int T) {
int home=0;
int i=0;
int pos=home=hash(T);
while(list[i]!=null) {
if(list[i]==T) {
return false;
}
i++;
pos=(home+probe(T,i))%maxsize;
if(pos==home) {
return false;
}
}
list[i]=T;
return true;
}
public boolean hashSearch(int item) {
int home=hash(item);
int i=0;
int pos=home;
while(list[i]!=null) {
if(list[i]==item) {
return true;
}
i++;
pos=(home+probe(item,i))%maxsize;
}
return false;
}
public boolean hashDelete(int item) {
int home=hash(item);
int i=0;
int pos=home;
while(list[i]!=null) {
if(list[i]==item) {
list[i]=null;
return true;
}
i++;
pos=(home+probe(item,i))%maxsize;
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
hashtable Hash=new hashtable(10);
Hash.hashInsert(5);
Hash.hashInsert(8);
Hash.hashInsert(13);
System.out.println(Hash.hashSearch(13));
}
}
六、排序
6.1 排序的基本概念
- 用来排序依据的属性称为关键字域，简称关键字。排序就是根据关键字的大小将无序的多条记录，调整为有序的序列。
- 当关键字可以重复出现时，建设Ki=Kj,且在排序前的序列R中，Ri领先与Rj,若在排序后的序列中仍领先，则称排序算法是稳定的。
- 可以将排序算法分为内部和外部排序。内部排序指的是待排序记录存放在计算机随机存储器中进行的排序过程。外部排序指的是待排序记录的数量很大，一次一次无法容纳全部记录，在排序过程中需要对外存进行访问的拍戏。
- 一比较次数和移动次数来度量排序算法的时间复杂度。
6.2 插入排序
6.2.1 直接插入排序
由n-1趟排序组成。第p趟排序保证从第0个位置到第p个位置上的元素为有序状态。第p+1趟排序是将第p+2个元素插入到前面p+1个元素的有序表中.
public static void InsertionSort(int[]a) {
for(int i=1;i<a.length;i++) {
int k=i;
if(a[i]<a[i-1]) {
int temp=a[i];
for(k=i-1;k>=0&&temp<=a[k];k--) {
a[k+1]=a[k];
}
a[k+1]=temp;
}
}
}6.2.2 折半插入排序
public void BinaryInsertionSort(int Data[],int n)
{
int left,mid,right,p;
for(int p=1;p<n;p++){
int temp=Data[p];
left=0;
right=p-1;
while(left<=right){
mid=(left+right)/2;
if(Data[mid]>temp){
right=mid-1;
}else {
left=mid+1
}
}
for(int i=p-1;i>=left;i++){
Data[i+1]=Data[i];
}
Data[left]=temp;
}
}6.2.3 希尔排序
思想：先将待排序数据序列划分成若干子序列分别进行直接插入排序；待整个序列中的数据基本有序后，再对全部数据进行一次直接插入排序。对于子序列的排序可以采用任意的排序算法。
public static void ShellSort(int[]a) {
int increasement=a.length;
do {
int k;
increasement=increasement/3+1;
for(int i=0;i<increasement;i++) {
for(int j=i+increasement;j<a.length;j+=increasement) {
int temp=a[j];
if(a[j]<a[j-increasement]) {
for(k=j-increasement;k>=0&&a[k]>temp;k-=increasement) {
a[k+increasement]=a[k];
}
a[k+increasement]=temp;
}
}
}
}while(increasement>1);
}6.3 交换排序
6.3.1 冒泡排序
冒泡排序通过不断比较相邻元素的大小，然后决定是否对这两个元素进行交换操作，从而达到排序的目的。
public static void Bubble(int[]a) {
for(int i=0;i<a.length;i++) {
for(int j=i;j<a.length-1-i;j++) {
if(a[j]>a[j+1]) {
int temp;
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
}6.3.2 快速排序
基于分治法思想提出的一种排序算法。由三步组成：分割、分治、合并。
public static void QuickSort(int[] a,int start,int end) {
int i=start;
int j=end;
if(start>=end) {
return;
}
int temp=a[start];
while(i<j) {
while(i<j&&a[j]>=temp) {
j--;
}
if(i<j) {
a[i]=a[j];
i++;
}
while(i<j&&a[i]<temp) {
i++;
}
if(i<j) {
a[j]=a[i];
j--;
}
}
a[i]=temp;
QuickSort(a,start,i-1);
QuickSort(a,i+1,end);
}
public static void QuickSort2(int[]a,int start,int end) {
int left=start+1;
int right=end;
if(right<left) {
return;
}
while(left<=right) {
while(left<=right&&a[start]>=a[left]) {
left++;
}
while(left<=right&&a[start]<a[right]) {
right--;
}
if(left<right) {
int temp=a[right];
a[right]=a[left];
a[left]=temp;
}
}
int temp=a[right];
a[right]=a[start];
a[start]=temp;
QuickSort2(a,start,right-1);
QuickSort2(a,right+1,end);
}6.4 选择排序
选择排序要经过N-1趟选择过程
6.4.1 简单选择排序
public static void Select(int[]a) {
int flag;
for(int i=0;i<a.length-1;i++) {
int temp=i;
for(int j=i;j<a.length;j++ ) {
if(a[temp]>=a[j]) {
temp=j;
}
}
flag=a[i];
a[i]=a[temp];
a[temp]=flag;
}
}6.4.2 堆排序
其实就是最小堆删除顶部。easy to control.
6.5 归并排序
若一个序列中只有一个元素，归并操作不执行任何操作。否则，归并排序算法按照递归步骤进行：
- 把序列划分为长度基本相等的子序列
- 对每个子序列进行归并排序
- 把排好序的子序列合并为最后的结果
由于需要申请额外的空间，归并排序的效果往往没有快速排序好
public static void Merge(int[]a,int start,int mid,int end) {
List<Integer> set1=new ArrayList<>();
List<Integer> set2=new ArrayList<>();
for(int i=start;i<=mid;i++) {
set1.add(a[i]);
}
for(int j=mid+1;j<=end;j++) {
set2.add(a[j]);
}
int i=0,j=0;
int k;
for(k=start;k<=end;k++) {
if(i==mid-start+1||j==end-mid) {
break;
}
if(set1.get(i)<set2.get(j)) {
a[k]=set1.get(i);
i++;
}else {
a[k]=set2.get(j);
j++;
}
}
if(i<=mid-start) {
for(int g=i;g<=mid-start+1;g++) {
a[k++]=set1.get(g);
}
}
if(j<=end-mid-1) {
for(int g=i;g<=end-mid-1;g++) {
a[k++]=set2.get(g);
}
}
}
public static void MergeSort(int[]a,int start,int end) {
if(start<end) {
int mid=(start+end)/2;
MergeSort(a,start,mid);
MergeSort(a,mid+1,end);
Merge(a,start,mid,end);
}
}6.6 比较排序算法的时间复杂度下界
基于比较的排序算法的时间复杂度的下界为nlogn.具有nlogn时间复杂度的算法在渐进意义来说是最优的算法
6.7 基数排序
借助多关键字排序的思想对单逻辑关键字进行排序的方法
- 高位优先法（MSDF）
按照优先级最高的关键字进行排序，然后按照次优先级关键字进行排序
- 低位优先法(LSDF)
按照优先级最低的关键字进行排序，依次重复，直至按照最高优先级的关键字排序，序列就会变成有序序列。
基数排序方法就是将带排序的数据元素的单逻辑关键字拆分成若干个关键字。下面算法是低位优先
package com;
import java.lang.reflect.Array;
import java.util.Arrays;
public class good {
public static final int RADIX=10;
public static TubNode[] Distribute(int Data[],int n,int ith){
TubNode[] tube=new TubNode[RADIX];
for(int i=0;i<RADIX;i++) {
tube[i]=new TubNode();
}
for(int i=0;i<n;i++) {
LinkNode t=new LinkNode();
int v=Data[i];
int j=ith-1;
while(j!=0) {
j--;
v=v/RADIX;
}
v=v%RADIX;
t.setData(Data[i]);
t.setNext(null);
if(tube[v].getFront()!=null) {
tube[v].getRear().setNext(t);
tube[v].setRear(t);
}else {
tube[v].setFront(t);
tube[v].setRear(t);
}
}
return tube;
}
public static void Collect(int Data[],TubNode[] tube) {
LinkNode t,p;
t=new LinkNode();
int index=0;
for(int i=0;i<RADIX;i++) {
t=tube[i].getFront();
while(t!=null) {
Data[index++]=t.getData();
t=t.getNext();
}
}
}
public static void RadixSort(int Data[],int n,int keys) {
TubNode[] tube=new TubNode[10];
for(int i=0;i<keys;i++) {
tube=Distribute(Data, n, i+1);
Collect(Data,tube);
}
}
public static void main(String[]args) {
int[] a=new int[] {304,680,796,981};
RadixSort(a,a.length,3);
System.out.println(Arrays.toString(a));
}
}
class TubNode{
private LinkNode rear=null;
private LinkNode front=null;
public TubNode (LinkNode rear,LinkNode front) {
this.rear=rear;
this.front=front;
}
public TubNode() {}
public LinkNode getRear() {
return rear;
}
public void setRear(LinkNode rear) {
this.rear = rear;
}
public LinkNode getFront() {
return front;
}
public void setFront(LinkNode front) {
this.front = front;
}
}
class LinkNode{
private int data;
private LinkNode next=null;
public LinkNode (int sdata,LinkNode next){
this.data=sdata;
this.next=next;
}
public LinkNode() {}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public LinkNode getNext() {
return next;
}
public void setNext(LinkNode next) {
this.next = next;
}
}