• <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
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			一道面試題
		
            
		
            
		
            最近面試遇到一道很懷念的題目，約瑟夫環(huán)，由于代碼較多沒有當(dāng)時(shí)寫在卷上，說了說思路，下來用模板實(shí)現(xiàn)了一下，使用雙向循環(huán)鏈表，每到第五個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ù)到第五個人出局
                {
                                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 閱讀(345) 評論(0)  編輯 收藏 引用  所屬分類: C++與編程之道 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



99热热久久这里只有精品68|
久久狠狠高潮亚洲精品|
久久久久一区二区三区|
Xx性欧美肥妇精品久久久久久|
久久高清一级毛片|
久久精品国产亚洲AV久|
久久99久久99小草精品免视看|
久久夜色精品国产噜噜亚洲a|
日产久久强奸免费的看|
久久精品国产亚洲AV香蕉|
国产免费久久精品丫丫|
久久香综合精品久久伊人|
久久亚洲国产欧洲精品一|
精品国产乱码久久久久软件|
久久99中文字幕久久|
伊人久久大香线蕉综合影院首页
|
亚洲午夜无码久久久久|
99久久精品国产综合一区|
欧美日韩精品久久久免费观看|
久久免费国产精品一区二区|
久久久久久精品无码人妻|
狠狠色丁香婷婷综合久久来来去|
亚洲欧美伊人久久综合一区二区|
91精品国产色综久久|
色狠狠久久AV五月综合|
亚洲国产成人久久综合碰|
国产AⅤ精品一区二区三区久久|
久久夜色精品国产噜噜麻豆
|
国内精品久久久久影院日本|
亚洲AⅤ优女AV综合久久久|
精品久久久久久久无码
|
久久99国产精品久久|
亚洲乱码中文字幕久久孕妇黑人|
欧美日韩精品久久久免费观看|
 久久综合狠狠综合久久激情 |
精品久久久久久中文字幕人妻最新|
久久精品一本到99热免费|
国产成人精品三上悠亚久久|
精品多毛少妇人妻AV免费久久|
欧美精品国产综合久久|
久久久久久综合网天天|