数据结构知识点整理
程序员文章站
2022-03-25 21:26:38
...
最近重新看了数据结构一书，从大学课程到考研复习，本以为看了很多遍，一些知识点看到就会想起来，实际情况却是即使是自己做的笔记，都一点映像都没了。life is a constant process of learning,fighting!
- KMP算法。
public class KMP {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String a = "abaabaaab";
String b = "aaab";
System.out.println(index_KMP(a.toCharArray(),b.toCharArray(),0));
System.out.println(Arrays.toString(next("abaabcac".toCharArray())));
System.out.println(Arrays.toString(next2("aaaab".toCharArray())));
}
private static int index_KMP (char source[] ,char target[],int pos) {
int next[] = next(target);
int i =pos;int j = 0;
while (i < source.length && j < target.length) {
if (j == -1 || source[i] == target[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j>=target.length) {
return i-target.length;
} else {
return -1;
}
}
//
private static int[] next (char[] target) {
int [] next = new int[target.length];
int i = 0,j = -1;
next[0] = -1;
while (i < target.length -1) {
if (j == -1 || target[i] == target[j]) {
++i;++j;
next [i] = j;
} else {
j = next[j];
}
}
return next;
}
//改进的next数组
private static int[] next2 (char[] target) {
int [] next = new int[target.length];
int i = 0,j = -1;
next[0] = -1;
while (i < target.length -1) {
if (j == -1 || target[i] == target[j]) {
++i;++j;
if (target[i] != target[j]) {
next [i] = j;
} else {
next[i] = next[j];
}
} else {
j = next[j];
}
}
return next;
}
}- KMP算法的核心是计算出字串的next数组。计算next数组的过程可以看成主串子串一样的模式匹配。next[i]的含义为：当模式中的第i个字符与主串的相对应字符失配是，在模式中重新与该字符进行比较的字符的位置，主串的指针不会回溯。时间复杂度O(M+N)；
public class BinaryTree {
public Node init() {// 注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
Node J = new Node(8, null, null);
Node H = new Node(4, null, null);
Node G = new Node(2, null, null);
Node F = new Node(7, null, J);
Node E = new Node(5, H, null);
Node D = new Node(1, null, G);
Node C = new Node(9, F, null);
Node B = new Node(3, D, E);
Node A = new Node(6, B, C);
return A; // 返回根节点
}
public void printNode(Node node) {
System.out.print(node.getData());
}
// 先序遍历
public void preOrderTraversal (Node root) {
Stack <Node> stack = new Stack<Node> ();
Node node = root;
while (node != null || stack.size()>0) {
if (node != null) {
printNode (node);
stack.push(node);
node = node.getLeftNode();
} else {
node = stack.pop();
node = node.getRightNode();
}
}
}
//中序遍历
public void inOrderTraversal (Node root) {
Stack <Node> stack = new Stack<Node> ();
Node node = root;
while (node != null || stack.size()>0) {
if (node != null) {
stack.push(node);
node = node.getLeftNode();
} else {
node = stack.pop();
printNode (node);
node = node.getRightNode();
}
}
}
//后序遍历
public void postOrderTraversal(Node root) {
Stack<Node> stack = new Stack<Node>();
Stack<Node> out = new Stack<Node>();
Node node = root;
while (node != null || stack.size() > 0) {
if (node != null) {
stack.push(node);
out.push(node);
node = node.getRightNode();
} else {
node = stack.pop();
node = node.getLeftNode();
}
}
while (out.size() > 0) {
printNode(out.pop());
}
}
}
class Node {
private int data;
private Node leftNode;
private Node rightNode;
public Node(int data, Node leftNode, Node rightNode) {
this.data = data;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}3.树的存储：双亲表示法、孩子表示法、带双亲的孩子表示法、孩子兄弟表示法（左孩子右兄弟）。先根后根遍历树，先序中序遍历森林。最优二叉树赫夫曼树，赫夫曼编码。
4.图的各个定义。图的存储：邻接矩阵、邻接表（头节点、表节点（邻接点域、链域、数据域）、十字链表）、邻接多重表。图的遍历算法：BFS、DFS，时间复杂度与存储结构有关，邻接矩阵O(N*N)，邻接表O(N+E)。最小生成树算法:
public class Prim {
public static void main(String[] args) throws Exception {
int MAX = Integer.MAX_VALUE;
int[][] map = new int[][]{
{0,10,MAX,MAX,MAX,11,MAX,MAX,MAX},
{10,0,18,MAX,MAX,MAX,16,MAX,12},
{MAX,MAX,0,22,MAX,MAX,MAX,MAX,8},
{MAX,MAX,22,0,20,MAX,MAX,16,21},
{MAX,MAX,MAX,20,0,26,MAX,7,MAX},
{11,MAX,MAX,MAX,26,0,17,MAX,MAX},
{MAX,16,MAX,MAX,MAX,17,0,19,MAX},
{MAX,MAX,MAX,16,7,MAX,19,0,MAX},
{MAX,12,8,21,MAX,MAX,MAX,MAX,0}
};
int sum = prim(map);
System.out.println(sum);
}
public static int prim(int[][] arr){
//统计最小的权
int sum = 0;
//当前最小生成树所能到达的顶点的最小权数组
int[] costs = new int[arr.length];
//当前各个顶点对应的起点
int[] startPoint = new int[arr.length];
//初始化
for(int i =1;i<arr.length;i++){
//所有点的起点赋值为0
startPoint[i] = 0;
//以0为起点到达各个顶点的权值
costs[i] = arr[0][i];
}
//挑选剩余的8个顶点
for(int i = 1;i<arr.length;i++){
//记录当前costs里面的最小权值是多少
int min = Integer.MAX_VALUE;
//记录当前costs里面的最小权值对应的数组下标,即顶点
//(数组[顶点]=该顶点对应的起点)
int minIndex = 0;
//遍历costs
for(int j=1;j<arr.length;j++){
int temp = costs[j];
//costs[j]==0代表节点j已加入MST
if(temp!=0&&temp < min){
min = temp;
minIndex = j;
}
}
sum+=min;
//将已加入MST的对应的权值赋值为0
costs[minIndex] = 0;
System.out.println(startPoint[minIndex] + "到:" +minIndex + "的边长度是:" +min);
//选定了新的顶点到MST后，树到达各顶点的最小开销和起点将更新
//更新costs和startPoint
for(int k=0;k<arr.length;k++){
//用minIndex顶点到各个顶点的权值比较costs数组的值，若较小则替换，并更新起点为minIndex
int newCost = arr[minIndex][k];
if(newCost!=0&&newCost<costs[k]){
costs[k] = newCost;
//更新K的起点为minIndex
startPoint[k] = minIndex;
}
}
}
return sum;
}
}public class Kruskal {
/**
* Description:
*
* @param args
* 1.0 YESUN Jul 18, 2013 8:47:10 AM Create. ChangeLog:
*/
public static void main(String[] args) {
int[][] map = new int[][]{
{0,10,MAX,MAX,MAX,11,MAX,MAX,MAX},
{10,0,18,MAX,MAX,MAX,16,MAX,12},
{MAX,MAX,0,22,MAX,MAX,MAX,MAX,8},
{MAX,MAX,22,0,20,MAX,MAX,16,21},
{MAX,MAX,MAX,20,0,26,MAX,7,MAX},
{11,MAX,MAX,MAX,26,0,17,MAX,MAX},
{MAX,16,MAX,MAX,MAX,17,0,19,MAX},
{MAX,MAX,MAX,16,7,MAX,19,0,MAX},
{MAX,12,8,21,MAX,MAX,MAX,MAX,0}
};
kruskal(map);
}
static int MAX = Integer.MAX_VALUE;
/**
* Description: by yesun
* @param arcs
* 1.0 YESUN Jul 18, 2013 1:42:42 PM Create.
* ChangeLog:
*/
public static void kruskal(int[][] arcs) {
//顶点个数
int num = arcs.length;
//存放对应顶点所在连通图标识
int[] group = new int[num];
int sum = 0, n1 = 0, n2 = 0;
boolean finished = false;
int groupNum = 1;
while(!finished) {
int min = Integer.MAX_VALUE;
//找出所有边中最小值
for(int i = 0; i < num; i++) {
for(int j = i+1; j < num; j++) {
if(arcs[i][j] > 0 && arcs[i][j] < min){
//如果group相同，则表示处理过，不相同或都为0都表示没处理过
if (group[i] != group[j] || (group[i] == 0 && group[j] == 0)) {
min = arcs[i][j];
n1 = i;
n2 = j;
}
}
}
}
if(min == Integer.MAX_VALUE){
continue;
}
System.out.println(n1 + " ---> " + n2 + " " + min);
sum += min;
//找到了最小值，设置连通标记
if(group[n1] == 0 && group[n2] == 0){
group[n1] = groupNum;
group[n2] = groupNum;
groupNum++;
}
else if(group[n1] > 0 && group[n2] > 0) {
int tmp = group[n2];
for(int m = 0; m < group.length; m++){
if(group[m] == tmp){
group[m] = group[n1];
}
}
}
else{
if(group[n1] == 0){
group[n1] = group[n2];
}
else{
group[n2] = group[n1];
}
}
for(int i = 0; i < group.length; i++) {
if(group[i] != group[0]){
finished = false;
break;
}
else{
finished = true;
}
}
if(finished) {
break;
}
}
System.out.println(" sum:"+sum);
}
}public class FindArcticul {
private static int count = 1;
private void find (Vertex root) {
List<Vertex> childs = root.getChildren();
root.setVisited(true);
root.setNum(count++);
root.setLow(count);
for (Vertex v : childs) {
if (!v.isVisited()) {
v.setParent(root);
find(v);
if (v.getLow()>=root.getNum() && root.getNum()!=1) {
}
root.setLow(Math.min(root.getNum(), v.getLow()));
} else {
//!node.parent.equals(n)通过另一条回边访问到的node，visited[k]
if(root.getParent()!=null&&!root.getParent().equals(v))
root.setLow(Math.min(root.getLow(),v.getNum()));
}
}
}
}
class Vertex {
Vertex(String name)
{
this.name=name;
children=new ArrayList<Vertex>();
}
public boolean equals(Vertex node)
{
if(this.name==node.name) return true;
return false;
}
private boolean visited;
/**
* @return the visited
*/
public boolean isVisited() {
return visited;
}
/**
* @param visited the visited to set
*/
public void setVisited(boolean visited) {
this.visited = visited;
}
/**
* @return the num
*/
public int getNum() {
return num;
}
/**
* @param num the num to set
*/
public void setNum(int num) {
this.num = num;
}
/**
* @return the low
*/
public int getLow() {
return low;
}
/**
* @param low the low to set
*/
public void setLow(int low) {
this.low = low;
}
/**
* @return the parent
*/
public Vertex getParent() {
return parent;
}
/**
* @param parent the parent to set
*/
public void setParent(Vertex parent) {
this.parent = parent;
}
/**
* @return the children
*/
public List<Vertex> getChildren() {
return children;
}
/**
* @param children the children to set
*/
public void setChildren(List<Vertex> children) {
this.children = children;
}
private int num;
private int low;
private Vertex parent;
private List<Vertex> children;
private String name;
}DAG有向无环图、AOV、AOE网，拓扑排序、关键路径算法：点击打开链接。
单源最短路径Dijkstra算法、所有顶点最短路径floyd算法：
public class Dijsktra {
/**
* @param args
*/
public static void main(String[] args) {
Integer MAX = 10000;
int[][] weight = {
{MAX,MAX,10,MAX,30,100},
{MAX,MAX,5,MAX,MAX,MAX},
{MAX,MAX,10,50,MAX,MAX},
{MAX,MAX,10,MAX,MAX,10},
{MAX,MAX,10,20,MAX,60},
{MAX,MAX,10,MAX,MAX,MAX}
};
dijsktra (weight,0);
}
public static void dijsktra (int[][] weight,int start) {
//shortpath[]记录最短距离的长度;
int length = weight.length;
int[] shortpath = new int[length];
//visited[]记录是否已经求出最短路径
boolean visited[] = new boolean[length];
//path[] 记录路径经过的顶点
String[] path = new String[length];
for (int i=0;i<length;i++) {//初始化
shortpath[i] = weight[start][i];
visited[i] =false;
path[i] = start + "->"+i;
}
visited[start] = true;//起始顶点
shortpath[start] = start;
/*遍历shortpath找出最短的且visited[k]=false，
* 并记录下标K。
* 满足shortpath[j]>shortpath[k]+weigth[k][j]且visited[j] =false条件的,
* 修改shortpath[j] = shortpath[k]+weigth[k][j]
* */
for (int i=1;i<length;i++) {//不需要求起始顶点
int k = 0;
int min = Integer.MAX_VALUE;
for (int j=0;j<length;j++) {
if (!visited[j]&& min > shortpath[j]) {
k = j;
min = shortpath[j];
}
}
//找到顶点K
visited[k] = true;
//更新shortpath[]
for (int j=0;j<length;j++) {
if (!visited[j] && shortpath[j]>shortpath[k]+weight[k][j]) {
shortpath[j] =shortpath[k]+weight[k][j];
path[j] = path[k] +"->" + j;
}
}
}
//打印路径及长度
for (int i=0;i<length;i++) {
System.out.println(path[i] +":" +shortpath[i]);
}
}
}
public class Floyd {
public static void main(String[] args) {
Integer MAX = 10000;
int[][] weight = {
{0,4,11},
{6,0,2},
{3,MAX,0}
};
floryd (weight);
}
public static void floryd (int[][] weight) {
int length = weight.length;
//二位数组记录路径
String[][] path = new String[length][length];
for (int i=0;i<length;i++) {
for (int j=0;j<length;j++) {
path[i][j] = i + "->" + j;
}
}
//从顶点0开始加入
for (int k=0;k<length;k++) {
for (int i=0;i<length;i++) {
for (int j=0;j<length;j++) {
if (weight[i][k] +weight[k][j] < weight[i][j]) {
weight[i][j] = weight[i][k] +weight[k][j];
path[i][j] = (path[i][k] +"->"+path[k][j]).replaceFirst("->"+k, "").trim();
}
}
}
}
System.out.println(Arrays.toString(weight[0]));
System.out.println(Arrays.toString(weight[1]));
System.out.println(Arrays.toString(weight[2]));
System.out.println(Arrays.toString(path[0]));
System.out.println(Arrays.toString(path[1]));
System.out.println(Arrays.toString(path[2]));
}
}5.查找排序：顺序查找、二分查找（判定树）、索引查找、二叉排序树、AVL树（插入旋转处理的4种情况）、红黑树、B树B+树（插入的2中情况超过m-1个关键字要分裂，删除的3种情况（只考虑子节点的输出，非子节点可以和子节点的关键字换位置后删除））
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对于B树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
哈希表：关键字和地址建立关系。哈希函数构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。处理冲突的方法：开放定址法线性、二次、伪随机，在哈希、链地址法、公共溢出区。
排序算法：
public class Sort {
/**
* @param args
*/
public static void main(String[] args) {
int a[] = { 51, 46, 20, 18, 65, 97, 82, 30, 77, 50 };
// insertSort (a);
// int[] k = {5,3,1};
// shellSort (a,k);
// bubbleSort(a);
// quickSort(a,0,a.length-1);
heapSort(a, 0, a.length-1);
System.out.println(Arrays.toString(a));
}
//插入排序
public static void insertSort (int[] target) {
int length = target.length;
for (int i=1;i<length;i++) {
int temp = target[i];
int k = 0;
for (int j=i-1;j>=0;j--) {
if (temp < target[j]) {
target[j+1] = target[j];
} else {
k = j + 1;
break;
}
}
target[k] = temp;
}
}
//希尔排序k[]增量序列且最后一个必须为1
public static void shellSort (int[] a,int[] k) {
for (int i=0;i<k.length;i++) {
shellInsert(a,k[i]);
}
}
private static void shellInsert (int[] a,int dk) {
for (int i=dk+1;i<a.length;i++) {
int temp = a[i];
int j = i-dk;
while (j >=0 && temp < a[j]) {
a[j+dk] = a[j];
j -= dk;
}
a[j+dk] = temp;
}
}
//冒泡排序
public static void bubbleSort (int[] a) {
boolean ischanged = true;
for (int i=a.length-1;i>0 && ischanged;i--) {
ischanged = false;
for (int j=0;j<i;j++) {
if (a[j] > a[j+1]) {
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
ischanged = true;
}
}
}
}
//快速排序
public static void quickSort (int[] a,int low,int high ) {
if (low < high) {
int pivot = partition(a,low,high);
quickSort(a,low,pivot-1);
quickSort(a,pivot+1,high);
}
}
//枢轴的位置pivotkey并赋值a[i] = a[pivotkey]
private static int partition (int[] a,int low,int high) {
int temp = a[low];
while (low < high) {
while (low < high && a[high] >= temp) {
high --;
}
a[low] = a[high];
while (low < high && a[low] <= temp) {
low ++;
}
a[high] = a[low];
}
a[low] = temp;
return low;
}
//堆排序
public static void heapSort (int[] a,int start,int end) {
//建立堆
for (int i=end/2;i>=start;i--) {
adjustHeap(a, i,end);
}
System.out.println("jianli dui +"+ Arrays.toString(a));
//筛选
for (int n = end; n >= 0; n--) {
int temp = a[start];
a[start] = a[n];
a[n] = temp;
adjustHeap(a, start, n - 1);
}
}
private static void adjustHeap (int[] a,int start,int end) {
int temp = a[start];
int s = start;
for (int j=start*2;j<=end;j*=2) {
if (j + 1<= end && a[j+1] >a[j]) {
j++;
}
if (a[j] > temp) {
a[s] = a[j];
s= j;
} else {
break;
}
a[s] = temp;
}
}
}