• <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í)寫在卷上，說了說思路，下來用模板實(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 閱讀(345) 評(píng)論(0)  編輯 收藏 引用  所屬分類: C++與編程之道 
		
            
	
            
	
	


	


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



无码任你躁久久久久久老妇App|
免费一级做a爰片久久毛片潮|
久久综合给合久久狠狠狠97色|
久久99精品久久久久久水蜜桃|
九九热久久免费视频|
99久久免费只有精品国产|
久久人人爽人人爽人人片AV不
|
A级毛片无码久久精品免费|
国产成人无码精品久久久性色|
国产V亚洲V天堂无码久久久|
久久99热这里只有精品国产|
性色欲网站人妻丰满中文久久不卡|
伊人久久久AV老熟妇色|
99久久精品无码一区二区毛片|
久久夜色精品国产|
久久无码av三级|
国内精品伊人久久久久AV影院|
国产精品成人久久久久三级午夜电影
|
久久99毛片免费观看不卡|
久久伊人精品一区二区三区|
久久国产综合精品五月天|
伊人色综合久久天天|
国产精品99精品久久免费|
人妻少妇久久中文字幕|
少妇精品久久久一区二区三区
|
久久亚洲国产欧洲精品一|
91精品国产乱码久久久久久|
久久久久久亚洲AV无码专区|
国产69精品久久久久777|
国产精品视频久久|
三级韩国一区久久二区综合|
少妇久久久久久久久久|
国产成人精品综合久久久|
久久综合色之久久综合|
欧美精品乱码99久久蜜桃|
精品久久久久久国产
|
精品一区二区久久久久久久网站|
国产韩国精品一区二区三区久久|
久久久久人妻精品一区三寸蜜桃|
亚洲精品美女久久777777|
99久久精品免费看国产免费|