网状数据结构

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
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
package com.hulinjun.springbootdemo.util;

import java.util.*;

public class GuoRuiUtil {

    public static void main(String[] args) {
        /*List<Map<String, String>> map1 = create(2, 5,3);
        List<Map<String,String>> o = new ArrayList<>();
        o.addAll(map1);
        List<Map<String, String>> map2 = create(3, 5,2);
        o.addAll(map2);
        //假设出现交叉
        //o.addAll(create(200000004,20));
        String initId = "6";*/
        //        List<Map<String, String>> map1 = create(2, 3,3);
        List<Map<String,String>> o = new ArrayList<>();
//        o.addAll(map1);
//        List<Map<String, String>> map2 = create(3, 5,2);
//        o.addAll(map2);
        //假设出现交叉
        //o.addAll(create(200000004,20));
        Map m = new HashMap();
        m.put("FROM","13800001538726"+"");
        m.put("TO","13800012502252"+"");
        o.add(m);
        Map m1 = new HashMap();
        m1.put("FROM","13800012502252"+"");
        m1.put("TO","13800006454281"+"");
        o.add(m1);
        Map m2 = new HashMap();
        m2.put("FROM","13310000001234"+"");
        m2.put("TO","13320000000091"+"");
        o.add(m2);
        Map m3 = new HashMap();
        m3.put("FROM","13800006454281"+"");
        m3.put("TO","13800002096649"+"");
        o.add(m3);
        Map m4= new HashMap();
        m4.put("FROM","13320000000091"+"");
        m4.put("TO","13320000000091"+"");
        o.add(m4);
        Map m5 = new HashMap();
        m5.put("FROM","13800002096649"+"");
        m5.put("TO","13320000000091"+"");
        o.add(m5);
        Map m6 = new HashMap();
        m6.put("FROM","13800023928215"+"");
        m6.put("TO","13310000001234"+"");
        o.add(m6);
        Map m7 = new HashMap();
        m7.put("FROM","13800009355365"+"");
        m7.put("TO","13800023928215"+"");
        o.add(m7);
        Map m8 = new HashMap();
        m8.put("FROM","13800003107424"+"");
        m8.put("TO","13800009355365"+"");
        o.add(m8);
        Map m9 = new HashMap();
        m9.put("FROM","13800003107426"+"");
        m9.put("TO","13800012502252"+"");
        o.add(m9);

        Map m10 = new HashMap();
        m10.put("FROM","13800003107426"+"");
        m10.put("TO","13800003107427"+"");
        o.add(m10);
        String initId = "13800006454281";
        Map<String,ListNode> d = new HashMap<>();
        find(initId,o,d);
        ListNode listNode = d.get(initId);
        List<String[]> strings = listNode.toList();
        for (String[] string : strings) {
            System.out.println(Arrays.toString(string));
        }
    }
    static void find(String initId , List<Map<String,String>> o,Map<String,ListNode> d){
        for (int i = o.size() -1; i >= 0 ; i--) {
            Map<String, String> m = o.get(i);
            String from = m.get("FROM");//获取到父节点
            String to = m.get("TO");//获取到子节点
            if(from.equals(to))continue;//如果重复会出现闭环
            if(d.get(from)==null)d.put(from,new ListNode(from));//备份
            if(d.get(to)==null)d.put(to,new ListNode(to));//备份
            i = findInner(initId, o, d, i, from, to);
            i = findInner(initId, o, d, i, to, from);
        }
    }

    private static int findInner(String initId, List<Map<String, String>> o, Map<String, ListNode> d, int i, String from, String to) {
        if (initId.equals(from)) {//如果找到初始ID
            //从dataMap里捞出变量 将他的next节点设置为to //添加一条链子
            d.get(from).add(d.get(to));
            o.remove(i);//移出数据
            i--;
            //开始递归
            find(to, o, d);
        }
        return i;
    }


    static List<Map<String,String>> create(int initId ,int size, int addNum){
        List<Map<String,String>> list = new ArrayList<>();
        boolean flag = false;
        for (int i = 0; i < size; i++) {
            Map m = new HashMap();
           if(!flag){
               m.put("FROM",initId+"");
               initId*=addNum;
               m.put("TO",initId+"");
           }else{
               m.put("TO",initId+"");
               initId*=addNum;
               m.put("FROM",initId+"");
           }
            flag = !flag;
           list.add(m);
        }
        return list;
    }
}

class ListNode{
    private String id;
    private List<ListNode> nexts = new ArrayList<>() ;

    public ListNode(String id) {
        this.id = id;
    }

    public String getId() {
        return id;
    }

    public void setId(String id) {
        this.id = id;
    }

    public List<ListNode> getNext() {
        return nexts;
    }

    public void setNext(List<ListNode> nexts) {
        this.nexts = nexts;
    }

    public void add(ListNode next){
        nexts.add(next);//添加一条链子
    }

    public List<String[]> toList(){
        LinkedList<String>nodess = new LinkedList<>();
        List<String[]> result = new ArrayList<>();
        try {
            nodess.add(this.getId());//一条链子都没有
            exec(nodess,this);
            result = new ArrayList<>();
            for (String nodesInfo : nodess) {
                System.out.println(nodesInfo);
                result.add(nodesInfo.split("==>"));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return result;

    }

    public void exec(LinkedList<String> list,ListNode node){
        int size = node.nexts.size();
        if(size > 0){
            //先取出原来的数据
            String s = list.removeLast();
            for (int i = 0; i < size; i++) {
                ListNode listNode = node.nexts.get(i);
                list.add(s+"==>"+listNode.getId());//加入数据
                exec(list,listNode);
            }
        }

    }
}