C++基礎(chǔ):遞歸遍歷存儲(chǔ)層次結(jié)構(gòu)的鏈表

最近碰到要從一個(gè)存儲(chǔ)層次結(jié)構(gòu)的鏈表中拿數(shù)據(jù)出來(lái)處理的問(wèn)題。層次結(jié)構(gòu)嵌套的層次是不明確的，所以要用遞歸來(lái)讀取。遞歸其實(shí)就是深度優(yōu)先搜索，也就是回溯法。遞歸是求解問(wèn)題本省能夠劃分為形式、結(jié)構(gòu)相同，但是問(wèn)題規(guī)模逐漸變小的子問(wèn)題的問(wèn)題的利器。
    所以遞歸實(shí)現(xiàn)有兩個(gè)關(guān)鍵點(diǎn)：
    一就是問(wèn)題劃分出來(lái)的子問(wèn)題和原問(wèn)題有相同的形式、結(jié)構(gòu)，只要這樣才能利用同一個(gè)函數(shù)體，即所說(shuō)的遞歸調(diào)用。
    二就是子問(wèn)題的規(guī)模逐漸變小，這個(gè)在遞歸調(diào)用時(shí)就體現(xiàn)在參數(shù)上。所以遞歸函數(shù)肯定是有參數(shù)的，如果沒(méi)有參數(shù)，則一定是用了全局變量。當(dāng)問(wèn)題規(guī)模足夠小的時(shí)候，就是遞歸調(diào)用返回的時(shí)候。在網(wǎng)上看到GOOGLE的筆試題中就考過(guò)這個(gè)知識(shí)點(diǎn)。
    下面用STL的list通用容器模擬了這類問(wèn)題。
    代碼如下：
    #include
    #include
    using namespace std;
    typedef struct tagNode {
    int data;
    list subList;
    } Node;
    void TraverseList(list L);
    int main()
    {
    list* pList = new list;
    Node* pnode1 = new Node;
    pnode1->data = 1;
    pList->insert(pList->begin(), pnode1);
    Node* pnode2 = new Node;
    pnode2->data = 2;
    pnode1->subList.insert(pnode1->subList.begin(), pnode2);
    Node* pnode3 = new Node;
    pnode3->data = 3;
    pnode2->subList.insert(pnode2->subList.begin(), pnode3);
    Node* pnode4 = new Node;
    pnode4->data = 4;
    pnode3->subList.insert(pnode3->subList.begin(), pnode4);
    Node* pnode5 = new Node;
    pnode5->data = 5;
    pnode4->subList.insert(pnode4->subList.begin(), pnode5);
    Node* pnode6 = new Node;
    pnode6->data = 6;
    list::iterator it = pList->end();
    pList->insert(it, pnode6);
    Node* pnode7 = new Node;
    pnode7->data = 7;
    it = pList->end();
    pList->insert(it, pnode7);
    TraverseList(*pList);
    return 0;
    }
    void TraverseList(list L)
    {
    if (!L.empty()) {
    list::iterator it = L.begin();
    Node* pNode = *it;
    do {
    if (pNode != NULL) {
    cout << pNode->data << endl;
    /*if (!pNode->subList.empty())*/
    TraverseList(pNode->subList);
    }
    } while (++it != L.end() && (pNode = *it) != NULL);
    }
    }