• <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精品国产免费久久久久久下载
|
久久久久噜噜噜亚洲熟女综合|
久久综合亚洲欧美成人|
99久久99久久精品国产片果冻|
久久夜色精品国产欧美乱|
国产人久久人人人人爽|
成人国内精品久久久久影院VR|
日韩影院久久|
99久久99这里只有免费费精品|
色综合色天天久久婷婷基地|
久久人人爽人爽人人爽av|
久久综合亚洲鲁鲁五月天|
99久久精品日本一区二区免费|
久久亚洲欧洲国产综合|
国内精品久久久久影院日本|
热综合一本伊人久久精品|
69久久精品无码一区二区|
久久国产AVJUST麻豆|
精品久久一区二区|
亚洲精品无码成人片久久|
久久这里有精品视频|
久久er热视频在这里精品|
日本强好片久久久久久AAA|
久久996热精品xxxx|
久久精品国产99国产精偷|
久久精品国产AV一区二区三区|
久久精品国产亚洲av瑜伽|
国产精品久久自在自线观看|
国产aⅴ激情无码久久|
久久最新免费视频|
国产精品综合久久第一页|
久久久久久狠狠丁香|
国内精品人妻无码久久久影院
|
久久人妻无码中文字幕|
久久影院亚洲一区|
久久久久国产成人精品亚洲午夜|
成人久久久观看免费毛片|
精品永久久福利一区二区|
99久久精品国产一区二区|
精品久久久无码21p发布|
亚洲日韩欧美一区久久久久我|