1 线性表
1.1 顺序存储结构
1.1.1 特点
查找的性能高
1.1.2 代表
ArrayList(java)，vector(java)，stack(java)
1.2 链式存储结构
1.2.1 特点
插入、删除的性能高
1.2.2 分类
单项链表、双向链表、单项循环链表、双向循环链表
1.2.3 代表
LinkedList(java)，Queue(java)
2 Map
3 Tree
3.1 二叉树
3.1.1 斜树
3.1.2 满二叉树
3.1.3 完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
3.1.4 二叉树（视频）
package com.dn.binarytree;
import java.util.*;
public class BinaryTree {
public static void main(String[] args) {
BinaryTree binaryTree=new BinaryTree();
// binaryTree.createBinaryTreeNor();
// int height=binaryTree.getHeight();
// System.out.println("treeHeight:"+height);
// int size=binaryTree.getSize();
// System.out.println("treeSize:"+size);
// binaryTree.preOrder(binaryTree.root);
// binaryTree.midOrder(binaryTree.root);
// binaryTree.postOrder(binaryTree.root);
ArrayList<String> data=new ArrayList<>();
String[] dataArray=new String[]{"A","B","D","#","#","E","#","#","C","#","F","#","#"};
for (String string : dataArray) {
data.add(string);
}
binaryTree.createBinaryTreePre(data);
binaryTree.preOrder(binaryTree.root);
}
public class TreeNode{
private int index;
private String data;
private TreeNode leftChild;
private TreeNode rightChild;
public TreeNode(int index,String data){
this.index=index;
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
}
private TreeNode root=null;
public BinaryTree(){
root=new TreeNode(1,"A");
}
//构建查找二叉树
// 构建二叉树
// A
// / \
// B C
// / \ \
// D E F
public void createBinaryTreeNor(){
createBinaryTree();
}
public void createBinaryTree(){
TreeNode nodeB=new TreeNode(2,"B");
TreeNode nodeC=new TreeNode(3,"C");
TreeNode nodeD=new TreeNode(4,"D");
TreeNode nodeE=new TreeNode(5,"E");
TreeNode nodeF=new TreeNode(6,"F");
root.leftChild=nodeB;
root.rightChild=nodeC;
nodeB.leftChild=nodeD;
nodeB.rightChild=nodeE;
nodeC.rightChild=nodeF;
}
//求深度
public int getHeight(){
return getHeight(root);
}
private int getHeight(TreeNode node){
if(node==null){
return 0;
}else{
int i=getHeight(node.leftChild);
int j=getHeight(node.rightChild);
return (i<j)?j+1:i+1;
}
}
//求节点总数
public int getSize(){
return getSize(root);
}
private int getSize(TreeNode node){
if(node==null){
return 0;
}else{
return 1+getSize(node.leftChild)+getSize(node.rightChild);
}
}
//前序遍历-迭代
public void preOrder(TreeNode node){
if(node==null){
return;
}else{
System.out.println("preOrder data:"+node.getData());
preOrder(node.leftChild);
preOrder(node.rightChild);
}
}
//通过前序遍历的结果反向生成二叉树
// A
// / \
// B C
// / \ / \
// D E # F
// / \ /\ / \
// # # # # # #
//
// A B D # # E # # C # F # #
public void createBinaryTreePre(ArrayList<String> data){
createBinaryTree(data.size(),data);
}
public TreeNode createBinaryTree(int size,ArrayList<String> data){
if(data.size()==0){
return null;
}
String d=data.get(0);
TreeNode node;
int index=size-data.size();
if(d.equals("#")){
node=null;
data.remove(0);
return node;
}
node=new TreeNode(index,d);
if(index==0){
root=node;
}
data.remove(0);
node.leftChild=createBinaryTree(size,data);
node.rightChild=createBinaryTree(size,data);
return node;
}
//中序遍历-迭代
public void midOrder(TreeNode node){
if(node==null){
return;
}else{
midOrder(node.leftChild);
System.out.println("midOrder data"+node.getData());
midOrder(node.rightChild);
}
}
//后序遍历-迭代
public void postOrder(TreeNode node){
if(node==null){
return;
}else{
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.println("preOrder data:"+node.getData());
}
}
}
3.1.5 查找二叉树（视频）
package com.pjw.sw;
public class SearchBinaryTree {
private TreeNode root;
public SearchBinaryTree(){
}
public static void main(String[] args) {
SearchBinaryTree binaryTree=new SearchBinaryTree();
int[] datas=new int[]{50,30,20,44,88,33,87,16,7,77};
for (int i : datas) {
binaryTree.put(i);
}
binaryTree.midOrder(binaryTree.root);
binaryTree.deleteNode(16);
System.out.println("##############");
binaryTree.midOrder(binaryTree.root);
}
//中序遍历-迭代
public void midOrder(TreeNode node){
if(node==null){
return;
}else{
midOrder(node.leftChild);
System.out.println("midOrder data"+node.getData());
midOrder(node.rightChild);
}
}
//创建查找二叉树，添加节点
public TreeNode put(int data){
TreeNode node=null;
TreeNode parent=null;
if(root==null){
node=new TreeNode(0,data);
root=node;
return node;
}
node=root;
while(node!=null){
parent=node;
if(data>node.data){
node=node.rightChild;
}else if(data<node.data){
node=node.leftChild;
}else{
return node;
}
}
node=new TreeNode(0,data);
if(data<parent.data){
parent.leftChild=node;
}else{
parent.rightChild=node;
}
node.parent=parent;
return node;
}
//删除节点
public void deleteNode(int key){
TreeNode node=searchNode(key);
if(node==null){
System.out.println("该节点无法找到");
}else{
delete(node);
}
}
public void delete(TreeNode node) {
if(node==null){
System.out.println("该节点无法找到");
}else{
TreeNode parent=node.parent;
//被删除的节点没有孩子
if(node.leftChild==null&&node.rightChild==null){
if(parent.leftChild==node){
parent.leftChild=null;
}else{
parent.rightChild=null;
}
return;
}
//被删除的只有左儿子
if(node.leftChild!=null&&node.rightChild==null){
if(parent.leftChild==node){
parent.leftChild=node.leftChild;
}else{
parent.rightChild=node.leftChild;
}
return;
}
//被删除的只有右儿子
if(node.leftChild==null&&node.rightChild!=null){
if(parent.leftChild==node){
parent.leftChild=node.rightChild;
}else{
parent.rightChild=node.rightChild;
}
return;
}
//被删除的有左儿子和右儿子
TreeNode next=getNextNode(node);
delete(next);
node.data=next.data;
}
}
//找该节点的后继节点
private TreeNode getNextNode(TreeNode node) {
if(node==null){
return null;
}else{
if(node.rightChild!=null){
return getMinTreeNode(node.rightChild);
}else{
TreeNode parent=node.parent;
while(parent!=null&&node==parent.rightChild){
node=parent;
parent=parent.parent;
}
return parent;
}
}
}
private TreeNode getMinTreeNode(TreeNode node) {
if(node==null){
return null;
}else{
while(node.leftChild!=null){
node=node.leftChild;
}
}
return node;
}
public TreeNode searchNode(int key) {
TreeNode node=root;
if(node==null){
return null;
}else{
while(node!=null&&key!=node.data){
if(key<node.data){
node=node.leftChild;
}else{
node=node.rightChild;
}
}
}
return null;
}
public class TreeNode{
private int key;
private TreeNode leftChild;
private TreeNode rightChild;
private TreeNode parent;
private int data;
public TreeNode(int key, int data) {
super();
this.key = key;
this.data = data;
this.leftChild=null;
this.rightChild=null;
this.parent=null;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
}
}
3.1.6 我的二叉树
前序遍历.png
mid.png
后.png
import java.util.*;
public class MyTree {
public static void main(String[] args) {
}
//已知节点总数，求树的层数
public static int 求树的层数(int 节点总数){
if(节点总数>0){
int 临时变量=2;
int 返回值=1;
while(临时变量<=节点总数){
临时变量=临时变量*2;
返回值++;
}
return 返回值;
}else{
return -1;
}
}
//已知树的层树，求树的左侧索引
public static ArrayList<Integer> 求树的左侧索引(int 树的层树){
ArrayList<Integer> 返回值=new ArrayList<>();
if(树的层树>0){
int 临时变量=0;
for (int i = 0; i < 树的层树; i++) {
返回值.add(临时变量);
临时变量=临时变量*2+1;
}
return 返回值;
}else{
返回值.add(-1);
return 返回值;
}
}
//求父节点索引
public static int 求父节点索引(int 自己的索引){
if(自己的索引==0){
return -1;
}
if(自己的索引>0){
return (自己的索引+1)/2-1;
}else{
return -1;
}
}
//求左儿子节点索引
public static int 求左儿子节点索引(int 自己的索引,int 节点总数){
if(自己的索引*2+1>节点总数-1){
return -1;
}else{
return 自己的索引*2+1;
}
}
//求右儿子节点索引
public static int 求右儿子节点索引(int 自己的索引,int 节点总数){
if(自己的索引*2+2>节点总数-1){
return -1;
}else{
return 自己的索引*2+2;
}
}
//返回最近的有右兄弟的祖宗
public static int 返回最近的有右兄弟的祖宗(int 自己的索引){
if(自己的索引==0){
return -1;
}
int 临时变量=自己的索引;
for(;;){
临时变量=求父节点索引(临时变量);
if(临时变量%2==1){
return 临时变量;
}else if(临时变量==0){
临时变量=-1;
return 临时变量;
}
}
}
//求最远左子孙
public static int 求最远左子孙(int 自己的索引,int 节点总数){
if(自己的索引*2+1>节点总数){
return -1;
}
int 返回值=自己的索引;
while(返回值*2+1<=节点总数-1){
返回值=返回值*2+1;
}
return 返回值;
}
//求自己的右兄弟
public static int 求自己的右兄弟(int 自己的索引,int 节点总数){
if(自己的索引%2==0){
return -1;
}
if(自己的索引+1<=节点总数-1){
return 自己的索引+1;
}else {
return -1;
}
}
//前序遍历二叉树
public static LinkedList<Integer> 前序遍历二叉树(int 节点总数){
LinkedList<Integer> 前序遍历索引=new LinkedList<>();
int 当前索引=0;
前序遍历索引.add(当前索引);
for(;;){
//有没有左儿子
if(求左儿子节点索引(当前索引,节点总数)>0){ //有
当前索引=求左儿子节点索引(当前索引,节点总数);
前序遍历索引.add(当前索引);
}else{ //没有
//有没有右兄弟
if(当前索引%2==1&&当前索引!=节点总数-1){ //有
//移动到右兄弟
当前索引++;
前序遍历索引.add(当前索引);
//查看它的祖宗有没有右兄弟
if(返回最近的有右兄弟的祖宗(当前索引)>0){ //有
当前索引=返回最近的有右兄弟的祖宗(当前索引)+1;
前序遍历索引.add(当前索引);
}else{ //没有
break;
}
}else{ //没有
//有没有父亲
if(当前索引==0){ //没有
break;
}else{ //有
//查看它的祖宗有没有右兄弟
if(返回最近的有右兄弟的祖宗(当前索引)>0){ //有
当前索引=返回最近的有右兄弟的祖宗(当前索引)+1;
前序遍历索引.add(当前索引);
}else{ //没有
break;
}
}
}
}
}
return 前序遍历索引;
}
//中序遍历二叉树
public static LinkedList<Integer> 中序遍历二叉树(int 节点总数) {
LinkedList<Integer> 中序遍历索引 = new LinkedList<>();
int 当前索引=求最远左子孙(0,节点总数);
中序遍历索引.add(当前索引);
a:for(;;){
//是否有父亲
if(求父节点索引(当前索引)>=0){ //有
当前索引=求父节点索引(当前索引);
中序遍历索引.add(当前索引);
b:for(;;){
//有没有右儿子
if(求右儿子节点索引(当前索引,节点总数)>0){ //有
int 右儿子节点=求右儿子节点索引(当前索引,节点总数);
//右孩子有没有子孙
if(求左儿子节点索引(右儿子节点,节点总数)>0){ //有
当前索引=求最远左子孙(右儿子节点,节点总数);
中序遍历索引.add(当前索引);
continue a;
}else{ //没有
当前索引=右儿子节点;
中序遍历索引.add(当前索引);
//有没有最近的有右兄弟的祖宗
if(返回最近的有右兄弟的祖宗(当前索引)==-1){ //没有
break a;
}else{ //有
当前索引=求父节点索引(返回最近的有右兄弟的祖宗(当前索引));
中序遍历索引.add(当前索引);
continue b;
}
}
}else{ //没有
//自己有没有有兄弟
if(求自己的右兄弟(当前索引,节点总数)>0){ //有
continue a;
}else{ //没有
//有没有最近的有右兄弟的祖宗
if(返回最近的有右兄弟的祖宗(当前索引)==-1){ //没有
break a;
}else{ //有
当前索引=求父节点索引(返回最近的有右兄弟的祖宗(当前索引));
中序遍历索引.add(当前索引);
continue b;
}
}
}
}
}else{ //没有
break a;
}
}
return 中序遍历索引;
}
//后序遍历二叉树
public static LinkedList<Integer> 后序遍历二叉树(int 节点总数) {
LinkedList<Integer> 后序遍历索引 = new LinkedList<>();
int 当前索引=求最远左子孙(0,节点总数);
后序遍历索引.add(当前索引);
for (;;){
//有没有右兄弟？
if(求自己的右兄弟(当前索引,节点总数)>0){ //有
int 自己的右兄弟=求自己的右兄弟(当前索引,节点总数);
//右兄弟有没有子孙？
if(求左儿子节点索引(自己的右兄弟,节点总数)>0){ //有
当前索引=求最远左子孙(自己的右兄弟,节点总数);
后序遍历索引.add(当前索引);
continue;
}else{ //没有
当前索引=自己的右兄弟;
后序遍历索引.add(当前索引);
continue;
}
}else{ //没有
//有没有父亲？
if(求父节点索引(当前索引)>=0){ //有
当前索引=求父节点索引(当前索引);
后序遍历索引.add(当前索引);
continue;
}else{ //没有
break;
}
}
}
return 后序遍历索引;
}
}
4 Graph
4.1
dfs.png
import java.util.*;
public class Graph {
public static void main(String[] args) {
Integer[] guanxi={
//0,1,2,3,4,5,6,7,8
0,1,5,0,0,0,0,0,0, //0
1,0,3,7,5,0,0,0,0, //1
5,3,0,0,1,7,0,0,0, //2
0,7,0,0,2,0,3,0,0, //3
0,5,1,2,0,3,6,9,0, //4
0,0,7,0,3,0,0,5,0, //5
0,0,0,3,6,0,0,2,7, //6
0,0,0,0,9,5,2,0,4, //7
0,0,0,0,0,0,7,4,0, //8
};
String[] hang={"0","1","2","3","4","5","6","7","8"};
String[] lie={"0","1","2","3","4","5","6","7","8"};
ArrayList<String> 行=new ArrayList<>(Arrays.asList(hang));
ArrayList<String> 列=new ArrayList<>(Arrays.asList(lie));
ArrayList<Integer> 关系=new ArrayList<>(Arrays.asList(guanxi));
///////////////////////////////////////////////////////////////////////
//HashMap<Integer,ArrayList<HashMap<String,Object>>> 图=构建图2(行,列,关系,"6");
迪杰斯特拉(行,列,关系,"4");
}
public static HashMap<Integer,ArrayList<HashMap<String,Object>>> 构建图2(ArrayList<String> 行,ArrayList<String> 列,
ArrayList<Integer> 关系,String 顶点){
HashMap<Integer,ArrayList<HashMap<String,Object>>> 返回值=new HashMap<>();
int 元素个数=行.size();
//获取根节点的连接节点
int 当前层数=1;
if(当前层数==1){
ArrayList<HashMap<String,Object>> 每层集合=new ArrayList<>();
ArrayList<String> 根节点的连接节点=new ArrayList<>();
HashMap<String,Object> 每层的每个元素=new HashMap<>();
每层的每个元素.put("元素", 顶点);
int 关系里的起始索引=行.size()*列.indexOf(顶点);
int 关系里的结束索引=行.size()*(列.indexOf(顶点)+1)-1;
for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {
if(关系.get(j)!=0){
根节点的连接节点.add(行.get(j%元素个数));
}
}
每层的每个元素.put("儿子",根节点的连接节点);
每层集合.add(每层的每个元素);
返回值.put(当前层数,每层集合 );
}
//第一层结束,进入下一层
当前层数++;
for(;;){
//上一层是否有儿子？
HashMap<String,ArrayList<String>> 上一层的儿子集合=new HashMap<>();
for (HashMap<String,Object> 每层的每个元素 : 返回值.get(当前层数-1)) {
for (String 每个儿子 : (ArrayList<String>)每层的每个元素.get("儿子")) {
//上一层的儿子集合里有没有每个儿子？
if(上一层的儿子集合.get(每个儿子)==null){ //没有
ArrayList<String> 临时数组=new ArrayList<>();
临时数组.add((String)每层的每个元素.get("元素"));
上一层的儿子集合.put(每个儿子,临时数组);
}else{ //有
上一层的儿子集合.get(每个儿子).add((String)每层的每个元素.get("元素"));
}
}
}
if(上一层的儿子集合.size()==0){ //上一层没有儿子
break;
}else{ //上一层有儿子
Set<String> 上一层的儿子集合所有键=上一层的儿子集合.keySet();
ArrayList<HashMap<String,Object>> 每层集合=new ArrayList<>();
for (String 上一层的每个儿子 : 上一层的儿子集合所有键) {
HashMap<String,Object> 每层的每个元素=new HashMap<>();
ArrayList<String> 兄弟=new ArrayList<>();
ArrayList<String> 儿子=new ArrayList<>();
每层的每个元素.put("元素",上一层的每个儿子);
每层的每个元素.put("父亲",上一层的儿子集合.get(上一层的每个儿子));
int 关系里的起始索引=元素个数*列.indexOf(上一层的每个儿子);
int 关系里的结束索引=元素个数*(列.indexOf(上一层的每个儿子)+1)-1;
for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {
if(关系.get(j)!=0){
//System.out.println(行.get(j%元素个数));
if(上一层的儿子集合.get(上一层的每个儿子).contains(行.get(j%元素个数))){ //是父亲
}else if(上一层的儿子集合所有键.contains(行.get(j%元素个数))){ //是兄弟
兄弟.add(行.get(j%元素个数));
}else{ //是儿子
儿子.add(行.get(j%元素个数));
}
}
}
每层的每个元素.put("本层所有元素",上一层的儿子集合所有键);
每层的每个元素.put("儿子",儿子);
每层的每个元素.put("兄弟",兄弟);
每层集合.add(每层的每个元素);
}
返回值.put(当前层数,每层集合);
当前层数++;
}
}
return 返回值;
}
public static void 深度优先搜索(HashMap<Integer,ArrayList<HashMap<String,Object>>> 图){
ArrayList<String> 返回值=new ArrayList<>();
int 当前层数=1;
String 根节点=(String)图.get(当前层数).get(0).get("元素");
String 临时变量=根节点;
返回值.add(临时变量);
b:for (;;){
//节点是否有未被遍历过的儿子，且该儿子的父亲列表中的第一个父亲为自己？
boolean 前进条件1=false;
ArrayList<String> 该节点的儿子列表=new ArrayList<>();
d:for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数)) {
if((String)每层的每个元素.get("元素")==临时变量){
该节点的儿子列表=(ArrayList<String>)每层的每个元素.get("儿子");
break d;
}
}
//ArrayList<String> 该节点的儿子列表=(ArrayList<String>)图.get(当前层数).get(0).get("儿子");
// System.out.println("当前节点："+临时变量);
// System.out.println("当前节点的儿子："+该节点的儿子列表);
a:for (String 每个儿子: 该节点的儿子列表) {
if(!返回值.contains(每个儿子)){
for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数+1)) {
if((String)每层的每个元素.get("元素")==每个儿子&&
((ArrayList<String>)每层的每个元素.get("父亲")).get(0)==临时变量){
前进条件1=true;
临时变量=每个儿子;
break a;
}
}
}
}
if(前进条件1){ //有
返回值.add(临时变量);
当前层数++;
continue b;
}else { //没有
//该节点是否有父亲？
boolean 前进条件2=false;
if(当前层数!=1){
c:for (HashMap<String,Object> 每层的每个元素: 图.get(当前层数)) {
if((String)每层的每个元素.get("元素")==临时变量){
前进条件2=true;
临时变量=((ArrayList<String>)每层的每个元素.get("父亲")).get(0);
break c;
}
}
}
if(前进条件2){ //有
当前层数--;
continue b;
}else{ //没有
break b;
}
}
}
System.out.println(返回值);
}
public static void 广度优先搜索(HashMap<Integer,ArrayList<HashMap<String,Object>>> 图){
ArrayList<String> 返回值=new ArrayList<>();
for (int i = 1; i <=图.size() ; i++) {
if(i==1){
返回值.add((String)图.get(i).get(0).get("元素"));
}else{
Set<String> 临时数组=new HashSet<>();
临时数组=(Set<String>)图.get(i).get(0).get("本层所有元素");
for (String str: 临时数组) {
返回值.add(str);
}
}
}
System.out.println(返回值);
}
public static HashMap<String,Integer> 求和某个节点连接的所有节点(ArrayList<String> 行,ArrayList<String> 列,
ArrayList<Integer> 关系,String 节点){
int 元素个数=行.size();
HashMap<String,Integer> 返回值=new HashMap<>();
int 关系里的起始索引=行.size()*列.indexOf(节点);
int 关系里的结束索引=行.size()*(列.indexOf(节点)+1)-1;
for (int j =关系里的起始索引; j <=关系里的结束索引 ; j++) {
if(关系.get(j)!=0){
返回值.put(行.get(j%元素个数),关系.get(j));
}
}
return 返回值;
}
public static void 普里姆(ArrayList<String> 行,ArrayList<String> 列,
ArrayList<Integer> 关系,String 起始节点){
HashMap<String,Integer> 返回值=new HashMap<>();
ArrayList<String> 已使用的节点=new ArrayList<>();
已使用的节点.add(起始节点);
for(;;){
String 哪个已使用节点=null;
String 临时节点=null;
int 目前最小权值=0;
for (String 每个节点:已使用的节点) {
HashMap<String,Integer> 和某个节点连接的所有节点=求和某个节点连接的所有节点(行, 列, 关系, 每个节点);
Set<String> 所有节点=和某个节点连接的所有节点.keySet();
for (String str: 所有节点) {
if(!已使用的节点.contains(str)){
if(目前最小权值==0){
目前最小权值=和某个节点连接的所有节点.get(str);
临时节点=str;
哪个已使用节点=每个节点;
}else{
if(目前最小权值>和某个节点连接的所有节点.get(str)){
目前最小权值=和某个节点连接的所有节点.get(str);
临时节点=str;
哪个已使用节点=每个节点;
}
}
}
}
}
已使用的节点.add(临时节点);
返回值.put(哪个已使用节点+"-"+临时节点,目前最小权值);
if(已使用的节点.size()==行.size()){
break;
}
}
System.out.println(返回值);
}
public static void 克鲁斯卡尔(ArrayList<String> 行,ArrayList<String> 列,
ArrayList<Integer> 关系,String 起始节点){
}
public static void 迪杰斯特拉(ArrayList<String> 行,ArrayList<String> 列,
ArrayList<Integer> 关系,String 起始节点){
LinkedList<String> 未遍历=new LinkedList<>();
HashMap<String,Integer> 最短路径权值=new HashMap<>();
最短路径权值.put(起始节点,0);
HashMap<String,ArrayList<String>> 最短路径路程=new HashMap<>();
ArrayList<String> 初始最短路径路程值=new ArrayList<>();
初始最短路径路程值.add(起始节点);
最短路径路程.put(起始节点,初始最短路径路程值);
LinkedList<String> 临时数组外部=new LinkedList<>();
临时数组外部.add(起始节点);
//初始化未遍历对象
for (String str: 行) {
未遍历.add(str);
}
while(未遍历.size()!=0){
System.out.println("临时数组外部"+临时数组外部);
ArrayList<String> 临时数组内部=new ArrayList<>();
//临时数组内部需要排序
for (String str: 临时数组外部) {
未遍历.remove(str);
//111111111111111111111
HashMap<String,Integer> 关系表=求和某个节点连接的所有节点(行,列,关系,str);
Set<String> 关系表键集合=关系表.keySet();
System.out.println("str"+str);
System.out.println("关系表键集合"+关系表键集合);
//22222222222222222222
Set<String> 最短路径权值键集合=最短路径权值.keySet();
for (String str2: 关系表键集合) {
System.out.println("aaaaa:"+str2);
System.out.println(最短路径权值键集合);
//3333333333333333
if(最短路径权值键集合.contains(str2)){
//55555555555555555555555555555
int 上面的值=最短路径权值.get(str)+关系表.get(str2);
int 下面的值=最短路径权值.get(str2);
//777777777777777777777
if(上面的值>下面的值){
}
//8888888888888888888888
else{
最短路径权值.put(str2,最短路径权值.get(str)+关系表.get(str2));
ArrayList<String> linshi=new ArrayList<>();
for (String str3:最短路径路程.get(str)) {
linshi.add(str3);
}
linshi.add(str2);
最短路径路程.put(str2,linshi);
}
}
//4444444444444444
else{
//66666666666666666
最短路径权值.put(str2,最短路径权值.get(str)+关系表.get(str2));
ArrayList<String> linshi=new ArrayList<>();
for (String str3:最短路径路程.get(str)) {
linshi.add(str3);
}
linshi.add(str2);
最短路径路程.put(str2,linshi);
临时数组内部.add(str2);
}
}
}
临时数组外部.clear();
for (String str4:临时数组内部) {
临时数组外部.add(str4);
}
}
System.out.println(最短路径权值);
System.out.println(最短路径路程);
}
}
5 排序
5.1 插入排序
5.1.1 直接插入排序
O( (N+1)*(N/2))
5.1.2 二分法插入排序
O(nlgn)
5.1.3 希尔排序
不稳定的排序
5.2 选择排序
5.2.1 简单选择排序
O( (N+1)*(N/2))
5.2.2 堆排序
大堆：二叉树里父节点比左右孩子节点都大
小堆：二叉树里父节点比左右孩子节点都小
O(nlgn)
5.3 交换排序
5.3.1 冒泡排序
O(N²)
5.3.2 快速排序
O (nlogn)
