一区二区三区产品免费精品久久75,亚洲一级电影,这里只有精品电影

C++完美實(shí)現(xiàn)Singleton模式

Singleton模式是常用的設(shè)計(jì)模式之一，但是要實(shí)現(xiàn)一個(gè)真正實(shí)用的設(shè)計(jì)模式卻也不是件容易的事情。
標(biāo)準(zhǔn)的實(shí)現(xiàn)

1 class Singleton
2 {
3 public:
4        static Singleton * Instance()
5        {
6               if( 0== _instance)
7               {
8                      _instance = new Singleton;
9               }
10               return _instance;
11        }
12 protected:
13        Singleton(void)
14        {
15        }
16        virtual ~Singleton(void)
17        {
18        }
19        static Singleton* _instance;
20 };

這是教科書上使用的方法?？雌饋?lái)沒(méi)有什么問(wèn)題，其實(shí)包含很多的問(wèn)題。下面我們一個(gè)一個(gè)的解決。

問(wèn)題一  自動(dòng)垃圾回收
上面的程序必須記住在程序結(jié)束的時(shí)候，釋放內(nèi)存。為了讓它自動(dòng)的釋放內(nèi)存，我們引入auto_ptr改變它。

1 #include <memory>
2 #include <iostream>
3 using namespace std;
4 class Singleton
5 {
6 public:
7        static Singleton * Instance()
8        {
9               if( 0== _instance.get())
10               {
11                      _instance.reset( new Singleton);
12               }
13               return _instance.get();
14        }
15 protected:
16        Singleton(void)
17        {
18               cout <<"Create Singleton"<<endl;
19        }
20        virtual ~Singleton(void)
21        {
22               cout << "Destroy Singleton"<<endl;
23        }
24        friend class auto_ptr<Singleton>;
25        static auto_ptr<Singleton> _instance;
26 };
27 //Singleton.cpp
28 auto_ptr<Singleton> Singleton::_instance;

問(wèn)題二  增加模板
在我的一個(gè)工程中，有多個(gè)的Singleton類，對(duì)Singleton類，我都要實(shí)現(xiàn)上面這一切，這讓我覺(jué)得煩死了。于是我想到了模板來(lái)完成這些重
復(fù)的工作。
現(xiàn)在我們要添加本文中最吸引人單件實(shí)現(xiàn)：
 1 #include <memory>
 2 using namespace std;
 3 using namespace C2217::Win32;
 4  
 5 namespace C2217
 6 {
 7 namespace Pattern
 8 {
 9 template <class T>
10 class Singleton
11 {
12 public:
13        static inline T* instance();
14       
15 private:
16        Singleton(void){}
17        ~Singleton(void){}
18        Singleton(const Singleton&){}
19        Singleton & operator= (const Singleton &){}
20  
21        static auto_ptr<T> _instance;
22 };
23  
24 template <class T>
25 auto_ptr<T> Singleton<T>::_instance;
26  
27 template <class T>
28  inline T* Singleton<T>::instance()
29 {
30        if( 0== _instance.get())
31        {
32               _instance.reset ( new T);
33        }
34       
35        return _instance.get();
36 }
37  
38 //Class that will implement the singleton mode,
39 //must use the macro in it's delare file
40 #define DECLARE_SINGLETON_CLASS( type ) \
41        friend class auto_ptr< type >;\
42        friend class Singleton< type >;
43 }
44 }
問(wèn)題三  線程安全
上面的程序可以適應(yīng)單線程的程序。但是如果把它用到多線程的程序就會(huì)發(fā)生問(wèn)題。主要的問(wèn)題在于同時(shí)執(zhí)行_instance.reset ( new T); 
就會(huì)同時(shí)產(chǎn)生兩個(gè)新的對(duì)象，然后馬上釋放一個(gè)，這跟Singleton模式的本意不符。所以，你需要更加安全的版本：
 1 #include <memory>
 2 using namespace std;
 3 #include "Interlocked.h"
 4 using namespace C2217::Win32;
 5  
 6 namespace C2217
 7 {
 8 namespace Pattern
 9 {
10 template <class T>
11 class Singleton
12 {
13 public:
14        static inline T* instance();
15       
16 private:
17        Singleton(void){}
18        ~Singleton(void){}
19        Singleton(const Singleton&){}
20        Singleton & operator= (const Singleton &){}
21  
22        static auto_ptr<T> _instance;
23        static CResGuard _rs;
24 };
25  
26 template <class T>
27 auto_ptr<T> Singleton<T>::_instance;
28  
29 template <class T>
30 CResGuard Singleton<T>::_rs;
31  
32 template <class T>
33  inline T* Singleton<T>::instance()
34 {
35        if( 0 == _instance.get() )
36        {
37               CResGuard::CGuard gd(_rs);
38               if( 0== _instance.get())
39               {
40                      _instance.reset ( new T);
41               }
42        }
43        return _instance.get();
44 }
45  
46 //Class that will implement the singleton mode,
47 //must use the macro in it's delare file
48 #define DECLARE_SINGLETON_CLASS( type ) \
49        friend class auto_ptr< type >;\
50        friend class Singleton< type >;
51 }
52 }
CresGuard 類主要的功能是線程訪問(wèn)同步,代碼如下：

1 class CResGuard {
2 public:
3    CResGuard()  { m_lGrdCnt = 0; InitializeCriticalSection(&m_cs); }
4    ~CResGuard() { DeleteCriticalSection(&m_cs); }
5
6    // IsGuarded is used for debugging
7    BOOL IsGuarded() const { return(m_lGrdCnt > 0); }
8
9 public:
10    class CGuard {
11    public:
12       CGuard(CResGuard& rg) : m_rg(rg) { m_rg.Guard(); };
13       ~CGuard() { m_rg.Unguard(); }
14
15    private:
16       CResGuard& m_rg;
17    };
18
19 private:
20    void Guard()   { EnterCriticalSection(&m_cs); m_lGrdCnt++; }
21    void Unguard() { m_lGrdCnt--; LeaveCriticalSection(&m_cs); }
22
23    // Guard/Unguard can only be accessed by the nested CGuard class.
24    friend class CResGuard::CGuard;
25
26 private:
27    CRITICAL_SECTION m_cs;
28    long m_lGrdCnt;   // # of EnterCriticalSection calls
29 };

問(wèn)題四實(shí)用方法

比如你有一個(gè)需要實(shí)現(xiàn)單件模式的類，就應(yīng)該這樣實(shí)現(xiàn)：

1 #include "singleton.h"
2 using namespace C2217::Pattern;
3
4 class ServiceManger
5 {
6 public:
7        void Run()
8        {
9        }
10 private:
11        ServiceManger(void)
12        {
13        }
14        virtual ~ServiceManger(void)
15        {
16        }
17        DECLARE_SINGLETON_CLASS(ServiceManger);
18 };
19
20 typedef Singleton<ServiceManger> SSManger;

在使用的時(shí)候很簡(jiǎn)單，跟一般的Singleton實(shí)現(xiàn)的方法沒(méi)有什么不同。

1 int _tmain(int argc, _TCHAR* argv[])
2 {
3 SSManger::instance()->Run();
4 }

一個(gè)簡(jiǎn)單的Singleton模式的實(shí)現(xiàn)，可以看到C++語(yǔ)言背后隱藏的豐富的語(yǔ)意，我希望有人能實(shí)現(xiàn)一個(gè)更好的Singleton讓大家學(xué)習(xí)。

posted @ 2012-11-09 14:10 Beatles 閱讀(1727) | 評(píng)論 (2) | 編輯收藏

C++將字符串轉(zhuǎn)換成數(shù)字

1 int changestr(char* str)
2 {
3        int len = strlen(str);
4        int sum = 0;
5        float carry = 1.0/10;
6        for(int i=0; i<len; i++)
7        {
8               carry *= 10;
9               sum += (str[len-1-i]-'0')*carry;
10        }
11        return sum;
12 }

其中sum為carry為當(dāng)前位之前的值。

str[len-1-i]-'0'是表示將字符的ascii碼減去0的ascii碼，最后出來(lái)的數(shù)字就是需要的數(shù)字。

每次*10的話就把當(dāng)前位往前移了。

*改進(jìn)了算法，增加了支持負(fù)數(shù)，以及碰到有問(wèn)題的字符就會(huì)throw exception

posted @ 2012-11-09 10:06 Beatles 閱讀(2040) | 評(píng)論 (0) | 編輯收藏

二叉樹(shù)的三種遍歷(遞歸算法)

1 struct Node
2 {
3     int data;
4     Node* lchild;
5     Node* rchild;
6 }
7 void preorder(Node* parent)
8 {
9     if (parent!=NULL)
10     {
11         cout<<parent->data<<endl;
12         preorder(parent->lchild);
13         preorder(parent->rchild);
14     }
15 }
16 void inorder(Node* parent)
17 {
18     if (parent!=NULL)
19     {
20         inorder(parent->lchild);
21         cout<<parent->data<<endl;
22         inorder(parent->rchild);
23     }
24 }
25 void postorder(Node* parent)
26 {
27     if (parent!=NULL)
28     {
29         postorder(parent->lchild);
30         postorder(parent->rchild);
31         cout<<parent->data<<endl;
32     }
33 }

重新又看了一遍二叉樹(shù)(Binary Tree)，發(fā)現(xiàn)很多東西自己還沒(méi)有弄明白，原來(lái)三種遍歷方式還不是自己想象中的那樣

前序遍歷(PreOrder)是先輸出自己，然后左，最后右。

中序遍歷(InOrder)是先左，再輸出自己，最后右。

后序遍歷(PostOrder)是先左，再右，最后輸出自己。

所謂的XX遍歷就是指把自己放在哪個(gè)優(yōu)先位置上，而不是指從哪里開(kāi)始遍歷。

算下來(lái)其實(shí)搜索匹配也可以用這個(gè)方法，基本上就是以遞歸形成的。

另外還需要研究一下DFS(Depth First Search)以及BFS(Breadth First Search)的算法。

posted @ 2012-11-09 10:04 Beatles 閱讀(1160) | 評(píng)論 (0) | 編輯收藏

C++中的單例模式

單例模式也稱為單件模式、單子模式，可能是使用最廣泛的設(shè)計(jì)模式。其意圖是保證一個(gè)類僅有一個(gè)實(shí)例，并提供一個(gè)訪問(wèn)它的全局訪問(wèn)點(diǎn)，該實(shí)例被所有程序模塊共享。有很多地方需要這樣的功能模塊，如系統(tǒng)的日志輸出，GUI應(yīng)用必須是單鼠標(biāo)，MODEM的聯(lián)接需要一條且只需要一條電話線，操作系統(tǒng)只能有一個(gè)窗口管理器，一臺(tái)PC連一個(gè)鍵盤。

單例模式有許多種實(shí)現(xiàn)方法，在C++中，甚至可以直接用一個(gè)全局變量做到這一點(diǎn)，但這樣的代碼顯的很不優(yōu)雅。使用全局對(duì)象能夠保證方便地訪問(wèn)實(shí)例，但是不能保證只聲明一個(gè)對(duì)象——也就是說(shuō)除了一個(gè)全局實(shí)例外，仍然能創(chuàng)建相同類的本地實(shí)例。

《設(shè)計(jì)模式》一書中給出了一種很不錯(cuò)的實(shí)現(xiàn)，定義一個(gè)單例類，使用類的私有靜態(tài)指針變量指向類的唯一實(shí)例，并用一個(gè)公有的靜態(tài)方法獲取該實(shí)例。

單例模式通過(guò)類本身來(lái)管理其唯一實(shí)例，這種特性提供了解決問(wèn)題的方法。唯一的實(shí)例是類的一個(gè)普通對(duì)象，但設(shè)計(jì)這個(gè)類時(shí)，讓它只能創(chuàng)建一個(gè)實(shí)例并提供對(duì)此實(shí)例的全局訪問(wèn)。唯一實(shí)例類Singleton在靜態(tài)成員函數(shù)中隱藏創(chuàng)建實(shí)例的操作。習(xí)慣上把這個(gè)成員函數(shù)叫做Instance()，它的返回值是唯一實(shí)例的指針。

定義如下：

1 class CSingleton
2
3 {
4
5 //其他成員
6
7 public:
8
9 static CSingleton* GetInstance()
10
11 {
12
13       if ( m_pInstance == NULL )  //判斷是否第一次調(diào)用
14
15         m_pInstance = new CSingleton();
16
17         return m_pInstance;
18
19 }
20
21 private:
22
23     CSingleton(){};
24
25     static CSingleton * m_pInstance;
26
27 };

用戶訪問(wèn)唯一實(shí)例的方法只有GetInstance()成員函數(shù)。如果不通過(guò)這個(gè)函數(shù)，任何創(chuàng)建實(shí)例的嘗試都將失敗，因?yàn)轭惖臉?gòu)造函數(shù)是私有的。GetInstance()使用懶惰初始化，也就是說(shuō)它的返回值是當(dāng)這個(gè)函數(shù)首次被訪問(wèn)時(shí)被創(chuàng)建的。這是一種防彈設(shè)計(jì)——所有GetInstance()之后的調(diào)用都返回相同實(shí)例的指針：

CSingleton* p1 = CSingleton :: GetInstance();

CSingleton* p2 = p1->GetInstance();

CSingleton & ref = * CSingleton :: GetInstance();

對(duì)GetInstance稍加修改，這個(gè)設(shè)計(jì)模板便可以適用于可變多實(shí)例情況，如一個(gè)類允許最多五個(gè)實(shí)例。

單例類CSingleton有以下特征：

它有一個(gè)指向唯一實(shí)例的靜態(tài)指針m_pInstance，并且是私有的；

它有一個(gè)公有的函數(shù)，可以獲取這個(gè)唯一的實(shí)例，并且在需要的時(shí)候創(chuàng)建該實(shí)例；

它的構(gòu)造函數(shù)是私有的，這樣就不能從別處創(chuàng)建該類的實(shí)例。

大多數(shù)時(shí)候，這樣的實(shí)現(xiàn)都不會(huì)出現(xiàn)問(wèn)題。有經(jīng)驗(yàn)的讀者可能會(huì)問(wèn)，m_pInstance指向的空間什么時(shí)候釋放呢？更嚴(yán)重的問(wèn)題是，該實(shí)例的析構(gòu)函數(shù)什么時(shí)候執(zhí)行？

如果在類的析構(gòu)行為中有必須的操作，比如關(guān)閉文件，釋放外部資源，那么上面的代碼無(wú)法實(shí)現(xiàn)這個(gè)要求。我們需要一種方法，正常的刪除該實(shí)例。

可以在程序結(jié)束時(shí)調(diào)用GetInstance()，并對(duì)返回的指針掉用delete操作。這樣做可以實(shí)現(xiàn)功能，但不僅很丑陋，而且容易出錯(cuò)。因?yàn)檫@樣的附加代碼很容易被忘記，而且也很難保證在delete之后，沒(méi)有代碼再調(diào)用GetInstance函數(shù)。

一個(gè)妥善的方法是讓這個(gè)類自己知道在合適的時(shí)候把自己刪除，或者說(shuō)把刪除自己的操作掛在操作系統(tǒng)中的某個(gè)合適的點(diǎn)上，使其在恰當(dāng)?shù)臅r(shí)候被自動(dòng)執(zhí)行。

我們知道，程序在結(jié)束的時(shí)候，系統(tǒng)會(huì)自動(dòng)析構(gòu)所有的全局變量。事實(shí)上，系統(tǒng)也會(huì)析構(gòu)所有的類的靜態(tài)成員變量，就像這些靜態(tài)成員也是全局變量一樣。利用這個(gè)特征，我們可以在單例類中定義一個(gè)這樣的靜態(tài)成員變量，而它的唯一工作就是在析構(gòu)函數(shù)中刪除單例類的實(shí)例。如下面的代碼中的CGarbo類（Garbo意為垃圾工人）：

1 class CSingleton
2
3 {
4
5 //其他成員
6
7 public:
8
9 static CSingleton* GetInstance();
10
11 private:
12
13     CSingleton(){};
14
15     static CSingleton * m_pInstance;
16
17 class CGarbo //它的唯一工作就是在析構(gòu)函數(shù)中刪除CSingleton的實(shí)例
18
19 {
20
21         public:
22
23             ~CGarbo()
24
25             {
26
27                 if( CSingleton::m_pInstance )
28
29                   delete CSingleton::m_pInstance;
30
31 }
32
33          }
34
35         Static CGabor Garbo; //定義一個(gè)靜態(tài)成員，程序結(jié)束時(shí)，系統(tǒng)會(huì)自動(dòng)調(diào)用它的析構(gòu)函數(shù)
36
37 }；

類CGarbo被定義為CSingleton的私有內(nèi)嵌類，以防該類被在其他地方濫用。

程序運(yùn)行結(jié)束時(shí)，系統(tǒng)會(huì)調(diào)用CSingleton的靜態(tài)成員Garbo的析構(gòu)函數(shù)，該析構(gòu)函數(shù)會(huì)刪除單例的唯一實(shí)例。

使用這種方法釋放單例對(duì)象有以下特征：

在單例類內(nèi)部定義專有的嵌套類；

在單例類內(nèi)定義私有的專門用于釋放的靜態(tài)成員；

利用程序在結(jié)束時(shí)析構(gòu)全局變量的特性，選擇最終的釋放時(shí)機(jī)；

使用單例的代碼不需要任何操作，不必關(guān)心對(duì)象的釋放。

(出處：http://hi.baidu.com/csudada/blog/item/208fb0f56bb61266dcc47466.html)

進(jìn)一步的討論

但是添加一個(gè)類的靜態(tài)對(duì)象，總是讓人不太滿意，所以有人用如下方法來(lái)重現(xiàn)實(shí)現(xiàn)單例和解決它相應(yīng)的問(wèn)題，代碼如下

1 class CSingleton
2
3 {
4
5     //其他成員
6
7     public:
8
9         static Singleton &GetInstance()
10
11 {
12
13     static Singleton instance;
14
15     return instance;
16
17 }
18
19         private:
20
21             Singleton() {};
22
23 };

使用局部靜態(tài)變量，非常強(qiáng)大的方法，完全實(shí)現(xiàn)了單例的特性，而且代碼量更少，也不用擔(dān)心單例銷毀的問(wèn)題。

但使用此種方法也會(huì)出現(xiàn)問(wèn)題，當(dāng)如下方法使用單例時(shí)問(wèn)題來(lái)了，

Singleton singleton = Singleton :: GetInstance();

這么做就出現(xiàn)了一個(gè)類拷貝的問(wèn)題，這就違背了單例的特性。產(chǎn)生這個(gè)問(wèn)題原因在于：編譯器會(huì)為類生成一個(gè)默認(rèn)的構(gòu)造函數(shù)，來(lái)支持類的拷貝。

最后沒(méi)有辦法，我們要禁止類拷貝和類賦值，禁止程序員用這種方式來(lái)使用單例，當(dāng)時(shí)領(lǐng)導(dǎo)的意思是GetInstance()函數(shù)返回一個(gè)指針而不是返回一個(gè)引用，函數(shù)的代碼改為如下：

1 static Singleton *GetInstance()
2
3 {
4
5 static Singleton instance;
6
7 return &instance;
8
9 }

但我總覺(jué)的不好，為什么不讓編譯器不這么干呢。這時(shí)我才想起可以顯示的生命類拷貝的構(gòu)造函數(shù)，和重載 = 操作符，新的單例類如下：

1 class Singleton
2
3 {
4
5     //其他成員
6
7     public:
8
9         static Singleton &GetInstance()
10
11 {
12
13     static Singleton instance;
14
15     return instance;
16
17 }
18
19         private:
20
21             Singleton() {};
22
23             Singleton(const Singleton);
24
25             Singleton & operate = (const Singleton&);
26
27 };

關(guān)于Singleton(const Singleton); 和 Singleton & operate = (const Singleton&); 函數(shù)，需要聲明成私用的，并且只聲明不實(shí)現(xiàn)。這樣，如果用上面的方式來(lái)使用單例時(shí)，不管是在友元類中還是其他的，編譯器都是報(bào)錯(cuò)。

不知道這樣的單例類是否還會(huì)有問(wèn)題，但在程序中這樣子使用已經(jīng)基本沒(méi)有問(wèn)題了。

（出處：http://snailbing.blogbus.com/logs/45398975.html）

優(yōu)化Singleton類，使之適用于單線程應(yīng)用

Singleton使用操作符new為唯一實(shí)例分配存儲(chǔ)空間。因?yàn)閚ew操作符是線程安全的，在多線程應(yīng)用中你可以使用此設(shè)計(jì)模板，但是有一個(gè)缺陷：就是在應(yīng)用程序終止之前必須手工用delete摧毀實(shí)例。否則，不僅導(dǎo)致內(nèi)存溢出，還要造成不可預(yù)測(cè)的行為，因?yàn)镾ingleton的析構(gòu)函數(shù)將根本不會(huì) 被調(diào)用。而通過(guò)使用本地靜態(tài)實(shí)例代替動(dòng)態(tài)實(shí)例，單線程應(yīng)用可以很容易避免這個(gè)問(wèn)題。下面是與上面的GetInstance()稍有不同的實(shí)現(xiàn)，這個(gè)實(shí)現(xiàn)專門用于單線程應(yīng)用：

1 CSingleton* CSingleton :: GetInstance()
2
3 {
4
5 static CSingleton inst；
6
7 return &inst；
8
9 }

本地靜態(tài)對(duì)象實(shí)例inst是第一次調(diào)用GetInstance()時(shí)被構(gòu)造，一直保持活動(dòng)狀態(tài)直到應(yīng)用程序終止，指針m_pInstance變得多余并且可以從類定義中刪除掉，與動(dòng)態(tài)分配對(duì)象不同，靜態(tài)對(duì)象當(dāng)應(yīng)用程序終止時(shí)被自動(dòng)銷毀掉，所以就不必再手動(dòng)銷毀實(shí)例了。

（出處：http://blog.csdn.net/pingnanlee/archive/2009/04/20/4094313.aspx）

代碼學(xué)習(xí)（從http://apps.hi.baidu.com/share/detail/32113057引用）

  1 #include <iostream>
  2
  3 using namespace std;
  4
  5 //單例類的C++實(shí)現(xiàn)
  6
  7 class Singleton
  8
  9 {
10
11 private:
12
13        Singleton();//注意:構(gòu)造方法私有
14
15
16
17        static Singleton* instance;//惟一實(shí)例
18
19        int var;//成員變量(用于測(cè)試)
20
21 public:
22
23        static Singleton* GetInstance();//工廠方法(用來(lái)獲得實(shí)例)
24
25        int getVar();//獲得var的值
26
27        void setVar(int);//設(shè)置var的值
28
29        virtual ~Singleton();
30
31 };
32
33 //構(gòu)造方法實(shí)現(xiàn)
34
35 Singleton::Singleton()
36
37 {
38
39        this->var = 20;
40
41        cout<<"Singleton Constructor"<<endl;
42
43 }
44
45 Singleton::~Singleton()
46
47 {
48
49        cout<<"Singleton Destructor"<<endl;
50
51        //delete instance;
52
53 }
54
55 //初始化靜態(tài)成員
56
57 /*Singleton* Singleton::instance=NULL;
58
59 Singleton* Singleton::GetInstance()
60
61 {
62
63        if(NULL==instance)
64
65               instance=new Singleton();
66
67        return instance;
68
69 }*/
70
71 Singleton* Singleton::instance=new Singleton;
72
73 Singleton* Singleton::GetInstance()
74
75 {
76
77        return instance;
78
79 }
80
81 //seter && getter含數(shù)
82
83 int Singleton::getVar()
84
85 {
86
87        return this->var;
88
89 }
90
91 void Singleton::setVar(int var)
92
93 {
94
95        this->var = var;
96
97 }
98
99 //main
100
101 void main()
102
103 {
104
105        Singleton *ton1 = Singleton::GetInstance();
106
107        Singleton *ton2 = Singleton::GetInstance();
108
109       if(ton1==ton2)
110
111               cout<<"ton1==ton2"<<endl;
112
113        cout<<"ton1 var = "<<ton1->getVar()<<endl;
114
115        cout<<"ton2 var = "<<ton2->getVar()<<endl;
116
117        ton1->setVar(150);
118
119        cout<<"ton1 var = "<<ton1->getVar()<<endl;
120
121        cout<<"ton2 var = "<<ton2->getVar()<<endl;
122
123        delete Singleton::GetInstance();//必須顯式地刪除
124
125 }

posted @ 2012-11-08 14:27 Beatles 閱讀(826) | 評(píng)論 (1) | 編輯收藏

C++中經(jīng)典的單向鏈表反轉(zhuǎn)

1 struct linka {
2 int data;
3 linka* next;
4 };
5 void reverse(linka*& head) {
6 if(head ==NULL)
7     return;
8 linka *pre, *cur, *ne;
9 pre=head;
10 cur=head->next;
11 while(cur)
12 {
13    ne = cur->next;
14    cur->next = pre;
15    pre = cur;
16    cur = ne;
17 }
18 head->next = NULL;
19 head = pre;
20 }

其中比較難理解的是linka*& head，傳入的其實(shí)就是linka *的類型就可以了，linka *是表示linka類型的指針，&表示head的地址，也就是linka的指針

另外需要熟悉的是head->next，其實(shí)有點(diǎn)像C#中的head.Next，就是structure中的一個(gè)屬性.

首先定義3個(gè)指針，分別是前中后，然后當(dāng)中間那個(gè)指針?lè)强眨褪钱?dāng)前不是空，就做循環(huán)里的事情

注意的是這個(gè)算法里面next是在循環(huán)里面賦值的

每次循環(huán)都把current指向previous了，然后大家都往后移一個(gè)，next=current->next必須在current改變方向之前做，否則改變了方向之后current的next就變成previous了。

最后跳出循環(huán)之后，將header的next首先置空，因?yàn)閔ead變成了最后一個(gè)node了。然后head就變成了previous，因?yàn)楫?dāng)時(shí) current和next都為NULL了，只有previous為最后一個(gè)節(jié)點(diǎn)（或者說(shuō)這時(shí)候應(yīng)該是第一個(gè)非空節(jié)點(diǎn)，也就是head）

終于把整個(gè)算法理解了一遍，最后想想其實(shí)挺簡(jiǎn)單，但是能用c++寫出來(lái)也不太容易，特別是在面試的時(shí)候。

再增加一個(gè)遞歸的單鏈表反轉(zhuǎn)的方法：

1 static link ReverseLink3(link pNode)   // using recursion
2         {
3             if (pNode.next == null)
4                 return pNode;
5             link pNext = pNode.next;
6             link head = ReverseLink3(pNext);
7             pNext.next = pNode;
8             pNode.next = null;
9             return head;
10         }

posted @ 2012-11-08 14:15 Beatles 閱讀(1194) | 評(píng)論 (0) | 編輯收藏

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

C++完美實(shí)現(xiàn)Singleton模式

C++將字符串轉(zhuǎn)換成數(shù)字

二叉樹(shù)的三種遍歷(遞歸算法)

C++中的單例模式

C++中經(jīng)典的單向鏈表反轉(zhuǎn)

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿

隨筆分類

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜