2011年軟考程序員考試復習筆試知識點整理(17)

　　后綴樹代碼如下：

　　//SuffixTree.h

　　typedef struct node //聲明節(jié)點的結構

　　{

　　string strdata; //存儲節(jié)點上的字符串

　　vector Child; //存儲該節(jié)點的子節(jié)點的地址

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

　　int breakpoint; //輔助變量,當該節(jié)點需要分裂時,用于記錄分裂點的位置

　　}*mynode;

　　classCSuffixTree

　　{

　　public:

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

　　mynode point; //point節(jié)點指針，搜索時指向搜索節(jié)點的父節(jié)點，搜索結束時根據搜索

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

　　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指針并產個根節(jié)點的第一個子節(jié)點，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++)//調用兩層循環(huán)，產生目標字符串每一個前綴的所 有后綴

　　{

　　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年)