编程珠玑 第十三章 搜索

从上一章的问题：生成[0, maxval]范围内m个随机整数的有序序列，不允许重复。实现伪代码：

initialize set S to empty
size = 0
while size < m do
　　t = bigrand() %d maxval
　　if t is not in S
　　　　insert t into S
　　　　size ++
print the elements of S in sorted order

将生成的数据结构称为IntSet，指整数集合S。接口定义如下：

//Intset.h 接口定义头文件
typedef int bool;
#define true 0
#define false 1
void intset_init(int maxelements, int maxval);
void insert(int t);
bool isinset(int t);
int getsize();
void report(int *v);
void destory_set();

int_set：初始化函数函数，参数 maxelements和maxval分别表示集合元素最大个数和集合中元素值的最大值，特定实现中可以忽略其中之一或两个都忽略；

insert：向集合中添加一个整数（前提需要先判断集合是否有已存在该值）；

isinset：判断集合中是否存在元素t；

getsize：获得集合中元素数目；

report：把集合中的元素拷贝到v指向的内存区域；

destory_set: 销毁集合，释放集合所占用的空间；

2. 集合实现

以下是采用不同的数据结构实现的集合操作：

（1）使用整数数组实现集合。

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
#include "Intset.h"


static int *set = NULL;
static int size;
//集合初始化，
//maxelements 为集合最大元素数目 
//maxval为元素最大值
void intset_init(int maxelements, int maxval)
{
    set = (int *)malloc((maxelements + 1)*sizeof(int));
    assert(set != NULL);
    size = 0;
    //哨兵元素，比元素最大值大1
    set[0] = maxval + 1;
}

//二分查找，集合set已包含t，则返回位置；否则，返回-1；
int search(int t)
{
    int l = 0, u = size - 1, p = -1,  m;
    m = (l + u) / 2;
    //printf("l=%d, u=%d\n", l, u);
    while(l < u)
    {
        //printf("l=%d, u=%d\n", l, u);
        if( set[m] > t)
            u = m - 1;
        else if ( set[m] < t)
            l = m + 1;
        else 
        {
            p = m;
            break;
        }
        m = (l + u) / 2;
    }
    return p;
}
//判断元素t是否在集合t
bool isinset(int t)
{
    if( search(t) == -1)
    {
        //printf("%d doesn't exist in set\n", t);
        return false;
    }
    else    
    {
        //printf("%d exist in set\n", t);
        return true;
        
    }
}
//把元素t插入到集合set中
void insert(int t)
{
    assert(set != NULL);
    int i, j;
    for(i= 0; set[i] < t; i ++)
        ;
    if(set[i] == t)
        return ;
    for(j = size; j > i; j --)
        set[j] = set[j - 1];
    set[i] = t;
    size ++;
    return ;
}

//获得集合set的大小
int getsize()
{
    return size;
}

//集合set拷贝到数组v
void report(int *v)
{
    int i;
    for(i = 0; i < size; i ++)
    {
        v[i] = set[i];
    }
}

//删除集合set
void destory_set()
{
    if(set != NULL)
    {
        free(set);
        set = NULL;
    }
}

（2）链表实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
#include "Intset.h"


static int *set = NULL;
static int size;
typedef struct node *pnode; 
typedef struct node{
    int val;
    pnode next;
    
}node; 

static pnode head = NULL;//头部节点
static pnode sentinel = NULL;//哨兵节点

//集合初始化，
//maxelements 为集合最大元素数目 
//maxval为元素最大值
void intset_init(int maxelements, int maxval)
{
    
    if((head = sentinel = (pnode)malloc(sizeof(node))) != NULL)
    {
        sentinel->val = maxval;
        sentinel->next = NULL;
        size = 0;
    }
    else 
    {
        printf("intset_init failed to malloc\n");
        exit(1);
    }
}

//判断元素t是否在集合t
bool isinset(int t)
{
    pnode p = head;
    while(p != sentinel)
    {
        if(p->val == t)
            return true;
        else
            p = p->next;
    }
    return false;
}

//递归插入元素t
pnode rinsert(pnode p, int t)
{
    pnode pt;
    if(p->val < t)
    {
        p->next = rinsert(p->next, t);
    }
    else
    {
        pt = (pnode)malloc(sizeof(node));
        pt->val = t;
        pt->next = p;
        size ++;
        p = pt;
    }
    return p;
}

//把元素t插入到集合set中
void insert(int t)
{
    head = rinsert(head, t);
    return;
    
}

//非递归方法把元素t插入到集合set中
void insert_norec(int t)
{
    pnode p = head, q = NULL, new;
    
    while(p->val < t)//最后遇到大于t的元素或遇到哨兵节点
    {
        q = p;
        p = q->next;
    }
    
    new = (pnode)malloc(sizeof(node));
    new->val = t;
    new->next = p;
    
    if(q == NULL)//插入到head头部节点
    {
        head = new;
    }
    else
    {
        q->next = new;
    }
    size ++;
    return;
}


//获得集合set的大小
int getsize()
{
    return size;
}

//集合set拷贝到数组v
void report(int *v)
{
    int i=0;
    pnode p = head;
    while(p != sentinel)
    {
        v[i ++] = p->val;
        p = p->next;
    }
}

//删除集合set
void destory_set()
{
    pnode p = head, q;
    if(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
}

（4）二叉树实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <malloc.h>
#include "Intset.h"
typedef struct node *pnode; 
typedef struct node{
    int val;
    pnode left;//左子树指针
    pnode right;//右子树指针
}node; 
//二叉树根节点
static pnode root;
static size;


//集合初始化，
//maxelements 为集合最大元素数目 
//maxval为元素最大值
void intset_init(int maxelements, int maxval)
{
    root = NULL;
    size = 0;
}
//递归插入节点t
pnode rinsert(pnode p, int t)
{
    if(p == NULL)
    {
        p = (pnode)malloc(sizeof(node));
        p->val = t;
        p->left = p->right = NULL;
        size ++;
    }
    else if( p->val > t)
    {
        p->left = rinsert(p->left, t);
    }
    else if(p->val < t)
    {
        p->right = rinsert(p->right, t);
    }
    return p;
}
//把元素t插入到集合set中
void insert(int t)
{
    root = rinsert(root, t);
}

//判断元素t是否在集合t
bool isinset(int t)
{
    pnode p = root;
    while(p != NULL)
    {
        if(p->val > t)
            p = p->left;
        else if(p->val < t)
            p = p->right;
        else
            return true;
    }
    return false;
}
int getsize()
{
    return size;
}
//中序遍历二叉树
void mid_traverse(pnode p, int *v)
{
    static int index = 0;
    if(p == NULL)
        return;
    if(p == root)
        index = 0;
    mid_traverse(p->left, v);
    v[index ++] = p->val;
    mid_traverse(p->right, v);
    
}

//集合set拷贝到数组v
void report(int *v)
{
    mid_traverse(root, v);
}

//递归删除节点
void destory_node(pnode p)
{
    if(p == NULL)
        return;
    else if(p->left != NULL)
    {
        destory_node(p->left);
    }
    else if(p->right != NULL)
    {
        destory_node(p->right);
    }
    free(p);
}

//删除集合set
void destory_set()
{
    destory_node(root);
    root = NULL;
}

（4）位图实现（参考编程珠玑第1章）

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include "Intset.h"
#define BITSPERWORD 32
#define SHIFT 5
#define MASK 0x1F
static unsigned int *bitmap;//位图指针
static unsigned int size = 0;//集合元素数目
static unsigned int max = 0;//集合中元素的最大值+1
// 数字k所对应位图的位置置为1
void set_bit(unsigned int k)
{
    unsigned int byte_position;
    unsigned short bit_position;
    byte_position = k >> 5;//byte_position表示k在位图中的字节
    bit_position = k & 0x1F;//bit_position表示k所在字节的位
    /*printf("byte = %d    bit = %d\n", byte_position, bit_position);*/
    bitmap[byte_position] = bitmap[byte_position] | (1 << bit_position);
}

//数字k所对应位图的位置清零
void clear_bit(unsigned int k)
{
    unsigned int byte_position;
    unsigned short bit_position;
    byte_position = k >> 5;
    bit_position = k & 0x1F;
    /*printf("byte = %d    bit = %d\n", byte_position, bit_position);*/
    bitmap[byte_position] = bitmap[byte_position] & ~(1 << bit_position);
}

//测试数字k所对应位图的位置为1或为0
bool test_bit(unsigned int k)
{
    unsigned int byte_position;
    unsigned short bit_position;
    byte_position = k >> 5;
    bit_position = k & 0x1F;
    /*printf("byte = %d    bit = %d\n", byte_position, bit_position);*/
    return bitmap[byte_position] & (1 << bit_position);
}


//初始化位图
void intset_init(int maxelements, int maxval)
{
    unsigned int size = 1 + maxval/BITSPERWORD, i;
    max = maxval;
    printf("maxval = %u    size = %u\n", maxval, size);
    bitmap = (unsigned int *)malloc(size*sizeof(unsigned int));
    if(bitmap == NULL)
    {
        printf("Failed to malloc\n");
        return ;
    }
    memset(bitmap, 0, size*sizeof(unsigned int));
    size = 0;
    return ;
}

void insert(int t)
{
    set_bit(t);
    size ++;
}

bool isinset(int t)
{
    if( test_bit(t) == 0)
        return false;
    else
        return true;
}

int getsize()
{
    return size;
}

void report(int *v)
{
    int i = 0, j = 0;
    for(i = 0; i < max; i ++)
    {
        if(isinset(i) == true)
            v[j ++] = i;
    }    
    return;
}

void destory_set()
{
    if(bitmap != NULL)
    {
        free(bitmap);
        bitmap = NULL;
    }
}

3.测试主函数实现

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "Intset.h"
//产生区间[lower upper]内的随机数，参考编程珠玑第8章习题
int randInt(lower, upper)
{
    assert( lower < upper);
    return rand()%(upper - lower + 1) + lower;
}
//打印集合中的元素
void print(int arry[], int length)
{
    int i;
    printf("the set is \n");
    for(i = 0; i < length; i ++)
        printf("%d\t", arry[i]);
    printf("\n");
}
//调用程序需要输入三个参数 count：集合数目 lower：集合下限 upper：集合上限
int main(int argc, char *argv[])
{

    int count = 0, i, lower, upper, *v;
    if(argc != 4)
    {
        printf("USAGE:%s count lower upper \n", argv[0]);
        return 1;
    }
    count = atoi(argv[1]);
    lower = atoi(argv[2]);
    upper = atoi(argv[3]);
    printf("lower=%d upper=%d count=%d\n", lower, upper, count);
    v = (int *)malloc(count * sizeof(int));
    intset_init(count , upper + 1);
    i = count;
    while(i > 0)
    {
        int t = randInt(lower, upper);
        printf("rand=%d\n", t);
        if( isinset(t) == false)//判断集合是否已存在该元素
        {
            insert(t);
            i --;
        }
    
    }
    report(v);
    destory_set();
    print(v, count);
    return 0;
}

4.以上各种数据结构实现集合操作的复杂度

集合表示	O（每个操作的时间） 初始化　　　　insert　　　　　　report	总时间　　空间
有序数组 有序链表 二叉树 箱 位向量	1　　　　　　m　　　　　　　　m 1　　　　　　m　　　　　　　　m 1　　　　　　logm　　　　　　 m m　　　　　  1　　　　　　      1 n　　　　　　1　　　　　 　      n	O(m^2)　　m O(m^2)　　2m O(mlogm)　3m O(m)　　　3m O(n)　　　　n/b