C++應(yīng)用程序性能優(yōu)化（四）——C++常用數(shù)據(jù)結(jié)構(gòu)性能分析

C++應(yīng)用程序性能優(yōu)化（四）——C++常用數(shù)據(jù)結(jié)構(gòu)性能分析

本文將根據(jù)各種實(shí)用操作（遍歷、插入、刪除、排序、查找）并結(jié)合實(shí)例對(duì)常用數(shù)據(jù)結(jié)構(gòu)進(jìn)行性能分析。

創(chuàng)新互聯(lián)建站是一家集網(wǎng)站建設(shè),平原企業(yè)網(wǎng)站建設(shè),平原品牌網(wǎng)站建設(shè),網(wǎng)站定制,平原網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷(xiāo),網(wǎng)絡(luò)優(yōu)化,平原網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿(mǎn)足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專(zhuān)業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶(hù)成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

一、常用數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)介

1、數(shù)組

數(shù)組是最常用的一種線(xiàn)性表，對(duì)于靜態(tài)的或者預(yù)先能確定大小的數(shù)據(jù)集合，采用數(shù)組進(jìn)行存儲(chǔ)是最佳選擇。
數(shù)組的優(yōu)點(diǎn)一是查找方便，利用下標(biāo)即可立即定位到所需的數(shù)據(jù)節(jié)點(diǎn)；二是添加或刪除元素時(shí)不會(huì)產(chǎn)生內(nèi)存碎片；三是不需要考慮數(shù)據(jù)節(jié)點(diǎn)指針的存儲(chǔ)。然而，數(shù)組作為一種靜態(tài)數(shù)據(jù)結(jié)構(gòu)，存在內(nèi)存使用率低、可擴(kuò)展性差的缺點(diǎn)。無(wú)論數(shù)組中實(shí)際有多少元素，編譯器總會(huì)按照預(yù)先設(shè)定好的內(nèi)存容量進(jìn)行分配。如果超出邊界，則需要建立新的數(shù)組。

2、鏈表

鏈表是另一種常用的線(xiàn)性表，一個(gè)鏈表就是一個(gè)由指針連接的數(shù)據(jù)鏈。每個(gè)數(shù)據(jù)節(jié)點(diǎn)由指針域和數(shù)據(jù)域構(gòu)成，指針一般指向鏈表中的下一個(gè)節(jié)點(diǎn)，如果節(jié)點(diǎn)是鏈表中的最后一個(gè)，則指針為NULL。在雙向鏈表（Double Linked List）中，指針域還包括一個(gè)指向上一個(gè)數(shù)據(jù)節(jié)點(diǎn)的指針。在跳轉(zhuǎn)鏈表（Skip Linked List）中，指針域包含指向任意某個(gè)關(guān)聯(lián)向的指針。

template <typename T>
class LinkedNode
{
public:
    LinkedNode(const T& e): pNext(NULL), pPrev(NULL)
    {
        data = e;
    }
    LinkedNode<T>* Next()const
    {
        return pNext;
    }
    LinkedNode<T>* Prev()const
    {
        return pPrev;
    }
private:
    T data;
    LinkedNode<T>* pNext;// 指向下一個(gè)數(shù)據(jù)節(jié)點(diǎn)的指針
    LinkedNode<T>* pPrev;// 指向上一個(gè)數(shù)據(jù)節(jié)點(diǎn)的指針
    LinkedNode<T>* pConnection;// 指向關(guān)聯(lián)節(jié)點(diǎn)的指針
};

與預(yù)先靜態(tài)分配好存儲(chǔ)空間的數(shù)組不同，鏈表的長(zhǎng)度是可變的。只要內(nèi)存空間足夠，程序就能持續(xù)為鏈表插入新的數(shù)據(jù)項(xiàng)。數(shù)組中所有的數(shù)據(jù)項(xiàng)都被存放在一段連續(xù)的存儲(chǔ)空間中，鏈表中的數(shù)據(jù)項(xiàng)會(huì)被隨機(jī)分配到內(nèi)存的某個(gè)位置。

3、哈希表

數(shù)組和鏈表有各自的優(yōu)缺點(diǎn)，數(shù)組能夠方便定位到任何數(shù)據(jù)項(xiàng)，但擴(kuò)展性較差；鏈表則無(wú)法提供快捷的數(shù)據(jù)項(xiàng)定位，但插入和刪除任意一個(gè)數(shù)據(jù)項(xiàng)都很簡(jiǎn)單。當(dāng)需要處理大規(guī)模的數(shù)據(jù)集合時(shí)，通常需要將數(shù)組和鏈表的優(yōu)點(diǎn)結(jié)合。通過(guò)結(jié)合數(shù)組和鏈表的優(yōu)點(diǎn)，哈希表能夠達(dá)到較好的擴(kuò)展性和較高的訪(fǎng)問(wèn)效率。
雖然每個(gè)開(kāi)發(fā)者都可以構(gòu)建自己的哈希表，但哈希表都有共同的基本結(jié)構(gòu)，如下：

哈希數(shù)組中每個(gè)項(xiàng)都有指針指向一個(gè)小的鏈表，與某項(xiàng)相關(guān)的所有數(shù)據(jù)節(jié)點(diǎn)都會(huì)被存儲(chǔ)在鏈表中。當(dāng)程序需要訪(fǎng)問(wèn)某個(gè)數(shù)據(jù)節(jié)點(diǎn)時(shí)，不需要遍歷整個(gè)哈希表，而是先找到數(shù)組中的項(xiàng)，然后查詢(xún)子鏈表找到目標(biāo)節(jié)點(diǎn)。每個(gè)子鏈表稱(chēng)為一個(gè)桶（Bucket），如何定位一個(gè)存儲(chǔ)目標(biāo)節(jié)點(diǎn)的桶，由數(shù)據(jù)節(jié)點(diǎn)的關(guān)鍵字域Key和哈希函數(shù)共同確定，雖然存在多種映射方法，但實(shí)現(xiàn)哈希函數(shù)最常用的方法還是除法映射。除法函數(shù)的形式如下：
F（k） = k % D
k是數(shù)據(jù)節(jié)點(diǎn)的關(guān)鍵字，D是預(yù)先設(shè)計(jì)的常量，F(xiàn)（k）是桶的序號(hào)（等同于哈希數(shù)組中每個(gè)項(xiàng)的下標(biāo)），哈希表實(shí)現(xiàn)如下：

// 數(shù)據(jù)節(jié)點(diǎn)定義
template <class E, class Key>
class LinkNode
{
public:
    LinkNode(const E& e, const Key& k): pNext(NULL), pPrev(NULL)
    {
        data = e;
        key = k;
    }
    void setNextNode(LinkNode<E, Key>* next)
    {
        pNext = next;
    }
    LinkNode<E, Key>* Next()const
    {
        return pNext;
    }
    void setPrevNode(LinkNode<E, Key>* prev)
    {
        pPrev = prev;
    }
    LinkNode<E, Key>* Prev()const
    {
        return pPrev;
    }

    E& getData()const
    {
        return data;
    }
    Key& getKey()const
    {
        return key;
    }
private:
    // 指針域
    LinkNode<E, Key>* pNext;
    LinkNode<E, Key>* pPrev;
    // 數(shù)據(jù)域
    E data;// 數(shù)據(jù)
    Key key;//關(guān)鍵字
};

// 哈希表定義
template <class E, class Key>
class HashTable
{
private:
    typedef LinkNode<E, Key>* LinkNodePtr;
    LinkNodePtr* hashArray;// 哈希數(shù)組
    int size;// 哈希數(shù)組大小
public:
    HashTable(int n = 100);
    ~HashTable();
    bool Insert(const E& data);
    bool Delete(const Key& k);
    bool Search(const Key& k, E& ret)const;
private:
    LinkNodePtr searchNode()const;
    // 哈希函數(shù)
    int HashFunc(const Key& k)
    {
        return k % size;
    }

};
// 哈希表的構(gòu)造函數(shù)
template <class E, class Key>
HashTable<E, Key>::HashTable(int n)
{
    size = n;
    hashArray = new LinkNodePtr[size];
    memset(hashArray, 0, size * sizeof(LinkNodePtr));
}
// 哈希表的析構(gòu)函數(shù)S
template <class E, class Key>
HashTable<E, Key>::~HashTable()
{
    for(int i = 0; i < size; i++)
    {
        if(hashArray[i] != NULL)
        {
            // 釋放每個(gè)桶的內(nèi)存
            LinkNodePtr p = hashArray[i];
            while(p)
            {
                LinkNodePtr toDel = p;
                p = p->Next();
                delete toDel;
            }
        }
    }
    delete [] hashArray;
}

分析代碼，哈希函數(shù)決定了一個(gè)哈希表的效率和性能。
當(dāng)F（k）=k時(shí)，哈希表中的每個(gè)桶僅有一個(gè)節(jié)點(diǎn)，哈希表是一個(gè)一維數(shù)組，雖然每個(gè)數(shù)據(jù)節(jié)點(diǎn)的指針會(huì)造成一定的內(nèi)存空間浪費(fèi)，但查找效率最高（時(shí)間復(fù)雜度O（1））。
當(dāng)F（k）=c時(shí)，哈希表所有的節(jié)點(diǎn)存放在一個(gè)桶中，哈希表退化為鏈表，同時(shí)還加上一個(gè)多余的、基本為空的數(shù)組，查找一個(gè)節(jié)點(diǎn)的時(shí)間效率為O（n），效率最低。
因此，構(gòu)建一個(gè)理想的哈希表需要盡可能的使用讓數(shù)據(jù)節(jié)點(diǎn)分配更均勻的哈希函數(shù)，同時(shí)哈希表的數(shù)據(jù)結(jié)構(gòu)也是影響其性能的一個(gè)重要因素。例如，桶的數(shù)量太少會(huì)造成巨大的鏈表，導(dǎo)致查找效率低下，太多的桶則會(huì)導(dǎo)致內(nèi)存浪費(fèi)。因此，在設(shè)計(jì)和實(shí)現(xiàn)哈希表前，需要分析數(shù)據(jù)節(jié)點(diǎn)的關(guān)鍵值，根據(jù)其分布來(lái)決定需要造多大的哈希數(shù)組和使用什么樣的哈希函數(shù)。
哈希表的實(shí)現(xiàn)中，數(shù)據(jù)節(jié)點(diǎn)的組織方式多種多樣，并不局限于鏈表，桶可以是一棵樹(shù)，也可以是一個(gè)哈希表。

4、二叉樹(shù)

二叉樹(shù)是一種常用數(shù)據(jù)結(jié)構(gòu)，開(kāi)發(fā)人員通常熟知二叉查找樹(shù)。在一棵二叉查找樹(shù)中，所有節(jié)點(diǎn)的左子節(jié)點(diǎn)的關(guān)鍵值都小于等于本身，而右子節(jié)點(diǎn)的關(guān)鍵值大于等于本身。由于平衡二叉查找樹(shù)與有序數(shù)組的折半查找算法原理相同，所以查詢(xún)效率要遠(yuǎn)高于鏈表（O（Log2n）），而鏈表為O（n）。但由于樹(shù)中每個(gè)節(jié)點(diǎn)都要保存兩個(gè)指向子節(jié)點(diǎn)的指針，空間代價(jià)要遠(yuǎn)高于單向鏈表和數(shù)組，并且樹(shù)中每個(gè)節(jié)點(diǎn)的內(nèi)存分配是不連續(xù)的，導(dǎo)致內(nèi)存碎片化。但二叉樹(shù)在插入、刪除以及查找等操作上的良好表現(xiàn)使其成為最常用的數(shù)據(jù)結(jié)構(gòu)之一。二叉樹(shù)的鏈表實(shí)現(xiàn)如下：

template <class T>
class TreeNode
{
public:
    TreeNode(const TreeNode& e): left(NULL), right(NULL)
    {
        data = e;
    }
    TreeNode<T>* Left()const
    {
        return left;
    }
    TreeNode<T>* Right()const
    {
        return right;
    }
private:
    T data;
    TreeNode<T>* left;
    TreeNode<T>* right;
};

二、數(shù)據(jù)結(jié)構(gòu)的遍歷操作

1、數(shù)組的遍歷

遍歷數(shù)組的操作很簡(jiǎn)單，無(wú)論是順序還是逆序都可以遍歷數(shù)組，也可以任意位置開(kāi)始遍歷數(shù)組。

2、鏈表的遍歷

跟蹤指針便能完成鏈表的遍歷：

    LinkNode<E>* pNode = pFirst;
    while(pNode)
    {
        pNode = pNode->Next();
        // do something
    }

雙向鏈表可以支持順序和逆序遍歷，跳轉(zhuǎn)鏈表通過(guò)過(guò)濾某些無(wú)用節(jié)點(diǎn)可以實(shí)現(xiàn)快速遍歷。

3、哈希表的遍歷

如果預(yù)先知道所有節(jié)點(diǎn)的Key值，可以通過(guò)Key值和哈希函數(shù)找到每一個(gè)非空的桶，然后遍歷桶的鏈表。否則只能通過(guò)遍歷哈希數(shù)組的方式遍歷每個(gè)桶。

 for(int i = 0; i < size; i++)
    {
        LinkNodePtr pNode = hashArray[i];
        while(pNode) != NULL)
        {
            // do something
            pNode = pNode->Next();
        }
    }

4、二叉樹(shù)的遍歷

遍歷二叉樹(shù)由三種方式：前序，中序，后序，三種遍歷方式的遞歸實(shí)現(xiàn)如下：

// 前序遍歷
template <class E>
void PreTraverse(TreeNode<E>* pNode)
{
    if(pNode != NULL)
    {
        // do something
        doSothing(pNode);
        PreTraverse(pNode->Left());
        PreTraverse(pNode->Right());
    }
}

// 中序遍歷
template <class E>
void InTraverse(TreeNode<E>* pNode)
{
    if(pNode != NULL)
    {
        InTraverse(pNode->Left());
        // do something
        doSothing(pNode);
        InTraverse(pNode->Right());
    }
}

// 后序遍歷
template <class E>
void PostTraverse(TreeNode<E>* pNode)
{
    if(pNode != NULL)
    {
        PostTraverse(pNode->Left());
        PostTraverse(pNode->Right());
        // do something
        doSothing(pNode);
    }
}

使用遞歸方式對(duì)二叉樹(shù)進(jìn)行遍歷的缺點(diǎn)主要是隨著樹(shù)的深度增加，程序?qū)瘮?shù)?？臻g的使用越來(lái)越多，由于?？臻g的大小有限，遞歸方式遍歷可能會(huì)導(dǎo)致內(nèi)存耗盡。解決辦法主要有兩個(gè)：一是使用非遞歸算法實(shí)現(xiàn)前序、中序、后序遍歷，即仿照遞歸算法執(zhí)行時(shí)函數(shù)工作棧的變化狀況，建立一個(gè)棧對(duì)當(dāng)前遍歷路徑上的節(jié)點(diǎn)進(jìn)行記錄，根據(jù)棧頂元素是否存在左右節(jié)點(diǎn)的不同情況，決定下一步操作（將子節(jié)點(diǎn)入?；虍?dāng)前節(jié)點(diǎn)退棧），從而完成二叉樹(shù)的遍歷；二是使用線(xiàn)索二叉樹(shù)，即根據(jù)遍歷規(guī)則，在每個(gè)葉子節(jié)點(diǎn)增加指向后續(xù)節(jié)點(diǎn)的指針。

三、數(shù)據(jù)結(jié)構(gòu)的插入操作

1、數(shù)組的插入

由于數(shù)組中的所有數(shù)據(jù)節(jié)點(diǎn)都保存在連續(xù)的內(nèi)存中，所以插入新的節(jié)點(diǎn)需要移動(dòng)插入位置之后的所有節(jié)點(diǎn)以騰出空間，才能正確地將新節(jié)點(diǎn)復(fù)制到插入位置。如果恰好數(shù)組已滿(mǎn)，還需要重新建立一個(gè)新的容量更大的數(shù)組，將原數(shù)組的所有節(jié)點(diǎn)拷貝到新數(shù)組，因此數(shù)組的插入操作與其它數(shù)據(jù)結(jié)構(gòu)相比，時(shí)間復(fù)雜度更高。
如果向一個(gè)未滿(mǎn)的數(shù)組插入節(jié)點(diǎn)，最好的情況是插入到數(shù)組的末尾，時(shí)間復(fù)雜度是O（1），最壞情況是插入到數(shù)組頭部，需要移動(dòng)數(shù)組的所有節(jié)點(diǎn)，時(shí)間復(fù)雜度是O（n）。
如果向一個(gè)滿(mǎn)數(shù)組插入節(jié)點(diǎn)，通常做法是先創(chuàng)建一個(gè)更大的數(shù)組，然后將原數(shù)組的所有節(jié)點(diǎn)拷貝到新數(shù)組，同時(shí)插入新節(jié)點(diǎn)，最后刪除元數(shù)組，時(shí)間復(fù)雜度為O（n）。在刪除元數(shù)組之前，兩個(gè)數(shù)組必須并存一段時(shí)間，空間開(kāi)銷(xiāo)較大。

2、鏈表的插入

在鏈表中插入一個(gè)新節(jié)點(diǎn)很簡(jiǎn)單，對(duì)于單鏈表只需要修改插入位置之前節(jié)點(diǎn)的pNext指針使其指向本節(jié)點(diǎn)，然后將本節(jié)點(diǎn)的pNext指針指向下一個(gè)節(jié)點(diǎn)即可（對(duì)于鏈表頭不存在上一個(gè)節(jié)點(diǎn)，對(duì)于鏈表尾不存在下一個(gè)節(jié)點(diǎn)）。對(duì)于雙向鏈表和跳轉(zhuǎn)鏈表，需要修改相關(guān)節(jié)點(diǎn)的指針。鏈表的插入操作與長(zhǎng)度無(wú)關(guān)，時(shí)間復(fù)雜度為O（1），當(dāng)然鏈表的插入操作通常會(huì)伴隨鏈表插入節(jié)點(diǎn)位置的定位，需要一定時(shí)間。

3、哈希表的插入

在哈希表中插入一個(gè)節(jié)點(diǎn)需要完成兩部操作，定位桶并向鏈表插入節(jié)點(diǎn)。

template <class E, class Key>
bool HashTable<E, Key>::Insert(const E& data)
{
    Key k = data;// 提取關(guān)鍵字
    // 創(chuàng)建一個(gè)新節(jié)點(diǎn)
    LinkNodePtr pNew = new LinkNodePtr(data, k);
    int index = HashFunc(k);//定位桶
    LinkNodePtr p = hashArray[index];
    // 如果是空桶，直接插入
    if(NULL == p)
    {
        hashArray[index] = pNew;
        return true;
    }
    // 在表頭插入節(jié)點(diǎn)
    hashArray[index] = pNew;
    pNew->SetNextNode(p);
    p->SetPrevNode(pNew);
    return true;
}

哈希表插入操作的時(shí)間復(fù)雜度為O（1），如果桶的鏈表是有序的，需要花時(shí)間定位鏈表中插入的位置，如果鏈表長(zhǎng)度為M，則時(shí)間復(fù)雜度為O（M）。

4、二叉樹(shù)的插入

二叉樹(shù)的結(jié)構(gòu)直接影響插入操作的效率，對(duì)于平衡二叉查找樹(shù)，插入節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（Log2N）。對(duì)于非平衡二叉樹(shù)，插入節(jié)點(diǎn)的時(shí)間復(fù)雜度比較高，在最壞情況下，非平衡二叉樹(shù)所有的left節(jié)點(diǎn)都為NULL，二叉樹(shù)退化為鏈表，插入節(jié)點(diǎn)新節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（n）。
當(dāng)節(jié)點(diǎn)數(shù)量很多時(shí)，對(duì)平衡二叉樹(shù)中進(jìn)行插入操作的效率要遠(yuǎn)高于非平衡二叉樹(shù)。工程開(kāi)發(fā)中，通常避免非平衡二叉樹(shù)的出現(xiàn)，或是將非平衡二叉樹(shù)轉(zhuǎn)換為平衡二叉樹(shù)。簡(jiǎn)單做法如下：
（1）中序遍歷非平衡二叉樹(shù)，在一個(gè)數(shù)組中保存所有的節(jié)點(diǎn)的指針。
（2）由于數(shù)組中所有元素都是有序排列的，可以使用折半查找遍歷數(shù)組，自上而下逐層構(gòu)建平衡二叉樹(shù)。

四、數(shù)據(jù)結(jié)構(gòu)的刪除操作

1、數(shù)組的刪除

從數(shù)組中刪除節(jié)點(diǎn)，如果需要數(shù)組沒(méi)有空洞，需要在刪除節(jié)點(diǎn)后將其后所有節(jié)點(diǎn)向前移動(dòng)。最壞情況下（刪除首節(jié)點(diǎn)），時(shí)間復(fù)雜度為O（n），最好情況下（刪除尾節(jié)點(diǎn)），時(shí)間復(fù)雜度為O（1）。
在某些場(chǎng)合（如動(dòng)態(tài)數(shù)組），當(dāng)刪除完成后如果數(shù)組中存在大量空閑位置，則需要縮小數(shù)組，即創(chuàng)建一個(gè)較小的新數(shù)組，將原數(shù)組中所有節(jié)點(diǎn)拷貝到新數(shù)組，再將原數(shù)組刪除。因此，會(huì)導(dǎo)致較大的空間與時(shí)間開(kāi)銷(xiāo)，應(yīng)謹(jǐn)慎設(shè)置數(shù)組的大小，即要盡量避免內(nèi)存空間的浪費(fèi)也要減少數(shù)組的放大或縮小操作。通常，每當(dāng)需要?jiǎng)h除數(shù)組中的某個(gè)節(jié)點(diǎn)時(shí)，并不將其真正刪除，而是在節(jié)點(diǎn)的位置設(shè)計(jì)一個(gè)標(biāo)記位bDelete，將其設(shè)置為true，同時(shí)禁止其它程序使用本節(jié)點(diǎn)，待數(shù)組中需要?jiǎng)h除的節(jié)點(diǎn)達(dá)到一定閾值時(shí)，再統(tǒng)一刪除，避免多次移動(dòng)節(jié)點(diǎn)操作，降低時(shí)間復(fù)雜度。

2、鏈表的刪除

鏈表中刪除節(jié)點(diǎn)的操作，直接將被刪除節(jié)點(diǎn)的上一節(jié)點(diǎn)的指針指向被刪除節(jié)點(diǎn)的下一節(jié)點(diǎn)即可，刪除操作的時(shí)間復(fù)雜度是O（1）。

3、哈希表的刪除

從哈希表中刪除一個(gè)節(jié)點(diǎn)的操作如下：首先通過(guò)哈希函數(shù)和鏈表遍歷（桶由鏈表實(shí)現(xiàn)）找到待刪除節(jié)點(diǎn)，然后刪除節(jié)點(diǎn)并重新設(shè)置前向和后向指針。如果被刪除節(jié)點(diǎn)是桶的首節(jié)點(diǎn)，則將桶的頭指針指向后續(xù)節(jié)點(diǎn)。

template <class E, class Key>
bool HashTable<E, Key>::Delete(const Key& k)
{
    // 找到關(guān)鍵值匹配的節(jié)點(diǎn)
    LinkNodePtr p = SearchNode(k);

    if(NULL == p)
    {
        return false;
    }
    // 修改前向節(jié)點(diǎn)和后向節(jié)點(diǎn)的指針
    LinkNodePtr pPrev = p->Prev();
    if(pPrev)
    {
        LinkNodePtr pNext = p->Next();
        if(pNext)
        {
            pNext->SetPrevNode(pPrev);
            pPrev->SetNextNode(pNext);
        }
        else
        {
            // 如果前向節(jié)點(diǎn)為NULL，則當(dāng)前節(jié)點(diǎn)p為首節(jié)點(diǎn)
            // 修改哈希數(shù)組中的節(jié)點(diǎn)的指針，使其指向后向節(jié)點(diǎn)。
            int index = HashFunc(k);
            hashArray[index] = p->Next();
            if(p->Next() != NULL)
            {
                p->Next()->SetPrevNode(NULL);
            }
        }
    }
    delete p;
    return true;
}

4、二叉樹(shù)的刪除

從二叉樹(shù)刪除一個(gè)節(jié)點(diǎn)需要根據(jù)情況討論：
（1）如果節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接刪除。
（2）如果刪除節(jié)點(diǎn)僅有一個(gè)子節(jié)點(diǎn)，則將子節(jié)點(diǎn)替換被刪除節(jié)點(diǎn)。
（3）如果刪除節(jié)點(diǎn)的左右子節(jié)點(diǎn)都存在，由于每個(gè)子節(jié)點(diǎn)都可能有自己的子樹(shù)，需要找到子樹(shù)中合適的節(jié)點(diǎn)，并將其立為新的根節(jié)點(diǎn)，并整合兩棵子樹(shù)，重新加入到原二叉樹(shù)。

五、數(shù)據(jù)結(jié)構(gòu)的排序操作

1、數(shù)組的排序

數(shù)組的排序包括冒泡、選擇、插入等排序方法。

template <typename T>
void Swap(T& a, T& b)
{
  T temp;
  temp = a;
  a = b;
  b = temp;
}

冒泡排序?qū)崿F(xiàn)：

/**********************************************
* 排序方式：冒泡排序
* array:序列
* len：序列中元素個(gè)數(shù)
* min2max：按從小到大進(jìn)行排序
* *******************************************/
template <typename T>
static void Bubble(T array[], int len, bool min2max = true)
{
    bool exchange = true;
    //遍歷所有元素
    for(int i = 0; (i < len) && exchange; i++)
    {
            exchange = false;
            //將尾部元素與前面的每個(gè)元素作比較交換
            for(int j = len - 1; j > i; j--)
            {
                    if(min2max?(array[j] < array[j-1]):(array[j] > array[j-1]))
                    {
                            //交換元素位置
                            Swap(array[j], array[j-1]);
                            exchange = true;
                    }
            }
    }
}

冒泡排序的時(shí)間復(fù)雜度為O（n^2），冒泡排序是穩(wěn)定的排序方法。
選擇排序?qū)崿F(xiàn)：

/******************************************
* 排序方式：選擇排序
* array:序列
* len：序列中元素個(gè)數(shù)
* min2max：按從小到大進(jìn)行排序
* ***************************************/
template <typename T>
void Select(T array[], int len, bool min2max = true)
{
 for(int i = 0; i < len; i++)
 {
     int min = i;//從第i個(gè)元素開(kāi)始
     //對(duì)待排序的元素進(jìn)行比較
     for(int j = i + 1; j < len; j++)
     {
         //按排序的方式選擇比較方式
         if(min2max?(array[min] > array[j]):(array[min] < array[j]))
         {
             min = j;
         }
     }
     if(min != i)
     {
        //元素交換
        Swap(array[i], array[min]);
     }
 }
}

選擇排序的時(shí)間復(fù)雜度為O（n^2），選擇排序是不穩(wěn)定的排序方法。
插入排序?qū)崿F(xiàn)：

/******************************************
 * 排序方式：選擇排序
 * array:序列
 * len：序列中元素個(gè)數(shù)
 * min2max：按從小到大進(jìn)行排序
 * ***************************************/
template <typename T>
void Select(T array[], int len, bool min2max = true)
{
  for(int i = 0; i < len; i++)
  {
      int min = i;//從第i個(gè)元素開(kāi)始
      //對(duì)待排序的元素進(jìn)行比較
      for(int j = i + 1; j < len; j++)
      {
          //按排序的方式選擇比較方式
          if(min2max?(array[min] > array[j]):(array[min] < array[j]))
          {
              min = j;
          }
      }
      if(min != i)
      {
         //元素交換
         Swap(array[i], array[min]);
      }
  }
}

插入排序的時(shí)間復(fù)雜度為O（n^2），插入排序是穩(wěn)定的排序方法。

2、鏈表的排序

雖然鏈表在插入和刪除操作上性能優(yōu)越，但排序復(fù)雜度卻很高，尤其是單向鏈表。由于鏈表中訪(fǎng)問(wèn)某個(gè)節(jié)點(diǎn)需要依賴(lài)其它節(jié)點(diǎn)，不能根據(jù)下標(biāo)直接定位到任意一項(xiàng)，因此節(jié)點(diǎn)定位的時(shí)間復(fù)雜度為O（N），排序效率低下。
工程開(kāi)發(fā)中，可以使用數(shù)組鏈表，當(dāng)需要排序時(shí)構(gòu)造一個(gè)數(shù)組，存放鏈表中每個(gè)節(jié)點(diǎn)的指針。在排序過(guò)程中通過(guò)數(shù)組定位每個(gè)節(jié)點(diǎn)，并實(shí)現(xiàn)節(jié)點(diǎn)的交換。
鏈表數(shù)組為直接訪(fǎng)問(wèn)鏈表的節(jié)點(diǎn)提供了便利，但是使用空間換時(shí)間的方法，如果希望得到一個(gè)有序鏈表，最好是在構(gòu)建鏈表時(shí)將每個(gè)節(jié)點(diǎn)插入到合適的位置。

3、哈希表的排序

由于采用哈希函數(shù)訪(fǎng)問(wèn)每個(gè)桶，因此哈希表中對(duì)哈希數(shù)組排序毫無(wú)意義，但具體節(jié)點(diǎn)的定位需要通過(guò)查詢(xún)每個(gè)桶鏈表完成（桶由鏈表實(shí)現(xiàn)），將桶的鏈表排序可以提高節(jié)點(diǎn)的查詢(xún)效率。

4、二叉樹(shù)的排序

對(duì)于二叉查找樹(shù)，其本身是有序的，中序遍歷可以得到二叉查找樹(shù)有序的節(jié)點(diǎn)輸出。對(duì)于未排序的二叉樹(shù)，所有節(jié)點(diǎn)被隨機(jī)組織，定位節(jié)點(diǎn)的時(shí)間復(fù)雜度為O（N）。

六、數(shù)據(jù)結(jié)構(gòu)的查找操作

1、數(shù)組的查找

數(shù)組的最大優(yōu)點(diǎn)是可以通過(guò)下標(biāo)任意的訪(fǎng)問(wèn)節(jié)點(diǎn)，而不需要借助指針、索引或遍歷，時(shí)間復(fù)雜度為O（1）。對(duì)于下標(biāo)未知的情況查找節(jié)點(diǎn)，則只能遍歷數(shù)組，時(shí)間復(fù)雜度為O（N）。對(duì)于有序數(shù)組，最好的查找算法是二分查找法。

template <class E>
int BinSearch(E array[], const E& value, int start, int end)
{
    if(end - start < 0)
    {
        return INVALID_INPUT;
    }
    if(value == array[start])
    {
        return start;
    }
    if(value == array[end])
    {
        return end;
    }
    while(end > start + 1)
    {
        int temp  = (end + start) / 2;
        if(value == array[temp])
        {
            return temp;
        }
        if(array[temp] < value)
        {
            start = temp;
        }
        else
        {
            end = temp;
        }
    }
    return -1;
}

折半查找的時(shí)間復(fù)雜度是O（Log2N），與二叉樹(shù)查詢(xún)效率相同。
對(duì)于亂序數(shù)組，只能通過(guò)遍歷方法查找節(jié)點(diǎn)，工程開(kāi)發(fā)中通常設(shè)置一個(gè)標(biāo)識(shí)變量保存更新節(jié)點(diǎn)的下標(biāo)，執(zhí)行查詢(xún)時(shí)從標(biāo)識(shí)變量標(biāo)記的下標(biāo)開(kāi)始遍歷數(shù)組，執(zhí)行效率比從頭開(kāi)始要高。

2、鏈表的查找

對(duì)于單向鏈表，最差情況下需要遍歷整個(gè)鏈表才能找到需要的節(jié)點(diǎn)，時(shí)間復(fù)雜度為O（N）。
對(duì)于有序鏈表，可以預(yù)先獲取某些節(jié)點(diǎn)的數(shù)據(jù)，可以選擇與目標(biāo)數(shù)據(jù)最接近的一個(gè)節(jié)點(diǎn)查找，效率取決于已知節(jié)點(diǎn)在鏈表中的分布，對(duì)于雙向有序鏈表效率會(huì)更高，如果正中節(jié)點(diǎn)已知，則查詢(xún)的時(shí)間復(fù)雜度為O（N/2）。
對(duì)于跳轉(zhuǎn)鏈表，如果預(yù)先能夠根據(jù)鏈表中節(jié)點(diǎn)之間的關(guān)系建立指針關(guān)聯(lián)，查詢(xún)效率將大大提高。

3、哈希表的查找

哈希表中查詢(xún)的效率與桶的數(shù)據(jù)結(jié)構(gòu)有關(guān)。桶由鏈表實(shí)現(xiàn)，則查詢(xún)效率和鏈表長(zhǎng)度有關(guān)，時(shí)間復(fù)雜度為O（M）。查找算法實(shí)現(xiàn)如下：

template <class E, class Key>
bool HashTable<E, Key>::SearchNode(const Key& k)const
{
    int index = HashFunc(k);
    // 空桶，直接返回
    if(NULL == hashArray[index])
        return NULL;
    // 遍歷桶的鏈表，如果由匹配節(jié)點(diǎn)，直接返回。
    LinkNodePtr p = hashArray[index];
    while(p)
    {
        if(k == p->GetKey())
            return p;
        p = p->Next();
    }
}

4、二叉樹(shù)的查找

在二叉樹(shù)中查找節(jié)點(diǎn)與樹(shù)的形狀有關(guān)。對(duì)于平衡二叉樹(shù)，查找效率為O（Log2N）；對(duì)于完全不平衡的二叉樹(shù)，查找效率為O（N）；
工程開(kāi)發(fā)中，通常需要構(gòu)建盡量平衡的二叉樹(shù)以提高查詢(xún)效率，但平衡二叉樹(shù)受插入、刪除操作影響很大，插入或刪除節(jié)點(diǎn)后需要調(diào)整二叉樹(shù)的結(jié)構(gòu)，通常，當(dāng)二叉樹(shù)的插入、刪除操作很多時(shí)，不需要在每次插入、刪除操作后都調(diào)整平衡度，而是在密集的查詢(xún)操作前統(tǒng)一調(diào)整一次。

七、動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)及分析

1、動(dòng)態(tài)數(shù)組簡(jiǎn)介

工程開(kāi)發(fā)中，數(shù)組是常用數(shù)據(jù)結(jié)構(gòu)，如果在編譯時(shí)就知道數(shù)組所有的維數(shù)，則可以靜態(tài)定義數(shù)組。靜態(tài)定義數(shù)組后，數(shù)組在內(nèi)存中占據(jù)的空間大小和位置是固定的，如果定義的是全局?jǐn)?shù)組，編譯器將在靜態(tài)數(shù)據(jù)區(qū)為數(shù)組分配空間，如果是局部數(shù)組，編譯器將在棧上為數(shù)組分配空間。但如果預(yù)先無(wú)法知道數(shù)組的維數(shù)，程序只有在運(yùn)行時(shí)才知道需要分配多大的數(shù)組，此時(shí)C++編譯器可以在堆上為數(shù)組動(dòng)態(tài)分配空間。
動(dòng)態(tài)數(shù)組的優(yōu)點(diǎn)如下：
（1）可分配空間較大。棧的大小都有限制，Linux系統(tǒng)可以使用ulimit -s查看，通常為8K。開(kāi)發(fā)者雖然可以設(shè)置，但由于需要保證程序運(yùn)行效率，通常不宜太大。堆空間的通?？晒┓峙鋬?nèi)存比較大，達(dá)到GB級(jí)別。
（2）使用靈活。開(kāi)發(fā)人員可以根據(jù)實(shí)際需要決定數(shù)組的大小和維數(shù)。
動(dòng)態(tài)數(shù)組的缺點(diǎn)如下：
（1）空間分配效率比靜態(tài)數(shù)組低。靜態(tài)數(shù)組一般由棧分配空間，動(dòng)態(tài)數(shù)組一般由堆分配空間。棧是機(jī)器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計(jì)算機(jī)會(huì)在底層為棧提供支持，即分配專(zhuān)門(mén)的寄存器存放棧的地址，壓棧和出棧都有專(zhuān)門(mén)的機(jī)器指令執(zhí)行，因而棧的效率比較高。堆由C++函數(shù)庫(kù)提供，其內(nèi)存分配機(jī)制比棧要復(fù)雜得多，為了分配一塊內(nèi)存，庫(kù)函數(shù)會(huì)按照一定的算法在堆內(nèi)存內(nèi)搜索可用的足夠大小的空間，如果發(fā)現(xiàn)空間不夠，將調(diào)用內(nèi)核方法去增加程序數(shù)據(jù)段的存儲(chǔ)空間，從而程序就有機(jī)會(huì)分配足夠大的內(nèi)存。因此堆的效率要比棧低。
（2）容易造成內(nèi)存泄露。動(dòng)態(tài)內(nèi)存需要開(kāi)發(fā)人員手工分配和釋放內(nèi)存，容易由于開(kāi)發(fā)人員的疏忽造成內(nèi)存泄露。

2、動(dòng)態(tài)數(shù)組實(shí)現(xiàn)

在實(shí)時(shí)視頻系統(tǒng)中，視頻服務(wù)器承擔(dān)視頻數(shù)據(jù)的緩存和轉(zhuǎn)發(fā)工作。一般，服務(wù)器為每臺(tái)攝像機(jī)開(kāi)辟一定大小且獨(dú)立的緩存區(qū)。視頻幀被寫(xiě)入此緩存區(qū)后，服務(wù)器在某一時(shí)刻再將其讀出，并向客戶(hù)端轉(zhuǎn)發(fā)。視頻幀的轉(zhuǎn)發(fā)是臨時(shí)的，由于緩存區(qū)大小有限而視頻數(shù)據(jù)源源不斷，所以一幀數(shù)據(jù)在被寫(xiě)入過(guò)后，過(guò)一段時(shí)間并會(huì)被新來(lái)的視頻幀所覆蓋。視頻幀的緩存時(shí)間由緩存區(qū)和視頻幀的長(zhǎng)度決定。
由于視頻幀數(shù)據(jù)量巨大，而一臺(tái)服務(wù)器通常需要支持幾十臺(tái)甚至數(shù)百臺(tái)攝像機(jī)，緩存結(jié)構(gòu)的設(shè)計(jì)是系統(tǒng)的重要部分。一方面，如果預(yù)先分配固定數(shù)量的內(nèi)存，運(yùn)行時(shí)不再增加、刪除，則服務(wù)器只能支持一定數(shù)量的攝像機(jī)，靈活性?。涣硪环矫?，由于視頻服務(wù)器程序在啟動(dòng)時(shí)將占據(jù)一大塊內(nèi)存，將導(dǎo)致系統(tǒng)整體性能下降，因此考慮使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)視頻緩存。
首先，服務(wù)器中為每臺(tái)攝像機(jī)分配一個(gè)一定大小的緩存塊，由類(lèi)CamBlock實(shí)現(xiàn)。每個(gè)CamBlock對(duì)象中有兩個(gè)動(dòng)態(tài)數(shù)組，分別存放視頻數(shù)據(jù)的_data和存放視頻幀索引信息的_frameIndex。每當(dāng)程序在內(nèi)存中緩存（讀?。┮粋€(gè)視頻幀時(shí)，對(duì)應(yīng)的CamBlock對(duì)象將根據(jù)視頻幀索引表_frameIndex找到視頻幀在_data中的存放位置，然后將數(shù)據(jù)寫(xiě)入或讀出。_data是一個(gè)循環(huán)隊(duì)列，一般根據(jù)FIFO進(jìn)行讀取，即如果有新幀進(jìn)入隊(duì)列，程序會(huì)在_data中最近寫(xiě)入幀的末尾開(kāi)始復(fù)制，如果超出數(shù)組長(zhǎng)度，則從頭覆蓋。

// 視頻幀的數(shù)據(jù)結(jié)構(gòu)
typedef struct
{
    unsigned short idCamera;// 攝像機(jī)ID
    unsigned long length;// 數(shù)據(jù)長(zhǎng)度
    unsigned short width;// 圖像寬度
    unsigned short height;// 圖像高度
    unsigned char* data; // 圖像數(shù)據(jù)地址
} Frame;

// 單臺(tái)攝像機(jī)的緩存塊數(shù)據(jù)結(jié)構(gòu)
class CamBlock
{
public:
    CamBlock(int id, unsigned long len, unsigned short numFrames):
        _data(NULL), _length(0), _idCamera(-1), _numFrames(0)
    {
        // 確保緩存區(qū)大小不超過(guò)閾值
        if(len > MAX_LENGTH || numFrames > MAX_FRAMES)
        {
            throw;
        }
        try
        {
            // 為幀索引表分配空間
            _frameIndex = new Frame[numFrames];
            // 為攝像機(jī)分配指定大小的內(nèi)存
            _data = new unsigned char[len];
        }
        catch(...)
        {
            throw;
        }
        memset(this, 0, len);
        _length = len;
        _idCamera = id;
        _numFrames = numFrames;

    }
    ~CamBlcok()
    {
        delete [] _frameIndex;
        delete [] _data;
    }
    // 根據(jù)索引表將視頻幀存入緩存
    bool SaveFrame(const Frame* frame);
    // 根據(jù)索引表定位到某一幀，讀取
    bool ReadFrame(Frame* frame);
private:
    Frame* _frameIndex;// 幀索引表
    unsigned char* _data;//存放圖像數(shù)據(jù)的緩存區(qū)
    unsigned long _length;// 緩存區(qū)大小
    unsigned short _idCamera;// 攝像機(jī)ID
    unsigned short _numFrames;//可存放幀的數(shù)量
    unsigned long _lastFrameIndex;//最后一幀的位置
};

為了管理每臺(tái)攝像機(jī)獨(dú)立的內(nèi)存塊，快速定位到任意一臺(tái)攝像機(jī)的緩存，甚至任意一幀，需要建立索引表CameraArray來(lái)管理所有的CamBlock對(duì)象。

class CameraArray
{
    typedef CamBlock BlockPtr;
    BlockPtr* cameraBufs;// 攝像機(jī)視頻緩存
    unsigned short cameraNum;// 當(dāng)前已經(jīng)連接的攝像機(jī)臺(tái)數(shù)
    unsigned short maxNum;//cameraBufs容量
    unsigned short increaseNum;//cameraBufs的增量
public:
    CameraArray(unsigned short max, unsigned short inc);
    ~CameraArray();
    // 插入一臺(tái)攝像機(jī)
    CamBlock* InsertBlock(unsigned short idCam, unsigned long size, unsigned short numFrames);
    // 刪除一臺(tái)攝像機(jī)
    bool RemoveBlock(unsigned short idCam);
private:
    // 根據(jù)攝像機(jī)ID返回其在數(shù)組的索引
    unsigned short GetPosition(unsigned short idCam);
};

CameraArray::CameraArray(unsigned short max, unsigned short inc):
    cameraBufs(NULL), cameraNum(0), maxNum(0), increaseNum(0)
{
    // 如果參數(shù)越界，拋出異常
    if(max > MAX_CAMERAS || inc > MAX_INCREMENTS)
        throw;
    try
    {
        cameraBufs = new BlockPtr[max];
    }
    catch(...)
    {
        throw;
    }
    maxNum = max;
    increaseNum = inc;
}

CameraArray::~CameraArray()
{
    for(int i = 0; i < cameraNum; i++)
    {
        delete cameraBufs[i];
    }
    delete [] cameraBufs;
}

通常，會(huì)為每個(gè)攝像機(jī)安排一個(gè)整型的ID，在CameraArray中，程序按照ID遞增的順序排列每個(gè)攝像機(jī)的CamBlock對(duì)象以方便查詢(xún)。當(dāng)一個(gè)新的攝像機(jī)接入系統(tǒng)時(shí)，程序會(huì)根據(jù)它的ID在CameraArray中找到一個(gè)合適的位置，然后利用相應(yīng)位置的指針創(chuàng)建一個(gè)新的CamBlock對(duì)象；當(dāng)某個(gè)攝像機(jī)斷開(kāi)連接，程序也會(huì)根據(jù)它的ID，找到對(duì)應(yīng)的CamBlock緩存塊，并將其刪除。

CamBlock* CameraArray::InsertBlock(unsigned short idCam, unsigned long size,
                                   unsigned short numFrames)
{
    // 在數(shù)組中找到合適的插入位置
    int pos = GetPosition(idCam);
    // 如果已經(jīng)達(dá)到數(shù)組邊界，需要擴(kuò)大數(shù)組
    if(cameraNum == maxNum)
    {
        // 定義新的數(shù)組指針，指定其維數(shù)
        BlockPtr* newBufs = NULL;
        try
        {
            BlockPtr* newBufs = new BlockPtr[maxNum + increaseNum];
        }
        catch(...)
        {
            throw;
        }
        // 將原數(shù)組內(nèi)容拷貝到新數(shù)組
        memcpy(newBufs, cameraBufs, maxNum * sizeof(BlockPtr));
        // 釋放原數(shù)組的內(nèi)存
        delete [] cameraBufs;
        maxNum += increaseNum;
        // 更新數(shù)組指針
        cameraBufs = newBufs;
    }
    if(pos != cameraNum)
    {
        // 在數(shù)組中插入一個(gè)塊，需要將其后所有指針位置后移
        memmov(cameraBufs + pos + 1, cameraBufs + pos, (cameraNum - pos) * sizeof(BlockPtr));
    }
    ++cameraNum;
    CamBlock* newBlock = new CamBlock(idCam, size, numFrames);
    cameraBufs[pos] = newBlock;
    return cameraBufs[pos];
}

如果接入系統(tǒng)的攝像機(jī)數(shù)量超出了最初創(chuàng)建CameraArray的設(shè)計(jì)容量，則考慮到系統(tǒng)的可擴(kuò)展性，只要硬件條件允許，需要增加cameraBufs的長(zhǎng)度。

bool CameraArray::RemoveBlock(unsigned short idCam)
{
    if(cameraNum < 1)
        return false;
    // 在數(shù)組中找到要?jiǎng)h除的攝像機(jī)的緩存區(qū)的位置
    int pos = GetPosition(idCam);
    cameraNum--;
    BlockPtr deleteBlock = cameraBufs[pos];
    delete deleteBlock;
    if(pos != cameraNum)
    {
        // 將pos后所有指針位置前移
        memmov(cameraBufs + pos, cameraBufs + pos + 1, (cameraNum - pos) * sizeof(BlockPtr));
    }
    // 如果數(shù)組中有過(guò)多空閑的位置，進(jìn)行釋放
    if(maxNum - cameraNum > increaseNum)
    {
        // 重新計(jì)算數(shù)組的長(zhǎng)度
        unsigned short len = (cameraNum / increaseNum + 1) * increaseNum;
        // 定義新的數(shù)組指針
        BlockPtr* newBufs = NULL;
        try
        {
            newBufs = new BlockPtr[len];
        }
        catch(...)
        {
            throw;
        }
        // 將原數(shù)組的數(shù)據(jù)拷貝到新的數(shù)組
        memcpy(newBufs, cameraBufs, cameraNum * sizeof(BlockPtr));
        delete cameraBufs;
        cameraBufs = newBufs;
        maxNum = len;
    }
    return true;
}

如果刪除一臺(tái)攝像機(jī)時(shí)，發(fā)現(xiàn)數(shù)組空間有過(guò)多空閑空間，則需要釋放相應(yīng)空閑空間。

網(wǎng)頁(yè)題目：C++應(yīng)用程序性能優(yōu)化（四）——C++常用數(shù)據(jù)結(jié)構(gòu)性能分析
文章網(wǎng)址：http://bm7419.com/article16/geigdg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷(xiāo)、自適應(yīng)網(wǎng)站、網(wǎng)站維護(hù)、網(wǎng)站改版、域名注冊(cè)、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)