/*
* tpop(2): algorithms and data structures
* created on Mar 2, 2011
*/
#include
/* NELEMS macro: computes the number of elements in the array */
#define NELEMS(array) (sizeof(array) / sizeof(array[0]))
typedef struct Nameval Nameval;
struct Nameval
{
char *name;
int value;
};
int lookup(char *, Nameval [], int); //binary search
int lookupV1(char *, Nameval [], int); //bsearch system function
int nvcmp(const void *, const void *);
/* lookup main: binary search a word in an array */
int main(int argc, char *argv[])
{
/* HTML characters, e.g. AElig is ligature of A and E. */
/* Values are Unicode/ISO10646 encoding. */
Nameval htmlchars[] = {
"AElig", 0x00c6,
"Aacute", 0x00c1,
"Acirc", 0x00c2,
/* ...*/
"zeta", 0x03b6,
};
if (argc == 1) /* why not argc == 1? */
printf("usage: binsearch name\n");
else
printf("Name %s was found at %d\n", argv[1], lookupV1(argv[1], htmlchars, NELEMS(htmlchars)));
}
/* lookup: binary search for name in tab; return index */
int lookup(char *name, Nameval tab[], int ntab)
{
int low, high, mid, cmp;
low = 0;
high = ntab-1;
while (low <= high) {
mid = (low + high) / 2;
cmp = strcmp(name, tab[mid].name);
if (cmp < 0)
high = mid - 1;
else if (cmp > 0)
low = mid + 1;
else /* found match */
return mid;
}
return -1; /* no match */
}
/* lookupV1: use bsearch to find name in tab, return index */
int lookupV1(char *name, Nameval tab[], int ntab)
{
Nameval key, *np;
key.name = name;
key.value = 0; /* unused; anthing will do */
np = (Nameval *)bsearch(&key, tab, ntab, sizeof(tab[0]), nvcmp);
if (np == NULL)
return -1;
else
return np-tab;
}
/* nvcmp: compare two Nameval names */
int nvcmp(const void *va, const void *vb)
{
const Nameval *a, *b;
a = (Nameval *)va;
b = (Nameval *)vb;
return strcmp(a->name, b->name);
}
阅读(463) | 评论(0) | 转发(0) |
