数据结构算法C语言实现（三十二）--- 9.1静态查找表
一、简述
静态查找表又分为顺序表、有序表、静态树表和索引表。以下只是算法的简单实现及测试，不涉及性能分析。
二、头文件
1 /**
2 author：zhaoyu
3 date:2016-7-12
4 */
5 #include "6_3_part1_for_chapter9.h"
6 typedef struct {
7 int key;
8 }SElemType;
9 //静态查找表的顺序储存结构
10 #define ElemType SElemType
11 #define KeyType int
12 typedef struct {
13 ElemType *elem;//数据元素储存空间基址，0号留空
14 int length;//表长度
15 }SSTable;
16 //这里简化了键值
17 //实现 EQ
18 bool EQ(int a, int b)
19 {
20 return a==b?true:false;
21 }
22 bool LT(int a, int b)
23 {
24 return a<b?true:false;
25 }
26 //实现创建 SSTbale
27 void createSSTable(SSTable &T)
28 {
29 //先输入长度 length
30 //再输入 length 个 元素
31 scanf("%d", &T.length);
32 T.elem = (ElemType *)malloc((T.length + 10)*sizeof(int));
33 for (int i = 1; i <= T.length; i++)
34 {
35 scanf("%d", &T.elem[i].key);
36 }
37 }
38
39 /**
40 algorithm 9.1
41 */
42 int Search_Seq(SSTable ST, KeyType key)
43 {
44 //在顺序表 ST 中顺序查找关键值等于key的数据元素，
45 //若找到返回元素在表中位置，否则返回0
46 ST.elem[0].key = key;
47 int i;
48 for (i = ST.length; !EQ(ST.elem[i].key, key); --i);
49 return i;
50
51 }
52
53 /**
54 algorithm 9.2
55 */
56 int Search_Bin(SSTable ST, KeyType key)
57 {
58 //在有序表 ST 中折半查找其关键字等于 key 的数据元素
59 //找到返回其位置，否则返回 0
60 int low = 1;
61 int high = ST.length;
62 while (low <= high)
63 {
64 int mid = (low + high) / 2;
65 if (EQ(key, ST.elem[mid].key))
66 {
67 return mid;
68 }
69 else if (LT(key, ST.elem[mid].key))
70 {
71 high = mid - 1;
72 }
73 else
74 {
75 low = mid + 1;
76 }
77 }
78 return 0;
79 }
9_1_1.h
1 //6_3_part1.h
2 /**
3 author：zhaoyu
4 date:2016-6-18
5 */
6 #include "head.h"
7 #define TElemType char
8 //----二叉树的二叉链表表示----
9 typedef struct BiTNode{
10 TElemType data;
11 struct BiTNode *lchild, *rchild;
12 }*BiTree;
13 Status Visit(TElemType e)
14 {
15 printf("%c\t", e);
16 return OK;
17 }
18
19 Status RecursionPreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
20 {//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
21 //先序遍历二叉树 T 的递归算法
22 if (T)
23 {
24 if (Visit(T->data))
25 {
26 if (RecursionPreOrderTraverse(T->lchild, Visit))
27 {
28 if (RecursionPreOrderTraverse(T->rchild, Visit))
29 {
30 return OK;
31 }
32 }
33 }
34 return ERROR;//这一行由于 Visit 函数只 return OK，貌似没什么用
35 }
36 else
37 {
38 return OK;
39 }
40 }
6_3_part1_for_chapter9.h
1 #include "6_3_part1_for_chapter9.h"
2 typedef struct {
3 char key;
4 float weight;
5 }SElemType;
6
7 //静态查找表的顺序储存结构
8 #define ElemType SElemType
9 #define KeyType char
10 typedef struct {
11 ElemType *elem;//数据元素储存空间基址，0号留空
12 int length;//表长度
13 }SSTable;
14 //实现创建 SSTbale
15 void createSSTable(SSTable &ST)
16 {
17 //先输入长度 length
18 //再输入 length 个 元素
19 scanf("%d", &ST.length);\
20 getchar();//输入老师犯错误
21 ST.elem = (ElemType *)malloc((ST.length + 10)*sizeof(ElemType));
22 for (int i = 1; i <= ST.length; i++)
23 {
24 scanf("%c", &ST.elem[i].key);
25 getchar();
26 scanf("%f", &ST.elem[i].weight);
27 getchar();//很是懵逼
28 }
29 }
30 //my code
31 void FindSW(float *sw, SSTable ST)
32 {
33 float sum = 0;
34 for (int i = 1; i <= ST.length; i++)
35 {
36 sum += ST.elem[i].weight;
37 sw[i] = sum;
38 }
39 }
40
41
42 /**
43 algorithm 9.3
44 */
45 void SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high)
46 {
47 //由有序表R[low...high]及其累计权值表sw（其中sw[0]==0）递归构造次优查找树
48 int i = low;
49 float min = abs(sw[high] - sw[low]);
50 float dw = sw[high] + sw[low - 1];
51 for (int j = low + 1; j <= high; j++)
52 {
53 if (abs(dw-sw[j] - sw[j-1]) < min)
54 {
55 i = j;
56 min = abs(dw-sw[j] - sw[j-1]);
57 }
58 }
59 T = (BiTree)malloc(sizeof(BiTNode));
60 T->data = R[i].key;
61
62 if (i == low)
63 {
64 T->lchild = NULL;
65 }
66 else
67 {
68 SecondOptimal(T->lchild, R, sw, low, i-1);
69 }
70
71 if (i == high)
72 {
73 T->rchild = NULL;
74 }
75 else
76 {
77 SecondOptimal(T->rchild, R, sw, i+1, high);
78 }
79 }
80
81 /**
82 algorithm 9.4
83 */
84 typedef BiTree SOSTree;//次优查找树采用二叉链表的储存结构
85 Status CreateSOSTree(SOSTree &T, SSTable ST)
86 {
87 float sw[100];
88 //有有序表构造一颗次优查找树T， ST的数据元素含有域weight
89 if (0 == ST.length)
90 {
91 T = NULL;
92 }
93 else
94 {
95 FindSW(sw, ST);//按照由有序表ST中各数据元素的weight域求累计权值表sw
96 SecondOptimal(T, ST.elem, sw, 1, ST.length);
97 }
98 return OK;
99 }
9_1_2.h
三、CPP文件
1 #include "9_1_1.h"
2 int main(int argc, char const *argv[])
3 {
4 SSTable T;
5 createSSTable(T);
6 printf("Search 9:\t%d\n", Search_Seq(T, 9));
7 printf("Search 3:\t%d\n", Search_Bin(T, 3));
8 return 0;
9 }
9_1_1.cpp
1 #include "9_1_2.h"
2 int main(int argc, char const *argv[])
3 {
4 SOSTree T;
5 SSTable ST;
6 createSSTable(ST);
7 CreateSOSTree(T, ST);
8 RecursionPreOrderTraverse(T, Visit);
9 printf("\n");
10 return 0;
11 }
9_1_2.cpp
四、测试
静态树表
反思：
考完试，动力明显不足了，怎能半途而废，一定要把这个工程在回家之前完成。此外，对于一些不常用，或较难或书上说的比较的含糊的算法明显静不下心来好好研究。效率奇低。
