数据结构 折半查找
实例代码：
|
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
|
/* 名称：折半查找 语言：数据结构C语言版 编译环境：VC++ 6.0 日期： 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define N 11 // 数据元素个数 typedef int KeyType; // 设关键字域为整型 typedef struct // 数据元素类型 { KeyType key; // 关键字域 int others; // 其它部分 }ElemType; // Search_Seq.h 静态查找表的顺序存储结构 typedef struct{ // 数据元素存储空间基址，建表时按实际长度分配，0号单元留空 ElemType *elem; int length; // 表长度 }SSTable; ElemType r[N]={ {05,1},{13,2},{19,3},{21,4}, {37,5},{56,6},{64,7},{75,8}, {80,9},{88,10},{92,11} }; // 数据元素(以教科书P219的数据为例),全局变量 // 静态查找表(顺序表和有序表)的基本操作(7个) // 构造一个含n个数据元素的静态顺序查找表ST(数据来自全局数组r) int Creat_Seq(SSTable *ST,int n) { int i; (*ST).elem = (ElemType *)calloc(n+1, sizeof(ElemType)); // 动态生成n+1个数据元素空间(0号单元不用) if(!(*ST).elem) return 0; for( i = 1; i <= n; i++) *((*ST).elem+i) = r[i-1]; // 将全局数组r的值依次赋给ST (*ST).length = n; return 1; } // 重建静态查找表为按关键字非降序排序 void Ascend(SSTable *ST) { int i, j, k; for(i = 1; i < (*ST).length; i++) { k = i; (*ST).elem[0] = (*ST).elem[i]; // 待比较值存[0]单元 for(j = i+1; j <= (*ST).length; j++) //从中找到第i小的值 if ((*ST).elem[j].key < (*ST).elem[0].key) { k=j; (*ST).elem[0]=(*ST).elem[j]; } if(k != i) // 有更小的值则交换 { (*ST).elem[k]=(*ST).elem[i]; (*ST).elem[i]=(*ST).elem[0]; } } } // 构造一个含n个数据元素的静态按关键字非降序查找表ST, // 数据来自全局数组r int Creat_Ord(SSTable *ST,int n) { int f; f = Creat_Seq(ST,n); //构建一个静态表 if( f ) //静态表存在，则对其进行重建 Ascend(ST); return f; } // 销毁表ST int Destroy(SSTable *ST) { free((*ST).elem); (*ST).elem = NULL; (*ST).length = 0; return 1; } // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数 // 值为该元素在表中的位置，否则为0。 int Search_Bin(SSTable ST,KeyType key) { int low, high, mid; low = 1; // 置区间初值 high = ST.length; while(low <= high) { mid = (low + high) / 2; if(key == ST.elem[mid].key) // 找到待查元素 return mid; else if(key < ST.elem[mid].key) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // 按顺序对ST的每个元素调用函数Visit()一次且仅一次。 int Traverse(SSTable ST,void(*Visit)(ElemType)) { ElemType *p; int i; p = ++ST.elem; // p指向第一个元素,第0个元素没有用 for(i = 1; i <= ST.length; i++) Visit( *p++ ); return 1; } void print(ElemType c) // Traverse()调用的函数 { printf("(%d %d) ", c.key, c.others); } int main() { SSTable st; int i; KeyType s; Creat_Ord(&st, N); // 由全局数组产生非降序静态查找表st Traverse(st,print); // 顺序输出非降序静态查找表st printf("\n请输入待查找值的关键字: "); scanf("%d", &s); i = Search_Bin(st, s); // 折半查找有序表 if( i ) print(st.elem[i]); else printf("没找到.\n"); Destroy(&st); system("pause"); return 0; } /* 输出效果： (5 1) (13 2) (19 3) (21 4) (37 5) (56 6) (64 7) (75 8) (80 9) (88 10) (92 11) 请输入待查找值的关键字: 75 (75 8) 请按任意键继续. . . */ |
运行结果如下：
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
