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 阅读(330) 评论(0)  编辑 收藏 引用 所属分类: C++与编程之道


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理