我們來(lái)看看輸出結(jié)果，看看是不是遍歷呢
結(jié)果是正確的，我們來(lái)分析下上面的測(cè)試代碼的效率。第一個(gè) for 循環(huán)，因?yàn)槊看味际窃?0 位置處插入數(shù)據(jù)元素，因此它的時(shí)間復(fù)雜度是 O(1)；而第二個(gè) for 循環(huán)，因?yàn)樗垦h(huán)一遍，因此它的時(shí)間復(fù)雜度為 O(n)。我們就奇怪了，明明同樣是兩個(gè) for 循環(huán)，效率竟然不相同。不能以線性的時(shí)間復(fù)雜度完成單鏈表的遍歷，那么此時(shí)新的需求就產(chǎn)生了：為單鏈表提供新的方法，在線性時(shí)間內(nèi)完成遍歷。
下來(lái)說(shuō)說(shuō)設(shè)計(jì)思路，利用游標(biāo)的思想：
1、在單鏈表的內(nèi)部定義一個(gè)游標(biāo)（Node* m_current）；
2、遍歷開始前將游標(biāo)指向位置為 0 的數(shù)據(jù)元素；
3、獲取游標(biāo)指向的數(shù)據(jù)元素；
4、通過(guò)結(jié)點(diǎn)中的 next 指針移動(dòng)游標(biāo)。
提供一組遍歷相關(guān)的函數(shù)，以線性的時(shí)間復(fù)雜度完成遍歷鏈表，如下
遍歷函數(shù)原型設(shè)計(jì)如下：
bool move(int i, int step = 1);
bool end();
T current();
bool next();
下來(lái)我們來(lái)看看優(yōu)化后的 LinkList.h 是怎樣的，如下
LinkList.h 源碼
#ifndef LINKLIST_H
#define LINKLIST_H
#include "List.h"
#include "Exception.h"
namespace DTLib
{
template < typename T >
class LinkList : public List
{
protected:
struct Node : public Object
{
T value;
Node* next;
};
mutable struct : public Object
{
char reserved[sizeof(T)];
Node* next;
} m_header;
int m_length;
int m_step;
Node* m_current;
Node* position(int i) const
{
Node* ret = reinterpret_cast(&m_header);
for(int p=0; pnext;
}
return ret;
}
public:
LinkList()
{
m_header.next = NULL;
m_length = 0;
m_step = 1;
m_current = NULL;
}
bool insert(const T& e)
{
return insert(m_length, e);
}
bool insert(int i, const T& e)
{
bool ret = ((0 <= i) && (i <= m_length));
if( ret )
{
Node* node = new Node();
if( node != NULL )
{
Node* current = position(i);
node->value = e;
node->next = current->next;
current->next = node;
m_length++;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
}
}
}
bool remove(int i)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
Node* current = position(i);
Node* toDel = current->next;
current->next = toDel->next;
delete toDel;
m_length--;
}
return ret;
}
bool set(int i, const T& e)
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
position(i)->next->value = e;
}
return ret;
}
T get(int i) const
{
T ret;
if( get(i, ret) )
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element ...");
}
}
bool get(int i, T& e) const
{
bool ret = ((0 <= i) && (i < m_length));
if( ret )
{
e = position(i)->next->value;
}
return ret;
}
int find(const T& e) const
{
int ret = -1;
int i = 0;
Node* node = m_header.next;
while( node )
{
if( node->value == e )
{
ret = i;
break;
}
else
{
node = node->next;
i++;
}
}
return ret;
}
int length() const
{
return m_length;
}
void clear()
{
while( m_header.next )
{
Node* toDel = m_header.next;
m_header.next = toDel->next;
delete toDel;
}
m_length = 0;
}
bool move(int i, int step = 1)
{
bool ret = (0 <= i) && (i < m_length) && (step > 0);
if( ret )
{
m_current = position(i)->next;
m_step = step;
}
return ret;
}
bool end()
{
return (m_current == NULL);
}
T current()
{
if( !end() )
{
return m_current->value;
}
else
{
THROW_EXCEPTION(INvalidOPerationException, "No value at current position ...");
}
}
bool next()
{
int i = 0;
while( (i < m_step) && !end() )
{
m_current = m_current->next;
i++;
}
return (i == m_step);
}
~LinkList()
{
clear();
}
};
}
#endif // LINKLIST_Hmain.cpp 源碼
#include
#include "LinkList.h"
using namespace std;
using namespace DTLib;
int main()
{
LinkList list;
for(int i=0; i<5; i++) // O(1)
{
list.insert(0, i);
}
for(list.move(0); !list.end(); list.next()) // O(1)
{
cout << list.current() << endl;
}
return 0;
}
我們來(lái)看看編譯結(jié)果
我們看到結(jié)果還是正確的，證明我們上面代碼的編寫是沒(méi)有錯(cuò)誤的。我們?cè)賮?lái)分析下，它每次移動(dòng)，移動(dòng)后 current 指針就停在那塊，等到下次移動(dòng)的時(shí)候還是從這塊開始移動(dòng)。也就是說(shuō)，每次遍歷的時(shí)候，它只需要遍歷一次就可以輸出結(jié)果了，這樣的話它遍歷的時(shí)間復(fù)雜度就為 O(1) 了。我們?cè)賮?lái)將 new 和 delete 操作封裝下，方便后面的使用，具體封裝如下
virtual Node* create()
{
return new Node();
}
virtual void destroy (Node* pn)
{
delete pn;
} 然后將下面的 new 和 delete 操作全部換成 create 和 destory 函數(shù)。我們來(lái)試下將 main.cpp 測(cè)試代碼中移動(dòng)的 step 改為 2，那么它便輸出的是偶數(shù)了。我們來(lái)看看結(jié)果
確實(shí)是輸出的只有偶數(shù)。那么我們移動(dòng)的 step 為 10 呢？那它就應(yīng)該只輸出 4 了，我們?cè)賮?lái)看看結(jié)果
現(xiàn)在我們的 LinkList 類已經(jīng)近乎完美了，優(yōu)化后的效率遍歷的時(shí)候極大的提高了。通過(guò)今天對(duì) LinkList 優(yōu)化的學(xué)習(xí)，總結(jié)如下：1、單鏈表的遍歷需要在線性時(shí)間內(nèi)完成；2、在單鏈表內(nèi)部定義游標(biāo)變量，通過(guò)游標(biāo)變量提高效率；3、遍歷相關(guān)的成員函數(shù)是相互依賴，相互配合的關(guān)系；4、封裝結(jié)點(diǎn)的申請(qǐng)和刪除操作更有利于增強(qiáng)擴(kuò)展性。
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
新聞標(biāo)題：?jiǎn)捂湵淼膬?yōu)化（十三）-創(chuàng)新互聯(lián)
轉(zhuǎn)載來(lái)源：http://weahome.cn/article/hhids.html
重慶分公司
重慶分公司
