2011年软考程序员考试复习笔试知识点整理(17)

　　后缀树代码如下：

　　//SuffixTree.h

　　typedef struct node //声明节点的结构

　　{

　　string strdata; //存储节点上的字符串

　　vector Child; //存储该节点的子节点的地址

　　int flag; //辅助标志位,用0和1表示该节点是否有子节点

　　int breakpoint; //辅助变量,当该节点需要分裂时,用于记录分裂点的位置

　　}*mynode;

　　classCSuffixTree

　　{

　　public:

　　mynode ST; //ST生成的后缀树的根节点

　　mynode point; //point节点指针，搜索时指向搜索节点的父节点，搜索结束时根据搜索

　　//结果指向要操作的节点

　　CSuffixTree(string str);

　　~CSuffixTree(void);

　　int Search(string str);

　　void CreatTree();

　　void Show(mynode ST);

　　void PrintNode(mynode p, int c, vector& isend);

　　private:

　　string data; //data源字符串变量，在构造函数中初始化

　　string left; //left用于记录每次搜索结束后，目标字符串中的剩余字符串

　　};

　　//SuffixTree.cpp

　　//构造函数，初始化data变量和ST,point指针并产个根节点的第一个子节点，ST的flag置1

　　CSuffixTree::CSuffixTree(stringstr)

　　{

　　data = str;

　　ST = (mynode) new node;

　　point = (mynode) new node;

　　point->strdata = data[0];

　　point->flag = 0;

　　ST->Child.push_back(point);

　　ST->flag = 1;

　　}

　　//析构函数

　　CSuffixTree::~CSuffixTree(void)

　　{

　　}

　　voidCSuffixTree::CreatTree()

　　{

　　int i, j, n, h, ic, jc;

　　string temp;

　　string tempuse;

　　mynode cnode;

　　for (i = 1; i <= (data.length()-1); i++)//调用两层循环，产生目标字符串每一个前缀的所 有后缀

　　{

　　for (j = 0; j <= i; j++)

　　{

　　temp.erase(temp.begin(),temp.end());

　　ic = i;

　　jc = j;

　　for (; jc <= ic; jc++)

　　{

　　temp.insert(temp.end(), data[jc]);

　　}

　　n = Search(temp); //调用Search函数搜索生成的字符串

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)