1 package iYou.neugle.search;
2
3 import java.util.ArrayList;
4 import java.util.List;
5
6 public class Index_search {
7 class IndexItem {
8 public int index;
9 public int start;
10 public int length;
11 }
12
13 public int m = 100;
14
15 public int[] table = new int[] { 101, 102, 103, 104, 105, 201, 202, 203,
16 204, 301, 302, 303 };
17
18 public List<IndexItem> indexTable = new ArrayList<Index_search.IndexItem>();
19
20 public static void main(String[] args) {
21 Index_search index = new Index_search();
22 // 创建索引
23 index.CreateIndex();
24 // 向索引表中插入数据
25 index.InsertIndex(205);
26 // 利用索引表查找数据
27 int result = index.SearchIndex(205);
28 System.out.println("索引位置为" + result);
29 }
30
31 public void CreateIndex() {
32 int[] type = new int[10000];
33 int[] typeNum = new int[10000];
34 for (int i = 0; i < this.table.length; i++) {
35 int n = this.table[i] / m - 1;
36 if (type[n] == 0) {
37 type[n] = 1;
38 }
39 typeNum[n]++;
40 }
41 int start = 0;
42 for (int i = 0; i < typeNum.length; i++) {
43 if (typeNum[i] == 0) {
44 break;
45 }
46 IndexItem item = new IndexItem();
47 item.index = i;
48 item.start = start;
49 item.length = typeNum[i];
50 indexTable.add(item);
51 start += typeNum[i];
52 }
53 }
54
55 public void InsertIndex(int key) {
56 int n = key / m - 1;
57 int index = -1;
58 // 更新索引表
59 for (int i = 0; i < this.indexTable.size(); i++) {
60 if (n == this.indexTable.get(i).index) {
61 index = this.indexTable.get(i).start
62 + this.indexTable.get(i).length;
63 this.indexTable.get(i).length++;
64 break;
65 }
66 }
67
68 for (int i = n + 1; i < this.indexTable.size(); i++) {
69 this.indexTable.get(i).start++;
70 }
71
72 // 更新数组
73 int[] temp = new int[this.table.length + 1];
74 for (int i = 0; i < temp.length; i++) {
75 if (i < index) {
76 temp[i] = this.table[i];
77 } else if (i == index) {
78 temp[i] = key;
79 } else {
80 temp[i] = this.table[i - 1];
81 }
82 }
83
84 this.table = temp;
85 }
86
87 public int SearchIndex(int key) {
88 int n = key / m - 1;
89 int start = -1;
90 int length = -1;
91 // 找到索引位置
92 for (int i = 0; i < this.indexTable.size(); i++) {
93 if (n == this.indexTable.get(i).index) {
94 start = this.indexTable.get(i).start;
95 length = this.indexTable.get(i).length;
96 break;
97 }
98 }
99
100 if (start == -1) {
101 return -1;
102 }
103 // 从索引位置找数据
104 for (int i = start; i < start + length; i++) {
105 if (this.table[i] == key) {
106 return i;
107 }
108 }
109 return -1;
110 }
111 }