2011年軟考程序員考試復(fù)習(xí)筆試知識(shí)點(diǎn)整理(17)

　　后綴樹代碼如下：

　　//SuffixTree.h

　　typedef struct node //聲明節(jié)點(diǎn)的結(jié)構(gòu)

　　{

　　string strdata; //存儲(chǔ)節(jié)點(diǎn)上的字符串

　　vector Child; //存儲(chǔ)該節(jié)點(diǎn)的子節(jié)點(diǎn)的地址

　　int flag; //輔助標(biāo)志位,用0和1表示該節(jié)點(diǎn)是否有子節(jié)點(diǎn)

　　int breakpoint; //輔助變量,當(dāng)該節(jié)點(diǎn)需要分裂時(shí),用于記錄分裂點(diǎn)的位置

　　}*mynode;

　　classCSuffixTree

　　{

　　public:

　　mynode ST; //ST生成的后綴樹的根節(jié)點(diǎn)

　　mynode point; //point節(jié)點(diǎn)指針，搜索時(shí)指向搜索節(jié)點(diǎn)的父節(jié)點(diǎn)，搜索結(jié)束時(shí)根據(jù)搜索

　　//結(jié)果指向要操作的節(jié)點(diǎn)

　　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源字符串變量，在構(gòu)造函數(shù)中初始化

　　string left; //left用于記錄每次搜索結(jié)束后，目標(biāo)字符串中的剩余字符串

　　};

　　//SuffixTree.cpp

　　//構(gòu)造函數(shù)，初始化data變量和ST,point指針并產(chǎn)個(gè)根節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)，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;

　　}

　　//析構(gòu)函數(shù)

　　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++)//調(diào)用兩層循環(huán)，產(chǎn)生目標(biāo)字符串每一個(gè)前綴的所 有后綴

　　{

　　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); //調(diào)用Search函數(shù)搜索生成的字符串

　　軟考程序員考試歷年真題重點(diǎn)題總結(jié)及答案

　　2011年上半年軟考報(bào)名時(shí)間及方式匯總

　　軟考程序員考試歷年真題匯總(2007年-2010年)