• <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, 評論 - 14, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數據加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			一道面試題
		
            
		
            
		
            最近面試遇到一道很懷念的題目，約瑟夫環，由于代碼較多沒有當時寫在卷上，說了說思路，下來用模板實現了一下，使用雙向循環鏈表，每到第五個kick out。
            注：模板未考慮非常規自定義類型的淺拷貝問題；另外代碼沒有優化，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) // 數到第五個人出局
                {
                                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 閱讀(352) 評論(0)  編輯 收藏 引用  所屬分類: C++與編程之道 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



日韩精品久久久久久|
久久婷婷国产剧情内射白浆|
久久青青草原精品影院|
久久国产精品偷99|
伊人久久大香线焦AV综合影院|
精品久久8x国产免费观看|
久久97久久97精品免视看|
久久精品国产色蜜蜜麻豆|
国产精品成人久久久久三级午夜电影
|
一本一道久久a久久精品综合|
久久狠狠爱亚洲综合影院|
亚洲国产二区三区久久|
日韩人妻无码一区二区三区久久|
国产伊人久久|
中文精品久久久久国产网址|
久久综合国产乱子伦精品免费|
久久久久99精品成人片三人毛片|
少妇人妻88久久中文字幕|
伊人久久大香线蕉综合热线|
国内精品久久久久久久影视麻豆|
亚洲乱码精品久久久久..|
思思久久99热只有频精品66|
精品久久久久中文字幕一区|
久久精品一区二区|
粉嫩小泬无遮挡久久久久久|
久久久久亚洲AV无码观看|
亚洲乱码日产精品a级毛片久久|
国产福利电影一区二区三区，免费久久久久久久精
|
久久香综合精品久久伊人|
久久久网中文字幕|
久久se精品一区二区影院|
国产A级毛片久久久精品毛片|
久久99精品久久久久久久不卡|
久久久久人妻一区精品色|
丁香色欲久久久久久综合网|
中文国产成人精品久久亚洲精品AⅤ无码精品|
一级做a爱片久久毛片|
久久99久久成人免费播放|
久久综合狠狠色综合伊人|
亚洲乱亚洲乱淫久久|
久久天天躁狠狠躁夜夜2020老熟妇
|