静态查找表

2023-10-16 18:52:16

一、顺序查找

1.若有等概率的n条记录，则查找成功时的平均查找长度：

ASL = ( n + 1 ) / 2;

2.设置监视哨(把查找表下标为0的位置设置为待查找的关键字),目的在于免去每一步都要检测整个表是否查找完毕。

3.实现：

 1 int SequentialSearch(SSTable T, int key)
 2 {
 3     int i = T.length;
 4     T.elem[0].key = key;//设置哨兵
 5     while (T.elem[i].key != key)
 6     {
 7         i--;
 8     }
 9     return i;
10 }

二、折半查找

1.必须是有序表

2.若有等概率的n条记录，则查找成功时的平均查找长度:

ASL = log₂(n + 1) - 1;     //当n > 50时，可以近似等于该式

3.实现：

int BinarySearch(SSTable T, int key)
{
    int mid = 0, low = 1;
    int high = T.length;
    PopSort(&T);//从小到大冒泡排序
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (T.elem[mid].key == key)
        {
            return mid;
        }
        else if (T.elem[mid].key < key)//右区间
        {
            low = mid + 1;
        }
        else//左区间
        {
            high = mid - 1;
        }
    }
    return 0;
}

三、次优查找树

1.必须是有序表

2.若有不等概率的n条记录，则查找成功时的平均查找长度：

3.由于C_i 的大小和判定树的构造有关，则查找成功时查找性能最优的判定树是其带权内路径长度之和 PH值最小的二叉树

4.由于构造静态最优查找树花费的时间代价较高，这里采用构造次优查找树

(设：下标为0的位置权值为0，则首项记录下标为low = 1，最后一项记录下标为high)

①求出各记录的累计权值和SW = 前n项记录的权值和；

②求出各记录的 ΔP_i = abs( SW[high] + SW[low - 1] - SW_i - SW_{i - 1} );

③次优查找树的根 = min( ΔP_i );

④若 i = low，则该树的左子树为空，否则令 high = i - 1继续递归构造左子树；

⑤若 i = high，则该树的右子树为空，否则令 low = i + 1继续递归构造右子树；

5.实现

求累计权值表

1 void GetSumWeight(SSTable S, int* sw)
2 {
3     int i = 0, sum = 0;
4     for (i = 0; i <= S.length; i++)
5     {
6         sum += S.elem[i].weight;
7         sw[i] = sum;
8     }
9 }

构造次优查找树

 1 void SecondOptimal(BTree* BT, SSTable S, int* sw, int low, int high)
 2 {//由有序表S及其累计权值表sw(其中sw[0]=0)递归构造次优查找树BT
 3     int i = low, j = low + 1;
 4     int min = abs(sw[high] - sw[low]);
 5     int dw = sw[high] + sw[low - 1];
 6     //寻根i
 7     for (j = low + 1; j <= high; j++)
 8     {
 9         if (abs(dw - sw[j] - sw[j - 1]) < min)//选择最小的PH(带权内路径长度之和)
10         {
11             i = j;
12             min = abs(dw - sw[j] - sw[j - 1]);
13         }
14     }
15     //构造次优查找树
16     (*BT) = (BTree)calloc(1, sizeof(BTNode));
17     (*BT)->data = S.elem[i].key;
18     if (i == low)
19     {
20         (*BT)->Lchild = NULL;
21     }
22     else
23     {
24         SecondOptimal(&((*BT)->Lchild), S, sw, low, i - 1);
25     }
26     if (i == high)
27     {
28         (*BT)->Rchild = NULL;
29     }
30     else
31     {
32         SecondOptimal(&((*BT)->Rchild), S, sw, i + 1, high);
33     }
34 }

四、源代码

生成随机数据至文件

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <time.h>
 5 #define DATASIZE 100
 6 
 7 int main(void)
 8 {
 9     int i = 0;
10     FILE* fp = fopen("D:\\C\\数据结构与算法\\7.查找\\test case.txt", "w");
11     srand((unsigned)time(NULL));
12     for (i = 0; i < DATASIZE; i++)
13     {
14         fprintf(fp, "%d ", rand() % 100);
15     }
16     fclose(fp);
17     return 0;
18 }

生成随机数据

查找静态查找表

  1 #define _CRT_SECURE_NO_WARNINGS
  2 #include <stdio.h>
  3 #include <stdlib.h>
  4 #define DATASIZE 100
  5 
  6 typedef struct
  7 {
  8     int key;
  9     int weight;
 10 }RecodeType;
 11 
 12 typedef struct
 13 {
 14     RecodeType elem[DATASIZE + 1];//0号位置不存储记录
 15     int length;
 16 }SSTable;//Static Search Table
 17 
 18 typedef struct Node
 19 {
 20     int data;
 21     struct Node* Lchild;
 22     struct Node* Rchild;
 23 }BTNode, *BTree;//Binary Tree Node
 24 
 25 int SequentialSearch(SSTable T, int key)//顺序表表示静态查找表
 26 {
 27     int i = T.length;
 28     T.elem[0].key = key;//设置哨兵
 29     while (T.elem[i].key != key)
 30     {
 31         i--;
 32     }
 33     return i;
 34 }
 35 
 36 void PopSort(SSTable* T)
 37 {
 38     int temp = 0;
 39     int i = 0, j = 0;
 40     for (i = 1; i < T->length; i++)
 41     {
 42         for (j = 1; j <= T->length - i; j++)
 43         {
 44             if (T->elem[j].key > T->elem[j + 1].key)
 45             {
 46                 temp = T->elem[j].key;
 47                 T->elem[j].key = T->elem[j + 1].key;
 48                 T->elem[j + 1].key = temp;
 49             }
 50         }
 51     }
 52 }
 53 
 54 int BinarySearch(SSTable T, int key)//有序表表示静态查找表
 55 {
 56     int mid = 0, low = 1;
 57     int high = T.length;
 58     PopSort(&T);//从小到大冒泡排序
 59     while (low <= high)
 60     {
 61         mid = (low + high) / 2;
 62         if (T.elem[mid].key == key)
 63         {
 64             return mid;
 65         }
 66         else if (T.elem[mid].key < key)//右区间
 67         {
 68             low = mid + 1;
 69         }
 70         else//左区间
 71         {
 72             high = mid - 1;
 73         }
 74     }
 75     return 0;
 76 }
 77 
 78 void GetWeight(SSTable T, SSTable* S)
 79 {
 80     int i = 1, j = 1;
 81     PopSort(&T);
 82     //首个元素
 83     S->elem[1].key = T.elem[1].key;
 84     S->elem[1].weight = 1;
 85     //其余元素
 86     for (i = 2; i <= T.length; i++)
 87     {
 88         if (T.elem[i].key == S->elem[j].key)
 89         {
 90             S->elem[j].weight++;
 91         }
 92         else
 93         {
 94             j++;
 95             S->elem[j].key = T.elem[i].key;
 96             S->elem[j].weight = 1;
 97         }
 98     }
 99     S->length = j;
100 }
101 
102 void GetSumWeight(SSTable S, int* sw)
103 {
104     int i = 0, sum = 0;
105     for (i = 0; i <= S.length; i++)
106     {
107         sum += S.elem[i].weight;
108         sw[i] = sum;
109     }
110 }
111 
112 void RecodeData(SSTable* T)//录入数据
113 {
114     int i = 0;
115     FILE* fp = NULL;
116     T->length = DATASIZE;
117     fp = fopen("D:\\C\\数据结构与算法\\7.查找\\test case.txt", "r");
118     for (i = 1; i <= T->length; i++)
119     {
120         fscanf(fp, "%d", &T->elem[i].key);
121     }
122     fclose(fp);
123 }
124 
125 void InitSSTable(SSTable* T)
126 {
127     int i = 0;
128     T->length = 0;
129     for (i = 0; i < DATASIZE + 1; i++)
130     {
131         T->elem[i].key = 0;
132         T->elem[i].weight = 0;
133     }
134 }
135 
136 void SecondOptimal(BTree* BT, SSTable S, int* sw, int low, int high)
137 {//由有序表S及其累计权值表sw(其中sw[0]=0)递归构造次优查找树BT
138     int i = low, j = low + 1;
139     int min = abs(sw[high] - sw[low]);
140     int dw = sw[high] + sw[low - 1];
141     //寻根i
142     for (j = low + 1; j <= high; j++)
143     {
144         if (abs(dw - sw[j] - sw[j - 1]) < min)//选择最小的PH(带权内路径长度之和)
145         {
146             i = j;
147             min = abs(dw - sw[j] - sw[j - 1]);
148         }
149     }
150     //构造次优查找树
151     (*BT) = (BTree)calloc(1, sizeof(BTNode));
152     (*BT)->data = S.elem[i].key;
153     if (i == low)
154     {
155         (*BT)->Lchild = NULL;
156     }
157     else
158     {
159         SecondOptimal(&((*BT)->Lchild), S, sw, low, i - 1);
160     }
161     if (i == high)
162     {
163         (*BT)->Rchild = NULL;
164     }
165     else
166     {
167         SecondOptimal(&((*BT)->Rchild), S, sw, i + 1, high);
168     }
169 }
170 
171 BTree SecondOptimalSearch(SSTable T, int key)
172 {
173     SSTable S;//带权值静态查找表
174     BTree BT = NULL;//次优查找树
175     BTree P = NULL;
176     int* sw = NULL;//累次权值表
177 
178     InitSSTable(&S);
179     GetWeight(T, &S);
180     sw = (int*)calloc(S.length, sizeof(int));
181     GetSumWeight(S, sw);//根据权值求累次权值表sw
182     SecondOptimal(&BT, S, sw, 1, S.length);//创建次优查找树
183 
184     P = BT;
185     while (P)    //在次优查找树中查找关键字key
186     {
187         if (P->data == key)
188         {
189             return P;
190         }
191         if (P->data < key)
192         {
193             P = P->Rchild;
194         }
195         else
196         {
197             P = P->Lchild;
198         }
199     }
200     return P;
201 }
202 
203 int main(void)
204 {
205     SSTable T;
206     int key = 0;
207 
208     InitSSTable(&T);
209     RecodeData(&T);
210     printf("请输入待查找的关键字：");
211     scanf("%d", &key);
212 
213     if (SequentialSearch(T, key)) //顺序表查找
214     {
215         printf("顺序表查找成功\n");
216     }
217 
218     if (BinarySearch(T, key)) //有序表查找
219     {
220         printf("有序表查找成功\n");
221     }
222 
223     if (SecondOptimalSearch(T, key))//静态树表查找
224     {
225         printf("静态树表查找成功");
226     }
227     return 0;
228 }

静态查找表

五、参考资料

《数据结构C语言版(严蔚敏)》

码农公寓

相关文章