查找

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define EQ(a,b) (!strcmp((a),(b))) /*字符串a和b相等*/
#define LT(a,b) (strcmp((a),(b)) < 0) /*字符串a小于字符串b*/
#define LQ(a,b) (strcmp((a),(b)) <= 0) /*字符串a小于等于字符串b*/

#define SZ_STRING 16

typedef char STRING[SZ_STRING];

/*顺序表中元素的类型*/
typedef struct elemtype
{
    STRING key;
    STRING value;
}ELEMTYPE;

/*静态查找表之顺序表：顺序存储结构(顺序表中元素的存放是无序的)*/
typedef struct sunxutable
{
    ELEMTYPE * elem; /*数据元素的基址，0号单元留空*/
    int length; /*表长度*/
}SUNXUTABLE;

typedef SUNXUTABLE * SunXuTablePtr;

/*次优二叉树结点结构体*/
typedef struct secondoptinaltreenode
{
    STRING key; /*结点键值*/
    STRING value; /*结点值*/
    int weight; /*结点权值*/
    struct secondoptinaltreenode * leftchild; /*左孩子*/
    struct secondoptinaltreenode * rightchild; /*右孩子*/
}SECONDOPTINALTREENODE;

typedef SECONDOPTINALTREENODE * SecOptTreeNodePtr;

/*由次优二叉树结点元素组成的有序表*/
typedef struct ordertable
{
    SecOptTreeNodePtr node; /*次优二叉树结点元素的基址，0号单元留空*/
    int length; /*有序表的长度*/
}ORDERTABLE;

typedef ORDERTABLE * OrderTablePtr;

int InitSxTable(SunXuTablePtr * sxtableptr);
int DestroySunXuTable(SunXuTablePtr sxtableptr);
int Search_Seq(SunXuTablePtr sxtableptr, STRING key);
int Search_Bin(SunXuTablePtr sxtableptr, STRING key);
int PrintSxTable(SunXuTablePtr sxtableptr);

int InitOrderTable(OrderTablePtr * ordertableptr);
int PrintOrderTable(OrderTablePtr ordertableptr, int * sw);
int FindSW(OrderTablePtr ordertableptr, int sw[], int length);
void CreateSecondOptimalTree(SecOptTreeNodePtr * secopttreenodeptr, OrderTablePtr ordertableptr, int * sw, int low, int high);
void PrintSecondOptimalTreeNode1(SecOptTreeNodePtr secopttreenodeptr, int * sw);
void PrintSecondOptimalTreeNode2(SecOptTreeNodePtr secopttreenodeptr, int * sw);
void PrintSecondOptimalTreeNode3(SecOptTreeNodePtr secopttreenodeptr, int * sw);

int main(int argc, char * * argv)
{
    freopen("chazhao.txt", "w", stdout);
    printf("查找的各种算法！(顺序查找，折半查找，次优查找)\n");

    SunXuTablePtr sxtableptr = NULL;
    InitSxTable(&sxtableptr); /*初始化顺序表*/

    printf("\n=======================================================\n\n");
    printf("顺序查找：适用于表中数据无序的情况！\n");
    printf("顺序表中所有数据如下：\n");

    PrintSxTable(sxtableptr);

    int search_index = -1;
    char key[16];
    memset(key, 0, sizeof(key));
    strcpy(key, "C");
    search_index = Search_Seq(sxtableptr, key);
    printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
    memset(key, 0, sizeof(key));
    strcpy(key, "I");
    search_index = Search_Seq(sxtableptr, key);
    printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
    memset(key, 0, sizeof(key));
    strcpy(key, "M");
    search_index = Search_Seq(sxtableptr, key);
    printf("顺序查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);

    printf("\n=======================================================\n\n");
    printf("折半查找：适用于表中数据有序并且查找概率相等的情况！\n");
    printf("有序表中所有数据如下：\n");
    PrintSxTable(sxtableptr);

    memset(key, 0, sizeof(key));
    strcpy(key, "D");
    search_index = Search_Bin(sxtableptr, key);
    printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
    memset(key, 0, sizeof(key));
    strcpy(key, "I");
    search_index = Search_Bin(sxtableptr, key);
    printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);
    memset(key, 0, sizeof(key));
    strcpy(key, "N");
    search_index = Search_Bin(sxtableptr, key);
    printf("折半查找：key=[%s],在顺序表中下标=[%d]\n", key, search_index);

    printf("\n=======================================================\n\n");
    printf("次优查找树折半查找：适用于表中数据有序并且查找概率不相等的情况！\n");

    OrderTablePtr ordertableptr = NULL;
    InitOrderTable(&ordertableptr); /*初始化有序表*/

    int sw[10]={0}; /*有序表中所有数据的累计权值和(0号留空，初值为0)*/
    printf("求有序表中各个数据元素的累计权值和：\n");
    FindSW(ordertableptr, sw, 10);
    printf("为构造次优查找树，准备的有序表中所有数据如下：\n");
    PrintOrderTable(ordertableptr, sw);

    SecOptTreeNodePtr secopttreenodeptr = NULL; /*次优查找树根结点*/
    int low = 1; /*0号下标为空，所以从1开始*/
    int high = ordertableptr->length; /*0号为空，9个元素的话，最高下标就是9*/
    printf("创建次优查找树!\n");
    CreateSecondOptimalTree(&secopttreenodeptr, ordertableptr, sw, 1, high);

    printf("\n按先序序列打印次优查找树：\n");
    PrintSecondOptimalTreeNode1(secopttreenodeptr, sw);
    printf("\n按中序序列打印次优查找树：\n");
    PrintSecondOptimalTreeNode2(secopttreenodeptr, sw);
    printf("\n按后序序列打印次优查找树：\n");
    PrintSecondOptimalTreeNode3(secopttreenodeptr, sw);

    DestroySunXuTable(sxtableptr);
    /*监视哨在最高下标处的算法*/
}

/*功能：按照有序表中各个元素的weight域，求累计权值和，保存在sw中*/
int FindSW(OrderTablePtr ordertableptr, int * sw, int length)
{
    int i = -1;
    int j = -1;
    /*求累计权值和！*/
    for(i=0; i<length; i++)
    {
        for(j=0; j<=i; j++)
        {
            sw[i] += ordertableptr->node[j].weight;
        }
    }
}

/*功能：打印出整颗二叉树(按照先序遍历序列)*/
void PrintSecondOptimalTreeNode1(SecOptTreeNodePtr secopttreenodeptr, int * sw)
{
    if(secopttreenodeptr == NULL)
    {
        return;
    }
    printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
    PrintSecondOptimalTreeNode1(secopttreenodeptr->leftchild, sw);
    PrintSecondOptimalTreeNode1(secopttreenodeptr->rightchild, sw);
}

/*功能：打印出整颗二叉树(按照中序遍历序列)*/
void PrintSecondOptimalTreeNode2(SecOptTreeNodePtr secopttreenodeptr, int * sw)
{
    if(secopttreenodeptr == NULL)
    {
        return;
    }
    PrintSecondOptimalTreeNode2(secopttreenodeptr->leftchild, sw);
    printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
    PrintSecondOptimalTreeNode2(secopttreenodeptr->rightchild, sw);
}

/*功能：打印出整颗二叉树(按照后序遍历序列)*/
void PrintSecondOptimalTreeNode3(SecOptTreeNodePtr secopttreenodeptr, int * sw)
{
    if(secopttreenodeptr == NULL)
    {
        return;
    }
    PrintSecondOptimalTreeNode3(secopttreenodeptr->leftchild, sw);
    PrintSecondOptimalTreeNode3(secopttreenodeptr->rightchild, sw);
    printf("元素:key=[%s],value=[%s],weight=[%d]\n", secopttreenodeptr->key,secopttreenodeptr->value, secopttreenodeptr->weight);
}

/***************************************************************
 *函数名：CreateSecondOptimalTree()
 *功能：创建次优查找树(采用二叉链式存储结构)
 *输入参数：
 * ordertableptr : 有序表地址
 * sw ：累计权值和表地址
 * low ：树区间最低下标(初始时:是有序表中的第1号元素，不是第0号)
 * high : 树区间最高下标
 *输出参数：
 * secopttreenodeptr : 创建的次优查找树
 *返回值：空
 *编程思想：
 * 1，在有序表中找出最小的(detaPi)元素所在的下标，作为树根结点。
 * 2，以树根结点为中心点，在顺序表中左右分开:左边是左子树的结点，右边是右子树的结点。
 * 3，在左右子树中继续1,2步，可以递归实现
****************************************************************/
void CreateSecondOptimalTree(SecOptTreeNodePtr * secopttreenodeptr, OrderTablePtr ordertableptr, int * sw, int low, int high)
{
    if((ordertableptr == NULL)||(sw == NULL)||(low > high))
        return;
    /*找树根结点元素:先找最小(detaPi)的值(detaPi:是第i个元素左右两边权值和之差的绝对值)*/
    int minPi = abs(sw[high]); /*最小的(detaPi)*/
    int minPi_index = -1; /*最小的(detaPi)元素所在的下标*/
    int i = 0;
    for(i=low; i<=high; i++)
    {
        /*abs((sw[high] - sw[i]) - (sw[i-1] - sw[low-1])) : |右边的权值和 - 左边的权值和|*/
        if(abs((sw[high] - sw[i]) - (sw[i-1] - sw[low-1])) < minPi) /*找最小(detaPi)*/
        {
            minPi = abs(sw[high] + sw[low-1] - sw[i] -sw[i-1]);
            minPi_index = i; /*记录最小(detaPi)元素的下标值*/
        }
    }
    /*minPi_index记录的下标就是树跟结点*/
    *secopttreenodeptr = (SecOptTreeNodePtr)malloc(sizeof(SECONDOPTINALTREENODE));
    if(*secopttreenodeptr == NULL)
    {
        printf("CreateSecondOptimalTree mallo err!\n");
        return;
    }
    memset(*secopttreenodeptr, 0, sizeof(SECONDOPTINALTREENODE));
    memcpy(*secopttreenodeptr, &(ordertableptr->node[minPi_index]), sizeof(SECONDOPTINALTREENODE)); /*生成根结点*/

    int newlow; /*孩子树区间最低下标*/
    int newhigh; /*孩子树区间最高下标*/
    if(minPi_index == low) /*左子树为空*/
    {
        (*secopttreenodeptr)->leftchild = NULL;
    }
    else /*创建左子树*/
    {
        newlow = low;
        newhigh = minPi_index - 1;
        CreateSecondOptimalTree(&((*secopttreenodeptr)->leftchild), ordertableptr, sw, newlow, newhigh);
    }
    if(minPi_index == high) /*右子树为空*/
    {
        (*secopttreenodeptr)->rightchild = NULL;
    }
    else /*创建右子树*/
    {
        newlow = minPi_index + 1;
        newhigh = high;
        CreateSecondOptimalTree(&((*secopttreenodeptr)->rightchild), ordertableptr, sw, newlow, newhigh);
    }
}

/*功能：打印有序表中的所有元素*/
int PrintOrderTable(OrderTablePtr ordertableptr, int * sw)
{
    if(ordertableptr == NULL)
         return -1;
    int i = 0;
    for(i=0; i<ordertableptr->length+1; i++)
    {
        printf("元素下标[%d],key=[%s],value=[%s],weight=[%d],sw=[%d]\n", i, ordertableptr->node[i].key, ordertableptr->node[i].value, ordertableptr->node[i].weight, sw[i]);
    }
    return 0;
}

/***************************************************************
 *函数名称：InitOrderTable()
 *功能：初始化次优二叉树的有序表(顺序存储结构)
 *输出参数：
 * ordertableptr : 有序表指针的地址
 *返回值：
****************************************************************/
 int InitOrderTable(OrderTablePtr * ordertableptr)
 {
     int weightvalue[128]={1, 1, 2, 5, 3, 4, 4, 3, 5};

    *ordertableptr = (ORDERTABLE*)malloc(sizeof(ORDERTABLE));
    if(*ordertableptr == NULL)
        return -1;
    memset((*ordertableptr), 0, sizeof(ORDERTABLE));
    (*ordertableptr)->length = 9;
    (*ordertableptr)->node = (SECONDOPTINALTREENODE *) malloc(((*ordertableptr)->length+1) * sizeof(SECONDOPTINALTREENODE)); /*0号单元留空*/
    if((*ordertableptr)->node == NULL)
        return -1;
    memset((*ordertableptr)->node, 0, (*ordertableptr)->length * sizeof(SECONDOPTINALTREENODE));
    /*初始化顺序表的元素*/
    strcpy((*ordertableptr)->node[0].key, "");
    strcpy((*ordertableptr)->node[0].value, "");
    (*ordertableptr)->node[0].weight = 0;
    (*ordertableptr)->node[0].leftchild = NULL;
    (*ordertableptr)->node[0].rightchild = NULL;
    strcpy((*ordertableptr)->node[1].key, "A");
    strcpy((*ordertableptr)->node[1].value, "AAA");
    (*ordertableptr)->node[1].weight = weightvalue[0];
    (*ordertableptr)->node[1].leftchild = NULL;
    (*ordertableptr)->node[1].rightchild = NULL;
    strcpy((*ordertableptr)->node[2].key, "B");
    strcpy((*ordertableptr)->node[2].value, "BBB");
    (*ordertableptr)->node[2].weight = weightvalue[1];
    (*ordertableptr)->node[2].leftchild = NULL;
    (*ordertableptr)->node[2].rightchild = NULL;
    strcpy((*ordertableptr)->node[3].key, "C");
    strcpy((*ordertableptr)->node[3].value, "CCC");
    (*ordertableptr)->node[3].weight = weightvalue[2];
    (*ordertableptr)->node[3].leftchild = NULL;
    (*ordertableptr)->node[3].rightchild = NULL;
    strcpy((*ordertableptr)->node[4].key, "D");
    strcpy((*ordertableptr)->node[4].value, "DDD");
    (*ordertableptr)->node[4].weight = weightvalue[3];
    (*ordertableptr)->node[4].leftchild = NULL;
    (*ordertableptr)->node[4].rightchild = NULL;
    strcpy((*ordertableptr)->node[5].key, "E");
    strcpy((*ordertableptr)->node[5].value, "EEE");
    (*ordertableptr)->node[5].weight = weightvalue[4];
    (*ordertableptr)->node[5].leftchild = NULL;
    (*ordertableptr)->node[5].rightchild = NULL;
    strcpy((*ordertableptr)->node[6].key, "F");
    strcpy((*ordertableptr)->node[6].value, "FFF");
    (*ordertableptr)->node[6].weight = weightvalue[5];
    (*ordertableptr)->node[6].leftchild = NULL;
    (*ordertableptr)->node[6].rightchild = NULL;
    strcpy((*ordertableptr)->node[7].key, "G");
    strcpy((*ordertableptr)->node[7].value, "GGG");
    (*ordertableptr)->node[7].weight = weightvalue[6];
    (*ordertableptr)->node[7].leftchild = NULL;
    (*ordertableptr)->node[7].rightchild = NULL;
    strcpy((*ordertableptr)->node[8].key, "H");
    strcpy((*ordertableptr)->node[8].value, "HHH");
    (*ordertableptr)->node[8].weight = weightvalue[7];
    (*ordertableptr)->node[8].leftchild = NULL;
    (*ordertableptr)->node[8].rightchild = NULL;
    /*注意：如果长度只分配9的话，node[9]其实已经越界了，在数组的外面了
    再操作mallo()的话，可能会覆盖这个空间*/
    strcpy((*ordertableptr)->node[9].key, "I");
    strcpy((*ordertableptr)->node[9].value, "III");
    (*ordertableptr)->node[9].weight = weightvalue[8];
    (*ordertableptr)->node[9].leftchild = NULL;
    (*ordertableptr)->node[9].rightchild = NULL;

    return 0;
 }

/***************************************************************
 *函数名：DestroySunXuTable()
 *函数功能：销毁顺序表
 *函数参数：
 * sxtableptr ：顺序表指针
****************************************************************/
int DestroySunXuTable(SunXuTablePtr sxtableptr)
{
    if(sxtableptr == NULL)
        return -1;
    if(sxtableptr->elem != NULL)
    {
        free(sxtableptr->elem);
        sxtableptr->elem = NULL;
    }
    if(sxtableptr != NULL)
    {
        free(sxtableptr);
        sxtableptr = NULL;
    }
    return 0;
}

/***************************************************************
 *函数名：Search_Bin()
 *功能：折半查找：在有序表中折半查找其指定的关键字的元素
 *输入参数：
 * sxtable ：顺序表
 * key ：待查找的关键字
 *返回值：
 * 若找到：  则返回该元素在表中的位置
 * 若未找到：则返回0
****************************************************************/
int Search_Bin(SunXuTablePtr sxtableptr, STRING key)
{
     if((key == NULL)||(sxtableptr == NULL))
         return 0;
     int low = 1; /*设置区间初值*/
     int high = sxtableptr->length;
     int mid = 0;

     while(low <= high)
     {
         mid = (low + high)/2;
         if(EQ(key, sxtableptr->elem[mid].key)) /*找到待查找元素,可以直接返回了*/
             return mid;
         else if(LT(key, sxtableptr->elem[mid].key))    /*继续在前半区间查找*/
             high = mid - 1;
         else low = mid + 1; /*继续在后半区间查找*/
     }

    return 0; /*找不到时，返回0*/
}

/*功能：打印顺序表中的所有元素*/
int PrintSxTable(SunXuTablePtr sxtableptr)
{
    if(sxtableptr == NULL)
         return -1;
    int i = 0;
    for(i=0; i<sxtableptr->length+1; i++)
    {
        printf("元素下标[%d],key=[%s],value=[%s]\n", i, sxtableptr->elem[i].key, sxtableptr->elem[i].value);
    }
    return 0;
}

/*功能：初始化顺序表(顺序存储结构)*/
int InitSxTable(SunXuTablePtr * sxtableptr)
{
    /*顺序表中元素的存放是无序的,为了试验有序表的折半查找，
    这里人为的让数据元素是有序的，免去了排序的操作
    所以也可以当有序表使用，并且，并不影响顺序查找的测试*/
    *sxtableptr = (SUNXUTABLE*)malloc(sizeof(SUNXUTABLE));
    if(*sxtableptr == NULL)
        return -1;
    memset((*sxtableptr), 0, sizeof(SUNXUTABLE));
    (*sxtableptr)->length = 9;
    (*sxtableptr)->elem = (ELEMTYPE *) malloc((*sxtableptr)->length * sizeof(ELEMTYPE));
    if((*sxtableptr)->elem == NULL)
        return -1;
    memset((*sxtableptr)->elem, 0, (*sxtableptr)->length * sizeof(ELEMTYPE));
    /*初始化顺序表的元素*/
    strcpy((*sxtableptr)->elem[1].key, "A");
    strcpy((*sxtableptr)->elem[1].value, "AAA");
    strcpy((*sxtableptr)->elem[2].key, "B");
    strcpy((*sxtableptr)->elem[2].value, "BBB");
    strcpy((*sxtableptr)->elem[3].key, "C");
    strcpy((*sxtableptr)->elem[3].value, "CCC");
    strcpy((*sxtableptr)->elem[4].key, "D");
    strcpy((*sxtableptr)->elem[4].value, "DDD");
    strcpy((*sxtableptr)->elem[5].key, "E");
    strcpy((*sxtableptr)->elem[5].value, "EEE");
    strcpy((*sxtableptr)->elem[6].key, "F");
    strcpy((*sxtableptr)->elem[6].value, "FFF");
    strcpy((*sxtableptr)->elem[7].key, "G");
    strcpy((*sxtableptr)->elem[7].value, "GGG");
    strcpy((*sxtableptr)->elem[8].key, "H");
    strcpy((*sxtableptr)->elem[8].value, "HHH");
    strcpy((*sxtableptr)->elem[9].key, "I");
    strcpy((*sxtableptr)->elem[9].value, "III");

    return 0;
}

/***************************************************************
 *函数名：Search_Seq()
 *功能：顺序查找：在顺序表中顺序查找其指定的关键字的元素
 *输入参数：
 * sxtable ：顺序表
 * key ：待查找的关键字
 *返回值：
 * 若找到：  则返回该元素在表中的位置
 * 若未找到：则返回0
****************************************************************/
int Search_Seq(SunXuTablePtr sxtableptr, STRING key)
{
     if((key == NULL)||(sxtableptr == NULL))
         return 0;
     strcpy(sxtableptr->elem[0].key, key); /*哨兵*/
     /*对0号元素elem[0]赋值key，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。
     elem[0]起到监视哨的作用，这仅仅是程序设计技巧上的改进*/
     int i = 0;
     for(i=sxtableptr->length; !EQ(sxtableptr->elem[i].key, key); i--); /*从后往前走*/

    return i; /*找不到时，会一直找到第一个，肯定相等，此时i=0*/
}