#ifndef SSTABLE_H
#define SSTABLE_H#include <iostream>
using namespace std;/*************************************************************
SSTable：stastic search table
靜態查找表的模板類實現
順序存儲結構
*************************************************************/template <typename ElemType>
class SSTable
{
private:ElemType *elem;int length;public:SSTable();SSTable(const SSTable &rhs);void clear();const SSTable& operator=(const SSTable &rhs);~SSTable();void create(const ElemType *r, int n);void ascend();void createOrder(const ElemType *r, int n);void show() const;/*模板類中的模板方法@function 從后向前順序查找關鍵字為key的元素@parameter key ElemType中的關鍵字@return 返回關鍵字為key的元素在靜態查找表中的位置，若無關鍵字為key的元素則返回0*/template <typename KeyType>int searchSeq(KeyType key) const{//將key包裝進臨時ElemType對象tmp中ElemType tmp;tmp.key = key;//將0號下標元素置為臨時對象tmp，起哨兵作用elem[0] = tmp;int i = length;while( elem[i].key != elem[0].key)--i;return i;}/*模板類中的模板方法@function 對排序表二分查找關鍵字為key的元素@parameter key ElemType中的關鍵字@return 返回關鍵字為key的元素在靜態查找表中的位置，若無關鍵字為key的元素則返回0*/template <typename KeyType>int searchBin(KeyType key) const{int low = 1;int high = length;while (low <= high){int middle = (high + low) / 2;if (elem[middle].key == key)return middle;else if (elem[middle].key < key)low = middle + 1;elsehigh = middle - 1;}return 0;}
};//默認構造函數
template <typename ElemType>
SSTable<ElemType>::SSTable()
{elem = nullptr;length = 0;
}//復制構造函數
template <typename ElemType>
SSTable<ElemType>::SSTable(const SSTable &rhs)
{length = rhs.length;elem = (ElemType *)calloc(length+1, sizeof(ElemType));for (int i = 1; i <= length; ++i)elem[i] = rhs.elem[i];
}//置空函數
template <typename ElemType>
void SSTable<ElemType>::clear()
{if (elem != nullptr)free(elem);elem = nullptr;length = 0;
}/*
*賦值函數
*@call clear()
*/
template <typename ElemType>
const SSTable<ElemType>& SSTable<ElemType>::operator=(const SSTable &rhs)
{clear();elem = (ElemType *)calloc(length);for (int i = 1; i <= length; ++i)elem[i] = rhs.elem[i];length = rhs.length;
}//析構函數
template <typename ElemType>
SSTable<ElemType>::~SSTable()
{clear();
}/*
*@function 根據一個大小為n的ElemType型數組，初始化SSTable對象
*@parameter r 一個ElemType型的數組
*@parameter n  數組r的大小
*/
template <typename ElemType>
void SSTable<ElemType>::create(const ElemType *r, int n)
{//分配大小為n+1的數組，0號位置不放元素elem = (ElemType *)calloc(n + 1, sizeof(ElemType));if (elem == nullptr)exit(-1);for (int i = 0; i < n; ++i)elem[i+1] = r[i];length = n;
}//將elem指向的數組進行比較排序，遞增
template <typename ElemType>
void SSTable<ElemType>::ascend()
{int index;for (int i = 1; i <= length; ++i){index = i;for (int j = i + 1; j <= length; ++j)if (elem[j].key < elem[index].key)index = j;ElemType tmp = elem[i];elem[i] = elem[index];elem[index] = tmp;}
}/*
*@function 根據一個大小為n的ElemType型數組，初始化SSTable對象，SSTable中elem所指向的數組為遞增排序
*@call create(const ElemType *r, int n)
*@call ascend()
*@parameter r 一個ElemType型的數組
*@parameter n  數組r的大小
*/
template <typename ElemType>
void SSTable<ElemType>::createOrder(const ElemType *r, int n)
{create(r, n);ascend();
}//將elem指向的數組輸出到控制臺
template <typename ElemType>
void SSTable<ElemType>::show() const
{for (int i = 1; i <= length; ++i)cout << elem[i].key << " ";cout << endl;
}#endif