• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			

            

            
	
            
		
			
            Code Knight
            
			Programming is so cool
		            		
	
            

            

            

            

            隨筆 - 52, 文章 - 0, 評(píng)論 - 14, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			一道面試題
		
            
		
            
		
            最近面試遇到一道很懷念的題目，約瑟夫環(huán)，由于代碼較多沒有當(dāng)時(shí)寫在卷上，說(shuō)了說(shuō)思路，下來(lái)用模板實(shí)現(xiàn)了一下，使用雙向循環(huán)鏈表，每到第五個(gè)kick out。
            注：模板未考慮非常規(guī)自定義類型的淺拷貝問題；另外代碼沒有優(yōu)化，delnode效率有提升空間，有興趣的改改看。
            

              1template<class T>
              2struct SNode
              3{
              4    SNode(T dNode)
              5    {
              6        dData = dNode;
              7    }
              8    T dData;
              9    SNode<T>* pNext;
             10    SNode<T>* pPre;
             11}            ;
             12
             13template<class T>
             14class CDoubleList
             15{
             16public:
             17    CDoubleList(T dDode);
             18    ~CDoubleList();
             19public:
             20    bool AddNode(T dNode);
             21    SNode<T>* DelNode(T dNode);
             22    int  GetSize(){return m_nListSize;}
             23    void PrintList();
             24
             25    SNode<T>* GetHead(){return m_pHead;}
             26private:
             27    SNode<T>* m_pHead;
             28    SNode<T>* m_pTail;
             29
             30    int          m_nListSize;
             31}            ;
             32
             33template<class T>
             34CDoubleList<T>::CDoubleList(T dHead):m_nListSize(0)
             35{
             36    m_pHead = new SNode<T>(dHead);
             37    if(!m_pHead)
             38    {
             39        // error
             40        return;
             41    }
             42
             43    m_pTail = m_pHead;
             44    m_pHead->pPre = m_pTail;
             45    m_pHead->pNext = m_pTail;
             46    m_pTail->pPre = m_pHead;
             47    m_pTail->pNext = m_pHead;
             48
             49    ++m_nListSize;
             50}
             51
             52template<class T>
             53CDoubleList<T>::~CDoubleList()
             54{
             55    SNode<T>* pStart = m_pHead;
             56    for(int i = 0; i < m_nListSize; ++i)
             57    {
             58        DelNode(pStart->dData);
             59    }
             60}
             61
             62template<class T>
             63bool CDoubleList<T>::AddNode(T dNode)
             64{
             65    if(GetSize() < 1)
             66        return false;
             67
             68    SNode<T>* pNewNode = new SNode<T>(dNode);
             69    pNewNode->pPre = m_pTail;
             70    pNewNode->pNext = m_pTail->pNext;
             71    m_pTail->pNext = pNewNode;
             72    pNewNode->pNext->pPre = pNewNode;
             73
             74    m_pTail = pNewNode;
             75
             76    ++m_nListSize;
             77
             78    return true;
             79}
             80
             81template <class T>
             82SNode<T>* CDoubleList<T>::DelNode(T dNode)
             83{
             84    static SNode<T>* pNode = m_pHead;
             85    // 遍歷，找到相同的刪除
             86    for(int i = 0; i < m_nListSize; ++i)
             87    {
             88        if(pNode->dData == dNode)
             89        {
             90            if(pNode == m_pHead)
             91            {
             92                // 刪除頭，特殊處理
             93                pNode->pPre->pNext = pNode->pNext;
             94                pNode->pNext->pPre = pNode->pPre;
             95
             96                m_pTail = pNode->pPre;
             97
             98                SNode<T>* pNewNode = pNode->pNext;
             99                delete pNode;
            100
            101                pNode = pNewNode;
            102
            103                m_pHead = pNode;
            104
            105                --m_nListSize;
            106                return m_pHead;
            107            }
            108            else
            109            {
            110                pNode->pPre->pNext = pNode->pNext;
            111                pNode->pNext->pPre = pNode->pPre;
            112
            113                SNode<T>* pNewNode = pNode->pNext;
            114                delete pNode;
            115
            116                pNode = pNewNode;
            117
            118                --m_nListSize;
            119
            120                return pNode;
            121            }
            122        }
            123
            124        pNode = pNode->pNext;
            125    }
            126
            127    return 0;
            128}
            129
            130
            131template <class T>
            132void CDoubleList<T>::PrintList()
            133{
            134    SNode<T>* pNode = m_pHead;
            135    for(int i = 0; i < m_nListSize; ++i)
            136    {    
            137        cout<<pNode->dData<<endl;
            138
            139        pNode = pNode->pNext;
            140    }
            141}
            

            #include "list.h"
            #include             <iostream>
            using namespace std;

            void main()
            {
                CDoubleList            <int> dList(1);
                            for(int i = 2; i < 10; ++i)
                            {
                        dList.AddNode(i);
                }
                dList.PrintList();
                cout            <<"begin do something"<<endl;

                SNode            <int>* pStart= dList.GetHead();
                            while(dList.GetSize() != 1) // 數(shù)到第五個(gè)人出局
                {
                                for(int i = 0; i < 4; ++i)
                                {
                                    if(!pStart)
                                    {
                                        //error
                        }

                        pStart             = pStart->pNext;
                    }

                    pStart             = dList.DelNode(pStart->dData);
                }

                dList.PrintList();
                cout            <<"magic end"<<endl;

                getchar();
            }
            

		
            
		
            
			posted on 2010-04-12 15:55 Code Knight 閱讀(343) 評(píng)論(0)  編輯 收藏 引用  所屬分類: C++與編程之道 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



7777精品伊人久久久大香线蕉|
亚洲国产成人久久综合碰碰动漫3d|
久久精品9988|
精品无码久久久久国产|
久久久一本精品99久久精品66|
人妻无码αv中文字幕久久琪琪布|
99精品国产99久久久久久97
|
久久A级毛片免费观看|
精品多毛少妇人妻AV免费久久|
亚洲国产美女精品久久久久∴|
久久精品国产清高在天天线|
精品久久久中文字幕人妻|
蜜臀久久99精品久久久久久|
亚洲欧洲精品成人久久曰影片|
国产精品久久久久久久人人看
|
亚洲欧美日韩精品久久亚洲区
|
久久无码专区国产精品发布
|
久久天堂AV综合合色蜜桃网|
99精品国产综合久久久久五月天
|
91视频国产91久久久|
久久久久亚洲爆乳少妇无|
久久国产成人亚洲精品影院|
亚洲精品国精品久久99热一|
伊人久久大香线蕉av不变影院|
男女久久久国产一区二区三区|
国内精品久久久久影院日本|
国产精品久久久久久久久鸭|
99久久99久久精品国产|
热久久国产欧美一区二区精品|
久久不见久久见免费视频7|
77777亚洲午夜久久多喷|
国产精品久久久久一区二区三区|
色欲久久久天天天综合网精品|
久久99国内精品自在现线|
91精品国产综合久久香蕉
|
久久激情五月丁香伊人|
9久久9久久精品|
国产巨作麻豆欧美亚洲综合久久|
久久综合成人网|
久久精品无码专区免费东京热|
91精品国产91久久久久久青草|