一、简述
静态查找表又分为顺序表、有序表、静态树表和索引表。以下只是算法的简单实现及测试，不涉及性能分析。
二、头文件
/**
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 + )*sizeof(int));
for (int i = ; 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[].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 = ;
int high = ST.length;
while (low <= high)
{
int mid = (low + high) / ;
if (EQ(key, ST.elem[mid].key))
{
return mid;
}
else if (LT(key, ST.elem[mid].key))
{
high = mid - ;
}
else
{
low = mid + ;
}
}
return ;
}
9_1_1.h
//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\t", 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;
}
}
6_3_part1_for_chapter9.h
#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 + )*sizeof(ElemType));
for (int i = ; 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 = ;
for (int i = ; 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 - ];
for (int j = low + ; j <= high; j++)
{
if (abs(dw-sw[j] - sw[j-]) < min)
{
i = j;
min = abs(dw-sw[j] - sw[j-]);
}
}
T = (BiTree)malloc(sizeof(BiTNode));
T->data = R[i].key; if (i == low)
{
T->lchild = NULL;
}
else
{
SecondOptimal(T->lchild, R, sw, low, i-);
} if (i == high)
{
T->rchild = NULL;
}
else
{
SecondOptimal(T->rchild, R, sw, i+, high);
}
} /**
algorithm 9.4
*/
typedef BiTree SOSTree;//次优查找树采用二叉链表的储存结构
Status CreateSOSTree(SOSTree &T, SSTable ST)
{
float sw[];
//有有序表构造一颗次优查找树T， ST的数据元素含有域weight
if ( == ST.length)
{
T = NULL;
}
else
{
FindSW(sw, ST);//按照由有序表ST中各数据元素的weight域求累计权值表sw
SecondOptimal(T, ST.elem, sw, , ST.length);
}
return OK;
}
9_1_2.h
三、CPP文件
#include "9_1_1.h"
int main(int argc, char const *argv[])
{
SSTable T;
createSSTable(T);
printf("Search 9:\t%d\n", Search_Seq(T, ));
printf("Search 3:\t%d\n", Search_Bin(T, ));
return ;
}
9_1_1.cpp
#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("\n");
return ;
}
9_1_2.cpp
四、测试
静态树表
反思：
考完试，动力明显不足了，怎能半途而废，一定要把这个工程在回家之前完成。此外，对于一些不常用，或较难或书上说的比较的含糊的算法明显静不下心来好好研究。效率奇低。