数据结构和算法

一.数据结构

1. 稀疏数组和队列

1.1稀疏数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
package DataStrucetures;

import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Arrays;

public class SparseArray {
    public static void main(String[] args) {
        int[][] chessArray = new int[11][11];
        chessArray[1][2]=1;
        chessArray[2][3]=2;
        System.out.println("原数组为：");
        int sum=0;
        for (int[] ints : chessArray) {
            for (int anInt : ints) {
                System.out.print("\t"+anInt);
                if (anInt!=0){
                    sum++;
                }
            }
            System.out.println();
        }
        int[][] XishuArray = new int[sum+1][3];
        XishuArray[0][0]=11;
        XishuArray[0][1]=11;
        XishuArray[0][2]=sum;
        int count=1;
        for (int i = 0; i < chessArray.length; i++) {
            for (int j = 0; j < chessArray[i].length; j++) {
                if (chessArray[i][j]!=0){
                    XishuArray[count][0]=i;
                    XishuArray[count][1]=j;
                    XishuArray[count][2]=chessArray[i][j];
                    count++;
                }
            }
        }
        try (PrintStream printStream = new PrintStream("XishuArray.txt")) {
            for (int i = 0; i < XishuArray.length; i++) {
                for (int i1 = 0; i1 < XishuArray[i].length; i1++) {
                    printStream.print(+XishuArray[i][i1]+"\t");
                }
                printStream.println();
            }

        }catch (Exception e){
            e.printStackTrace();
        }
        for (int[] ints : XishuArray) {
            for (int anInt : ints) {
                System.out.print("\t"+anInt);
            }
            System.out.println();
        }
        int[][] scArray = new int[XishuArray[0][0]][XishuArray[0][1]];
        for (int i = 1; i < XishuArray.length; i++) {
            scArray[XishuArray[i][0]][XishuArray[i][1]]=XishuArray[i][2];
        }
        for (int[] ints : scArray) {
            for (int anInt : ints) {
                System.out.print("\t"+anInt);
            }
            System.out.println();
        }
    }
}

加io流版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
{
    public static void main(String[] args) {
        try (
                BufferedReader br=new BufferedReader(new FileReader("XishuArray.txt"));
                ){
            String line ;
            String lines=br.readLine();
            String[] s = lines.split("\t");
            int[] int1 = Arrays.stream(s).mapToInt(Integer::parseInt).toArray();
            int[][] ints1 = new int[int1[0]][int1[1]];
            while ((line=br.readLine())!=null){
                String[] s1 = line.split("\t");
                int[] ints = Arrays.stream(s1).mapToInt(Integer::parseInt).toArray();
                ints1[ints[0]][ints[1]]=ints[2];
//            int[] array = Arrays.asList(s1).stream().mapToInt(Integer::parseInt).toArray();
//                Arrays.stream(ints).forEach(System.out::println);
            }
//            while ((line=br.readLine())!=null){
//                System.out.println(line);
//            }
            for (int[] ints : ints1) {
                for (int anInt : ints) {
                    System.out.print("\t"+anInt);
                }
                System.out.println();
            }
            System.out.println("-----------");
//            while ((len=br.read())!=-1){
//                System.out.print((char)len);
//            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

建议使用序列化和反序列化.

1.2 队列

数组模拟队列代码实现
标准数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package DataStrucetures.ArrayQueue;

import java.util.Arrays;
import java.util.Scanner;

public class ArrayQueueDemo {
    public static void main(String[] args) {
        ArrayQueue aq = new ArrayQueue(3);
        Scanner sc = new Scanner(System.in);
        Boolean flag = true;
        while (flag){
            System.out.println("A.添加数据");
            System.out.println("B.取出数据");
            System.out.println("C.得到队列");
            System.out.println("D.展示头部");
            System.out.println("E.退出程序");
            String choice = sc.next();
            switch (choice){
                case "A":
                    aq.AddQueue(sc.nextInt());
                    break;
                case "B":
                    try {
                        int value = aq.getValue();
                        System.out.println("取出的数据为:"+value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case "C":
                    aq.showValues();
                    break;
                case "D":
                    try {
                        int i = aq.headQueue();
                        System.out.println("头部为:"+i);
                    } catch (Exception e){
                        e.printStackTrace();
                    }
                    break;
                case "E":
                    sc.close();
                    System.out.println("退出程序");
                    System.exit(0);
                default:
                    System.out.println("输入有误!!!");

            }

        }
    }
}
class ArrayQueue{
    private int front =-1;//指向队列头部，队列头的前一个位置
    private int last = -1;//指向队列尾部，队列尾部的具体数据
    private int maxSize;
    private int[] arrays;
    public ArrayQueue(){
    }
    public ArrayQueue(int maxSize){
        this.maxSize=maxSize;
        arrays=new int[maxSize];
    }
    public Boolean isFull(){
        return last==maxSize-1;
    }
    public Boolean isEmpty(){
        return front==last;
    }
    public void AddQueue(int number){
        if (isFull()){
            System.out.println("队列已满无法加入数据!!!!");
            return;
        }
        last++;
        arrays[last]=number;
    }
    public int getValue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空~~~~~~");
        }
        return arrays[++front];
    }
    public void showValues(){
        if (isEmpty()){
            System.out.println("队列为空!!!!");
            return;
        }
        for (int i = front+1; i <= last; i++) {
            System.out.println(arrays[i]+"\t");
        }
    }
    public int headQueue(){
        if (isEmpty()){
            throw new RuntimeException("没有数据");
        }
        return arrays[front+1];
    }
}
环形数组
printf用法

目前printf支持以下格式：
%c 单个字符
%d 十进制整数
%f 十进制浮点数
%o 八进制数
%s 字符串
%u 无符号十进制数
%x 十六进制数
%% 输出百分号%

printf的格式控制的完整格式：
% - 0 m.n l或h 格式字符

下面对组成格式说明的各项加以说明：
①%：表示格式说明的起始符号，不可缺少。
②-：有-表示左对齐输出，如省略表示右对齐输出。
③0：有0表示指定空位填0,如省略表示指定空位不填。
④m.n：m指域宽，即对应的输出项在输出设备上所占的字符数。N指精度。用于说明输出的实型数的小数位数。为指定n时，隐含的精度为n=6位。
⑤l或h:l对整型指long型，对实型指double型。h用于将整型的格式字符修正为short型。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
格式字符
格式字符用以指定输出项的数据类型和输出格式。
①d格式：用来输出十进制整数。有以下几种用法：
%d：按整型数据的实际长度输出。
%md：m为指定的输出字段的宽度。如果数据的位数小于m，则左端补以空格，若大于m，则按实际位数输出。
%ld：输出长整型数据。
②o格式：以无符号八进制形式输出整数。对长整型可以用”%lo”格式输出。同样也可以指定字段宽度用“%mo”格式输出。
例：
main() {
int a = -1;
printf(“%d, %o”, a, a);
}
运行结果：-1,177777
程序解析：-1在内存单元中（以补码形式存放）为(1111111111111111)2，转换为八进制数为(177777)8。
③x格式：以无符号十六进制形式输出整数。对长整型可以用”%lx”格式输出。同样也可以指定字段宽度用”%mx”格式输出。
④u格式：以无符号十进制形式输出整数。对长整型可以用”%lu”格式输出。同样也可以指定字段宽度用“%mu”格式输出。
⑤c格式：输出一个字符。
⑥s格式：用来输出一个串。有几中用法
%s：例如:printf(“%s”, “CHINA”)输出”CHINA”字符串（不包括双引号）。
%ms：输出的字符串占m列，如字符串本身长度大于m，则突破获m的限制,将字符串全部输出。若串长小于m，则左补空格。
%-ms：如果串长小于m，则在m列范围内，字符串向左靠，右补空格。
%m.ns：输出占m列，但只取字符串中左端n个字符。这n个字符输出在m列的右侧，左补空格。
%-m.ns：其中m、n含义同上，n个字符输出在m列范围的左侧，右补空格。如果n>m，则自动取n值，即保证n个字符正常输出。
⑦f格式：用来输出实数（包括单、双精度），以小数形式输出。有以下几种用法：
%f：不指定宽度，整数部分全部输出并输出6位小数。
%m.nf：输出共占m列，其中有n位小数，如数值宽度小于m左端补空格。
%-m.nf：输出共占n列，其中有n位小数，如数值宽度小于m右端补空格。
⑧e格式：以指数形式输出实数。可用以下形式：
%e：数字部分（又称尾数）输出6位小数，指数部分占5位或4位。
%m.ne和%-m.ne：m、n和”-”字符含义与前相同。此处n指数据的数字部分的小数位数，m表示整个输出数据所占的宽度。
⑨g格式：自动选f格式或e格式中较短的一种输出，且不输出无意义的零。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
关于printf函数的进一步说明：
如果想输出字符”%”,则应该在“格式控制”字符串中用连续两个%表示，如:
printf(“%f%%”, 1.0/3);
输出0.333333%。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
对于单精度数，使用%f格式符输出时，仅前7位是有效数字，小数6位．
对于双精度数，使用%lf格式符输出时，前16位是有效数字，小数6位．

######################################拾遗########################################
由高手指点
对于m.n的格式还可以用如下方法表示（例）
char ch[20];
printf(“%*.s\n”,m,n,ch);
前边的定义的是总的宽度，后边的定义的是输出的个数。分别对应外面的参数m和n 。我想这种方法的好处是可以在语句之外对参数m和n赋值，从而控制输出格式。

-——————————————————————————-
今天又看到一种输出格式 %n 可以将所输出字符串的长度值赋绐一个变量, 见下例:

int slen;

printf(“hello world%n”, &slen);

执行后变量被赋值为11。

不记得的时候，看看还是很有帮助的，特别是scanf的格式化输入，让我大汗，以前对其理解太少了。原来正则也可以在里面使用。

自己在阅读源码的时候，也发现了一些上面所谓提及的。慢慢积累下来，供自己和再看的读者享用。

《UNIX系统编程》P9页（英文版P15）：

fprintf(stderr, “a at %p and\nx at %p\n”, (void *)a, (viod *)&x);

其中提及了%p,自己理解为打印指针地址的格式。

-—————————————————————————

public class TestPrintf {
public static void main(String[] args) {
//定义一些变量，用来格式化输出。
double d = 345.678;
String s = “你好！”;
int i = 1234;
//“%”表示进行格式化输出，”%”之后的内容为格式的定义。
System.out.printf(“%f”,d); //“f”表示格式化输出浮点数。
System.out.println();
System.out.printf(“%9.2f”,d); //“9.2”中的9表示输出的长度，2表示小数点后的位数。
System.out.println();
System.out.printf(“%+9.2f”,d); //“+”表示输出的数带正负号。
System.out.println();
System.out.printf(“%-9.4f”,d); //“-“表示输出的数左对齐（默认为右对齐）。
System.out.println();
System.out.printf(“%+-9.3f”,d); //“+-“表示输出的数带正负号且左对齐。
System.out.println();
System.out.printf(“%d”,i); //“d”表示输出十进制整数。
System.out.println();
System.out.printf(“%o”,i); //“o”表示输出八进制整数。
System.out.println();
System.out.printf(“%x”,i); //“d”表示输出十六进制整数。
System.out.println();
System.out.printf(“%#x”,i); //“d”表示输出带有十六进制标志的整数。
System.out.println();
System.out.printf(“%s”,s); //“d”表示输出字符串。
System.out.println();
System.out.printf(“输出一个浮点数：%f，一个整数：%d，一个字符串：%s”,d,i,s);
//可以输出多个变量，注意顺序。
System.out.println();
System.out.printf(“字符串：%2$s，%1$d的十六进制数：%1$#x”,i,s);
//“X$”表示第几个变量。
}
}

1.3链表

单链表实现队列
单链表代码(无排序)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
package DataStrucetures.ArrayQueue.LinkedMethods;

public class LinkedDemo01 {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode h2 = new HeroNode(2, "卢俊", "玉麒麟");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头");
        SingleListed sl = new SingleListed();
        sl.add(h1);
        sl.add(h2);
        sl.add(h3);
        sl.add(h4);
        sl.list();
    }
}
class SingleListed{
    private HeroNode head=new HeroNode(0,"","");
    public void add(HeroNode heroNode){
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=heroNode;
    }
    public void list(){
        if (head.next==null){
            System.out.println("链表为0");
            return;
        }
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp=temp.next;
        }
    }
}
class HeroNode{
    private int no;
    private String name;
    private String nickname;
    public HeroNode next;
    public HeroNode(){
    }
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

单链表(带排序)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

public class LinkedDemo01 {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode h2 = new HeroNode(2, "卢俊", "玉麒麟");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头");
        SingleListed sl = new SingleListed();
//        sl.add(h1);
//        sl.add(h2);
//        sl.add(h3);
//        sl.add(h4);
        sl.addByorder(h2);
        sl.addByorder(h1);
        sl.addByorder(h4);
        sl.addByorder(h3);
        sl.list();
    }
}
class SingleListed{
    private HeroNode head=new HeroNode(0,"","");
    public void add(HeroNode heroNode){
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=heroNode;
    }
    public void addByorder(HeroNode heroNode){
        boolean flag=false;
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==heroNode.no){
                flag=true;
                break;
            } else if (temp.next.no>heroNode.no){
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println("已填加过改英雄！！！！");
        }else {
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }
    public void list(){
        if (head.next==null){
            System.out.println("链表为0");
            return;
        }
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp=temp.next;
        }
    }
}
class HeroNode{
    public int no;
    private String name;
    private String nickname;
    public HeroNode next;
    public HeroNode(){
    }
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}
单链表(带增删改)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
public class LinkedDemo01 {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode h2 = new HeroNode(2, "卢俊", "玉麒麟");
        HeroNode h3 = new HeroNode(3, "吴用", "智多星");
        HeroNode h4 = new HeroNode(4, "林冲", "豹子头");
        SingleListed sl = new SingleListed();
//        sl.add(h1);
//        sl.add(h2);
//        sl.add(h3);
//        sl.add(h4);
        sl.addByorder(h2);
        sl.addByorder(h1);
        sl.addByorder(h4);
        sl.addByorder(h3);
        sl.upadate(new HeroNode(2,"陆军军","小花臂"));
        sl.delete(2);
        sl.list();
    }
}
class SingleListed{
    private HeroNode head=new HeroNode(0,"","");
    public void add(HeroNode heroNode){
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=heroNode;
    }
    public void addByorder(HeroNode heroNode){
        boolean flag=false;
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==heroNode.no){
                flag=true;
                break;
            } else if (temp.next.no>heroNode.no){
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println("已填加过改英雄！！！！");
        }else {
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }
    public void list(){
        if (head.next==null){
            System.out.println("链表为0");
            return;
        }
        HeroNode temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            System.out.println(temp.next);
            temp=temp.next;
        }
    }
    public void upadate(HeroNode newHeroNode){
        HeroNode temp=head;
        if (temp.next==null){
            System.out.println("链表为空!!");
            return;
        }
        boolean flag =false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==newHeroNode.no){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next.nickname = newHeroNode.nickname;
            temp.next.name = newHeroNode.name;
        }else {
            System.out.println("未找到！！！！！！！");
        }
    }
    public void delete(int a){
        HeroNode temp=head;
        if (temp.next==null){
            System.out.println("链表为空!!");
            return;
        }
        boolean flag=false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.no==a){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.println("未查找到改数据");
        }
    }
}
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    public HeroNode(){
    }
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

==面试题==
得到链表长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public  int getLength(){
    //可以去掉static
    HeroNode temp=head;
    int count=0;
    if (temp.next==null){
        System.out.println("此列表为空！！！");
        return 0;
    }
    while (true){
        if (temp.next==null){
            break;
        }
        count++;
        temp=temp.next;
    }
    return count;
}
得到倒数第k个链表(新浪)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void getDk(int k){
    HeroNode temp=head;
    if (temp.next==null){
        System.out.println("链表为空");
    }
    int length = getLength();
    int key = length-k+1;
    if (k>length){
        System.out.println("此链表长度不足！！");
    }
    int count=1;
    while (true){
        if (key==count){
            break;
        }
        count++;
        temp=temp.next;
    }
    System.out.println(temp.next);
}
得到反转链表(腾讯)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void reserveLinked(){
        if (head.next==null || head.next.next==null){
            return;
        }
        HeroNode cur=head.next;
        HeroNode middle=null;
        HeroNode reserveHead=new HeroNode(0,"","");
        while (cur!=null){
            middle=cur.next;
            cur.next=reserveHead.next;
            reserveHead.next=cur;
            cur=middle;
        }
        head.next=reserveHead.next;
    }
从末端输出链表(百度)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void daoQu(){
        if (head.next==null){
            System.out.println("此链表无数据!!!");
            return;
        }
        HeroNode temp=head;
        Stack<HeroNode> hn = new Stack<>();
        while (temp.next!=null){
            hn.push(temp.next);
            temp=temp.next;
        }
        while (!hn.isEmpty()){
            System.out.println(hn.pop());
        }
    }
1.4双向链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
public class DoubleLinkedDemo {
    public static void main(String[] args) {
        Node n1 = new Node(1, "宋江", "及时雨");
        Node n2 = new Node(2, "晁盖", "大头鬼");
        Node n3 = new Node(3, "林冲", "豹子头");
        Node n4 = new Node(4, "王英", "矮脚虎");
        DoubleLinked dl = new DoubleLinked();
        dl.add(n1);
        dl.add(n2);
        dl.add(n3);
        dl.add(n4);
        dl.list();
        System.out.println("------------");
        Node n5 = new Node(3, "林总", "包子头");
        dl.update(n5);
        dl.list();
        System.out.println("-------------");
        dl.del(4);
        dl.list();
        System.out.println("-------------");
        DoubleLinked dl1 = new DoubleLinked();
        Node n6 = new Node(6, "宋江", "及时雨");
        Node n7 = new Node(7, "晁盖", "大头鬼");
        Node n8 = new Node(8, "林冲", "豹子头");
        Node n9 = new Node(9, "王英", "矮脚虎");
        dl1.addByOrder(n6);
        dl1.addByOrder(n7);
        dl1.addByOrder(n9);
        dl1.addByOrder(n8);
        dl1.list();
    }
}
class DoubleLinked{
    private Node head=new Node(0,"","");
    public Node getHead() {
        return head;
    }
    public void add(Node node){
        Node temp=head;
        while (temp.next!=null){
            temp=temp.next;
        }
        temp.next=node;
        temp.next.pre=temp;
    }
    public void list(){
        Node temp=head;
        if (temp.next==null){
            System.out.println("链表为空");
            return;
        }
        while (temp.next!=null){
            System.out.println(temp.next);
            temp=temp.next;
        }
    }
    public void update(Node node){
        Node temp=head;
        if (temp.next==null){
            System.out.println("链表无元素");
            return;
        }
        Boolean flag=true;
        while (flag){
            if (temp.next==null){
                break;
            }
            if (temp.next.no == node.no){
                flag=false;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println("没有找到");
        }else {
            temp.next.nickname = node.nickname;
            temp.next.name = node.name;
        }
    }
    public void del(int k){
        if (head.next==null){
            System.out.println("无数据");
            return;
        }
        Node temp=head.next;
        Boolean flag=true;
        while (temp!=null){
            if (temp.no==k){
                flag=false;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println("未找到");
        }else {
            temp.pre.next=temp.next;
            if (temp.next!=null){
                temp.next.pre=temp.pre;
                //避免空指针异常
            }
        }
    }
    public void addByOrder(Node node){
        Node temp=head;
        Boolean flag=true;
        while (temp.next!=null){
            if (node.no<temp.next.no){
                flag=false;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=node;
            node.pre=temp;
        }else {
            temp.next.pre=node;
            node.next=temp.next;
            temp.next=node;
            node.pre=temp;

        }
    }

}
class Node{
    public int no;
    public String name;
    public String nickname;
    public Node next;
    public Node pre;
    public Node(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
}

1.5约瑟夫环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
public class Josepfu {
    public static void main(String[] args) {
        Circle cc = new Circle();
        cc.add(4);
        cc.showList();
        cc.outCircle(2,5,3);
    }
}
class Circle{
    private joseNode first=null;
    public void add(int nums){
        if (nums<1){
            System.out.println("添加的值不正确");
            return;
        }else {
            joseNode cur=null;
            for (int i = 1; i <= nums; i++) {
                joseNode jn = new joseNode(i);
                if (i==1){
                    first=jn;
                    first.setNext(first);
                    cur=first;
                }else {
                    cur.setNext(jn);
                    jn.setNext(first);
                    cur=jn;
                }
            }
        }
    }
    public void showList(){
        joseNode cur=first;
        if (cur.getNext()==null){
            System.out.println("空");
            return;
        }
        while (true){
            System.out.println("node"+cur.getNo());
            if (cur.getNext()==first){
                break;
            }
            cur=cur.getNext();
        }
    }
    public void outCircle(int startNo,int nums,int count){
        add(nums);
        if (first==null||startNo<1||startNo>nums){
            System.out.println("有误");
            return;
        }
        joseNode temp=first;
        for (int i = 1; i < startNo; i++) {
            first=first.getNext();
            if (temp.getNext()!=first){
                temp=temp.getNext();
            }
        }
        while (true){
            if (temp==first){
                break;
            }
            for (int i = 1; i < count; i++) {
                first=first.getNext();
                temp=temp.getNext();
            }
            System.out.println("小孩出圈"+first.no);
            first=first.getNext();
            temp.setNext(first);
        }
        System.out.println("留下来的为"+first.no);
}
class joseNode {
    private int no;
    private joseNode next;

    public joseNode() {
    }

    public joseNode(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public joseNode getNext() {
        return next;
    }

    public void setNext(joseNode next) {
        this.next = next;
    }
  }
}

2.栈

2.1数组实现栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class StackArray {
    public static void main(String[] args) {
        Stack stack = new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.list();
    }
}
class Stack{
    private int maxSize;
    private int[] stack;
    private int top=-1;
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }
    public Boolean isEmpty(int[] stack){
        return top==-1;
    }
    public Boolean isFull(int[] stack){
        return top==maxSize-1;
    }
    public void push(int a){
        if (isFull(stack)){
            System.out.println("已满!!!");
            return;
        }
        top++;
        stack[top]=a;
    }
    public int pop(){
        if (isEmpty(stack)){
            throw new RuntimeException("无数据警告!!!");
        }
        int value=stack[top];
        top--;
        return value;
    }
    public void list(){
        if (isEmpty(stack)){
            throw new RuntimeException("无数据警告!!!");
        }
        for (int i = top; i >=0; i--) {
            System.out.println(stack[i]+" ");
        }
    }
}

2.2计算器
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package DataStrucetures.Stack;

import java.util.IllegalFormatCodePointException;
import java.util.Scanner;

public class Calculator {
    public static void main(String[] args) {
        int index=0;
        String expression="7-2*6+4*2";
        //7-2*5+4-2,7+2*6-4*2
        Stacks numstacks = new Stacks(10);
        Stacks operstacks = new Stacks(10);
        char ch=' ';
        int num1=0;
        int num2=0;
        int oper=0;
        int res;
        while (true){
            ch = expression.substring(index, index + 1).charAt(0);
            if (operstacks.isOper(ch)){
                if (operstacks.isEmpty()){
                    operstacks.push(ch);
                }else {
                    //不为空
                    if (operstacks.priority(ch)>operstacks.priority(operstacks.peak())){
                        operstacks.push(ch);
                    }else if (operstacks.priority(ch)<=operstacks.priority(operstacks.peak())){
                        //小于先运算
                        num1=numstacks.pop();
                        num2=numstacks.pop();
                        oper= operstacks.pop();
                        res = numstacks.cal(num1, num2, oper);
                        numstacks.push(res);
                        operstacks.push(ch);
                    }
                }
            }else {
                //为数字
                numstacks.push(ch-48);
            }
            index++;
            if (expression.length()<=index){
                break;
            }
        }
        while (true){
            if (operstacks.isEmpty()){
                break;
            }
            num1=numstacks.pop();
            num2=numstacks.pop();
            oper=operstacks.pop();
            res =numstacks.cal(num1, num2, oper);
            numstacks.push(res);
        }
        int ress=numstacks.pop();
        System.out.println(ress);
    }
}
class Stacks{
    private int maxSize;
    private int[] stack;
    private int top=-1;
    public Stacks(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }
    public int peak(){
        return stack[top];
    }
    public Boolean isEmpty(){
        return top==-1;
    }
    public Boolean isFull(){
        return top==maxSize-1;
    }
    public void push(int a){
        if (isFull()){
            System.out.println("已满!!!");
            return;
        }
        top++;
        stack[top]=a;
    }
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("无数据警告!!!");
        }
        int value=stack[top];
        top--;
        return value;
    }
    public void list() {
        if (isEmpty()) {
            throw new RuntimeException("无数据警告!!!");
        }
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i] + " ");
        }
    }
    public int priority(int oper){
        if (oper=='*'||oper=='/'){
            return 1;
        }else if (oper=='+'||oper=='-'){
            return 0;
        }else {
            return -1;
        }
    }
    public Boolean isOper(char oper){
        return oper=='*'||oper=='/'||oper=='+'||oper=='-';
    }
    public int cal(int num1,int num2,int oper){
        int res=0;
        switch (oper){
            case '+':
                res=num1+num2;
                break;
            case '-' :
                res=num2-num1;
                break;
            case '*' :
                res=num1*num2;
                break;
            case '/' :
                res=num2/num1;
                break;
        }
        return res;
    }
}
2.3中缀表达式转后缀表达式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package DataStrucetures.Stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
import java.util.stream.Collectors;

public class PolandNatation {
    public static void main(String[] args) {
        String expression="1+((2+3)*4)-5";
        String[] arr = expression.split("");
        List<String> list = Arrays.stream(arr).collect(Collectors.toList());
        List<String> pas = getParseList(list);
        String[] s1=new String[pas.size()];
        int i=0;
        for (String pa : pas) {
            s1[i]=pa;
            i++;
        }
        System.out.println(cal(s1));

        //        System.out.println(cal(arr));
    }
    public static List<String> getParseList(List<String> Is){
        List<String> res = new ArrayList<>();
        Stack<String> s1 = new Stack<>();
        for (String ss: Is){
            if (ss.matches("\\d+")){
                res.add(ss);
            }else if (ss.equals("(")){
                s1.push(ss);
            }else if (ss.equals(")")){
                while (!s1.peek().equals("(")){
                    res.add(s1.pop());
                }
                s1.pop();
            }else {
                while (s1.size()!= 0&&Operation.getVlaue(s1.peek())>Operation.getVlaue(ss)){
                    res.add(s1.pop());
                }
                s1.push(ss);
            }
        }
        while (s1.size()!=0){
            res.add(s1.pop());
        }
        return res;
    }
    public static int cal(String[] arr){
        Stack<String> stack = new Stack<>();
        for (String s : arr) {
            if (s.matches("\\d+")) {
                stack.push(s);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (s.equals("+")) {
                    res = num1 + num2;
                } else if (s.equals("-")) {
                    res = num2 - num1;
                } else if (s.equals("*")) {
                    res = num1 * num2;
                } else if (s.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("表达式错误!!!!");
                }
                stack.push(String.valueOf(res));
            }

        }
        return Integer.parseInt(stack.pop());
    }
}
class Operation{
    private static int ADD=1;
    private static int SUB=1;
    private static int MUL=2;
    private static int DIV=2;
    public static int getVlaue(String str){
        int result = 0;
        switch (str){
            case "+":
                result=ADD;
                break;
            case "-":
                result=SUB;
                break;
            case "*":
                result=MUL;
                break;
            case "/":
                result=DIV;
                break;
            default:
                System.out.println("没有该运算符!!!!");
                break;
        }
        return result;
    }
}

3.递归

3.1迷宫问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package DataStrucetures.Recursion;

import java.util.Arrays;

public class maze {
    public static void main(String[] args) {
        int[][] ints = new int[8][7];
        for (int i = 0; i < 7; i++){
            ints[0][i] = 1;
            ints[7][i] = 1;
        }
        for (int i = 0; i < 8; i++){
            ints[i][0] = 1;
            ints[i][6] = 1;
        }
        ints[3][1]=1;
        ints[3][2]=1;
        for (int i=0;i<ints.length;i++){
            for (int j=0;j<ints[i].length;j++){
                System.out.print(ints[i][j]+" ");
            }
            System.out.println("");
        }
        getWay(ints,1,1);
        System.out.println("------------");
        for (int i=0;i<ints.length;i++){
            for (int j=0;j<ints[i].length;j++){
                System.out.print(ints[i][j]+" ");
            }
            System.out.println("");
        }
    }
    public static boolean getWay(int[][] map,int i,int j){
        if (map[6][5]==2){
            return true;
        }else if (map[i][j]==0){
            map[i][j]=2;
            //假设走得通
            if (getWay(map,i+1,j)){
                return true;
            }else if (getWay(map,i,j+1)){
                return true;
            }else if (getWay(map,i-1,j)){
                return true;
            }else if (getWay(map,i,j-1)){
                return true;
            }else {
                map[i][j]=3;
                return false;
            }
        }else {
            return false;
        }
    }
}

3.2八皇后问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
package DataStrucetures.Recursion;

public class Queen8 {
    static int max=8;
    static int[] array=new int[max];
    static int count=0;
    public static void main(String[] args) {
        check(0);
        System.out.println("共有"+count+"种结果");
    }

    public static void check(int n){
        if (n==max){
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            array[n]=i;
            if (judge(n)){
                check(n+1);
            }
        }
    }
    public static boolean judge(int n){
        for (int i = 0; i < n; i++) {
            if (array[i]==array[n]||Math.abs(n-i)==Math.abs(array[i]-array[n])){
                return false;
            }
        }
        return true;
    }
    public static void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
        }
        count++;
        System.out.println("");
        System.out.println("");
    }
}