• <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++與編程之道

            欧美久久综合九色综合| 国产韩国精品一区二区三区久久| 国内精品久久国产大陆| 国产精品成人99久久久久| 久久综合一区二区无码| 久久精品青青草原伊人| 婷婷伊人久久大香线蕉AV| 国产精品免费看久久久香蕉| 久久亚洲AV成人无码| 久久美女网站免费| 亚洲欧美成人综合久久久| 99久久成人18免费网站| 久久精品人人做人人妻人人玩 | 午夜精品久久久久久久| 日韩精品国产自在久久现线拍 | 亚洲欧美日韩久久精品| 国产精品久久精品| 日产精品久久久久久久| 午夜精品久久久久9999高清| 狠狠干狠狠久久| 日韩精品无码久久久久久| 亚洲第一永久AV网站久久精品男人的天堂AV| 久久亚洲AV无码精品色午夜| 久久无码一区二区三区少妇 | 久久精品国产久精国产果冻传媒 | 欧美精品国产综合久久| 久久综合五月丁香久久激情| 久久高清一级毛片| 久久精品人妻一区二区三区| 麻豆精品久久久一区二区| 精品国产VA久久久久久久冰| 久久精品国产日本波多野结衣| 狠狠色综合久久久久尤物| 久久狠狠一本精品综合网| 久久最新精品国产| 99久久国产主播综合精品| 91精品国产91久久| 久久国产成人午夜aⅴ影院| 久久综合亚洲色HEZYO国产| 久久综合色之久久综合| 久久午夜免费视频|