数据结构算法C语言实现（三十二）--- 9.1静态查找表

　　一、简述

　　静态查找表又分为顺序表、有序表、静态树表和索引表。以下只是算法的简单实现及测试，不涉及性能分析。

　　二、头文件

/**
author：zhaoyu
date:2016-7-12
*/
#include "6_3_part1_for_chapter9.h"
typedef struct {
    int key;
}SElemType;
//静态查找表的顺序储存结构
#define ElemType SElemType
#define KeyType int
typedef struct {
    ElemType *elem;//数据元素储存空间基址，0号留空
    int length;//表长度
}SSTable;
//这里简化了键值
//实现 EQ
bool EQ(int a, int b)
{
    return a==b?true:false;
}
bool LT(int a, int b)
{
    return a<b?true:false;
}
//实现创建 SSTbale
void createSSTable(SSTable &T)
{
    //先输入长度 length
    //再输入 length 个 元素
    scanf("%d", &T.length);
    T.elem = (ElemType *)malloc((T.length + 10)*sizeof(int));
    for (int i = 1; i <= T.length; i++)
    {
        scanf("%d", &T.elem[i].key);
    }
}

/**
algorithm 9.1
*/
int Search_Seq(SSTable ST, KeyType key)
{
    //在顺序表 ST 中顺序查找关键值等于key的数据元素，
    //若找到返回元素在表中位置，否则返回0
    ST.elem[0].key = key;
    int i;
    for (i = ST.length; !EQ(ST.elem[i].key, key); --i);
    return i;

}

/**
algorithm 9.2
*/
int Search_Bin(SSTable ST, KeyType key)
{
    //在有序表 ST 中折半查找其关键字等于 key 的数据元素
    //找到返回其位置，否则返回 0
    int low = 1;
    int high = ST.length;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (EQ(key, ST.elem[mid].key))
        {
            return mid;
        }
        else if (LT(key, ST.elem[mid].key))
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return 0;
}

//6_3_part1.h
/**
author：zhaoyu
date:2016-6-18
*/
#include "head.h"
#define TElemType char
//----二叉树的二叉链表表示----
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild, *rchild;
}*BiTree;
Status Visit(TElemType e)
{
    printf("%c	", e);
    return OK;
}

Status RecursionPreOrderTraverse(BiTree T, Status (* Visit)(TElemType e))
{//采用二叉链表存储结构，Visit是对数据元素操作的应用函数
//先序遍历二叉树 T 的递归算法
    if (T)
    {
        if (Visit(T->data))
        {
            if (RecursionPreOrderTraverse(T->lchild, Visit))
            {
                if (RecursionPreOrderTraverse(T->rchild, Visit))
                {
                    return OK;
                }
            }
        }
        return ERROR;//这一行由于 Visit 函数只 return OK，貌似没什么用
    }
    else
    {
        return OK;
    }
}

#include "6_3_part1_for_chapter9.h"
typedef struct {
    char key;
    float weight;
}SElemType;

//静态查找表的顺序储存结构
#define ElemType SElemType
#define KeyType char
typedef struct {
    ElemType *elem;//数据元素储存空间基址，0号留空
    int length;//表长度
}SSTable;
//实现创建 SSTbale
void createSSTable(SSTable &ST)
{
    //先输入长度 length
    //再输入 length 个 元素
    scanf("%d", &ST.length);
    getchar();//输入老师犯错误
    ST.elem = (ElemType *)malloc((ST.length + 10)*sizeof(ElemType));
    for (int i = 1; i <= ST.length; i++)
    {
        scanf("%c", &ST.elem[i].key);
        getchar();
        scanf("%f", &ST.elem[i].weight);
        getchar();//很是懵逼
    }
}
//my code
void FindSW(float *sw, SSTable ST)
{
    float sum = 0; 
    for (int i = 1; i <= ST.length; i++)
    {
        sum += ST.elem[i].weight;
        sw[i] = sum;
    }
}


/**
algorithm 9.3
*/
void SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high)
{
    //由有序表R[low...high]及其累计权值表sw（其中sw[0]==0）递归构造次优查找树
    int i = low;
    float min = abs(sw[high] - sw[low]);
    float dw = sw[high] + sw[low - 1];
    for (int j = low + 1; j <= high; j++)
    {
        if (abs(dw-sw[j] - sw[j-1]) < min)
        {
            i = j;
            min = abs(dw-sw[j] - sw[j-1]);
        }
    }
    T = (BiTree)malloc(sizeof(BiTNode));
    T->data = R[i].key;

    if (i == low)
    {
        T->lchild = NULL;
    }
    else 
    {
        SecondOptimal(T->lchild, R, sw, low, i-1);
    }

    if (i == high)
    {
        T->rchild = NULL;
    }
    else
    {
        SecondOptimal(T->rchild, R, sw, i+1, high);
    }    
}

/**
algorithm 9.4
*/
typedef BiTree SOSTree;//次优查找树采用二叉链表的储存结构
Status CreateSOSTree(SOSTree &T, SSTable ST)
{
    float sw[100];
    //有有序表构造一颗次优查找树T， ST的数据元素含有域weight
    if (0 == ST.length)
    {
        T = NULL;
    }
    else
    {
        FindSW(sw, ST);//按照由有序表ST中各数据元素的weight域求累计权值表sw
        SecondOptimal(T, ST.elem, sw, 1, ST.length);
    }
    return OK;
}

　　三、CPP文件

#include "9_1_1.h"
int main(int argc, char const *argv[])
{
    SSTable T;
    createSSTable(T);
    printf("Search 9:	%d
", Search_Seq(T, 9));
    printf("Search 3:	%d
", Search_Bin(T, 3));
    return 0;
}

#include "9_1_2.h"
int main(int argc, char const *argv[])
{
    SOSTree T;
    SSTable ST;
    createSSTable(ST);
    CreateSOSTree(T, ST);
    RecursionPreOrderTraverse(T, Visit);
    printf("
");
    return 0;
}

　　四、测试

　　

　　静态树表

　　

　　反思：

　　考完试，动力明显不足了，怎能半途而废，一定要把这个工程在回家之前完成。此外，对于一些不常用，或较难或书上说的比较的含糊的算法明显静不下心来好好研究。效率奇低。