問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2531思路:
更像是枚舉的搜索，外加一個簡單的對稱性減枝，不過耗時比較久
代碼:
1 #define MAX_NUM 21
2 int matrix[MAX_NUM][MAX_NUM];
3 int mark[MAX_NUM], mark_num;
4 int num, max;
5
6 int
7 calculate()
8 {
9 int i, j;
10 int sum = 0;
11 for(i=0; i<num; i++)
12 if(mark[i]) {
13 for(j=0; j<num; j++)
14 if(!mark[j])
15 sum += matrix[i][j];
16 }
17 return sum;
18 }
19
20 void
21 dfs(int depth)
22 {
23 int rt;
24 if(depth == num) {
25 rt = calculate();
26 max = rt>max ? rt : max;
27 return;
28 }
29 ++mark_num;
30 mark[depth] = 1; /* mark[depth]=1, put 'depth' into the category I */
31 if(mark_num <= (num>>1)) /* pruning */
32 dfs(depth+1);
33 --mark_num;
34 mark[depth] = 0;
35 dfs(depth+1); /* put 'depth' into the category II */
36 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1606http://acm.pku.edu.cn/JudgeOnline/problem?id=3414思路:
典型的BFS
好玩的就是如何來處理輸出，每個狀態包含一個指向前一個狀態的指針
代碼:
1 #define QUEUE_LEN 10000
2 #define MAX_VOL 101
3 const char ops[][12] = {
4 "FILL(1)",
5 "FILL(2)",
6 "DROP(1)",
7 "DROP(2)",
8 "POUR(1,2)",
9 "POUR(2,1)" };
10 int vola, volb, target;
11 int head, tail;
12 int visited[MAX_VOL][MAX_VOL];
13 struct EACH {
14 int a, b;
15 int opnum;
16 int opidx;
17 struct EACH *pre;
18 } queue[QUEUE_LEN];
19
20 #define ADD(na, nb, num, idx) ++tail; \
21 queue[tail].a = na; \
22 queue[tail].b = nb; \
23 queue[tail].opnum = num+1; \
24 queue[tail].opidx = idx; \
25 queue[tail].pre = queue+head; \
26 visited[na][nb] = 1;
27
28 void
29 output(struct EACH *item)
30 {
31 if(item == NULL)
32 return;
33 output(item->pre);
34 if(item->opidx >= 0)
35 printf("%s\n", ops[item->opidx]);
36 }
37
38 void
39 bfs()
40 {
41 int cur_a, cur_b, ta, tb, cur_opnum;
42 queue[tail].a = 0;
43 queue[tail].b = 0;
44 queue[tail].opnum = 0;
45 queue[tail].opidx = -1;
46 queue[tail].pre = NULL;
47 visited[0][0] = 1;
48 while(head < tail) {
49 ++head;
50 cur_a = queue[head].a;
51 cur_b = queue[head].b;
52 cur_opnum = queue[head].opnum;
53 if(cur_a==target || cur_b==target) {
54 printf("%d\n", cur_opnum);
55 output(queue+head);
56 return;
57 }
58 if(!visited[vola][cur_b]) { /* FILL(1) */
59 ADD(vola, cur_b, cur_opnum, 0);
60 }
61 if(!visited[cur_a][volb]) { /* FILL(2) */
62 ADD(cur_a, volb, cur_opnum, 1);
63 }
64 if(!visited[0][cur_b]) { /* DROP(1) */
65 ADD(0, cur_b, cur_opnum, 2);
66 }
67 if(!visited[cur_a][0]) { /* DROP(2) */
68 ADD(cur_a, 0, cur_opnum, 3);
69 }
70 /* POUR(1,2) */
71 if(cur_a+cur_b > volb) {
72 ta = cur_a+cur_b-volb;
73 tb = volb;
74 if(!visited[ta][tb]) {
75 ADD(ta, tb, cur_opnum, 4);
76 }
77 } else {
78 ta = 0;
79 tb = cur_a + cur_b;
80 if(!visited[ta][tb]) {
81 ADD(ta, tb, cur_opnum, 4);
82 }
83 }
84 /* POUR(2,1) */
85 if(cur_a+cur_b > vola) {
86 ta = vola;
87 tb = cur_a+cur_b-vola;
88 if(!visited[ta][tb]) {
89 ADD(ta, tb, cur_opnum, 5);
90 }
91 } else {
92 ta = cur_a + cur_b;
93 tb = 0;
94 if(!visited[ta][tb]) {
95 ADD(ta, tb, cur_opnum, 5);
96 }
97 }
98 }
99 printf("impossible\n");
100 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3083思路:
對于求最短路徑，BFS即可解決，沒有什么難度
該題的難點在于如何求沿左、沿右走的問題
剛開始，完全不知道這是什么意思，無奈只能在網上看代碼，總結如下:
沿左策略的一般次序: left, up, right, down
沿右策略的一般次序: right, up, left, down
求解的關鍵是如何根據前一個方向以及一般次序來決定目前訪問上下左右四個方向的順序，例如:
對于沿左前進策略，如果前一個方向是right，那么訪問次序是up, right, down, left(與前一個方向相反的方向總是放在最后)
代碼:
1 #define MAX_LEN 42
2 #define QUEUE_LEN 1600
3 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
4 char maze[MAX_LEN][MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col;
7 int start_x, start_y;
8 /* left, up, right, down */
9 const int dx[] = {0, -1, 0, 1};
10 const int dy[] = {-1, 0, 1, 0};
11 /* right, up, left, down */
12 const int dx_right[] = {0, -1, 0, 1};
13 const int dy_right[] = {1, 0, -1, 0};
14 int lcount, rcount;
15 int head, tail;
16 struct EACH {
17 int x, y;
18 int mv;
19 } queue[QUEUE_LEN];
20
21
22 void
23 init()
24 {
25 int i;
26 char *p;
27 memset(visited, 0, sizeof(visited));
28 head = -1;
29 tail = 0;
30 lcount = rcount = 0;
31 scanf("%d %d", &col, &row);
32 for(i=0; i<row; i++) {
33 scanf("%s", maze[i]);
34 if((p=strchr(maze[i], 'S')) != NULL) {
35 start_x = i;
36 start_y = p-maze[i];
37 }
38 }
39 }
40
41 /*
42 * dir: previous direction
43 * switch(dir):
44 * case(right): up right down left (order)
45 * case(up): left up right down
46 * case(left): down left up right
47 * case(down): right down left up
48 */
49 void
50 dfs_left(int x, int y, int dir)
51 {
52 int i, tx, ty;
53 ++lcount;
54 if(maze[x][y] == 'E') {
55 return;
56 }
57 dir = (dir+3)%4;
58 for(i=0; i<4; i++) {
59 tx = x + dx[(dir+i)%4];
60 ty = y + dy[(dir+i)%4];
61 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
62 dfs_left(tx, ty, (dir+i)%4);
63 break;
64 }
65 }
66 }
67
68 void
69 dfs_right(int x, int y, int dir)
70 {
71 int i, tx, ty;
72 ++rcount;
73 if(maze[x][y] == 'E')
74 return;
75 dir = (dir+3)%4;
76 for(i=0; i<4; i++) {
77 tx = x + dx_right[(dir+i)%4];
78 ty = y + dy_right[(dir+i)%4];
79 if(is_valid(tx, ty) && maze[tx][ty]!='#') {
80 dfs_right(tx, ty, (dir+i)%4);
81 break;
82 }
83 }
84 }
85
86 int
87 bfs()
88 {
89 int i, cx, cy, tx, ty, cmv;
90 memset(visited, 0, sizeof(visited));
91 queue[tail].x = start_x;
92 queue[tail].y = start_y;
93 queue[tail].mv = 1;
94 visited[start_x][start_y] = 1;
95 while(head < tail) {
96 ++head;
97 cx = queue[head].x;
98 cy = queue[head].y;
99 cmv = queue[head].mv;
100 if(maze[cx][cy] == 'E')
101 return cmv;
102 for(i=0; i<4; i++) {
103 tx = cx + dx[i];
104 ty = cy + dy[i];
105 if(is_valid(tx, ty) && !visited[tx][ty] && maze[tx][ty]!='#') {
106 ++tail;
107 queue[tail].x = tx;
108 queue[tail].y = ty;
109 queue[tail].mv = cmv+1;
110 visited[tx][ty] = 1;
111 }
112 }
113 }
114 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3009思路:
這題要求進行一個簡單的游戲，判斷最優步數。通常來說，這種判斷最短步驟的問題可以使用廣度優先搜索解決(bfs),由于題目中地圖會由于游戲的進行發生變化，使用bfs會比較麻煩（需要記錄地圖狀態），注意到題目中有一個條件：只能在10步以內完成游戲，于是我們可以考慮使用深度優先搜索（dfs）+限制步數來完成。簡單的說：就是我們遍歷整個搜索樹尋找可能解中的最優步數，但當搜索樹深度大于10時則不必繼續搜索下去。
代碼:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 #define INF 100000
3 #define THROW_MAX 10
4 #define MAX_LEN 21
5 int row, col, start_x, start_y;
6 int board[MAX_LEN][MAX_LEN];
7 int min;
8 const int dx[] = {0, 0, -1, 1};
9 const int dy[] = {-1, 1, 0, 0};
10
11 void
12 dfs(int depth, int x, int y)
13 {
14 int i, tx, ty;
15 if(depth>=THROW_MAX || depth>=min) /* pruning */
16 return;
17 for(i=0; i<4; i++) {
18 tx = x;
19 ty = y;
20 if(board[tx+dx[i]][ty+dy[i]] == 1) /* block immediately */
21 continue;
22 do {
23 tx += dx[i];
24 ty += dy[i];
25 if(is_valid(tx, ty) && board[tx][ty] == 3) { /* end */
26 min = depth+1;
27 return;
28 }
29 } while(is_valid(tx, ty) && board[tx][ty]!=1);
30 if(is_valid(tx, ty)) {
31 board[tx][ty] = 0; /* the block disappears */
32 dfs(depth+1, tx-dx[i], ty-dy[i]);
33 board[tx][ty] = 1;
34 }
35 }
36 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2488思路:
十分熟悉的DFS
需要注意的一點是: 字典序，所以八個方向的搜索次序不是任意的，從左向右，從上到下，這里定義:
1 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
2 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
另外，我覺得只有從任何一個點出發都沒法遍歷，才應該輸出impossible
不過，看了網上的代碼，都只需要從左上角出發即可得出結論
代碼:
1 #define is_valid(x, y) (x>=0 && x<row && y>=0 && y<col)
2 struct Item {
3 int x, y;
4 } path[MAX_LEN];
5 int visited[MAX_LEN][MAX_LEN];
6 int row, col, flag;
7 const int dx[] = {-1, 1, -2, 2, -2, 2, -1, 1};
8 const int dy[] = {-2, -2, -1, -1, 1, 1, 2, 2};
9
10 void
11 dfs(int depth, int x, int y)
12 {
13 int i, tx, ty;
14 visited[x][y] = 1;
15 path[depth].x = x;
16 path[depth].y = y;
17 if(depth+1 == row*col) {
18 if(!flag) {
19 flag = 1;
20 for(i=0; i<row*col; i++)
21 printf("%c%d", 'A'+path[i].y, path[i].x+1);
22 printf("\n");
23 }
24 }
25 if(!flag) {
26 for(i=0; i<8; i++) {
27 tx = x + dx[i];
28 ty = y + dy[i];
29 if(is_valid(tx, ty) && !visited[tx][ty])
30 dfs(depth+1, tx, ty);
31 }
32 }
33 visited[x][y] = 0;
34 }
35
36 void
37 solve()
38 {
39 int i, j;
40 memset(visited, 0, sizeof(visited));
41 flag = 0;
42 for(i=0; i<row; i++)
43 for(j=0; j<col; j++)
44 if(!flag)
45 dfs(0, i, j);
46 if(!flag)
47 printf("impossible\n");
48 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2251思路:
三維的迷宮
其實，該題是典型的BFS
不過由于二維迷宮的影響以及網上題目分類的誤導，開始直接DFS，結果TLE
值得小慶祝一番的是: 這是AC的第50題(*^__^*) 嘻嘻……，繼續加油
代碼:
TLE的DFS
1 void
2 dfs(int sl, int sr, int sc, int m)
3 {
4 if(m >= min) /* pruning */
5 return;
6 if(sl==end_l && sr==end_r && sc==end_c) {
7 min = m;
8 return;
9 }
10 int i, tl, tr, tc;
11 for(i=0; i<6; i++) {
12 tl = sl + dl[i];
13 tr = sr + dr[i];
14 tc = sc + dc[i];
15 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
16 visited[tl][tr][tc] = 1;
17 dfs(tl, tr, tc, m+1);
18 visited[tl][tr][tc] = 0;
19 }
20 }
21 }
AC的BFS
1 #define MAX_SIZE 31
2 #define QUEUE_SIZE 100000
3 #define is_valid(l, r, c) (l>=0 && l<level && r>=0 && r<row && c>=0 && c<column)
4 char maze[MAX_SIZE][MAX_SIZE][MAX_SIZE];
5 int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE];
6 int level, row, column;
7 int begin_l, begin_r, begin_c;
8 int end_l, end_r, end_c;
9 /* direction: north, south, west, east, up, down */
10 const int dl[] = {0, 0, 0, 0, -1, 1};
11 const int dr[] = {-1, 1, 0, 0, 0, 0};
12 const int dc[] = {0, 0, -1, 1, 0, 0};
13 struct EACH {
14 int l, r, c;
15 int mins;
16 } queue[QUEUE_SIZE];
17 int head, tail;
18
19
20 void
21 init()
22 {
23 int i, j;
24 char *p;
25 memset(visited, 0, sizeof(visited));
26 memset(queue, 0, sizeof(queue));
27 head = -1;
28 tail = 0;
29 for(i=0; i<level; i++) {
30 for(j=0; j<row; j++) {
31 scanf("%s", maze[i][j]);
32 if((p=strchr(maze[i][j], 'S')) != NULL) {
33 begin_l = i;
34 begin_r = j;
35 begin_c = p-maze[i][j];
36 }
37 if((p=strchr(maze[i][j], 'E')) != NULL) {
38 end_l = i;
39 end_r = j;
40 end_c = p-maze[i][j];
41 }
42 }
43 getchar();
44 }
45 }
46
47 int
48 bfs()
49 {
50 int i, tl, tr, tc, cl, cr, cc, cm;
51 queue[tail].l = begin_l;
52 queue[tail].r = begin_r;
53 queue[tail].c = begin_c;
54 queue[tail].mins = 0;
55 visited[begin_l][begin_r][begin_c] = 1;
56 while(head < tail) {
57 ++head;
58 cl = queue[head].l;
59 cr = queue[head].r;
60 cc = queue[head].c;
61 cm = queue[head].mins;
62 if(cl==end_l && cr==end_r && cc==end_c)
63 return cm;
64 for(i=0; i<6; i++) {
65 tl = cl + dl[i];
66 tr = cr + dr[i];
67 tc = cc + dc[i];
68 if(is_valid(tl, tr, tc) && !visited[tl][tr][tc] && maze[tl][tr][tc]!='#') {
69 visited[tl][tr][tc] = 1;
70 ++tail;
71 queue[tail].l = tl;
72 queue[tail].r = tr;
73 queue[tail].c = tc;
74 queue[tail].mins = cm+1;
75 }
76 }
77 }
78 return -1;
79 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3126思路:
BFS，一次AC
代碼:
1 #define QUEUE_LEN 10000
2 int from, to;
3 int head, tail;
4 struct EACH {
5 int plen;
6 int num;
7 } queue[QUEUE_LEN];
8 int hash[QUEUE_LEN];
9
10 int
11 is_prime(int num)
12 {
13 int i, up = (int)sqrt(num*1.0);
14 for(i=2; i<=up; i++)
15 if(num%i == 0)
16 return 0;
17 return 1;
18 }
19
20 int
21 bfs()
22 {
23 int cur_plen, cur_num, next_num;
24 int i, j, k, t, div;
25 queue[tail].plen = 0;
26 queue[tail].num = from;
27 hash[queue[tail].num] = 1;
28 while(head < tail) {
29 ++head;
30 cur_plen = queue[head].plen;
31 cur_num = queue[head].num;
32 if(cur_num == to)
33 return cur_plen;
34 div = 1000;
35 t = cur_num;
36 for(i=3; i>=0; i--) {
37 k = t/div;
38 for(j=0; j<=9; j++) {
39 if(i==3 && j==0)
40 continue;
41 next_num = cur_num;
42 next_num -= k*div;
43 next_num += j*div;
44 if(!hash[next_num] && is_prime(next_num)) {
45 ++tail;
46 queue[tail].plen = cur_plen + 1;
47 queue[tail].num = next_num;
48 hash[queue[tail].num] = 1;
49 }
50 }
51 t = t%div;
52 div /= 10;
53 }
54 }
55 return -1;
56 }
// RS Hash Function
unsigned int RSHash( char * str)
{
unsigned int b = 378551 ;
unsigned int a = 63689 ;
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * a + ( * str ++ );
a *= b;
}
return (hash & 0x7FFFFFFF );
}
// JS Hash Function
unsigned int JSHash( char * str)
{
unsigned int hash = 1315423911 ;
while ( * str)
{
hash ^= ((hash << 5 ) + ( * str ++ ) + (hash >> 2 ));
}
return (hash & 0x7FFFFFFF );
}
// P. J. Weinberger Hash Function
unsigned int PJWHash( char * str)
{
unsigned int BitsInUnignedInt = (unsigned int )( sizeof (unsigned int ) * 8 );
unsigned int ThreeQuarters = (unsigned int )((BitsInUnignedInt * 3 ) / 4 );
unsigned int OneEighth = (unsigned int )(BitsInUnignedInt / 8 );
unsigned int HighBits = (unsigned int )( 0xFFFFFFFF ) << (BitsInUnignedInt - OneEighth);
unsigned int hash = 0 ;
unsigned int test = 0 ;
while ( * str)
{
hash = (hash << OneEighth) + ( * str ++ );
if ((test = hash & HighBits) != 0 )
{
hash = ((hash ^ (test >> ThreeQuarters)) & ( ~ HighBits));
}
}
return (hash & 0x7FFFFFFF );
}
// ELF Hash Function
unsigned int ELFHash( char * str)
{
unsigned int hash = 0 ;
unsigned int x = 0 ;
while ( * str)
{
hash = (hash << 4 ) + ( * str ++ );
if ((x = hash & 0xF0000000L ) != 0 )
hash ^= (x >> 24 );
hash &= ~ x;
}
return (hash & 0x7FFFFFFF );
}
// BKDR Hash Function
unsigned int BKDRHash( char * str)
{
unsigned int seed = 131 ; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0 ;
while ( * str)
{
hash = hash * seed + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// SDBM Hash Function
unsigned int SDBMHash( char * str)
{
unsigned int hash = 0 ;
while ( * str)
{
hash = ( * str ++ ) + (hash << 6 ) + (hash << 16 ) - hash;
}
return (hash & 0x7FFFFFFF );
}
// DJB Hash Function
unsigned int DJBHash( char * str)
{
unsigned int hash = 5381 ;
while ( * str)
{
hash += (hash << 5 ) + ( * str ++ );
}
return (hash & 0x7FFFFFFF );
}
// AP Hash Function
unsigned int APHash( char * str)
{
unsigned int hash = 0 ;
int i;
for (i = 0 ; * str; i ++ )
{
if ((i & 1 ) == 0 )
{
hash ^= ((hash << 7 ) ^ ( * str ++ ) ^ (hash >> 3 ));
}
else
{
hash ^= ( ~ ((hash << 11 ) ^ ( * str ++ ) ^ (hash >> 5 )));
}
}
return (hash & 0x7FFFFFFF );
}
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=3087思路:
類似于模擬題的BFS，判重使用的是字符串哈希，哈希函數: ELFHash(見PKU 2503)
代碼:
1 int
2 shuffle()
3 {
4 int i, count = 0;
5 int hash_val;
6 memset(hash, 0, sizeof(hash));
7 while(1) {
8 for(i=0; i<2*len; i++) {
9 if(i%2==0)
10 queue[count][i] = tmp2[i/2];
11 else
12 queue[count][i] = tmp1[i/2];
13 }
14 queue[count][i] = '\0';
15 strncpy(tmp1, queue[count], len);
16 strncpy(tmp2, queue[count]+len, len);
17 if(strcmp(queue[count], desire) == 0)
18 return count+1;
19 if(search(queue[count]) != -1)
20 return -1;
21 hash_val = ELFHash(queue[count]);
22 insert(hash_val, count);
23 ++count;
24 }
25 }
問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2503思路:
字符串哈希
這里使用的哈希函數是ELFHash
1 int ELFHash(char *str)
2 {
3 unsigned long t, hash = 0;
4 while(*str) {
5 hash = (hash<<4) + (*str++);
6 if((t = hash&0xF0000000L))
7 hash ^= t>>24;
8 hash &= ~t;
9 }
10 return (hash & 0x7FFFFFFF)%PRIME;
11 }
因為之前寫哈希表解決沖突都是用的鏈接法，這里想嘗試一下開放地址法，采用最簡單的線性探查，結果居然TLE
無奈還是改成鏈接法，然后就AC了
不過，時間卻有719MS之多，而網上幾乎相同的代碼只需要230MS左右，不知道是何原因
代碼:
TLE的開放地址法
1 void
2 insert(int hash_val, int index)
3 {
4 if(!hash[hash_val].used) {
5 hash[hash_val].used = 1;
6 hash[hash_val].index = index;
7 } else
8 insert((hash_val+1)%PRIME, index); /* linear probing */
9 }
10
11 int
12 search(char *f_word)
13 {
14 int hash_val = ELFHash(f_word);
15 int i = 0;
16 while(1) {
17 if(!hash[hash_val].used || i==PRIME)
18 break;
19 if(strcmp(f_word, flg[hash[hash_val].index])==0)
20 return hash[hash_val].index;
21 hash_val = (hash_val+1)%PRIME;
22 ++i;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }
AC的鏈接法
1 void
2 insert(int hash_val, int index)
3 {
4 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
5 if(node == NULL) {
6 fprintf(stderr, "malloc error in: insert\n");
7 exit(1);
8 }
9 node->index = index;
10 node->next = hash[hash_val];
11 hash[hash_val] = node;
12 }
13
14 int
15 search(char *f_word)
16 {
17 int hash_val = ELFHash(f_word);
18 struct Node *node = hash[hash_val];
19 while(node != NULL) {
20 if(strcmp(f_word, flg[node->index]) == 0)
21 return node->index;
22 node = node->next;
23 }
24 return -1;
25 }
26
27 void
28 input_hash()
29 {
30 int hash_val, index = 0;
31 char tmp[MAX_LEN*2+1];
32 memset(hash, 0, sizeof(hash));
33 while(gets(tmp) && tmp[0]) {
34 sscanf(tmp, "%s %s", eng[index], flg[index]);
35 hash_val = ELFHash(flg[index]);
36 insert(hash_val, index);
37 ++index;
38 }
39 }