(精华)2020年8月28日 数据结构与算法解析(分块查找)

分块查找要求是顺序表，分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

• 将n个数据元素"按块有序"划分为m块（m ≤ n）。
• 每一块中的结点不必有序，但块与块之间必须"按块有序"；
• 即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；
• 而第2块中任一元素又都必须小于第3块中的任一元素，……

1、先选取各块中的最大关键字构成一个索引表；
2、查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；
3、在已确定的块中用顺序法进行查找。

示例：

namespace IndexSearch.CSharp
{
    /// <summary>
    /// 索引项实体
    /// </summary>
    public class IndexItem
    {
        public int Index { get; set; } 

        public int Start { get; set; }

        public int Length { get; set; }

    }

    public class Program
    {
        /// <summary>
        /// 主表
        /// </summary>
        static int[] studentList = new int[] {
            101,102,103,104,105,0,0,0,0,0,
            201,202,203,204,0,0,0,0,0,0,
            301,302,303,0,0,0,0,0,0,0
        };

        /// <summary>
        /// 索引表
        /// </summary>
        static IndexItem[] IndexItemList = new IndexItem[] {
            new IndexItem{ Index=1,Start=0,Length=5},
            new IndexItem{ Index=2,Start=10,Length=4},
            new IndexItem{ Index=3,Start=20,Length=3}
        };

        /// <summary>
        /// 索引查找算法
        /// </summary>
        /// <param name="key">给定值</param>
        /// <returns>给定值在表中的位置</returns>
        public static int IndexSearch(int key)
        {
            IndexItem item = null;

            // 建立索引规则
            var index = key / 100;

            //遍历索引表,找到对应的索引项
            for (int i = 0; i < IndexItemList.Count(); i++)
            {
                //找到索引项
                if (IndexItemList[i].Index == index)
                {
                    item = new IndexItem() { Start = IndexItemList[i].Start, Length = IndexItemList[i].Length };
                    break;
                }
            }

            //索引表中不存在该索引项
            if (item == null)
                return -1;

            //在主表顺序查找
            for (int i = item.Start; i < item.Start + item.Length; i++)
            {
                if (studentList[i] == key)
                {
                    return i;
                }
            }
            return -1;
        }

        /// <summary>
        /// 插入数据
        /// </summary>
        /// <param name="key"></param>
        /// <returns>true,插入成功，false,插入失败</returns>
        public static bool Insert(int key)
        {
            IndexItem item = null;

            try
            {
                //建立索引规则
                var index = key / 100;

                int i = 0;

                //遍历索引表,找到对应的索引项
                for (i = 0; i < IndexItemList.Count(); i++)
                {
                    if (IndexItemList[i].Index == index)
                    {
                        item = new IndexItem()
                        {
                            Start = IndexItemList[i].Start,
                            Length = IndexItemList[i].Length
                        };
                        break;
                    }
                }

                //索引表中不存在该索引项
                if (item == null)
                    return false;

                //依索引项将值插入到主表中
                studentList[item.Start + item.Length] = key;

                //更新索引表
                IndexItemList[i].Length++;
            }
            catch
            {
                return false;
            }
            return true;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("********************索引查找(C#版)********************\n");
            Console.WriteLine("原始数据：{0}",String.Join(" ",studentList));

            int value = 205;
            Console.WriteLine("插入数据:{0}",value);
            //插入成功
            if (Insert(value))
            {
                Console.WriteLine("\n插入后数据:{0}",String.Join(",", studentList));
                Console.WriteLine("\n元素205在列表中的位置为:{0} ",IndexSearch(value));
            }

            Console.ReadKey();
        }
    }
}

  

 

  
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
 

时间复杂度：O(log(m)+N/m)

文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。

原文链接：codeboy.blog.csdn.net/article/details/108280056